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?
  • $\begingroup$ calculate $r$? What you mean. $r$ is chosen uniformly from $\mathcal{Z}_N$ to achieve the semantic security. $\endgroup$ – kelalaka Nov 27 '18 at 9:46
  • $\begingroup$ @kelalaka Thanks for your comment, I mean how to recover random r based on plaintext, ciphertext and private key. $\endgroup$ – 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.

| improve this answer | |
  • $\begingroup$ It is strange that Wikipedia propose to choose $r\mod N^2$ while $r^N\mod N^2$ depends on $r\mod N$ only. $\endgroup$ – Alexey Ustinov Sep 29 '19 at 12:15

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.