Cryptographic Assumptions in Hidden-Order Groups

In this post, we summarize some of the cryptographic hardness assumptions used in hidden-order groups.

Terminology and notation

We try to describe these assumptions in terms of a generic hidden-order group $\Gho$ of order $\Ghosz$. We denote the identity element in such a group by $\Ghoid$.

Sometimes, we specifically refer to the RSA group $\Gho=\ZNs$. Specifically, let $N = pq$ be the product of two sufficiently-large prime integers $p, q$. Then, \(\ZNs = \{0 < a < N \mathrel| \gcd(a, N) = 1\}\) is the multiplicative group of integers co-prime with $N$. Recall that the size or order of this group is given by the totient function: $|\ZNs| = \phi(N) = (p-1)(q-1)$.

Other times we might also refer to the class group of imaginary quadratic orders introduced by Buchmann and Williams¹.

When we say “Assumption $A$ implies assumption $B$” this means that “for $A$ to hold, $B$ must hold”. Or, put differently, this means that “$A$ can be broken given an algorithm that breaks $B$”. For example, to say that “the Strong RSA assumption implies the order assumption (OA)” is the same thing as saying “the Strong RSA problem reduces to the order problem”, which is the same thing as saying “given an algorithm for solving the order problem, one can solve the Strong RSA problem.”

All of our probability clauses $\Pr[\dots]=\negl(\lambda)$ below would more formally be stated as “for all polynomial probabilistic time (PPT) adversaries $\Adv$, there exists a negligible function $\negl(\cdot)$ such that $\Pr[\dots] = \negl(\lambda)$.

Assumptions

Factoring

\[\Pr \begin{bmatrix} p, q \xleftarrow{\$}\primes{\poly(\lambda)},\\ N = pq : \\ (p,q) \leftarrow \Adv(N) \\ \end{bmatrix} \leq \negl(\lambda)\]

Discrete logarithm

\[\Pr \begin{bmatrix} \Gho \leftarrow \GenGho(\lambda),\\ (g,h) \xleftarrow{\$} \Gho \times \Gho,\\ \ell \leftarrow \Adv(\Gho, g, h) : \\ g^{\ell} = h \end{bmatrix} \leq \negl(\lambda)\]

Bach² shows that factoring $N$ reduces to computing discrete logs in $\ZNs$.

The RSA assumption (RSA)

Introduced by Rivest, Shamir and Adleman in their seminal 1978 paper on public-key cryptosystems³.

\[\Pr \begin{bmatrix} \Gho \leftarrow \GenGho(\lambda),\\ (g, \ell) \xleftarrow{\$} \Gho \times \Z\ \text{s.t.}\ \gcd(\ell, \Ghosz)=1\\ u \leftarrow \Adv(\Gho, g, \ell) : \\ g^{1/\ell} = u \end{bmatrix} \leq \negl(\lambda)\]

When $\Gho=\ZNs$, we cannot have $\ell=2$ because it would not be co-prime with $\phi(N) = (p-1)(q-1)$ and $f(x) = x^\ell = x^2$ would not be a permutation. But if the subgroup of quadratic residues $\QRn$ is used, then $\ell = 2$ can be used (see here). So it is best not to restrict the definition above.

Strong RSA assumption

This assumption says that, given a random $g\in \Gho$, it is hard to find any root of it: i.e., an integer $\ell$ in $\Z$ and a group element $u$ such that $g^{1/\ell} = u$. Note that this generalizes the RSA assumption, which gives the adversary not only $g$, but also the root $\ell$ that should be computed.

\[\Pr \begin{bmatrix} \Gho \leftarrow \GenGho(\lambda),\\ g\xleftarrow{\$} \Gho,\\ (u,\ell) \leftarrow \Adv(\Gho, g) : \\ g^{1/\ell} = u\ \text{and}\ \ell > 1 \end{bmatrix} \leq \negl(\lambda)\]

