# Equality checking using additive homomorphic encryption

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?

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

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.

• I think this should answer the question. There is no solution if you do not allow for interaction. Jun 14, 2016 at 1:13
• Thanks Yehuda, Your understanding of question is right. I could not think of any other too Jun 14, 2016 at 6:44
• can you please consider answering if there is a better solution for crypto.stackexchange.com/questions/30908/… Jun 14, 2016 at 13:25
• Done. Please take a look and see if this is what you were looking for. Jun 14, 2016 at 15:15
• @YehudaLindell would you be able to include what the security implications would be if the "one party A, with private key" sends an encrypted 0 value to the "other party B" such that they can do an equality check on the encrypted value? Am I misunderstanding how often randomness is included, yielding two different encrypted values for the same decrypted 0, or would sending a known encrypted message allow the "other party B" to guess the random number or private key of "party A" (or something else)?
– a.t.
Jan 29 at 11:53