2
$\begingroup$

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 I’m missing?

$\endgroup$
  • 2
    $\begingroup$ Not really; what you need to check is whether such a D exists. $\endgroup$ – fkraiem Feb 1 '17 at 13:52
  • $\begingroup$ @fkraiem and such a D exist? I just don't get it, how I can define this D? how can I check if D can distinguished between them or not? means, how do I get an answer to this calculate? I just don't get it... $\endgroup$ – Moshe9362 Feb 1 '17 at 14:16
  • $\begingroup$ "And such a D exist?" Well, I don't know; that's exactly the question you are asked to answer. $\endgroup$ – fkraiem Feb 1 '17 at 15:15
  • $\begingroup$ Well actually you are asked to check whether this is true for all D, or equivalently, whether there exists a D for which this is not true. $\endgroup$ – fkraiem Feb 1 '17 at 15:20
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.