1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ I think I get it this time, thanks for your explaination. $\endgroup$
    – rzxh
    Sep 16 at 6:25

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.