Join Log in
Score:1
kentakenta avatar Crypto

Internal direct product of group of invertible elements in a Paillier modulus

kn flag
kentakenta

Let $p$ and $q$ are Sophie-Germain primes such that $p=2p'+1$ and $q=2q'+1$. Also let $n=pq$ and $n'=p'q'$. In Section 8.2.1 of this paper, the internal direct product of $\mathbb{Z}_{n^2}^*$ is shown as $$\mathbb{G}_{n}\cdot\mathbb{G}_{n'}\cdot\mathbb{G}_{2}\cdot T$$ where $\mathbb{G}_{\tau}$ is the cyclic group with the order $\tau$ and $T$ is the subgroup generated by $-1\text{ mod }n^2$. Furthermore, the paper says that this decomposition is unique except $\mathbb{G}_{2}$ where there are two possible choices. However, as far as I know, there is a unique cyclic group with order 2. Hence, I think that $\mathbb{G}_{2}$ must also be unique. What am I missing there?

27
0 + 0
rsa
Score:1
Daniel S avatar Crypto
ru flag
Daniel S

Let $g$ be such that $g\equiv 1\pmod {p^2}$ and $g\equiv -1\pmod {q^2}$, there is a unique solution to this by the Chinese remainder theorem (and this solution is not 0, 1 or -1). We see that $\langle g\rangle$ is a cyclic group of order 2, because $g^2\equiv 1\pmod {p^2}$ and $g^2\equiv 1\pmod {q^2}$ which implies that $g^2\equiv 1\pmod {n^2}$.

Likewise let $h$ be such that $h\equiv -1\pmod {p^2}$ and $h\equiv 1\pmod {q^2}$, there is a unique solution to this by the Chinese remainder theorem. We see that $\langle h\rangle$ is also a cyclic group of order 2, but the groups are distinct.

Note that $g=-h$ and vice-versa.

The group $\mathbb G_2$ can be taken as either $\langle g\rangle$ or $\langle h\rangle$.

0 + 0
kentakenta avatar
kn flag
kentakenta
Let me ask a further question which is both related to the paper and the previous question. Let $g'\leftarrow \mathbb{Z}_{n^2}^*$ and $g=(g')^{2n}$. Then, considering our direct product, $g$ must be a member of $\mathbb{G}_{n'}$, right?
0
Reply
Daniel S avatar
ru flag
Daniel S
Yes (assuming that you've not picked a pathological case such as $p'=q$).
1
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.