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
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$– MimiJan 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$– kelalakaJan 9, 2021 at 10:17