6
$\begingroup$

Given two ciphertexts $c_1 = enc(p_1)$ and $c_2= enc(p_2)$ using any additive homomorphic encryption scheme (or specifically Paillier).

Can we find out whether the underlying plaintexts $p_1,p_2$ are equal without decrypting $c_1,c_2$ i.e. homomorphically?

$\endgroup$
  • 1
    $\begingroup$ Given only the ciphertext or do you allow for interaction? $\endgroup$ – mikeazo Jun 11 '16 at 1:47
  • 1
    $\begingroup$ both options are ok , if there is a solution $\endgroup$ – sashank Jun 11 '16 at 4:30
  • 1
    $\begingroup$ This should not be possible in a semantically secure encryption scheme. $\endgroup$ – user27950 Jun 11 '16 at 8:13
6
$\begingroup$

I'm not sure if I understand what you are asking, so I'll clarify what I am about to answer. We are given two ciphertexts and we want to know if they encrypt the same plaintext or if they encrypt different plaintexts, and we want to do this without revealing anything but this fact.

Then, using the additive homomorphism, it's possible to compute $c=enc(r\cdot (p_1-p_2))$. If $p_1=p_2$ then this is an encryption of 0; else it's an encryption of a random value.

Now, let's consider the setting where one party holds the private key and the other has $c_1,c_2$. Then, the 2nd party can compute the above as I showed and send it to the first party. The first party can then decrypt and see if it is 0 or not. There exist ways for the first party to prove this to the second party efficiently.

I hope that this answers the question.

$\endgroup$
  • $\begingroup$ I think this should answer the question. There is no solution if you do not allow for interaction. $\endgroup$ – mikeazo Jun 14 '16 at 1:13
  • $\begingroup$ Thanks Yehuda, Your understanding of question is right. I could not think of any other too $\endgroup$ – sashank Jun 14 '16 at 6:44
  • $\begingroup$ can you please consider answering if there is a better solution for crypto.stackexchange.com/questions/30908/… $\endgroup$ – sashank Jun 14 '16 at 13:25
  • $\begingroup$ Done. Please take a look and see if this is what you were looking for. $\endgroup$ – Yehuda Lindell Jun 14 '16 at 15:15

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.