7
$\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?

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

1 Answer 1

Reset to default
7
$\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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think this should answer the question. There is no solution if you do not allow for interaction. $\endgroup$
    – mikeazo
    Jun 14, 2016 at 1:13
  • $\begingroup$ Thanks Yehuda, Your understanding of question is right. I could not think of any other too $\endgroup$
    – sashank
    Jun 14, 2016 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, 2016 at 13:25
  • $\begingroup$ Done. Please take a look and see if this is what you were looking for. $\endgroup$
    – Yehuda Lindell
    Jun 14, 2016 at 15:15

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.