Paillier and Gentry - homomorphic encryption

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 Paillier cryptosystem eludes me a bit in this aspect).

Answer 1

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.

There you work in a cyclic group of prime order $q$, e.g. the order $q$ subgroup of $Z_p^*$ with $p$ being a safe prime, generated by $g$. This version of ElGamal is IND-CPA secure (and thus probabilistic) and works as follows: Let $y=g^x$ be the public key and $x\in Z_q^*$ be the private key. You encode a message $m\in Z_q^*$ as an element $g^m$. To encrypt this message $m$ you choose a random $k\in Z_q^*$ (the randomizer) and the ciphertext is $(g^k, g^m\cdot y^k)$ (note that decryption yields $g^m$ and you have to compute discrete logarithms to get back $m$ - so this is only attractive for small message spaces but this does nothing to the example here). It is easy to check that given two ciphertexts to $m$ and $m'$ and randomizers $k$ and $k'$ respectively and multiplying them componentwise gives you a ciphertext to $m+m' \bmod q$. Note that the resulting ciphertext is a ciphertext with respect to randomness $k+k' \pmod q$ and if both $k$ and $k'$ are random and hidden (which is the case) so is $k+k' \pmod q$. So this scheme is additively homomorphic but still probabilistic (IND-CPA). Same holds for Paillier and FHE schemes are usually also probabilistic - as it is the case for Gentrys first construction (I just used ElGamal as it is simpler to present).

Hope this helps - its hard to type such answers on a mobile :)