Pseudorandom generators, indistinguishability, and stream ciphers

Updated 06 Nov 2026

• •

  Pseudorandom generators (PRGs)

  • •

    Definition

    • •

      a deterministic, polynomial-time algorithm $G: \{0, 1\}^s \to \{0, 1\}^n$ where $n \gg s$

    • •

      $s$ -> seed length (short secret input)

    • •

      $n$ -> output length (expanded pseudorandom keystream)

    • •

      the seed contains all the entropy; $G$ itself is entirely deterministic

  • •

    Computational indistinguishability ( $P_1 \approx_p P_2$ )

    • •

      two probability distributions $P_1$ and $P_2$ over $\{0, 1\}^n$ are computationally indistinguishable if no efficient statistical test can tell hem apart with non-negligible advantage

• •

  Statistical tests and PRG security

  • •

    Statistical test

    • •

      an efficient algorithm $A: \{0, 1\}^n \to \{0, 1\}$ taking an $n$-bit candidate string and outputting 1 ("looks random") or 0 ("does not look random")

    • •

      Examples -> testing whether 0s and 1s are balanced ($|\#0 - \#1| \le 3\sqrt{n}$), counting "00" substrings, or measuring longest consecutive runs.

    • •

      Limitation of fixed test batteries -> passing empirical statistical suites (e.g. NIST SP 800-22) does not establish cryptographic security; an adversary can devise a custom polynomial-time test not included in the battery.

  • •

    PRG distinguishing advantage

    • •

      evaluates the difference in acceptance probability between pseudorandom output and true uniform randomness:

      • •
        $$\mathbf{Adv}_{\mathrm{PRG}}[A, G] := |\Pr_{k \xleftarrow{R} \{0,1\}^s}[A(G(k)) = 1] - \Pr_{r \xleftarrow{R} \{0,1\}^n}[A(r) = 1]|$$
  • •

    Cryptographically secure PRG

    • •

      generator $G$ is secure if for every efficient statistical test $A$, $\mathbf{Adv}_{\mathrm{PRG}}[A, G] \le \operatorname{negl}$

    • •

      Open complexity problem -> proving the existence of a secure PRG unconditionally would prove $P \neq NP$; cryptographic implementations therefore rely on candidate constructions supported by extensive cryptanalytic vetting.

• •

  Predictability and Yao's Next-Bit Theorem

  • •

    Next-bit predictability

    • •

      a generator $G$ is predictable at index $i \in \{0, \dots, n-1\}$ if an efficient algorithm $A$, given the prefix $G(k)[0..i-1]$, predicts the $(i)$-th bit with probability non-negligibility greater than $1/2$

      • •
        $$\Pr[A(G(k)[0..i-1]) = G(k)[i]] \ge \frac{1}{2} + \epsilon \quad (\epsilon \text{ non-negligible})$$
  • •

    Why predictability ruins cipher security

    • •

      if an attacker knows a common message prefix (e.g. "<html>" or "From:"), XORing it with the ciphertext reveals the initial keystream prefix

    • •

      a predictable PRG allows the attacker to extrapolate subsequent keystream bits and decrypt the remainder of the message

  • •

    Yao's Next-Bit Theorem (Yao 1982)

    • •

      a generator $G$ is unpredictable at every bit position $i \in \{0, \dots, n-1\}$ if and only if $G$ is a cryptographically secure PRG

    • •

      Universality of next-bit predictors -> although statistical tests can evaluate arbitrary global properties, next-bit predictability is mathematically complete: if no efficient algorithm can predict the next bit, no efficient statistical test can distinguish $G(k)$ from uniform randomness.

    • •

      easy direction: a next-bit predictor readily forms a statistical test. surprising direction: indistinguishability from all tests follows from next-bit unpredictability alone.

• •

  Stream cipher construction and security reduction

  • •

    

  • •

    let $G: K \to \{0, 1\}^L$ be a cryptographically secure PRG

  • •

    define stream cipher $\mathcal{E} = (E, D)$ over $(K, \{0, 1\}^L, \{0, 1\}^L)$:

    • •

      Encryption -> $c = E(k, m) := m \oplus G(k)$.

    • •

      Decryption -> $m = D(k, c) := c \oplus G(k)$.

  • •

    Shannon limitation

    • •

      since key length $|k| = s \ll L = |m|$, Shannon's Theorem dictates the cipher cannot have perfect security

  • •

    Security Theorem -> If $G$ is a secure PRG, the resulting stream cipher $\mathcal{E}$ is semantically secure.

  • •

    The "Swap-to-Random" security reduction (Game-hopping proof)

    • •

      Game 0 (Real Game) -> challenger samples $k \xleftarrow{R} K$, computes challenge ciphertext $c = m_b \oplus G(k)$, and sends $c$ to adversary $A$.

    • •

      Game 1 (Ideal Game) -> challenger samples truly random string $R \xleftarrow{R} \{0, 1\}^L$, computes challenge $c = m_b \oplus R$, and sends $c$ to $A$.

    • •

      Step 1 (Ideal Game analysis) -> in game 1, the encryption is an actual One-Time Pad. By the XOR Uniformity Lemma , $c$ is strictly uniform and independent of bit $b$. Therefore, the adversary's advantage in Game 1 is identically zero:

      • •
        $$\mathbf{Adv}_{\mathrm{SS}}[A, \text{Game 1}] = 0$$
    • •

      Step 2 (Distinguisher construction) -> if adversary $A$'s behavior changes between Game 0 and Game 1, $A$ serves as an efficient distinguisher $D$ against the PRG $G$:

      • •
        $$|\mathbf{Adv}_{\mathrm{SS}}[A, \text{Game 0}] - \mathbf{Adv}_{\mathrm{SS}}[A, \text{Game 1}]| \le \mathbf{Adv}_{\mathrm{PRG}}[D, G]$$
    • •

      Conclusion -> $\mathbf{Adv}_{\mathrm{SS}}[A, \mathcal{E}] \le \mathbf{Adv}_{\mathrm{PRG}}[D, G] \le \operatorname{negl}$.

  • •

    

• •

  Multi-message security and Nonces

  • •

    The single-message restriction -> basic stream cipher keys must never encrypt more than one message, otherwise keystreams collide.

  • •

    Nonce-based stream ciphers

    • •

      PRG accepts a secret key $k$ and a public Nonce $r$ ("number used once"):
      $$G: K \times R \to \{0, 1\}^L$$

    • •

      Encryption -> $E(k, m; r) := (r, m \oplus G(k, r))$.

    • •

      Decryption -> $D(k, (r, c)) := c \oplus G(k, r)$.

  • •

    Security requirement

    • •

      the pair $(k, r)$ must never be reused.

    • •

      the nonce $r$ does not require confidentiality; it can be transmitted in the clear alongside the ciphertext.

    • •

      nonces can be generated using stateful counters or uniform random sampling from a sufficiently wide space (e.g., 64 to 96 bits) to avoid birthday collisions.

  • •

    WEP's structural failure -> IEEE 802.11b WEP used a 24-bit IV prepended to the key. After transmitting $2^{12} \approx 4096$ frames, the Birthday Paradox ensures IV collisions, leading to complete keystream reuse.

◌ Explore connections in Graph view