In the original paper of Paillier, lemma 1 shows why $n$ must divide the order of $g$. What I don't understand in the proof of this lemma is why $g^{x_2-x_1}(y_2/y_1)^n$ implies $g^{\lambda(x_2-x_1)}$. Where does this result come from?


This is obtained by raising to $\lambda=\lambda(n)$: since the order of any element in $\mathbb{Z}_{n^2}$ divides $n\cdot\lambda$, the second part cancels out:

$$\begin{align} g^{x_1-x_2}\cdot(y_2/y_1)^n=1\bmod{n^2} &\Leftrightarrow\\ g^{(x_1-x_2)\cdot\lambda}\cdot(y_2/y_1)^{n\cdot\lambda}=1\bmod{n^2}&\Leftrightarrow\\ g^{(x_1-x_2)\cdot\lambda}\cdot 1=1\bmod{n^2}&\Leftrightarrow\\ g^{(x_1-x_2)\cdot\lambda}=1\bmod{n^2} \end{align}$$

| improve this answer | |
  • $\begingroup$ Thx! I didn't see that. $\endgroup$ – mip Jun 14 at 16:13

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.