Slightly Wrong Discrete Log Problem
-
Recall that in showing that hardness of the Discrete Log
Problem implies collision resistance of the Discrete Log Hash Family
we only showed how to solve Dlogx(y) mod p
when both x and y are primitive.
No method of solution was provide when y was non-primitive, as allowed in
the general Dlog problem.
(For the case p = 2q + 1, q prime, this implied
failure to solve Dlog for about half of all cases).
Suppose a number ε has been found such that:
For each non-primitive n ∈ Zp* ,
the conditional probability
Prob( mn is primitive |
m is primitive ) > ε
Let δ denote the probability that a randomly chosen element
in Zp* is primitive.
- (8 pts.)
Show that if Dlog is solvable by a deterministic algorithm
when x and y are primitive, then
a Las-Vegas algorithm with probability > δε for success
can be given for solving the general Dlog problem.
- (2 pts.) Calculate ε for p = 2q + 1, where p, q are prime.
- (EC 10 pts.) Find a formula for &epsilon which
works for all primes p (the formula may depend on the factorization of p). Prove your formula.
Last modified: Thu Oct 28 23:41:06 2004