Cryptanalysis of the RSA Subgroup Assumption from TCC 2005

Jean-Sébastien Coron 1 Antoine Joux Avradip Mandal 1 David Naccache 2, 3 Mehdi Tibouchi 2, 3
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : At TCC 2005, Groth underlined the usefulness of working in small RSA subgroups of hidden order. In assessing the security of the relevant hard problems, however, the best attack considered for a subgroup of size 22ℓ had a complexity of O(2ℓ). Accordingly, ℓ= 100 bits was suggested as a concrete parameter. This paper exhibits an attack with a complexity of roughly 2ℓ/2 operations, suggesting that Groth’s original choice of parameters was overly aggressive. It also discusses the practicality of this new attack and various implementation issues.
Type de document :
Communication dans un congrès
Dario Catalano; Nelly Fazio; Rosario Gennaro; Antonio Nicolosi. PKC 2011 - Proceedings of the 2011 International Conference on Practice and Theory in Public Key Cryptography, Mar 2011, Taormina, Italy. Springer, 6571, pp.147-155, 2011, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-642-19379-8_9〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01110234
Contributeur : Brigitte Briot <>
Soumis le : mardi 27 janvier 2015 - 17:01:13
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

Identifiants

Collections

Citation

Jean-Sébastien Coron, Antoine Joux, Avradip Mandal, David Naccache, Mehdi Tibouchi. Cryptanalysis of the RSA Subgroup Assumption from TCC 2005. Dario Catalano; Nelly Fazio; Rosario Gennaro; Antonio Nicolosi. PKC 2011 - Proceedings of the 2011 International Conference on Practice and Theory in Public Key Cryptography, Mar 2011, Taormina, Italy. Springer, 6571, pp.147-155, 2011, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-642-19379-8_9〉. 〈hal-01110234〉

Partager

Métriques

Consultations de la notice

190