# Hardcore Bit proof for discrete log

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$?
• 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? – Cpt Wobbles Sep 24 '15 at 18:10
• @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$? – D.W. Sep 24 '15 at 19:09