RSA Assumptions

Relations between RSA assumptions

Definitions

Most assumptions are formulated with respect to the security parameter . This means that the group parameters are selected so that the assumption holds with overwhelming probability as a function of (for example, with ). The set of parameters as a function of is modelled as a group generator .

RSA Assumption

The RSA Assumption states that no efficient adversary can compute -th roots a given random group element for a random . Specifically, it holds for if for any probabilistic polynomial time adversary :

Strong RSA Assumption

The Strong RSA Assumption states that no efficient adversary can compute roots of a random group element. Specifically, it holds for if for any probabilistic polynomial time adversary :

QR-strong RSA Assumption

Let denote the RSA modulus and being the set of quadratic residues (those that are squares of other elements) in .

The QR-Strong RSA Assumption states that no efficient adversary can compute a root of a given random quadratic residue. Specifically, it holds for if for any probabilistic polynomial time adversary :

-Strong RSA Assumption

The -Strong RSA Assumption states that an efficient adversary can compute at most -th roots of a given random group element. Specifically, it holds for if for any probabilistic polynomial time adversary :

Remarks:

  • For the definition is identical to the standard Strong RSA Assumption.
  • For , the adversary is efficiently able to take square roots. In class groups of imaginary quadratic order taking square roots is easy [1].
  • In -th order class groups taking -th roots is easy [1].

Adaptive Root Assumption

The Adaptive Root Assumption holds for if there is no efficient adversary that succeeds in the following task. First, outputs an element and some state . Then, a random prime in is chosen and outputs . For all efficient :

Remarks:

  • The number of primes in should be exponential in : it is possible to precompute using exponentiations. Then, an adversary with memory can store intermediate exponents and compute adaptive roots using exponentiations for each.

Order assumption

The Order assumption. For any probabilistic polynomial time adversary computing the order of a random element is hard:

Low Order Assumption

The Low Order assumption. For any probabilistic polynomial time adversary finding any element of low order is hard:

Fractional Root Assumption

The Fractional Root assumption. For any probabilistic polynomial time adversary

Diffie-Hellman Assumption

The Diffie-Hellman Assumption holds for if no efficient can compute from for random :

Discrete Logarithm

The Discrete Logarithm assumption holds for if for all efficient :

Factoring

The Factoring assumption states that for random primes it is difficult to factor .

Reductions and security

Trivial reductions

  • The Adaptive Root assumption implies the Low Order assumption. Indeed, for an element of order one can compute a -th root by setting .
  • The Strong RSA assumption implies the RSA assumption (trivially).
  • The Strong RSA assumption implies the QR-Strong assumption (almost trivial, due to the size of ).
  • The Low Order assumption unconditionally holds in because it contains no elements of low order.
  • If the RSA modulus is the product of strong primes then the Order assumption in is equivalent to factoring.

Nontrivial reductions

  • The Factoring assumption implies the Discrete Logarithm assumption in an RSA group. [2]

  • The Strong RSA assumption is equivalent to the Fractional Root Assumption in the group of quadratic residues modulo . [3]

Generic Group Model

A generic group algorithm is a program that performs only group operations and equality checks. The group is modelled as an oracle , who knows the group order , and a random function that maps to bit strings, called the encoding. The algorithm input is . The algorithm can query the oracle on pairs , and the oracle returns . Equivalently, it computes and informs about equal elements in results.

It is crucial that a generic group algorithm does not have access to the internal representation of group elements, which are integers in RSA. Most RSA assumptions hold in the Generic Group Model.

  • The Strong RSA assumption holds in the Generic Group Model. [4]

This implies that the RSA assumption is hard too. The Factoring assumption can not be formulated in the Generic Group Model as the group size is unknown to the algorithm.

  • The Adaptive Root assumption holds in the Generic Group Model. [1]

However, these results give little insight to the actual security of RSA assumptions, as most existing RSA attacks use the integer form of the group elements. For example, computing the Jacobi symbol (see below) in an RSA group is easy despite being provably hard in the Generic Group Model.

Generic Ring Model

Here we consider algorithms that are given the unit ring element and a single ring element as input and are supposed to output some element . They can query the ring oracle using multiplication, division, and addition queries on the already known ring elements, and see if the oracle outputs a previously known element. Effectively these algorithms compute rational polynomial functions of .

  • If there is a generic ring algorithm that computes such that on a non-negligible fraction of points then one can derive a factoring algorithm. [6]

  • If there is an generic ring algorithm that breaks the Strong RSA assumption by outputting rational functions and , then can be factored with the same complexity. [7]

Pseudo-freeness

Let be a set of constants and be the free group generated by i.e. the set of all finite products with multiples from .

Let be a set of variables and consider equations of form where , where is a set of products of elements from and is a a set of products of elements from . A group is pseudo-free if no efficient adversary can find an equation that does not have solutions in and a solution to this equation in (i.e. where and are mapped to some elements of ), where the mapping from to is a random function, chosen for every run of the adversary.

Informally, a group is pseudo-free if no efficient algorithm can find a non-trivial relation among randomly chosen group elements. Recall that a safe prime has form where is also prime. It is unknown if there are infinitely many safe primes.

  • Assume that is the product of two safe primes. Then the Strong RSA assumption is equivalent to the RSA group being pseudo-free. [9, 10]

  • The Order assumption holds in a pseudo-free group. [8]

  • The Diffie-Hellman assumption holds for a non-negligible fraction of bases in a pseudo-free group. [9]

Therefore, the Strong RSA assumption implies the Order assumption if is the product of two safe primes. The situation when the Strong RSA assumption holds but the Adaptive Root assumption does not hold may thus only happen if the order of in the Adaptive Root assumption is unknown but roots are computable.

References

[1] Benedikt Bunz, Ben Fisch, and Alan Szepieniec. Transparent snarks from dark compilers. Cryptology ePrint Archive, Report 2019/1229, 2019. https://eprint.iacr.org/2019/1229.

[2] Eric Bach. Discrete logarithms and factoring. Computer Science Division, University of California Berkeley, 1984. Available at https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186.pdf.

[3] Ronald Cramer and Victor Shoup. Signature schemes based on the strong RSA assumption. In ACM Conference on Computer and Communications Security, pages 46–51. ACM, 1999.

[4] Ivan Damgård and Maciej Koprowski. Generic lower bounds for root extraction and signature schemes in general groups. In EUROCRYPT, volume 2332 of Lecture Notes in Computer Science, pages 256–271. Springer, 2002.

[5] Divesh Aggarwal and Ueli M. Maurer. Breaking RSA generically is equivalent to factoring. In EUROCRYPT, volume 5479 of Lecture Notes in Computer Science, pages 36–53. Springer, 2009.

[6] Divesh Aggarwal, Ueli Maurer, and Igor Shparlinski. The equivalence of strong rsa and factoring in the generic ring model of computation. 2011. Available at https://hal.inria.fr/inria-00607256/ document.

[7] Daniele Micciancio. The RSA group is pseudo-free. In EUROCRYPT, volume 3494 of Lecture Notes in Computer Science, pages 387–403. Springer, 2005.

[8] Ronald L. Rivest. On the notion of pseudo-free groups. In TCC, volume 2951 of Lecture Notes in Computer Science, pages 505–521. Springer, 2004.

[9] Shingo Hasegawa, Shuji Isobe, Hiroki Shizuya, and Katsuhiro Tashiro. On the pseudo-freeness and the CDH assumption. Int. J. Inf. Sec., 8(5):347–355, 2009.