Strong RSA assumption implies RSA assumption: If RSA assumption doesn’t hold then Strong RSA doesn’t either. To see this, consider a Strong RSA adversary $\Adv$ that gets a random $g$ as input. Since RSA doesn’t hold, there exists an RSA adversary $\Badv$ that given such a random $g$ and random $\ell\in \Z$ with $\gcd(\ell, \Ghosz) = 1$, outputs $u$ such that $g^{1/\ell} = u$. Note that $\Adv$ can use $\Badv$ to break Strong RSA! Specifically, $\Adv$ simply picks a random $\ell$ which, with overwhelming probability is co-prime with $\Ghosz$ (or else $\Adv$ can factor $N$ ). Next, $\Adv$ calls $\Badv$ with $g$ and $\ell$, obtaining $u$ such that $g^{1/\ell} = u$ with non-negligible probability. Finally, $\Adv$ simply outputs $(u,\ell)$, breaking Strong RSA with non-negligible probability.

The order assumption (OA)

This assumption says that, given a random $g\in \Gho$, it is hard to find any multiple of its order: i.e., an integer $\ell$ such that $g^\ell = \Ghoid$ This is known as the order problem.

The earliest reference I could find to the order problem is in a paper by Gary L. Miller⁴, which shows it to be equivalent to factoring (under the Extended Riemann Hypothesis).

\[\Pr \begin{bmatrix} \Gho \leftarrow \GenGho(\lambda),\\ g\xleftarrow{\$} \Gho,\\ \ell \leftarrow \Adv(\Gho, g) : \\ \ell \ne 0 \wedge g^\ell = \Ghoid \end{bmatrix} \leq \negl(\lambda)\]

Biehl et al. highlight that “The order problem can only be difficult if the order of random elements in G is large with a very high probability.”⁵

DL assumption implies OA: Biehl et al.⁵ also give a reduction from the order problem to the discrete logarithm (DL) problem. Specifically, given an order problem instance $g$, if one can compute the DL $x$ of $g$ relative to $g^{-1}$ such that $g^x = g^{-1}$, then this gives a solution to the order problem as $g^{x+1} = \Ghoid$.

Strong RSA assumption implies OA: This is shown by Boneh et al.⁶ in Lemma 3. Suppose there is a generic adversary $\Adv$ who, given a (random) order problem $g$, solves it by outputting an $\ell$ such that $g^\ell = \Ghoid$. Then, there exists an adversary $\Badv$ that uses $\Adv$ to solve a random Strong RSA problem $g$. Specifically, $\Badv$ uses $\Adv$ to break the order problem $g$ and find the $\ell$ mentioned above. Then, $\Badv$ picks an odd prime $e$ that does not divide $\ell$ and outputs $u = g^{e^{-1} \bmod \ell}$ as the Strong RSA solution. Note that $e^{-1} \bmod \ell$ is notation for the multiplicative inverse of $e$ modulo $\ell$ (i.e., $e e^{-1} \equiv 1 \pmod \ell$). This inverse exists since $\gcd(e, \ell)=1$ (because $e$ is prime and does not divide $\ell$). The Extended Euclidean Algorithm (EEA) can be used to obtain the inverse $a = e^{-1} \bmod \ell$ by finding $(a,b)$ such that:

\[ae + b\ell = 1 \Rightarrow a = (1 - b\ell)/e\]

Also, note that that $u^e = g$ and so $(u, e)$ is a solution to the Strong RSA problem $g$:

\[u^e = (g^{e^{-1} \bmod \ell})^e = (g^\frac{1-b\ell}{e})^e = g^{1-b\ell} = g/(g^{\ell})^b= g\]

RSA assumption implies OA: Bieh et al.⁵ give a reduction from the RSA problem to the order problem⁷. Specifically, given an RSA instance $(g, e)$ such that $e$ does not divide $\Ghosz$, if one can compute a multiple $\ell$ of the order of $g$ such that $g^\ell = \Ghoid$, then one can break the RSA instance as follows. We have two cases.

• First case: If $e$ does not divide $\ell$, then we can break the assumption just like we broke Strong RSA above: output $u = g^{e^{-1} \bmod \ell}$.
• Second case: If $e$ divides $\ell$, then we can let $\ell’ = \ell / e$. Importantly, since $e$ does not divide the order of $\Gho$, then $\ell’$ is still a multiple of the order of $g$⁸. Thus, we can output $u = g^{e^{-1} \bmod \ell’}$ as before.

