I'm reading the original Paillier paper.

I've reached Lemma 3: If the order of $g$ is a nonzero multiple of $n$, then $\varepsilon_g(x,y) = g^x y^n \mod n^2$ is a bijection, where $x \in \mathbb{Z}_n$ and $y \in \mathbb{Z}_n^*$.

Take for example $n=6$, $n^2=36, \mathbb{Z}_6^* = \{1, 5\}$.

Let $g=5$. The order of $5$ modulo $36$ is $6$ (see WolframAlpha), which is a multiple of $6$, so $\varepsilon_g$ should be a bijection.

Let $(x_1, y_1) = (1, 1)$ and $(x_2, y_2) = (1, 5)$. Then:

  • $y_1, y_2 \in \mathbb{Z}_6^*$ as required.
  • $\varepsilon(x_1, y_1) = 5^1 \cdot 1^6 = 5$
  • $\varepsilon(x_2, y_2) = 5^1 \cdot 5^6 = 5$ (assuming operations are modulo $36$.)

So... It's not a bijection. Am I missing something?


Short answer: This appears to be an error in the paper, but it's not a problem in practice.

The proof of Lemma 3 uses the following implication:

Since $\gcd(\lambda,n)=1$, $x_2-x_1$ is necessarily a multiple of $n$. Consequently, $x_2-x_1=0\bmod n$ and $(y_2/y_1)^n=1\bmod n^2$, which leads to the unique solution $y_2/y_1=1$ over $\mathbb Z_n^\ast$.

As your example shows, the assertion $\gcd(\lambda,n)=1$ is wrong in general: $n=2\cdot 3$, hence $\lambda=(2-1)\cdot(3-1)=2$, and $\gcd(\lambda,n)=2\neq1$. Structurally, this becomes manifest in the fact that the ring $\mathbb Z/n^2$ contains nontrivial $n$th roots of unity — in your case the element $5$ — which voids the uniqueness claim.

It is not hard to prove that for $n=pq$ a product of two primes, this phenomenon occurs if and only if $p=2$ or $q=2kp+1$ for some $k\in\mathbb N$. (Modulo reordering of $p$ and $q$.) The chance of this happening is negligible for any realistically-sized and randomly generated pair of primes $(p,q)$, hence this is not going to be an issue in practice.

  • $\begingroup$ Do you know if a proof that $(2, 3)$ and $(p, 2kp+1)$ are the only exceptions exists somewhere online? $\endgroup$ – danxinnoble Apr 25 '17 at 12:52
  • 1
    $\begingroup$ Got the proof about $gcd(\lambda, n)$ from p492 of this book If we assume w.l.o.g. $q>p$, $\gcd(\lambda,n) = \gcd((p-1)(q-1), pq) > 1 \implies \gcd(p-1, p) > 1 $ OR $ \gcd(q-1, q) > 1$ (both impossible) OR $\gcd(p-1, q) > 1$ (also impossible since $q$ is prime, $q > p$) OR $\gcd(q-1, p) > 1$. So it must be the last case: $q-1 = c p, c\in \mathbb{Z}$. We know $q$ is odd, so if $c$ is odd, $p$ must be even, so $p=2$. Else $c = 2k, k \in \mathbb{Z}$. $\endgroup$ – danxinnoble Apr 25 '17 at 13:30
  • $\begingroup$ @danxinnoble A relevant link is A Note on 'Non-secret Encryption'. It decribes RSA prehistory ($e=n$) and gives correct conditions $(p-1,q)=(q-1,p)=1.$ $\endgroup$ – Alexey Ustinov Mar 9 '18 at 23:44

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.