Information Security and Cryptography Research Group

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},
}

Files and Links