Stream Cipher

Updated 13 Aug 2026

•
Definition
- •
  a practical cipher built by replacing the One-Time Pad's truly random key with a Pseudorandom Generator (PRG) 's output: $E(k, m) := m \oplus G(k)$ , $D(k, c) := c \oplus G(k)$
•
Why it's not perfectly secure
- •
  the key kk k (the PRG seed) is much shorter than the message, and Shannon's Theorem says perfect security requires a key at least as long as the message — so a stream cipher can never be perfectly secure by construction
•
Security theorem
- •
  if $G$ is a secure PRG, the resulting stream cipher is semantically secure
•
Proof idea (a "swap to random" reduction)
- •
  modify the semantic-security challenger to also sample a truly random string $R$ , but ignore it and still encrypt with $G(k)$ — this doesn't change the adversary's view at all
- •
  now actually switch the challenger to encrypt with $R$ instead of $G(k)$ — since $G$ is a secure PRG, no efficient adversary can tell $G(k)$ apart from $R$ , so this swap changes the adversary's winning probability by at most a negligible amount
- •
  but encrypting with a truly random $R$ is exactly a one-time-pad game, where every adversary (even unbounded ones) has advantage 0
- •
  chaining these two negligible-difference steps together: the original stream-cipher adversary's advantage must also be negligible
•
Related

Linked references 11