Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
