2
$\begingroup$

Yao's theorem says that for a distribution, next bit unpredictability is equivalent to pseudo-randomness. This link proves Yao's theorem, but the proof relies on non-uniform probabilistic polynomial time algorithms. Is there a proof of Yao's theorem that instead only uses uniform probabilistic polynomial time algorithms?

$\endgroup$
1
2
$\begingroup$

At the end of Section 2 of the lecture notes that you cite, it explicitly states "We note that an analogue of this result holds for uniform distinguishers and predictors, provided that we change the definition of next-bit predictor to involve a random choice of $i \leftarrow R [n]$ instead of a fixed value of $i$, and change the time bounds in the conclusions to be $t − O(n)$ rather than $t − O(1)$ and $t$ (we can’t do tricks like in the final paragraph of the proof). In contrast to the multiple-sample indistinguishability result from last time, this result does not need $X$ to be efficiently samplable for the uniform version."

$\endgroup$
2
  • $\begingroup$ Might you know of any reference that proves this analogue? $\endgroup$ – BlackHat18 Jan 31 at 9:00
  • $\begingroup$ I don't, but I think that it's the standard uniform hybrid reduction. You can find this in Oded Goldreich's Foundations of Cryptography. It also appears in my lecture notes. See Theorem 4.4 of Section 4.1.1 of u.cs.biu.ac.il/~lindell/89-856/main-89-856.pdf. $\endgroup$ – Yehuda Lindell Jan 31 at 10:00

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.