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

*Ivan Damgard and Maciej Koprowski*

**Abstract: **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.
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.

**Category / Keywords: **public-key cryptography / root extraction problem, RSA, digital signatures

**Publication Info: **Extended version of what is to appear in Eurocrypt 2002.

**Date: **received 29 Jan 2002, last revised 24 Feb 2004

**Contact author: **mkoprow at brics dk

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **An error in the security proof of the signature scheme was corrected.

**Version: **20040224:133537 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]