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
In the Paillier cryptosystem we choose $n=p\,q$ where $p$ and $q$ are primes, $g=n+1$, $\lambda=\phi(n)$, $\mu=\lambda^{-1}\bmod n$.
The public key is: $(n,g)$.
The private key is: $(\lambda,\mu)$.
Encryption: choose random $r$ ($0<r<n$), encryption of message $m$ is $c=(g^m)(r^n)\bmod n^2$
Decryption: $m=((c^\lambda\bmod n^2-1)/n)\,\mu\bmod n$.
I am asking: is it possible to decrypt the ciphertext of the Paillier cryptosystem with knowledge of the random number $r$?
Once you know $r$, you can remove it from the ciphertext. If $c=(1+n)^m\bmod n^2$ then $m=(c-1)/n\mod n.$
Yes, it would be possible to decrypt the ciphertext of the Paillier cryptosystem if the random number $r$ leaked.
Encryption if per $c=(g^m)(r^n)\bmod n^2$. We know that $g=n+1$. Thus $c=((n+1)^m)(r^n)\bmod n^2$. By the binomial theorem, $$(n+1)^m=\sum_{k=0}^m\binom n k n^k$$ and $n^k\bmod n^2=0$ when $k>1$. Therefore, $(n+1)^m\bmod n^2$ reduces to $m\,n+1\bmod n^2$, and we get $c=(m\,n+1)(r^n)\bmod n^2$.
Knowing $r$, and $n$ being public, we can computes $s=r^{-1}\bmod n$, e.g. by the (half) extended Euclidean algorithm. We can then compute $t=s^n\,c\bmod n^2$ which is such that $t=m\,n+1\bmod n^2$.
And then, since $0\le m<n$, we can compute $m$ as $(t-1)/n$.
$c=(g^m)(r^n)\bmod n^2$. $\endgroup$