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.
Chapter PDF
Similar content being viewed by others
References
Bernstein, D.J.: Fast multiplication and its applications. In: Algorithmic number theory: lattices, number fields, curves and cryptography. MSRI Publications, vol. 44, pp. 325–384. Cambridge University Press, Cambridge (2008)
Bluestein, L.I.: A linear filtering approach to the computation of the discrete Fourier transform. IEEE Trans. Electroacoustics 18, 451–455 (1970)
Bostan, A.: Algorithmique efficace pour des opérations de base en calcul formel, Ph.D. thesis, École polytechnique (2003) (in English)
Bostan, A., Schost, E.: Polynomial evaluation and interpolation on special sets of points. Journal of Complexity 21(4), 420–446 (2005)
Coron, J.-S., Joux, A., Mandal, A., Naccache, D., Tibouchi, M.: Cryptanalysis of the RSA subgroup assumption from TCC 2005, Cryptology ePrint Archive, Report 2010/650 (2005), http://eprint.iacr.org/ , Full version of this paper
Damgård, I.B., Geisler, M., Krøigaard, M.: Efficient and Secure Comparison for On-Line Auctions. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP 2007. LNCS, vol. 4586, pp. 416–430. Springer, Heidelberg (2007)
Groth, J.: Cryptography in Subgroups of \(Z_n^*\). In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 50–65. Springer, Heidelberg (2005)
Hanrot, G., Quercia, M., Zimmermann, P.: The middle product algorithm, I. In: Applicable Algebra in Engineering, Communication and Computing, vol. 14, pp. 415–438. Springer, Heidelberg (2004)
Hart, W.B., Harvey, D., et al.: Fast library for number theory, http://www.flintlib.org
Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thomé, E., Bos, J.W., Gaudry, P., Kruppa, A., Montgomery, P.L., Osvik, D.A., te Riele, H., Timofeev, A., Zimmermann, P.: Factorization of a 768-Bit RSA Modulus. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 333–350. Springer, Heidelberg (2010)
Paillier, P., Pointcheval, D.: Efficient Public-Key Cryptosystems Provably Secure Against Active Adversaries. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 165–179. Springer, Heidelberg (1999)
Rabiner, L.R., Schafer, R.W., Rader, C.M.: The chirp z-transform algorithm and its applications. Bell System Tech. J. 48, 1249–1292 (1969)
Sage Library, http://www.sagemath.org/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 International Association for Cryptologic Research
About this paper
Cite this paper
Coron, JS., Joux, A., Mandal, A., Naccache, D., Tibouchi, M. (2011). Cryptanalysis of the RSA Subgroup Assumption from TCC 2005. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds) Public Key Cryptography – PKC 2011. PKC 2011. Lecture Notes in Computer Science, vol 6571. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19379-8_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-19379-8_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19378-1
Online ISBN: 978-3-642-19379-8
eBook Packages: Computer ScienceComputer Science (R0)