0
$\begingroup$

I am fairly new to HE and would like a short clarification on how exactly integers are securely encrypted using bits. The main idea is that one encrypts each bit value and represents the n bit number as n ciphertexts like this: $$E(x)=(E(x1),E(x2),...,E(xn))$$ where xi is the bit on position i. Why is that secure, when I have just ciphertexts that correspond to '0' and '1' in a particular order? Example: $$101 -> (E(1), E(0), E(1))$$ Can't I just guess 101 only from the E() values. Why is this not possible? Pointing me out to a good paper or read on that would be greatly appreciated!

$\endgroup$
  • 1
    $\begingroup$ Any HE scheme that will qualify as a reasonable scheme will provide IND-CPA security and hence encryptions of 0 and 1 are indistinguishable. So from simply looking at the ciphertexts there will be no way of deciding whether a ciphertext at some position encrypts 0 or 1. $\endgroup$ – DrLecter Oct 10 '18 at 8:47
0
$\begingroup$

Yes the adversary can guess the plaintext, and there is some probability $p$ his guess is correct. There is no way we can prevent that, and this is not a security flaw of the encryption scheme.

If the homomorphic encryption scheme you use is IND-CPA secure (or equivalently, semantically secure), the ciphertext should be indistinguishable. It entails that any (PPT) adversary cannot gain useful information from the ciphertext about the plaintext, hence the ciphertexts do not give the adversary any advantage in guessing the correct plaintext. So without the ciphertext, the probability of guessing correctly is $p$, and with the ciphertext, the probability of guessing correctly is $p+\epsilon$ where $\epsilon$ is negligible. Thus the ciphertexts, although are produced from the plaintexts, are useless from the adversary's point of view.

So the takeaway message is that security of an encryption scheme is not defined in term of "plaintext cannot be recovered" (which is impossible to achieve), but in terms of "the scheme does not make it easier for the adversary to recover the plaintext".

$\endgroup$
  • $\begingroup$ Thanks for the answer, just to make sure I got it all correctly - basically we have a certain randomization and there are many encryptions of the same thing. This is similar to random padding in RSA? So this is just a property, a requirement for my Enc/Dec functions in my ecnryption scheme? I also found this video that explains this nicely -youtube.com/watch?v=xlcb_G1_rzk&feature=youtu.be&t=368 $\endgroup$ – Yordan Boev Oct 10 '18 at 9:26
  • $\begingroup$ Yes, randomization is needed to achieve IND-CPA security. $\endgroup$ – Changyu Dong Oct 10 '18 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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