Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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:
- $\operatorname{gcd}(N, \phi(N))=1.$
- 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 .$
- $\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}^{*}. $
