# The Generic Complexity of Index-Search Problems and Applications to Cryptography

## Ueli Maurer and Stefan Wolf

```
```This paper is concerned with the complexity of generic algorithms
solving so-called index-search problems (isp) such as the discrete-logarithm
problem in a cyclic group. The isp was defined as follows:
given a list $(a_i)_{i\in I}$ of elements of some set $S$, and given an
element $b$ of $S$, find an $i\in I$ such that $b=a_i$.
The notion of a generic algorithm on the other hand was introduced
by Shoup. Intuitively, a generic algorithm is a general-purpose algorithm
which does not exploit any particular property of the representation
of the objects, for instance of the group elements. By using purely
information-theoretic arguments, a general lower bound on the complexity
of generic \isp s is proved. Some implications of this result are the
optimality of the baby-step giant-step algorithm in many situations,
Shoup's result concerning the hardness of the generic discrete logarithm
problem, and a complete characterization of groups for which
breaking the Diffie-Hellman key-distribution protocol
is computationally equivalent in a generic sense to computing
discrete logarithms in the same group: this holds exactly for groups
whose order is * not\/*} divisible by a
large multiple prime factor.