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?


2 Answers 2


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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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