Cryptography
pseudo-random-generator
Updated Fri, 20 May 2022 02:22:45 GMT

Can you help me understand this pseudo random generator example?


I'm new to crypto. I'm learning according to the book "Introduction to Modern Cryptography". I'm having troubles with understanding of PRG and how to prove if some function is PRG or not.

I'm trying to solve this simple example:

G(x1,x2...xn) = x1,x2,...xn, x1 xor x2 xor x3... xor xn

Is G a PRG?

Well, according to the book I need to check if

$$|Pr[D(r)=1]-Pr[D(G(s))=1| <= negl(n)$$

where $r$ is chosen uniformly at random from $\{0,1\}^|G(s)|$
the seed $s$ is chosen uniformly at random from $\{0, l\}^n$,
and the probabilities are taken over the random coins used by $D$ and the choice of $r$ and $s$.

but I don't know how to calculate $D(r)$ and $D(G(s))$... I'm feeling like I'm missing something here. Can you help me grasp what Im missing?




Solution

Assuming your question is whether $G(x_1,x_2,...,x_n) = x_1,x_2,...,x_n, x_1 \oplus x_2 \oplus x_3 ... \oplus x_n$ is a PRG.

$D$ is some fixed probabilistic polynomial time distinguisher.

So to prove that $G(.)$ is a PRG, you need so show that for all such distinguishers, $D(G(.))$ cannot be distinguished from $D(.)$.

e.g. $\big| Pr[D(G(s))=1] - Pr[D(s)=1] \big| \leqslant negl(n)$ where $s \leftarrow \{0,1\}^n $

Conversely to show $G(.)$ is not a PRG you simply need to identify a distinguisher $D(.)$ such that the above equation does not hold.

In this case, $G(.)$ looks like it could be distinguished from a random distribution, since the output is just the input, followed by the xor of the inputs.

i.e. $D(.)$ is some function which outputs $1$ if the final bit of output is the xor of all of the previous bits. This would be true half of the time applied to a random distribution, but would always be true for $G(.)$. This would mean that $\big| Pr[D(G(s))=1] - Pr[D(s)=1] \big| = \big| 1 - 0.5 \big| = 0.5$

Since a half is not negligible we can say that $G(.)$ is not a PRG.