Hard Instances of the Constrained Discrete Logarithm Problem

Details Hard Instances of the Constrained Discrete Logarithm Problem Hard Instances of the Constrained Discrete Logarithm Problem

2006-06-29

arxiv.org/abs/math/0606771v2

In proceedings of 7th Algorithmic Number Theory Symposium (ANTS VII), pages 582--598, 2006

Mathematics

Number Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Hard Instances of the Constrained Discrete Logarithm Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hard Instances of the Constrained Discrete Logarithm Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hard Instances of the Constrained Discrete Logarithm Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-117430