I am trying to prove the following:

Given an ensemble $\{p_n, g_n\}$ ($p_n$ is an $n$-bit prime and $g_n \in \mathbb{Z}^*_{p_n}$ is a generator), if $A$ is a deterministic polynomial time algorithm such that:

$$ \Pr_{x \leftarrow \mathbb{Z}^*_{p_n}} [A(a)=x \text{ where } g_n^x=a]=\frac{1}{poly(n)}$$

then there is a PPT algorithm $A'$ that solves discrete log with high probability for this ensemble.

I would probably need to somehow call $A$ a polynomial number of times and use the results, but I have no concrete direction on how to proceed with this intuition to define $A'$. Obviously, I can verify the response by $A$, since computing $g^x$ can be done in polynomial time, but if it's wrong - then what?

Note, I have seen all sorts of questions on discrete log using something called baby step giant step, but I am not familiar with that at all (in case it may be useful here).

Any help would be greatly appreciated.


1 Answer 1


Yes, the discrete logarithm is random self reduceable, that is the worst case is as hard as the random case.

If we are given y and wish to find $x$ s.t $y=g^x \bmod p$ we can pick a random a and calculate b=$g^a\times y =g^{a+x}$

This value $b$ is uniformly distributed regardless of y. If however, we solve a discrete logarithm for it we can easily subtract $a$ and find $x$.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.