Paper 2006/253

Hard Instances of the Constrained Discrete Logarithm Problem

Ilya Mironov, Anton Mityagin, and Kobbi Nissim

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ös 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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. 7th Algorithmic Number Theory Symposium (ANTS VII), pages 582--598, 2006.
Keywords
discrete logarithm problem
Contact author(s)
mironov @ microsoft com
History
2006-07-24: received
Short URL
https://ia.cr/2006/253
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/253,
      author = {Ilya Mironov and Anton Mityagin and Kobbi Nissim},
      title = {Hard Instances of the Constrained Discrete Logarithm Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2006/253},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/253}},
      url = {https://eprint.iacr.org/2006/253}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.