3
$\begingroup$

I have two pseudorandom generators $G_1$ and $G_2$ from $k$ bit to $2k$ bit. I have another PRG $G_3$ from $k$ to $2k$ bits. Now I buildup a new function from $k$ to $4k$ as follows:

Let $x$ be $k$ bit then apply $G_3$ on it on $x$. Then let output by $y$. Apply $G_1$ on first $k$ bits and $G_2$ on last $k$ and join the resulting output. Then resulting function is a PRG. How do you prove this?

$\endgroup$
  • $\begingroup$ What exactly is a PRNG “from k bit to 2k bit”? $\endgroup$ – gnasher729 Apr 5 at 8:43
3
$\begingroup$

The idea is to use a hybrid argument. Let us first write a formula for the new PRG: $$ G(x) = G_1(G_{3,1}(x)) G_2(G_{3,2}(x)), $$ where $G_3(x) = G_{3,1}(x) G_{3,2}(x)$.

Suppose that we could distinguish between $G(U_k)$ and $U_{4k}$, where $U_n$ denotes $n$ random bits. Consider the following sequence: $$ G(U_k); G_1(U_k) G_2(U_k); U_{2k} G_2(U_k); U_{4k}. $$ By assumption, we can distinguish between the first distribution and the last distribution. Hence we can distinguish an adjacent pair of distributions.

  • If we can distinguish $G(U_k)$ and $G_1(U_k) G_2(U_k)$, then this gives a distinguisher for $G_3$.
  • If we can distinguish $G_1(U_k) G_2(U_k)$ and $U_{2k} G_2(U_k)$, then this gives a distinguisher for $G_1$.
  • If we can distinguish $U_{2k} G_2(U_k)$ and $U_{4k}$, then this gives a distinguisher for $G_2$.

By assumption, $G_1,G_2,G_3$ are all secure, so we obtain a contradiction.

$\endgroup$
2
$\begingroup$

This is the Goldreich-Goldwasser-Micali construction, and its security is proved in good textbooks on the foundations of cryptography (e.g., Oded Goldreich's book).

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