Is there a proof by now that Paillier is secure against chosen-ciphertext attack? The original Paillier paper mentions that it is not.


1 Answer 1


Is it yet proofed that Paillier is secure against chosen-ciphertext attack. The original Paillier paper mentions that it is not.

It is indeed not - CCA security is incompatible with the property of partially homomorphic encryption.

If we have a ciphertext $C$ and an Oracle that will decrypt any ciphertext (other than $C$), what an attacker can do to decrypt $C$ is generate the encryption of $0$ (which is presumably not the ciphertext value $1$), and homomorphically add that to $C$, generating the ciphertext $C'$, and hand $C'$ to the decryption oracle. As long as the encryption of $0$ is not $1$, then $C \ne C'$, and so the decryption oracle will have us the plaintext corresponding to $C'$, which will be exactly the same value as the plaintext of $C$ - the attacker wins.

  • $\begingroup$ So is there any security measurement to compensate for this weakness in paillier. I am trying to compare between paillier and Elgamal and it seems that both have the same weaknesses in terms of security. $\endgroup$
    – Mimi
    Jan 8, 2021 at 16:44
  • $\begingroup$ @TasneemGhunaim Poncho showed more than that. The malleability of the scheme prevents the CCA. It is not a weakness, there are schemes that can achieve CCA, take AES-GCM, for example, it has AEAD and AEAD > CCA. The partial homomorphism, actually the full homomorphism was the target of the work of Pailler's scheme to seek for the Holy Grail of cryptography - Fully, Homomorphic Encryption, the first existence demesorated by Gentry's seminal work. $\endgroup$
    – kelalaka
    Jan 9, 2021 at 10:17

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.