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.