# 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 \lbrace 0,1 \rbrace^n \to \lbrace 0,1 \rbrace^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)}$?

-

## 1 Answer

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 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. – xag Mar 20 at 16:12
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 19, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.930199146270752, "perplexity_flag": "middle"}