Skip to Main content Skip to Navigation
Conference papers

The Equivalence of Strong RSA and Factoring in the Generic Ring Model of Computation

Abstract : 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 ZN , it is computationally infeasible to com- pute a y 2 ZN and an e 2 N n f1g such that ye x (mod 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 crypto- graphic 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 rep- resentation 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 e ciently reduced to solving the Strong RSA problem on ZN in the generic ring model of computation, where an algorithm can perform ring operations, inverse ring operations, and test equality.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Assia Saadi Connect in order to contact the contributor
Submitted on : Friday, July 8, 2011 - 1:55:49 PM
Last modification on : Wednesday, November 29, 2017 - 10:27:32 AM
Long-term archiving on: : Monday, November 12, 2012 - 10:30:22 AM


Files produced by the author(s)


  • HAL Id : inria-00607256, version 1



Divesh Aggarwal, Ueli Maurer, Igor Shparlinski. The Equivalence of Strong RSA and Factoring in the Generic Ring Model of Computation. WCC 2011 - Workshop on coding and cryptography, Apr 2011, Paris, France. pp.17-26. ⟨inria-00607256⟩



Les métriques sont temporairement indisponibles