# Homomorphic Encryption: how does the equality test on ciphertexts work?

Let's suppose we have a asymmetric crypto-system $H$ which is homomorphic with respect to some function $F$.

• Alice encrypts a message $m$ with her private key $e$ in the crypto-system $H$ and obtains the ciphertext $C = H(M)$
• Alice sends $C$ to Bob
• Bob computes $F$ over $C$ and obtains $C' = F(C)$
• Bob sends $C'$ to Alice
• Alice wants to check whether $C'$ is equal to some number $n$.

Let's suppose the decryption operation is costly, much more costly than the encryption. Can Alice check the equality by comparing the encryption of $n (H(n))$ and $C'$? Is that possible? With which homomorphic crypto-system(s)?

• You could likely do it with some sort of interactive protocol (think Zero-knowledge proof). – mikeazo Dec 23 '14 at 1:43

No, what you want to do is not possible, because encryption is randomized: if you were to encrypt the same message many times, you'd get many different ciphertexts. Therefore, Alice can't just compare two ciphertexts to see if they are the same; the two ciphertexts will be different even if they decrypt to the same thing.

Since Alice encrypts the message $m$ she knows the plaintext. Now Bob computes F with the public key of Alice.Alice knows the secret key of the underlying homomorphic scheme and decrypts $C'$ and obtains the underlying values. This is how homomorphic schemes operate

• Thanks for your reply. I know how homomorphic schemes operate. I was wondering what Alice may do if the decryption operation is much more costly than the encryption. May Alice avoid to decrypt C' by encrypting n and comparing the two ciphertexts? – pAkY88 Aug 29 '14 at 10:12
• No. Encryption must be randomized, so the ciphertext Alice generates will be different from the one Bob produced, even if the plaintexts are the same. – Chris Peikert Aug 29 '14 at 11:07
• @pAkY88 Well since you are thinking of not decrypting then it seems that you are looking for a homomorhpic hash-tag like primitive... – curious Aug 29 '14 at 12:17
• That's correct about RSA, but ElGamal and all the recent somewhat/fully homomorphic encryption schemes are randomized. They must be, in order to be semantically secure. – Chris Peikert Aug 29 '14 at 13:30
• Paillier cryptosystem is also randomized. It is additively homomorphic. EAch time the same message is encrypted in different ciphertexts. However the decryption is deterministic... That's why encryption algorithms are described as randomized processes and decryption as deterministic. The former it's for security while the latter it's for correctness – curious Aug 29 '14 at 13:38