Statistical Test

Updated 30 Sep 2026

•
Definition
- •
  an efficient algorithm $A$ that takes an $n$ -bit string and outputs 0 ("doesn't look random") or 1 ("looks random")
•
Example tests
- •
  checking that the count of 0s and 1s is close to equal
- •
  checking that the count of "00" substrings is close to $n/4$
- •
  checking that the longest run of 0s is close to $\log n$
•
Note
- •
  statistical tests can be arbitrarily clever or arbitrarily silly (e.g. a test that always outputs 0, or one fooled by the all-1s string) - a fixed battery of ad hoc tests is not a good security definition, since it's always possible a generator passes every test in the battery yet is still broken by some other test
•
Advantage (against a generator $G$ )
- •
  $\mathbf{Adv}_{PRG}[A, G] := |\Pr[A(G(k)) = 1] - \Pr[A(r) = 1]|$ , comparing how often $A$ says "random" on a pseudorandom output vs. a truly random string
- •
  advantage near 1 means $A$ can tell pseudorandom apart from random (it "broke" $G$ ); advantage near 0 means it can't
•
Definition of a secure PRG
- •
  $G$ is secure if every efficient statistical test has negligible advantage against it - not just a fixed battery, but literally every efficient algorithm
•
Open problem
- •
  no PRG has ever been proven secure under this definition - doing so would imply $P \neq NP$ ; the field instead relies on well-studied heuristic candidates that have resisted decades of cryptanalysis
•
Related

Linked references 5