# Proof of the standard pseudorandom generator + XOR encryption scheme in Goldreich

Reading Goldreich's Foundations of Cryptography II, I found this proof for the security of the common pseudorandom generator + XOR encryption scheme (Proposition 5.2.12 in the book):

Assume you have a secure pseudorandom generator $g \colon \{ 0,1\}^n \to \{0,1\}^m$, and you construct your encryption scheme in the standard way by XOR'ing the output of $g$ to a message of length $m$. To prove that this is one-message-IND-secure, Goldreich proceeds as follows:

1. Assume, for the sake of contrdiction, that there is an adversary $\mathcal{A}$ (really a poly-sized circuit in the book, but that is not important here) against this encryption scheme, such that for $x,y \in \lbrace 0,1 \rbrace^m$, $U_n \in \lbrace 0,1 \rbrace^n$ and polynomial $p$ we have: $$|Pr[\mathcal{A}(x \oplus g(U_n)) = 1] - Pr[\mathcal{A}(y \oplus g(U_n)) = 1] > \frac{1}{p(n)}.$$
2. Observe that for $U_m \in \lbrace 0,1 \rbrace^m$ we have: $$Pr[\mathcal{A}(x \oplus U_m) = 1] = Pr[\mathcal{A}(y \oplus U_m) = 1].$$
3. Then, WLOG: $$|Pr[\mathcal{A}(x \oplus g(U_n)) = 1] - Pr[\mathcal{A}(x \oplus U_m) = 1]| > \frac{1}{2p(n)},$$ which contradicts the security of $g$ (since we can distinguish its output from random).

My question

How do you get to that last inequality in step 3? In particular, how do you derive the term $\frac{1}{2p(n)}$?

-

The inequality is obtained by a distance argument.

Consider two points $X,Y$ on the real line. Taking another point $Z$, you have $|X-Z| + |Y-Z| \geq |X-Z+Z-Y| = |X-Y|$.

Applying this "triangle" inequality to your equality 1, we have for any $z \in \mathbb{R}$, $\begin{array}{l} \bigl\lvert\Pr[A(x\oplus g(U_n))=1] - z\bigr\rvert + \bigl\lvert \Pr[A(y\oplus g(U_n))=1]- z\bigl\rvert \\ \geq \bigl\lvert\Pr[A(x\oplus g(U_n))=1] - z + z - \Pr[A(y\oplus g(U_n))=1]\bigr\rvert \\ = \bigl\lvert\Pr[A(x\oplus g(U_n))=1]-\Pr[A(y\oplus g(U_n))=1]\bigr\rvert \\ > 1/p(n). \\ \end{array}$

By setting $z = \Pr[A(x \oplus U_m)=1] = \Pr[A(y \oplus U_m) = 1]$, we have $\begin{array}{l} \bigl\lvert\Pr[A(x\oplus g(U_n))=1] - \Pr[A(x \oplus U_m)=1]\bigr\rvert \\ + \bigl\lvert \Pr[A(y\oplus g(U_n))=1]-\Pr[A(y \oplus U_m) = 1]\bigr\rvert \\ > 1/p(n). \\ \end{array}$

The one of two absolute values is bigger than $1/(2p(n))$. Therefore, WLOG, you obtain your equation 3.

-
Exactly the answer I was looking for, thx! It's funny though: I had done exactly the same thing as you, including the consideration of the "triangle" inequality. But, when I got to your last equation, I couldn't figure out where that $1/2$ factor should come from. However, its good too see that I wasn't to far of :) – hakoja Mar 16 '13 at 15:35
Suppose the two absolute values are at most 1/(2p), then you get 1/p < |...| + |...| <= 2 * 1/(2p) = 1/p, that is, contradiction. – xagawa Mar 20 '13 at 16:12