Lower Bounds on Generic Algorithms in Groups
Ueli Maurer and Stefan Wolf
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.