# Paillier paper: Number Theoretic Lemma doesn't seem to work

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?

## 1 Answer

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.

• Do you know if a proof that $(2, 3)$ and $(p, 2kp+1)$ are the only exceptions exists somewhere online? – danxinnoble Apr 25 '17 at 12:52
• 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}$. – danxinnoble Apr 25 '17 at 13:30
• @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.$ – Alexey Ustinov Mar 9 '18 at 23:44