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

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

Bach2 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 cryptosystems3.

$\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. Miller4, 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) : \\ 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.”5

DL assumption implies OA: Biehl et al.5 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.6 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, \ell)$ are a solution for 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.5 give a reduction from the RSA problem to the order problem7. 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$8. 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 Cryptography9.

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

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

This assumption was introduced by Wesolowski12, 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 used by Pietrzak13 to construct verifiable delay functions (VDFs) and later formalized by Boneh et al.14 Informally, the assumptions says that the low-order problem is “hard” to solve. Specifically, 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.14 show that LOA holds in generic groups15, because breaking it implies breaking the adaptive root assumption, which holds generically (see Section 4).

Seres and Burcsi16 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

Hohenberger17 introduces the notion of a pseudo-free group and Rivest18 shows that if $\ZNs$ is pseudo-free, then $\ZNs$ satisfies Strong RSA and DL.

Rabin19 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).

Shor10 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 Miller4 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).

1. A Key-Exchange System Based on Imaginary Quadratic Fields, by Johannes Buchmann and Hugh C. Williams, in Journal of Cryptology, 1988

2. Discrete logarithms and factoring, by Eric Bach, 1984, [URL]

3. A method for obtaining digital signatures and public-key cryptosystems, by R. L. Rivest and A. Shamir and L. Adleman, in Communications of the {ACM}, 1978, [URL]

4. Riemann’s hypothesis and tests for primality, by Gary L. Miller, in Journal of Computer and System Sciences, 1976, [URL]  2 3

5. A Signature Scheme Based on the Intractability of Computing Roots, by Biehl, Ingrid and Buchmann, Johannes and Hamdy, Safuat and Meyer, Andreas, in Designs, Codes and Cryptography, 2002, [URL]  2 3

6. Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains, by Dan Boneh and Benedikt Bünz and Ben Fisch, in Cryptology ePrint Archive, Report 2018/1188, 2018, [URL]

7. A reduction from the RSA problem to the order problem is an algorithm that solves the RSA problem given an oracle for solving the order problem.

8. One way to see why $g^{\ell’} = \Ghoid$ is to note that $g^{\ell} = g^{\ell’ e} = \Ghoid$ and, since $e$ does not divide $\Ghosz$ and $e$ is prime, it follows that $\gcd(e, \Ghosz)$ = 1. Thus, $e$ can be inverted. Raising $g^{\ell’ e} = \Ghoid$ to the inverse $e^{-1}$ gives $g^{\ell’} = \Ghoid$.

9. Public-Key Parameters, by Menezes, Alfred J and van Oorschot, Paul C and Vanstone, Scott A, in Handbook of Applied Cryptography, 1996, [URL]

10. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, by Shor, Peter W., in SIAM Journal on Computing, 1997, [URL]  2

11. Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Orders, by Hamdy, Safuat and M"oller, Bodo, in Advances in Cryptology — ASIACRYPT 2000, 2000

12. Efficient Verifiable Delay Functions, by Wesolowski, Benjamin, in Advances in Cryptology – EUROCRYPT 2019, 2019

13. Simple Verifiable Delay Functions, by Krzysztof Pietrzak, in Cryptology ePrint Archive, Report 2018/627, 2018, [URL]

14. A Survey of Two Verifiable Delay Functions, by Dan Boneh and Benedikt Bünz and Ben Fisch, in Cryptology ePrint Archive, Report 2018/712, 2018, [URL]  2

15. Generic Lower Bounds for Root Extraction and Signature Schemes in General Groups, by Damg\aard, Ivan and Koprowski, Maciej, in Advances in Cryptology — EUROCRYPT 2002, 2002

16. A Note on Low Order Assumptions in RSA groups, by István András Seres and Péter Burcsi, in Cryptology ePrint Archive, Report 2020/402, 2020, [URL]

17. The Cryptographic Impact of Groups with Infeasible Inversion, by Susan Rae Hohenberger, Master’s Thesis, MIT, 2003

18. On the Notion of Pseudo-Free Groups, by Rivest, Ronald L., in Theory of Cryptography, 2004

19. Digitalized Signatures and Public-key Functions as Intractable as Factorization, by Rabin, M. O., 1979