How to construct a next bit predictor from a distinguisher

Question

I read the claim, without proof, that it is possible to construct a next bit predictor for any PRNG given an oracle distinguisher for that PRNG and vice versa. How do I prove that?

A distinguisher takes a bitstring and tells you if it was generated by the PRNG or not. A next bit predictor takes a bitstring and tells you what the PRNG would output next.

My own idea for distinguisher to predictor is as follows: Let s be the bitstring generated so far by the PRNG. I will ask the distinguisher if s||1 or s||0 (s appended a 0 or 1) is a string generated by the PRNG. I will then take the one where the distinguisher says its coming from the PRNG.

My idea for predictor to distinguisher is: Take s without the last bit and predict the next bit for this. If it matches s came from the PRNG.

If the distinguisher/predictor is only right with some probability, the first case gets an unusable case where the distinguisher outputs the same thing for s||0 and s||1, but that won't always happen. The second case stays the same.

Can I prove the above claim in that way, i.e. is what I am saying correct? Google doesn't really help here.

Answer 1

Your idea for constructing a distinguisher from a predictor is fine, assuming you know that the predictor predicts the last bit. The more general statement is: if you can predict any bit of the output, say the $i$th bit, given the first $i-1$ bits, then you can also build a distinguisher. A similar idea to what you showed also works to prove this statement.

For constructing a predictor, your idea doesn't work; we have to work a bit more. The problem is you don't know which bit is predictable; it could be any of the bits. Here's how we handle that. We prove that if none of the bits is predictable, then there can be no distinguisher. You prove this using a hybrid argument (do you know what that is?). Then, take the contrapositive, and you get the result you wanted.