I have a question about an implementation of the Paillier cryptosystem.

In the description of Paillier above, encryption of a plaintext message $m$ on $\mathbb {Z}_{n^{2}}$, $0\leq m<n$, proceeds by choosing a random number $r$ such that $0 < r < n$ and computing the ciphertext as $c=g^{m}\cdot r^{n}{\bmod n}^{2}$ for generator $g$.

However, in one open source Paillier implementation in Python, the encryption function creates $r$ as a prime number, making for slow encryptions.

I am curious about why $r$ is made prime in that implementation, when no such restriction exists in the public algorithm description. Could it be that it is a mathematical shortcut, or a compensation for some other shortcut, perhaps as the generator g is "hard coded" to $n+1$, rather than chosen by random/trial testing?

Is there any risk in changing the implementation to make $r$ random but not necessarily prime?

I mean no discredit to the author of the code. It is robust code and has served me quite well. I want to understand the reasons why the restriction. Thanks!

  • 2
    $\begingroup$ Be careful using that library, it uses the python random module, instead of cryptography secure prng. $\endgroup$ Aug 3 '18 at 20:20
  • $\begingroup$ It also recommends that pickle be used to serialize keys/ciphertexts, which is terrible advice. $\endgroup$
    – Ella Rose
    Aug 3 '18 at 21:29

Is there any risk in changing the implementation to make $r$ random but not necessarily prime?

None [1]. Consider the case where you encrypt two values, forming the ciphertexts $g^m r^n$ and $g^{m'} {r'}^n$, and then you homomophically add them (by multiplying the two ciphertexts).

That results in the ciphertext $g^{m + m'} (r \cdot r')^n$.

As a result, $r \cdot r'$ may not be prime [2]; if this were a security risk, that means that you really couldn't use homomorphic addition (or, actually, Paillier at all, as an attacker could take your ciphertext, add an encrypted 0, and generate another ciphertext that encrypts the same plaintext, but with a likely composite $r$).

Hence, there is no drawback for choosing a composite $r$

[1]: Other than the risk inherent with modifying any cryptosoftware and accidentally breaking something you didn't intend...

[2]: Actually, it might happen to be, as it's actually $r \cdot r' \bmod n$, and that value just might happen to be a prime within $\mathbb{Z}$

  • $\begingroup$ I can't debate your logic, thank you! Perhaps the implementer got some bad advice, then? $\endgroup$
    – Russ
    Aug 3 '18 at 21:14
  • $\begingroup$ @Russ: or possibly he grabbed the first 'generate random number' routine he found, which just happened to be the 'generate random prime' one. I wasn't there, I cannot guess... $\endgroup$
    – poncho
    Aug 3 '18 at 21:18
  • $\begingroup$ On your note [2], (it should be $\mod{n}^2$), I interpret your point as there could exist equivalent ciphertexts $\bmod n^2$, where one is the product of primes and the other is a prime: $g^{m + m'} (r \cdot r')^n \equiv g^{m + m'} (r'')^n \mod n^2$ for prime $r''$. In my mind, that's more of what is happening. $\endgroup$
    – Russ
    Aug 6 '18 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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