Yao's Next-Bit Theorem

Updated 13 Aug 2026

•
Definition
- •
  a generator is unpredictable at every bit position if and only if it is a secure PRG (indistinguishable from random by every efficient statistical test) — due to Yao, 1982
•
Significance
- •
  "next-bit predictors" turn out to be universal — if no efficient algorithm can predict any single next bit from a prefix, then no efficient statistical test of any kind can distinguish the generator's output from random, even though there are vastly more possible statistical tests than next-bit predictors
•
One direction is easy
- •
  a predictor can always be turned into a distinguishing statistical test (run the predictor on the first $i$ bits, output 1 if it correctly predicts bit $i{+}1$ ); this direction doesn't need Yao's theorem
- •
  the converse (unpredictable ==> secure) is the genuinely surprising, harder direction
•
Related

Linked references 2