In the theory of pseudorandomness, there is a well-known lemma that says roughly the following. Let $X$ be a probability distribution over $\{0, 1\}^n$. Suppose there is an efficient algorithm that distinguishes $X$ from the uniform distribution with advantage $\varepsilon$. Then there is an efficient algorithm that correctly predicts the $i$th bit of $X$ with probability $1/2 + \varepsilon / n$ given the first $i - 1$ bits of $X$, for some $i \in [n]$.

The lemma is typically attributed to Yao, with a citation to the paper "Theory and Application of Trapdoor Functions" (FOCS 1982). For example, in the journal version of Blum and Micali's paper "How to Generate Cryptographically Strong Sequences of Pseudorandom Bits" (SICOMP 1984), they give a perfectly clear statement of (one version of) this lemma and attribute it to Yao.

But looking through Yao's paper, I am struggling to find the proof or even the statement of the lemma. In Section 2.3, Yao does briefly discuss the distinction between unpredictability and indistinguishability from the uniform distribution, but I can't find the generic reduction between the two notions of pseudorandomness in his paper.

Does the lemma somehow follow from some of the analysis in Yao's paper? Is there a "full version" of his paper with more details? What is the history of this lemma and its proof?

  • 4
    $\begingroup$ There is a running joke about how a lot of Andrew Yao's attributions are in person, at lectures, rather than in paper. Perhaps this is another example. $\endgroup$ Apr 22, 2021 at 1:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.