# 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. – kelalaka Nov 27 '18 at 9:46
• @kelalaka Thanks for your comment, I mean how to recover random r based on plaintext, ciphertext and private key. – shascc Nov 27 '18 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. – Alexey Ustinov Sep 29 '19 at 12:15