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.
