Stream Ciphers and Pseudo Random Generators

Stream Cipher

making OTP practical

Idea: replace "random" key by "pseudo random" key.

Definition: Pseudo random generator(PRG) is a function $G:\{0,1\}^s \rightarrow \{0,1\}^n$, where $n >> s$.

• ${0,1}^s$ is the space of seed
• $G$ should be efficient computable by a deterministic algorithm
• Output should seem random

the only random thing is the seed

• Stream Cipher cannot hace perfect secrecy
• Need a different definition of security (Because the length of stream cipher key is usually shorter than plaintext)
• Security will depend on specific PRG

PRGs Must be Unpredictable

It will be a problem if PRGs are predictable: $\exists i: G(k)[1, ..., i] \stackrel{ alg. }{\to} G(k)[i+1, ..., n]$. The formula demostrates that there's a specific algorithm $\stackrel{ alg. }{\to}$ which can predict the $G(k)$ value after $i$ such as $(i + 1)$, from the existing set of $G(k)[1, ..., i]$.