I am having a problem with Paillier encryption as described on Wikipedia. It says to pick $0 < r < n$, where $n=pq$ for large, equally sized primes $p$ and $q$. However, I've been testing this under trivial key sizes, setting p=11, q=13, and encrypting m=1. When I try all legal values of r, I find that decryptions fail when $p | r$ or $q | r$.

(To be clear, I'm doing the gcd checks and seeking a random generator less than $n^2$, not using the "simpler variant" on the Wiki page although I have tried that, too, without success.)

I've seen a particular Paillier implementation in Python in which the random value of $r$ is chosen to be a prime number, maybe to avoid this problem (I asked about it in this thread), but I see no such specification of a restriction on this randomness constant in the Wikipedia page or the original Paillier paper.

What am I doing wrong? If it's appropriate to post ~40 lines of Python code on this forum, I will - please indicate in a comment. I don't want to junk up the feed.

If this is a theoretic problem, what is a good limit to avoid choosing an r that is a multiple of p or q, without revealing knowledge of p or q to the party doing the encryption, (gcd with n is 1,) or is it just based on the law of large numbers that the sender will never land on such an r in practice?

Thank you.

up vote 3 down vote accepted

In Paillier encryption, the ciphertext is $c=g^n \cdot r^n \bmod n^2$, and to decrypt, you compute $m=L(c^\lambda \bmod n^2)\cdot \mu \bmod n$.

For decryption to be correct, $r$ must be a member of group $\Bbb Z_{n^2}^*$, so that $r^{n\lambda} \equiv 1 \bmod n^2$ and $r$ can be cancelled in the decryption process. If $p$ or $q$ divides $r$, then $r$ is not in $\Bbb Z_{n^2}^*$ thus cannot be cancelled and your decryption will be incorrect.

When you use small $p,q$, it is likely you can easily choose $r$ that is not in $\Bbb Z_{n^2}^*$. However, when $p,q$ are large, the probability that a random $0<r<n$ is not in $\Bbb Z_{n^2}^*$ is negligible (otherwise the RSA problem can be solved). So we usually can just use $0<r<n$, without any more constraints (requiring $r$ to be a prime to me is not necessary).

  • Thanks! Is a simple sender test to ensure the gcd with n is one? Is it worth updating the Wiki page? – Russ Sep 15 at 12:16
  • You can do that. But as I said, it is not necessary because the probility you pick an invalid $r$ is so small. Basically when you find an $r$ such that $gcd(r,n) \ne 1$, you obtain a factor of n, which means you can solve the RSA problem. The probability must be negligible. – Changyu Dong Sep 15 at 12:34

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.