Paillier encryption problem when q or p divides r

Question

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.

Answer 1

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