# 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)}$?

## 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 '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
{"ft_lang_label":"__label__en","ft_lang_prob":0.76457435,"math_prob":0.9996675,"size":1317,"snap":"2021-21-2021-25","text_gpt3_token_len":438,"char_repetition_ratio":0.13099772,"word_repetition_ratio":0.029126214,"special_character_ratio":0.33181474,"punctuation_ratio":0.111524165,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99998164,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-06-12T22:30:21Z\",\"WARC-Record-ID\":\"<urn:uuid:d1b983b2-3124-4e70-a2aa-12c06f95928b>\",\"Content-Length\":\"168114\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:e0aae064-e71b-4007-b1b7-209b2f60d964>\",\"WARC-Concurrent-To\":\"<urn:uuid:2ebcfe43-bf43-469f-bd3d-a58f3393f356>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://crypto.stackexchange.com/questions/6708/proof-of-the-standard-pseudorandom-generator-xor-encryption-scheme-in-goldreic\",\"WARC-Payload-Digest\":\"sha1:RYZ6SXTF3656DZ74MW7E6WHPPFTHUJKB\",\"WARC-Block-Digest\":\"sha1:ZT2Q6MIGTZNW2R45NLHOXZVWAQLZ3Q4K\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-25/CC-MAIN-2021-25_segments_1623487586465.3_warc_CC-MAIN-20210612222407-20210613012407-00124.warc.gz\"}"}