The Equivalence of Strong RSA and Factoring in the Generic Ring Model of Computation.
Divesh Aggarwal, Ueli Maurer, and Igor Shparlinski
Let $N$ be the result of an RSA modulus generation, i.e., 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 Strong RSA assumption states that, given an $x$ chosen uniformly at random from $\Z_N$, it is computationally infeasible to compute a $y\in \Z_N$ and an $e \in \N \setminus \{1\}$ such that $y^e \equiv x \pmod N$. This assumption is important in cryptography and has been used to construct several cryptosystems.
Due to the lack of complexity-theoretic lower bound proofs for cryptographic problems in a general model of computation, it is a common practice in cryptography to give proofs of computational security in meaningful restricted models of computation. Some examples of restricted models that are interesting in cryptography are the generic group model for proving lower bounds for the discrete logarithm problem and related problems, and the random oracle model for proving the soundness of protocols or hash function constructions. A generic model captures that an algorithm does not exploit the bit representation of the elements other than for testing equality. The security of the RSA public-key cryptosystem can be analyzed in the generic ring model.
In this paper, we prove that for almost all possible distributions of $N$, the problem of factoring $N$ can be efficiently reduced to solving the Strong RSA problem on $\Z_N$ in the generic ring model of computation, where an algorithm can perform ring operations, inverse ring operations, and test equality.
BibTeX Citation
@inproceedings{AgMaSh11,
author = {Divesh Aggarwal and Ueli Maurer and Igor Shparlinski},
title = {The Equivalence of Strong RSA and Factoring in the Generic Ring Model of Computation.},
editor = {Daniel Augot and Anne Canteaut},
booktitle = {Workshop on Coding and Cryptography - WCC 2011},
volume = inria00607256, version 1,
year = 2011,
month = 7,
publisher = {INRIA},
}