Stream cipher

From CRYPTUTOR

This page is under construction. Do not rely on its accuracy until it is finished. Please edit this page or use the talk page to leave comments.

A stream cipher is similar to a pseudorandomness generator, in that it takes a short random seed, and outputs a string which "appears random" to all efficient computations. But the output length is not fixed a priori. Instead, a stream cipher, once initialized with a seed, maintains an internal state and produces output bits on demand. It derives its name from its use in encrypting a stream of data (by XORing the data stream with the pseudorandom stream).

[edit]

Definition

A pair of functions $(G, U)$ is a stream cipher with a state-space $Σ$ (w.l.o.g $Σ = {0,1} k$ ), if it has the following properties (here $k$ is the security parameter of the stream cipher):

Efficiency: $G:\Sigma\rightarrow\{0,1\}$ and $U:\Sigma\rightarrow\Sigma$ are computable in (deterministic) polynomial time in the input length. (Further $Σ$ is efficiently samplable.)
Pseudorandomness: For every polynomial $\ell(k)$ , the distribution $\mathcal{G}^\ell_k = \{G(s)\cdot G(U(s))\cdot G(U^2(s) \cdots G(U^{\ell(k)-1}(s))\}_{s\gets\Sigma}$ is a pseudorandom distribution. That is, it is computationally indistinguishable from the uniform distribution on $\ell(k)$ -bit strings. (More precisely, for every polynomial $\ell$ the distribution ensemble $\{\mathcal{G}^\ell_k\}_k\,$ is pseudorandom).