Paillier: guessing the message when knowing the cipher and the random number

I cannot get my head around this.

In Paillier, the ciphertext is calculated using

$c = g^m.r^n\ mod\ n^2$

where $(n,g)$ forms the public key and $r$ is a random number $0<r<n$.

Assuming an attacker knows $c$, $r$, $n$. and $g$, what would it take - in average - to find $m$ ?

You don't need to guess, you can find $m$ for sure.

If you know $c,r,n,g$, then you can eliminate $r^n$ from the ciphertext and get $c'=g^m \bmod n^2$.

In $Z_{n^2}^*$, we have $(n+1)^x = 1+nx \bmod n^2$ ($x\in Z_n$). Therefore:

• If $g=n+1$ is used, then $c'=g^m \bmod n^2 =1+mn$, then you can find $m=(c'-1)/n$.
• If $g\ne n+1$, since the order of $g$ must be a multiple of $n$, we have $g= (1+n)^a=1+an \bmod n^2$ for some $a$, then we can find $a=(g-1)/n$. Then $c'=g^m \bmod n^2 =1+amn$, and we can compute $m=(c'-1)/an$.

Added based on Bruno's comment: the general forumula (for all $g$) is $m=(c'-1)/(g-1)$.

• Doesn't $m=(c'-1)/n$ with $c'=c\,r^{-n}\bmod n^2$ silently assumes $g=n+1$ ? Otherwise, things are more complex, perhaps much more costly. The best I get so far is solving $g^m\bmod n$ for $m$ by baby-step/giant step, with $\approx 2\sqrt{m_\text{max}}$ modular multiplications modulo $n$. [update] Ah the new answer seems to address that!
– fgrieu
Jul 11 '18 at 10:54
• @fgrieu Thanks for pointing this out. The answer is edited to add the case where $g\ne n+1$. Jul 11 '18 at 10:59
• Thanks. Generalizes to $m=(c'-1)/(g-1)$ for all values of $g$ then
– BGR
Jul 11 '18 at 13:29