Paper 2010/650

Cryptanalysis of the RSA Subgroup Assumption from TCC 2005

Jean-Sebastien Coron, Antoine Joux, Avradip Mandal, David Naccache, and Mehdi Tibouchi

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 2^{2k} had a complexity of O{2^k}. Accordingly, k=100 bits was suggested as a concrete parameter. This paper exhibits an attack with a complexity of roughly 2^{k/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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. An extended abstract will appear at PKC 2011. This is the full version.
Keywords
RSA modulihidden ordersubgroupcryptanalysis.
Contact author(s)
mehdi tibouchi @ normalesup org
History
2010-12-21: received
Short URL
https://ia.cr/2010/650
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/650,
      author = {Jean-Sebastien Coron and Antoine Joux and Avradip Mandal and David Naccache and Mehdi Tibouchi},
      title = {Cryptanalysis of the RSA Subgroup Assumption from TCC 2005},
      howpublished = {Cryptology ePrint Archive, Paper 2010/650},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/650}},
      url = {https://eprint.iacr.org/2010/650}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.