OA implies factoring assumption: We have to show that order problem reduces to factoring. Well, if you have a factoring oracle, you can factor $N=pq$, compute $\phi(N)= (p-1)(q-1)$ and then factor $\phi(N)$ as well. Next, given an order problem $g$, you know that $g^{\phi(N)} = \Ghoid$. If only multiples of the order are desired, then the problem is solved. Otherwise, if the actual order is required, then we know the order has to be a divisor of $\phi(N)$, the order of $\ZNs$. Thus, one can repeatedly divide out the divisors of $\phi(N)$ from the exponent and check if the result is still $\Ghoid$. For details, see this post or see Algorithm 4.79 in Chapter 4 of the Handbook of Applied Cryptography⁹.

Factoring assumption implies OA: Miller⁴ shows that one can factor $N$ if one can compute the order of random group elements in $\ZNs$ (see Theorem 4). Shor¹⁰ explains this reduction succinctly (see Section 5).

OA in class groups: Hamdy and Moller¹¹ explain how to solve the order problem in class groups whose class number is smooth.

Adaptive root assumption (ARA)

This assumption was introduced by Wesolowski¹², who initially called it the “root finding game”.

\[\Pr \begin{bmatrix} \Gho \leftarrow \GenGho(\lambda),\\ (g, \mathsf{state}) \xleftarrow{\$} \Adv_0(\Gho),\\ \ell \xleftarrow{\$} \primes{\lambda}, \\ u \leftarrow \Adv_1(\mathsf{state}, g,\ell): \\ g^{1/\ell} = u\ \text{and}\ g\ne \Ghoid \end{bmatrix} \leq \negl(\lambda)\]

The low-order assumption (LOA)

This assumption was first formalized by Boneh et al¹³ in order to prove the security of Pietrzak¹⁴’s verifiable delay function (VDF) in any hidden order group. (In contrast, Pietrzak proved his VDF secure in the subgroup of quadratic residues modulo a composite $N$ where this assumption holds unconditionally.) Informally, the assumptions says that the low-order problem is “hard” to solve: i.e., given a group $\Gho$ of hidden-order, it is hard to find $g\in \Gho$ and $\ell \ne 0$ such that $g^{\ell} = \Ghoid$.

\[\Pr \begin{bmatrix} \Gho \leftarrow \GenGho(\lambda),\\ (g, \ell) \leftarrow \Adv(\Gho) : \\ g^\ell = \Ghoid, g \ne \Ghoid\ \text{and}\ \ell < 2^{\poly(\lambda)} \end{bmatrix} \leq \negl(\lambda)\]

Distinction: LOA differs from the order assumption (OA) since the LOA adversary gets to choose both $g$ and $\ell$ such that $g^\ell = 1$. In contrast, in OA, the adversary was given a random $g$ and needed to find an $\ell$.

Adaptive root assumption implies LOA: Boneh et al.¹³ show that LOA holds in generic groups¹⁵, because breaking it implies breaking the adaptive root assumption, which holds generically (see Section 4).

Seres and Burcsi¹⁶ explain that LOA is stronger than factoring arbitrary $N$ because in $\QRn$ all elements are of high order, so factoring $N$ will not help. However, for particular kinds of $N$, they show that factoring reduces to LOA.

Other notes

Hohenberger¹⁷ introduces the notion of a pseudo-free group and Rivest¹⁸ shows that if $\ZNs$ is pseudo-free, then $\ZNs$ satisfies Strong RSA and DL.

Rabin¹⁹ shows that solving polynomial congruences $\phi(x) \equiv 0 \pmod N$ is as hard as factoring $N$ (see Section 5). He also shows that an algorithm, which given $(y,N)$, computes quadratic residues $x$ such that $x^2 = y \pmod N$ can be used to factor $N$ (see Theorem 1).

Shor¹⁰ shows that finding the order $\ell$ of a random element $g$ in $\ZNs$ (i.e., $g^\ell = 1$) can be done using a quantum computer in polynomial time. (Shor specifically requires $\ell$ to be the order: i.e., the smallest such integer.) Then, Shor uses a reduction by Miller⁴ to factor $N$, given the quantum oracle for solving the order problem. Stephanie Blanda gives an intuitive explanation.

Theorem: For all $a < N$, $\exists r\in \Z$, such that $a^r = 1 \pmod N$ iff. $\gcd(a, N)=1$ (see here).

Acknowledgements

Big thanks to Munshi Rejwan Ala Muid for pointing out a typo in the “Strong RSA assumption implies OA” subsection.