Skip to Main content Skip to Navigation
Conference papers

Cryptanalysis of the RSA Subgroup Assumption from TCC 2005

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
Complete list of metadata
Contributor : Brigitte Briot <>
Submitted on : Tuesday, January 27, 2015 - 5:01:13 PM
Last modification on : Tuesday, May 4, 2021 - 2:06:02 PM

Links full text




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⟩