Join Log in
Score:1
rzxh avatar Crypto

Generation of the order $\lambda$ (which is lcm((p-1),(q-1))) element g in modified paillier, why $-a^{2n}$?

de flag
rzxh

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.

37
0 + 0
Score:4
Daniel S avatar Crypto
ru flag
Daniel S

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

0 + 0
rzxh avatar
de flag
rzxh
I think I get it this time, thanks for your explaination.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.