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