1
$\begingroup$

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. :)

$\endgroup$
  • 2
    $\begingroup$ Is there any relation between $x_1$ and $x_2$ that can be identified at the output? $\endgroup$ – Yuval Filmus Feb 8 '11 at 2:06
  • 5
    $\begingroup$ Homework problem? $\endgroup$ – Jukka Suomela Feb 8 '11 at 2:14
  • $\begingroup$ @Yuval: By definition, $G'$ is pseudorandom if for large-enough, randomly selected $x_1x_2 \in \{0,1\}^{2k}$, the output of $G'$ on $x_1x_2$ is computationally indistinguishable from the uniform distribution. Since the seed is randomly selected, it is unstructured, meaning you can't assume any relationship between $x_1$ and $x_2$. $\endgroup$ – M.S. Dousti Feb 8 '11 at 3:42
  • $\begingroup$ @Yuval (cont'd): On the other hand, even for the random selection of the seed, there might be some structuredness in the output which leads to distinguishing it from uniform distribution. For instance, a $1 / 2^k$ fraction of inputs have $x_1=x_2$, leading to $G(x_1)=G(x_2)$ (this is not enough per se, since this fraction is negligible). $\endgroup$ – M.S. Dousti Feb 8 '11 at 4:01
  • 1
    $\begingroup$ ps: It seems to me that this construction works (i.e. is secure) since breaking it means breaking $G$ with multiple sampling, and that is equivalent to breaking $G$ (using single sampling). You can find the argument in Crypto textbooks, "PRNG secure against multiple sampling". So if there is not a relation between $x_1$ and $x_2$ this is secure (and I guess this was the reason for Yuval's comment). $\endgroup$ – Kaveh Feb 8 '11 at 9:19
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Well done, Kristoffer! $\endgroup$ – M.S. Dousti Feb 8 '11 at 10:57
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

@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.

$\endgroup$
  • 2
    $\begingroup$ this should really be a comment. $\endgroup$ – Suresh Venkat Feb 8 '11 at 5:44
  • 3
    $\begingroup$ I agree with Suresh. I tired unsuccessfully to convert it into a comment but it is too long. It might be better to incorporate this in the question as the motivation. $\endgroup$ – Kaveh Feb 8 '11 at 9:10

Your Answer

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