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

  • $\begingroup$ I'm having a hard time understanding your question. You seem to believe that Paillier and Gentry's FHE schemes are both weak. Why do you believe this? There are no practical weaknesses in either. $\endgroup$
    – mikeazo
    May 29, 2014 at 14:10
  • $\begingroup$ I have edited the question, I didn't mean the both are weak, mere wanted to get something cleared up. In my understanding, the homomorphic encryption systems where mathematical operations on the ciphertext have regular effects on the plaintext. How do they then achieve randomness? I am trying to get my head around this, but failing misserably. $\endgroup$ May 29, 2014 at 14:24
  • $\begingroup$ Concerning "how would it stand next to AES for example": There's quite a huge difference between symmetric and asymmetric encryption setup, because AES comes with a fixed block size while public key encryption schemes don't (it all depends on the parameter). What it comes down to is a tradeoff between computation and security (more security, more computation time), and then they are worlds apart. Common public key primitives are already much slowed than symmetric encryption schemes (with comparable parameters), and FHE is MUCH MUCH slower beyond that. $\endgroup$
    – tylo
    Jun 3, 2014 at 8:57

1 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 :)

  • 1
    $\begingroup$ It is a very much appreciated answer, and impressive no less typing it on the mobile :) It does make sense now, so thanks again! $\endgroup$ May 29, 2014 at 18:59

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.