search

homenc / HElib

HElib is an open-source software library that implements homomorphic encryption. It supports the BGV scheme with bootstrapping and the Approximate Number CKKS scheme. HElib also includes optimizations for efficient homomorphic evaluation, focusing on effective use of ciphertext packing techniques and on the Gentry-Halevi-Smart optimizations.
https://homenc.github.io/HElib
Other
3.16k stars 761 forks source link

Semantic Security #49

Closed rohitkhera closed 9 years ago

rohitkhera commented 9 years ago

On the face of it the HElib scheme is semantically secure - for two encryptions of the same plaintext, each encryption samples fresh randomness. For bitstring comparison, if one encrypts an element A in a ring F(2^d) and another element B in the same ring, then Enc(A) + Enc(B) (in F(2^d) arithmetic) is bitstring comparison - it should return the zero element if the strings match. In the case of identical strings, their encrypted versions incorporate distinct randomness, so I should not be able to (homorphically) tell that they are the same? But on the other hand, the scheme is additively homomorphic so Enc(A) + Enc(B) should give me a correct result for comparison. Is there a contradiction or is it a specious argument ?

TomMD commented 9 years ago

Your argument suggests you can recognize encryptions of zero, which would be... surprising.

Consider your two string example. Assuming a space of 2^d, E("Hello") + E("Hello") certainly equals E(0) but this is indistinguishable from the encryption of anything else.

rohitkhera commented 9 years ago

@TomMD, I understand your point, my confusion was primarily around the fact that the comparison was possible at all given semantic security. I think the answer may be that Enc("Hello") + Enc("Hello) = Enc(0) + (noise/randomness) where the noise/randomness is taken away by decryption. Either way, I will be closing the issue