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?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Cross-posted: crypto.stackexchange.com/q/87884/351, cs.stackexchange.com/q/134905/755. Please do not post the same question on multiple sites. $\endgroup$– D.W.Jan 29, 2021 at 23:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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."
answered Jan 31, 2021 at 7:01
-
$\begingroup$ Might you know of any reference that proves this analogue? $\endgroup$ Jan 31, 2021 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$ Jan 31, 2021 at 10:00