Paillier cryptosystem is a probabilistic asymmetric algorithm for public key cry

Question

Paillier cryptosystem is a probabilistic asymmetric algorithm for public key cryptography. Doesn't homomorphic encryption schemes have regular effects on the plaintext, and does that mean Pailliers cryptosystem missing the nonce? What is that I am missing?

I am also trying to understand if there are a disadvantage of Gentry's fully homomorphic scheme in terms of security (e.g. besides that the scheme is homomorphic how would it stand next to AES for example). Note that I do not refer to its impractical use due to its many series of computations.

Can anyone shed some light on these things for me, or perhaps point me in a direction where I can find information about it (I have been looking around, and the actual paper Gentry wrote is quite difficult to grasp for me and Pailliers cryptosystem eludes me a bit in this aspect).

Explanation / Answer

You seem to have some conceptual misunderstanding. A homomorphic property of an encryption scheme does not necessarily mean that it is deterministic.

There are examples like textbook RSA which has a multiplicatively homomorphic property (multiplying ciphertexts modulo the modulus gives you a ciphertext to the product of the two hidden plaintexts modulo the modulus), but is insecure due to its deterministic property, i.e., no IND-CPA security. Loosely speaking, you can test against given ciphertexts by trial encryptions using the respective public key with candidate plaintexts.

What is clearly true is that homomorphic encryption schemes can not be secure against adaptively chosen ciphertext attacks (IND-CCA2) as the homomorphism prevents this type of security. But everything below is possible. For instance, Paillier is secure against chosen plaintext attacks (IND-CPA), but is additively homomorphic.

Another (from the point of math) more simple example is additively homomorphic aka "exponential" ElGamal, which is simpler for illustration.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.