I am studying Crypto and am trying to understand why discrete log creates is useful for creating a PRG. More specifically, I want to prove via reduction that $B(x)=(x<p/2)$ is a hardcore bit for the one-way function $f_{p,g}(x)=g^x \bmod p$. So far, I have shown that if there is a polynomial-time algorithm $D$ that computes this bit perfectly, then there is another polynomial-time algorithm $I$ that inverts the one-way function perfectly. I want to extend the proof to the case when $D$ is imperfect, but successful with probability $\frac12 +\epsilon$ for some nonnegligible $\epsilon$ (in this case, the probability is taken over a random choice of $x$ between 0 and $p-1$). I want to show that for this case, it is possible to invert $f$ with nonnegligible probability in polynomial time.

Any help is appreciated.


The usual approach is to identify a randomized self-reduction. In other words, given a problem instance $x$, you generate a randomized version of $x$, say $x'$, and show how the solution to $x'$ gives you the solution to $x$.

How does this help? Given a problem instance $x$, you can generate many randomized versions, say $x'_1,x'_2,\dots,x'_m$ (each one using independent randomness). Now, try to solve each of the $x'_1,x'_2,\dots,x'_m$. By the conditions of your problem, you know that you'll have a way to solve them, so that a $1/2 + \epsilon$ fraction of the answers are correct: i.e., so that $m/2 + \epsilon m$ of the $m$ answers are correct.

Now, you take it from here. How could you use that to form a reasonable guess at the solution to $x$?

| cite | improve this answer | |
  • $\begingroup$ So this has a miller-rabin vibe to it. Ie it seems that the more times I choose a random $x_{i} \in U_{p}$ the better chance of correctly choosing the principal square (as this is what is "hard" about Discrete log). So it would seem that I need to extend my oracle D (which predicts hardcore bits with probability $\frac{1}{2} + \epsilon$ to finding principal roots with this probability. I would then need to account for situations where the "failures" cluster in segments of my bit string by multiplying by $g^r$ for some random $r$. I am fuzzy with the details of this though. any hints? $\endgroup$ – Cpt Wobbles Sep 24 '15 at 18:10
  • $\begingroup$ @CptWobbles, Given a solution to $x'$, you can derive a solution to $x$. If your solution to $x'$ was correct, what can you say about whether your solution to $x$ will be correct? If you have $m$ candidates for the solution to $x$, and you know that at least $m/2+\epsilon m$ of them are correct, can you use that to help you predict the correct solution to $x$? $\endgroup$ – D.W. Sep 24 '15 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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