Score:2

VDF / RSA groups

ar flag

I believe I am overthinking it; however, I need to clear out my doubts.

What is exactly RSA groups and how their order is unknown? I know in RSA N is computed by multiplying two prime numbers (p and q) and it is hard to find p and q given N. Is N what is called RSA group?

In VDF they use unknown order of RSA group; however, N is public.

Score:7
ng flag

The RSA group for modulus $N$ of secret factorization simply is the multiplicative group of integers modulo $N$, often noted $\mathbb Z_N^*$. That can be viewed or defined as the subset of integers $m$ in the interval $[0,N)$ with $\gcd(N,m)=1$. The group law is multiplication modulo $N$, that is $a*b$ is the remainder of the Euclidean division of $a\times b$, where $\times$ is integer multiplication.

That group has order¹ the Euler totient $\varphi(N)$. That quantity is unknown, since the factorization of $N$ is. We can easily compute $\varphi(N)$ if we know the factorization of $N$, and it turns out we can factor $N$ if we know $N$ and $\varphi(N)$.

Note: RSA encryption/decryption is often operating on the full monoid $[0,N)$ under multiplication modulo $N$, rather than it's group subset $\mathbb Z_N^*$. This requires that $N$ is squarefree for decryption to work reliably.


In Benjamin Wesolowski's Efficient Verifiable Delay Functions (in proceedings of EuroCrypt 2019), $(\mathbf Z/N\mathbf Z)^×$ is $\mathbb Z_N^*$. Their notation reflects a construction of this group as the restriction to invertible elements of the quotient set of equivalence classes in integers (that they note $\mathbf Z$ rather than $\mathbb Z$ above), for the equivalence relation congruent² modulo $N$, under the law $×$ which is compatible with this equivalence relation. I get this is how real math guys do it; I'm not really one.

See comment for more references on VDFs.


¹ that is, since it's a finite set, it's number of elements.

² by definition, $a\equiv b\pmod N\iff\exists q,\,a=b+q\times N$, with all quantities in $\mathbb Z$.

ckamath avatar
ag flag
VDFs were defined [here](https://eprint.iacr.org/2018/601), to be precise. ([This](https://eprint.iacr.org/2018/712) is a good survey.)
Score:0
in flag

how their order is unknown?

The RSA public key may be generated using multiparty computation (MPC) (or, less nicely, by a third trusted party). Then, N is indeed public, but p and q are not, and so the group order is unknown.

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.