As the question states, in variants of paillier cryptosystem, such as CS01 and DT-PKC, when they want an element $g$ of order $\lambda$, they choose a random number $a$ from group $Z^*_{n^2}$ and calculate $-a^{2n}$ as $g$. First, what's this multiplication of $-1$ for? Second, why $a^{2n}$ not just $a^{n}$? I think $-1$ changes nothing and $a^{2n}$ will give us an element of order $\lambda/2$ more likely, not $\lambda$. Could anyone explain this for me? Thanks.
1 Answer
If we choose $n$ to be the product of two strong primes $p=2r+1$ and $q=2s+1$ with $r$ and $s$ prime, note that $p$ and $q$ are 3 mod 4 and that $\mathrm{LCM}(p-1,q-1)=2rs$. Choosing a random $a$ and raising it to the power $2n$ gives an element of order $\lambda/2=rs$ (there is a vanishingly small chance of getting order $r$, $s$ or $1$) and which is therefore a quadratic residue. Multiplying by -1 then makes it a non-residue and hence of order $\lambda=2rs$. It also ensures that the Jacobi symbol is 1 so that no information is leaked via such symbols.
If we did not do this, there would be a non-negligible chance that $a$ is a quadratic residue and hence that $g$ would be of order $\lambda/2$ rather than $\lambda$.
-
$\begingroup$ I think I get it this time, thanks for your explaination. $\endgroup$– rzxhSep 16, 2021 at 6:25