Aarhus University Seal

Generic Lower Bounds for Root Extraction and Signature Schemes in General Groups

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearch

  • Department of Computer Science
We study the problem of root extraction in finite Abelian groups, where the group order is unknown. This is a natural generalization of the problem of decrypting RSA ciphertexts. We study the complexity of this problem for generic algorithms, that is, algorithms that work for any group and do not use any special properties of the group at hand. We prove an exponential lower bound on the generic complexity of root extraction, even if the algorithm can choose the public exponent itself. In other words, both the standard and the strong RSA assumption are provably true w.r.t. generic algorithms. The results hold for arbitrary groups, so security w.r.t. generic attacks follows for any cryptographic construction based on root extracting. As an example of this, we revisit Cramer-Shoup signature scheme [10]. We modify the scheme such that it becomes a generic algorithm. This allows us to implement it in RSA groups without the original restriction that the modulus must be a product of safe primes. It can also be implemented in class groups. In all cases, security follows from a well defined complexity assumption (the strong root assumption), without relying on random oracles, and the assumption is shown to be true w.r.t. generic attacks.
Original languageEnglish
Title of host publicationAdvances in Cryptology - EUROCRYPT 2002 : International Conference on the Theory and Applications of Cryptographic Techniques Amsterdam, The Netherlands, April 28 - May 2, 2002 Proceedings
EditorsLars Ramkilde Knudsen
Number of pages16
Publication year2002
ISBN (print)978-3-540-43553-2
Publication statusPublished - 2002
EventInternational Conference on the Theory and Applications of Cryptographic Techniques - Amsterdam, Netherlands
Duration: 28 Apr 20022 May 2002
Conference number: 21


ConferenceInternational Conference on the Theory and Applications of Cryptographic Techniques
SeriesLecture Notes in Computer Science

    Research areas

  • Decryption, Cryptography, Finite group, Abelian group, Extraction, Root

See relations at Aarhus University Citationformats

ID: 281402