Security of stream ciphers

Perfect Security. A cipher $(E,D)$ over $(\mathcal K, \mathcal M, \mathcal C)$ is called perfectly secure if for all $c\in \mathcal C$, $k \in_r \mathcal K$, and $m_1,m_0\in \mathcal M$ with $|m_1| = |m_0|$, $$P\{ E(k,m_0)=c \} = P\{E(k,m_1)=c \}.$$ The canonical example of perfectly secure cipher is the one-time pad (OTP). This definition of security, however, turns out to be too strict for practical ciphers: It is clear that a necessary condition for perfect security is $|\mathcal K| \ge |\mathcal M|$, since for any $c \in\mathcal C$ and any $m \in\mathcal M$ there must exist $k \in\mathcal K$ such that $E(k,m)=c$. Hence perfect security can be guaranteed only if $|k|=\omega(|m|)$, which made perfectly secure ciphers hard to use in practice. (Recall that a stream cipher uses symmetric key. If we have a secure channel to transfer a key as long as a message, why not using it to transfer the message in the first place?)

Semantic Security. A cipher $(E,D)$ over $(\mathcal K, \mathcal M, \mathcal C)$ is called semantically secure if for $k \in_r \mathcal K$ and all $m_0,m_1\in \mathcal M$ with $|m_0| = |m_1|$, there is no efficient algorithm that can distinguish $E(k,m_0)$ from $E(k,m_1)$ with non-negligible probability. This fact can also be written as $\{E(k, m_0)\} \approx_p \{E(k, m_1)\},$ which means the two distributions are computationally indistinguishable.

Recall that a PRG is secure if it is computational indistinguishable from a true RNG. The following theorem connects the definition of secure PRGs and and the definition of semantic security.

Theorem. A stream cipher derived from a secure PRG is semantically secure.

The intuition of behind the theorem is as follows. It is clear that any stream cipher derived from a true RNG is semantically secure. Therefore, if a PRG derives a stream cipher that is not semantically secure, then there exists an efficient way to distinguish the PRG from a true RNG (i.e., by deriving a stream cipher and then testing the semantic security of the derived cipher), which would imply that the PRG is not secure.

Before we proceed to a formal proof, we need to make the statement ‘‘distinguish A from B’’ more precise. We define the advantage of an adversary $A$ over an algorithm $G$ with respect to $G'$ as $$Adv(A,G,G')=|P\{A(G(X))=1\} - P\{A(G'(Y))=1\}|,$$ where $X$ and $Y$ and random variables. The larger the advantage is, the more capable $A$ can distinguish $G$ from $G'$. With this definition, we see that $G(X) \approx_p G'(Y)$ if and only if $Adv(A,G,G')$ is negligible for all efficient adversaries $A$. We shall write $Adv(A,G)$ for simplicity when $G'$ is clear from the context.
Now suppose that $E$ is a stream cipher derived from PRG $G$.

Proof of the theorem. It suffices to show that for any adversary $A$ for the cipher, there is an adversary $B$ for the PRG such that $Adv(A,E) \le 2Adv(B,G).$ Our approach, which is quite standard in proving results concerning strength of security, is to build adversary $B$ using $A$ as an oracle. Formally, we define $B_i(X)=A(m_i\oplus G(X))$ for $i\in \{0,1\}$ and let $B=B_j$ where $j=\arg\max_i\{Adv(B_i,G) \}$. The construction of $B_0$ is illustrated as follows.

When $Y$ is uniformly random, there is no way to tell $m_0\oplus Y$ from $m_1 \oplus Y$, and thus $P\{A(m_0\oplus Y)=1\} = P\{A(m_1 \oplus Y)=1\}$. Now, note that

$Adv(A,E)=|P\{A(m_0 \oplus G(X))=1\} - P\{A(m_1 \oplus G(X))=1\}| \\ = |P\{A(m_0 \oplus G(X))=1\} - P\{A(m_0 \oplus Y)=1\} + P\{A(m_1 \oplus Y)=1\} - P\{A(m_1 \oplus G(X))=1\}| \\ \le |P\{A(m_0 \oplus G(X))=1\} - P\{A(m_0 \oplus Y)=1\}| + |P\{A(m_1 \oplus Y)=1\} - P\{A(m_1 \oplus G(X))=1\}| \\ =Adv(B_0,G) + Adv(B_1,G) \le 2Adv(B,G).$

This completes the proof. $\square$