Welcome to the resource topic for
**2002/013**

**Title:**

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

**Authors:**
Ivan Damgard, 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.

**ePrint:**
https://eprint.iacr.org/2002/013

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .