Predictability (PRG)

Updated 12 Aug 2026

•
Definition
- •
  a generator $G$ is predictable if there's some position $i$ and an efficient algorithm that, given only the first $i$ output bits, can guess the $(i{+}1)$ -th bit with probability noticeably better than $1/2$ (i.e. $1/2 + \epsilon$ for non-negligible $\epsilon$ )
•
Why predictability breaks security
- •
  if an attacker knows a plaintext prefix (e.g. an email is known to start with "From:"), they can XOR it against the matching ciphertext prefix to recover a prefix of the pseudorandom pad — and a predictable generator lets them extend that prefix to predict (and thus decrypt) the rest of the message
•
Unpredictable generator
- •
  a generator where no efficient algorithm can do this, for any position $i$ — a necessary (and, by Yao's Next-Bit Theorem, sufficient) condition for a secure PRG
•
Related
- •
  Pseudorandom Generator (PRG)
- •
  Yao's Next-Bit Theorem

Linked references 3