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.

  • $\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$ Sep 29 '19 at 12:15
  • $\begingroup$ Is there a reason why you assume G to be equal to N + 1? $\endgroup$
    – UTF-8
    Aug 26 at 14:22
  • $\begingroup$ This is what Damgard-Jurik propose and it has many advantages. $\endgroup$ Aug 28 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.


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.