# Information Security and Cryptography Research Group

## Lower Bounds on Generic Algorithms in Groups

### Ueli Maurer and Stefan Wolf

Advances in Cryptology — EUROCRYPT '98, Lecture Notes in Computer Science, Springer-Verlag, vol. 1403, pp. 72–84, May 1998.

In this paper we consider generic algorithms for computational problems in cyclic groups. The model of a generic algorithm was proposed by Shoup at Eurocrypt '97. A generic algorithm is a general-purpose algorithm that does not make use of any particular property of the representation of the group elements. Shoup proved the hardness of the discrete logarithm problem and the Diffie-Hellman problem with respect to such algorithms for groups whose order contains a large prime factor. By extending Shoup's technique we prove lower bounds on the complexity of generic algorithms solving different problems in cyclic groups, and in particular of a generic reduction of the discrete logarithm problem to the Diffie-Hellmanproblem. It is shown that the two problems are not computationally equivalent in a generic sense for groups whose orders contain a multiple large prime factor. This complements earlier results which stated this equivalence for all other groups. Furthermore, it is shown that no generic algorithm exists that computes $p$-th roots efficiently in a group whose order is divisible by $p^2$ if $p$ is a large prime.

## BibTeX Citation

@inproceedings{MauWol98e,
author       = {Ueli Maurer and Stefan Wolf},
title        = {Lower Bounds on Generic Algorithms in Groups},
editor       = {Kaisa Nyberg},
booktitle    = {Advances in Cryptology --- EUROCRYPT~'98},
pages        = 72--84,
series       = {Lecture Notes in Computer Science},
volume       = 1403,
year         = 1998,
month        = 5,
publisher    = {Springer-Verlag},
}