Paper 2010/650 Original: eprint.iacr.org/2010/650 ↗
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 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
- Preprint.
- History
- 2010-12-21: last updated
- 2010-12-21: published
- Short URL
- https://ia.cr/2010/650
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2010/650}
}