Simple question about pseudorandom generator

Question

I am stuck on the following question related to pseudorandom generator and any help would be appreciated.

Let $G:\{0,1\}^k \to \{0,1\}^{k+1}$ be a pseudorandom generator. Define $G':\{0,1\}^{2k} \to \{0,1\}^{2k+2}$ by $G'(x_1x_2)=G(x_1)G(x_2)$ where $x_1, x_2 \in \{0,1\}^k$.

Prove that $G'$ is not a pseudorandom generator in general.

I don't think it is necessary (and feasible) to find a counter-example $G'$ since it requires us to find a pseudorandom generator $G$, (which means we will have proved the existence of pseudorandom if we can find such $G$) so normally how can we tackle this kind of problem?

Thank you very much in advance. :)

Answer 1

I assume you mean a cryptographic PRG.

Let's assume on the contrary that the $G'$ is not secure. So let $A$ be a probabilistic Turing machine that distinguishes the output of $G'$ from uniformly random bits.

Let $x_1,x_2$ be $k$ bit random strings, and let $z_1,z_2$ be $k+1$ bit random strings.

We have that $A$ distinguishes the distribution of strings $D_0 : G(x_1)G(x_2)$ and $D_2: z_1z_2$.

Consider now the hybrid distribution of strings given by $D_1: G(x_1)z_2$.

By the triangle inequality $A$ also distinguishes between either $D_0$ and $D_1$ or between $D_1$ and $D_2$.

Assume without loss of generality that $A$ distinguishes between $D_0$ and $D_1$. Then we can break $G$ as follows. On input $y$, pick uniformly random $k$ bit string $x_1$ and give the string $G(x_1)y$ to $A$.

Answer 2

I've been thinking about this construction for quite some time, and I didn't came up with a counterexample to its security. As Kristoffer showed, your construct is secure. However, I wanted to point out that your construction is outperformed by the traditional one (in almost all cases), whereas you claimed:

I wonder whether there is any "trivial" construction that is better than the "extra-bit" construction, and therefore I came across the "construction" in my question.

Let me elaborate. A pseudorandom generator is a function $G \colon \{0,1\}^n \to \{0,1\}^{\ell(n)}$, where $\ell(\cdot)$ is a stretch function; that is, $\ell(n) > n$ for all $n$. The function $G$ has to satisfy some security requirements, which I'm neglecting for the moment. (My comments above mention these requirements.)

Now assume that we have a seed $s$ of size $n$. Applying $G(G(s))$, we stretch this seed to a pseudorandom bit sequence of size $\ell(\ell(n))$, while applying your construct, one gets an output of size $\ell(n/2) + \ell(n/2)$., and we don't even know that this output is pseudorandom.

Two examples:

1) For you case, $\ell(n) = n + 1$:

• The traditional construction output is $(n+1)+1 = n+2$ bits;
• Your construction output is $(n/2+1)+(n/2+1) = n+2$ bits;

So the performance are the same.

2) On the other hand, for $\ell(n) = 3n$

• The traditional construction output is $3(3n) = 9n$ bits;
• Your construction output is $(3n/2)+(3n/2) = 3n$ bits;

And your construction is outperformed.

Answer 3

@Jukka: This is not a homework problem. Recently I have read about pseudorandom generator in a book, and it talks about increasing the expansion factor of a pseudorandom generator.

Given a pseudorandom generator $G:\{0,1\}^k \to \{0,1\}^{k+1}$, we can construct a pseudorandom generator $G_d:\{0,1\}^k \to \{0,1\}^{k+d}$ by iteratively applying $G$ on the seed to get an extra bit in each iteration.

I wonder whether there is any "trivial" construction that is better than the "extra-bit" construction, and therefore I came across the "construction" in my question.

I believe that the "construction" in the question does not give a pseudorandom generator in general, so I attempt to prove that by myself, but then I realise that the "normal" approach of finding a counterexample does not work in this case. I have no idea how to tackle this problem, so I would like to get some help on solving this problem.

Thanks.