2
$\begingroup$

I must be missing something, and I am sorry if this is a novice question...

I have seen in places (eg. https://crypto.stanford.edu/~dwu4/talks/SecurityLunch0214.pdf page 13) that linear regression is possible on the cipher text of a fully Homomorphic Encryption system.

My question is: if you can generate the inverse of the matrix (X^T X), then can't you generate the cipher version of the identity matrix, and determine what E(1) is? And if you have E(1) can't you generate E(2) ... E(n) using either encrypted addition or plain text multiplication?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

if you can generate the inverse of the matrix (X^T X), then can't you generate the cypher version of the identity matrix, and determine what E(1) is?

I believe that the point you're missing is that homomorphic encryption is probabilistic; there are lots of legal representations of $E(1)$. The encryption process takes the plaintext (1 in this case), and some random values (we call them random coins); different values for the coins give you different ciphertexts.

Yes, you can generate values which you know is an encryption of 1 (in fact, they can be a lot easier than doing a full matrix multiply, if you have the public key, you can just take 1 and encrypt it yourself).

And, because there are many different ways of representing $E(1)$, just because you know one of them doesn't mean that you can recognize the others (in fact, we hope there's no such way, otherwise (as you implied) the whole system is broken).

Improve this answer
$\endgroup$
2
  • $\begingroup$ That makes a lot of sense, and thank you for the response. With respect to the multiple values of E(1)... are the values of E(1) an interval? I believe, with a lot of the partial HE systems, they are. So all of the E(1) would be "near" each other? $\endgroup$
    – markers
    Jul 22, 2016 at 20:25
  • $\begingroup$ @markers: one would hope that they're not isolated to an interval; to reiterate my ending comment, we certainly hope there's no way to distinguish an $E(1)$ value from $E(x \ne 1)$. That's because, if there is, the system is broken; an attacker can decrypt $E(x)$ by guessing values $y$, computing $E(x - y + 1)$, and checking whether that's a representation of $E(1)$ $\endgroup$
    – poncho
    Jul 22, 2016 at 20:48
2
$\begingroup$

Sure you can, but homomorphic encryption schemes are all randomized, so this doesn't actually result in a bruteforce attack. If you compute $c_1 = E(pk,1)$ and then compute $c_2 = E(pk,1)$ a second time, it won't be the case that $c_1 = c_2$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.