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
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.
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
No comments:
Post a Comment