# How to calculate random factor in Paillier cryptosystem?

I am currently learning paillier cryptosystem,and have two questions about random r.I use the characteristics of homomorphic addition to obtain the product of two ciphertexts C and the corresponding plaintext P.

1. Assuming I know the private key,how can I calculate r？(I want to know more details about how to calculate r)
2. If I get r and send it to another person who only knows the public key, can he use (P,r) encryption to get ciphertext C to prove that my decryption operation is correct?
• calculate $r$? What you mean. $r$ is chosen uniformly from $\mathcal{Z}_N$ to achieve the semantic security. Nov 27, 2018 at 9:46
• @kelalaka Thanks for your comment, I mean how to recover random r based on plaintext, ciphertext and private key. Nov 27, 2018 at 11:51

Let $$C$$ be the ciphertext and let $$N$$ be the public key. Thus, $$C=(1+N)^m \cdot r^N \bmod N^2$$ for some message $$m$$. We want to recover $$r$$ given the private key $$\phi(N)$$. This can be achieved by first computing $$C'$$ as an encryption of 0. To do this, decrypt to get $$P$$ and then take $$C'=C\cdot (1-P\cdot N)\bmod N^2$$ (this is scalar subtraction). Next, compute $$M = N^{-1}\bmod \phi(N)$$ and finally we have $$r = {C'}^M\bmod N$$. This works since $${C'}^M = r^{N\cdot M} = r^{1+k\cdot\phi(N)} = r \cdot (r^{\phi(N)})^k= r \bmod N$$ since the order of $$\mathbb{Z}_N^*$$ is $$\phi(N)$$.

Regarding your second question, if you give someone $$P$$ and $$r$$ then they can just re-encrypt using $$r$$ and compare to $$C$$. This would prove that decryption is correct, but is not zero-knowledge. In case zero-knowledge is needed, this is also possible (and very efficient) in Paillier.

• It is strange that Wikipedia propose to choose $r\mod N^2$ while $r^N\mod N^2$ depends on $r\mod N$ only. Sep 29, 2019 at 12:15
• Is there a reason why you assume G to be equal to N + 1? Aug 26, 2021 at 14:22
• This is what Damgard-Jurik propose and it has many advantages. Aug 28, 2021 at 17:51

The existing answer relies on the assumption that $$G$$ is equal to $$N + 1$$. If this is not the case, you can introduce a corrective factor of $$(\frac{(1+N)}{g})^P$$ that is multiplied to $$C'$$ to get the correct randomness.

In Wikipedia's notation, the entire process is:

$$m = \text{dec}(c, (\lambda, \mu))$$

$$f = ((1 + n) \cdot g^{-1})^m \mod n^2$$

$$C' = c \cdot (1 - m \cdot n) \cdot f \mod n^2$$

$$M = n^{-1} \mod \phi(N)$$

$$r = C'^M \mod n$$

The order $$\phi(N)$$ is not usually part of the secret key. However, it can easily be computed during key generation as $$\phi(N) = (p-1) \cdot (q-1)$$.

While implementing this, I found that $$f = {g^{-1}}^m \mod n^2$$ also works. However, I'm not sure whether this is mathematically sound. Maybe someone can comment on this.