Rigorous proof against pseudorandom generator

Question

I am trying to teach myself the principles of cryptograhpy, and want to solve the following question:

Let G be the algorithm that takes an input x = (x1, . . . , xn) from {0, 1} n (so each xi ∈ {0, 1}) and outputs the string G(x1, . . . , xn) = (x1, . . . , xn, x1 ⊕ x2) in {0, 1} n+1. Rigorously prove that G is not a pseudorandom generator.

So, we would want to prove that either expansion doesn't hold (for all n, l(n) > n), which, in this case, would mean that for each x, the corresponding G > x, or pseudorandomness doesn't hold ( For efficient algorithm D, there is a negligible function 'n' such that:

Pr[D(r) = 1]-Pr[D(G(s)) = 1] $\leq$ $\epsilon$(n),

where 'r' is uniform on {0,1}$^{l(n)}$ and 's' is uniform on {0,1}$^n$

), which, in this case, means that we need to prove that there does not exist a function n such that the difference of the probabilities of the function D(r) and D(G(s)) is very small.

Now, I understand these concepts, but I am having trouble approaching this problem practically... what would be the best way to start?

Answer 1

Your definition of pseudorandomness is misleading. A better definition would start with a function with "expansion", and then state then it is indistinguishable from random. In your case, the function is "expanding" since it takes $n$ bits and outputs $n+1$ bits. However, the $n+1$ bits it produces don't look random. Can you tell why?

Answer 2

An equivalent requirement for the pseudo-randomness property is to pass the next-bit test (as proven by Yao, see https://en.wikipedia.org/wiki/Next-bit_test).

This "test" means that if you are given output bits $x_1,...,x_n$ of the generator, you will not be able to guess the next bit $x_{n+1}$ (except with a negligible advantage over 1/2, which is the probability to guess an unknown bit.)

Clearly, the generator you suggest doesn't pass the next-bit test and is not a pseudo-random generator.