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.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.inria.fr/hal-01110234
Contributor : Brigitte Briot <>
Submitted on : Tuesday, January 27, 2015 - 5:01:13 PM
Last modification on : Wednesday, January 30, 2019 - 11:07:36 AM

Links full text

Identifiers

Collections

Citation

Jean-Sébastien Coron, Antoine Joux, Avradip Mandal, David Naccache, Mehdi Tibouchi. Cryptanalysis of the RSA Subgroup Assumption from TCC 2005. PKC 2011 - Proceedings of the 2011 International Conference on Practice and Theory in Public Key Cryptography, Mar 2011, Taormina, Italy. pp.147-155, ⟨10.1007/978-3-642-19379-8_9⟩. ⟨hal-01110234⟩

Share

Metrics

Record views

202