International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Hard Instances of the Constrained Discrete Logarithm Problem

Authors:
Ilya Mironov
Anton Mityagin
Kobbi Nissim
Download:
URL: http://eprint.iacr.org/2006/253
Search ePrint
Search Google
Abstract: The discrete logarithm problem (DLP) generalizes to the constrained DLP, where the secret exponent $x$ belongs to a set known to the attacker. The complexity of generic algorithms for solving the constrained DLP depends on the choice of the set. Motivated by cryptographic applications, we study sets with succinct representation for which the constrained DLP is hard. We draw on earlier results due to Erd\"os et~al. and Schnorr, develop geometric tools such as generalized Menelaus' theorem for proving lower bounds on the complexity of the constrained DLP, and construct sets with succinct representation with provable non-trivial lower bounds.
BibTeX
@misc{eprint-2006-21746,
  title={Hard Instances of the Constrained Discrete Logarithm Problem},
  booktitle={IACR Eprint archive},
  keywords={foundations / discrete logarithm problem},
  url={http://eprint.iacr.org/2006/253},
  note={7th Algorithmic Number Theory Symposium (ANTS VII), pages 582--598, 2006. mironov@microsoft.com 13353 received 23 Jul 2006},
  author={Ilya Mironov and Anton Mityagin and Kobbi Nissim},
  year=2006
}