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.
Type de document :
Communication dans un congrès
WCC 2011 - Workshop on coding and cryptography, Apr 2011, Paris, France. pp.17-26, 2011
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00607256
Contributeur : Assia Saadi <>
Soumis le : vendredi 8 juillet 2011 - 13:55:49
Dernière modification le : mercredi 29 novembre 2017 - 10:27:32
Document(s) archivé(s) le : lundi 12 novembre 2012 - 10:30:22

Fichier

15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00607256, version 1

Collections

Citation

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, 2011. 〈inria-00607256〉

Partager

Métriques

Consultations de la notice

241

Téléchargements de fichiers

243