I'm trying to understand the Paillier Scheme but there's something I can't understand in the keyGen algorithm:

Ensure $n$ divides the order of $g$ by checking the existence of the following modular multiplicative inverse: $$\mu = (L(g^\lambda \bmod n^2))^{-1} \bmod n.$$

I'm trying hard to find the relation between $n$ divides the order of $g$ and $\gcd(n, L(g^\lambda \bmod n^2))=1$ but I can't find it. I hope that somebody can help me understand it.


1 Answer 1


You can find the folowing information in the book Katz, Lindell "Introduction to modern cryptography".

PROPOSITION 13.6 Let $N=p q$ , where $p, q$ are distinct odd primes of equal length. Then:

  1. $\operatorname{gcd}(N, \phi(N))=1.$
  2. For any integer $a \geq 0,$ we have $(1+N)^{a}=(1+a N) \bmod N^{2}.$

As a consequence, the order of $(1+N)$ in $\mathbb{Z}_{N^{2}}^{*}$ is $N .$ That is, $(1+N)^{N}=1 \bmod N^{2}$ and $(1+N)^{a} \neq 1 \bmod N^{2}$ for any $1 \leq a<N .$

  1. $\mathbb{Z}_{N} \times \mathbb{Z}_{N}^{*}$ is isomorphic to $\mathbb{Z}_{N^{2}}^{*},$ with isomorphism $f : \mathbb{Z}_{N} \times \mathbb{Z}_{N}^{*} \rightarrow \mathbb{Z}_{N^{2}}^{*}$ given by $$ f(a, b)=\left[(1+N)^{a} \cdot b^{N} \bmod N^{2}\right] $$

It means that $n$ divides the order of $g=f(a,b)$ iff $L(g^\lambda \bmod n^2)=a\cdot \phi(N)\in \mathbb{Z}_{N}^{*}. $


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.