Breaking RSA Generically Is Equivalent to Factoring.

Let N be a random variable distributed according to some appropriate distribution over the set of products of two primes, such that factoring N is believed to be hard. The RSA assumption states that, given an a chosen uniformly at random from and an e \in {\mathbb {N}} \setminus \{1\} such that \gcd (e, \phi (N)) = 1 , it is computationally hard to find an x\in \mathbb Z N such that x^{e} - a \equiv 0 \pmod N . When complexity-theoretic (relative) lower bounds for certain cryptographic problems in a general model of computation seem to elude discovery, a common practice in cryptography is to give proofs of computational security in meaningful restricted models of computation. An example of such a restricted model that is interesting in cryptography is the generic group model that has been used for proving lower bounds for the discrete logarithm problem and other related problems. A generic model captures that an algorithm does not exploit the bit representation of the elements other than for testing equality. In this paper, we prove that the problem of factoring $N$ can be efficiently reduced to solving the RSA problem on {\mathbb {Z}}_{N} in the generic ring model of computation, where an algorithm can perform ring operations, inverse ring operations, and test equality. This provides evidence toward the soundness of the RSA encryption and digital signature scheme, in particular showing that under the factoring assumption, they are not vulnerable to certain kinds of cryptanalytic attacks. [ABSTRACT FROM AUTHOR]