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)?

  • $\begingroup$ You could likely do it with some sort of interactive protocol (think Zero-knowledge proof). $\endgroup$
    – mikeazo
    Dec 23, 2014 at 1:43

2 Answers 2


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

  • $\begingroup$ 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? $\endgroup$
    – pAkY88
    Aug 29, 2014 at 10:12
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 29, 2014 at 11:07
  • $\begingroup$ @pAkY88 Well since you are thinking of not decrypting then it seems that you are looking for a homomorhpic hash-tag like primitive... $\endgroup$
    – curious
    Aug 29, 2014 at 12:17
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 29, 2014 at 13:30
  • 3
    $\begingroup$ 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 $\endgroup$
    – curious
    Aug 29, 2014 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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