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

Ueli Maurer and Stefan Wolf

1997, Manuscript.

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.

BibTeX Citation

@unpublished{MauWol97,
    author       = {Ueli Maurer and Stefan Wolf},
    title        = {The Generic Complexity of Index-Search Problems and Applications to Cryptography},
    year         = {1997},
    note         = {Manuscript},
}