Is there any obstacle if we restrict in Paillier the plaintext values to be drawn from $\mathbb{Z}_N^*$ instead of $\mathbb{Z}_N$ as the original scheme indicates.


1 Answer 1


Nope, you can always restrict your message space to a subset of the message space for which the scheme is defined (which is the case here).

Note that in practice you will deal with messages relatively prime to $N$, i.e., from $\mathbb{Z}_N^*$, anyways (any message not coprime to $N$ - except zero - would allow you to factor $N$ - thus its very unlikely to hit such a message).

  • 1
    $\begingroup$ Note that one can compute an encryption of zero from two encryptions of the same messages because of the additive homomorphism though $\endgroup$ Apr 8, 2015 at 11:09
  • $\begingroup$ @FlorianBourse Yes, due to the homomorphism you may get a ciphertext to a message outside your space (i.e., 0). But I am not sure what your point exactly is. $\endgroup$
    – DrLecter
    Apr 8, 2015 at 11:18
  • $\begingroup$ The point is just that you cannot force all ciphertext to be for non-zero elements. A friend of mine wanted to use additively homomorph encryption with non-zero elements at some point to build a protocol, and restricting the message space isn't enough. As the question is not really precise, I wanted to add this comment on your correct answer for more details ;) $\endgroup$ Apr 8, 2015 at 11:27
  • 1
    $\begingroup$ @FlorianBourse Yes, I totally agree. But the question asks for restricting (by that I mean input to the Enc algorithm) and not enforcing :) Clearly, if you have a scheme that is homomorphic you can always produce ciphertexts to messages outside a restricted message space by means of the homomorphism. $\endgroup$
    – DrLecter
    Apr 8, 2015 at 11:30
  • $\begingroup$ @FlorianBourse this can be done by any homomorphic scheme since they are not supposed to be CCA secure. Meaning, the adversary can alter on its will the ciphertext $\endgroup$
    – curious
    Apr 8, 2015 at 11:58

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.