5
$\begingroup$

I am puzzled by the following question, since I am not very familiar with proof methods of Pseudo-Random Generators (I only know how to use the inequality from the PRG definition to prove or disprove, but it may not work in this case?).

For any PRG $G$, if we partition an input binary string $s$ with length $n$, into substrings $s_1$ and $s_2$ with $s=s_1||s_2$ and where $|s_1|\leq|s_2|\leq|s_1|+1$, which means almost half and half, then is the following new generator $G'$ a PRG as well?

$G'(s)=G(s_1)||G(s_2)$,which means use the two sub-strings as input to $G$, and concatenate the results. Assume $|G(n)|=n+1$, and here clearly $|G'(n)|=n+2$

I think such $G'$ is a PRG but I do not know how to prove it, and I also wonder if it could be generalized like $s=s_1||s_2|| \ldots s_m$ and $G'(s)=G(s_1)||G(s_2)||\ldots G(s_m)$, is $G'(s)$ a PRG as well?

$\endgroup$
  • $\begingroup$ In my opinion, since s is randomly, so s1 and s2 are independent, then G(s1) and G(s2) are independent, they are both pseudo random string, after the concatenation, it must be pseudo random as well. But I think this expression is too informal and unreliable, so I really hope someone could give a formal proof, thank you guys. $\endgroup$ – Meow Oct 12 '16 at 1:25
  • $\begingroup$ part of the definition of the PRG is that the output is undistinguishable from the random output. Therefore until the contatenation is undistinguishable from the random output, you're still having PRG $\endgroup$ – gusto2 Oct 13 '16 at 7:55
  • $\begingroup$ Thank you, but that is exact my intuition. Unfortunately, I think it may not work since it does not like a formal proof. $\endgroup$ – Meow Oct 13 '16 at 21:32
4
$\begingroup$

The function $G'$, as you intuited, is indeed a PRG. The standard way to establish such results is through the hybrid argument. Details follow.

Let $G_n:\{0,1\}^n\rightarrow\{0,1\}^{n+1}$ be an $\epsilon(n)$-secure PRG; that is: $$G_n(U_n)\approx_{\epsilon(n)}U_{n+1},~~~~~(1)$$ where $\approx_{\epsilon(n)}$ denotes computational distance$^*$ of $\epsilon(n)$, and $U_n$ is the uniform distribution on $\{0,1\}^n$.

Given $(1)$, we show that $G'_n$ is an $2\epsilon(n/2)$-secure PRG (for even $n$ for the moment); that is: $$G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})\approx_{2\epsilon(n/2)}U_{n+2}.~~~~~(2)$$ This is accomplished in two steps using a hybrid (intermediate) distribution $U_{n/2+1}\|G_{n/2}(U_{n/2})$. We first show that $$G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})\approx_{\epsilon(n/2)}U_{n/2+1}\|G_{n/2}(U_{n/2}),~~~~~(3)$$ and then that $$U_{n/2+1}\|G_{n/2}(U_{n/2})\approx_{\epsilon(n/2)}U_{n+2}.~~~~~(4)$$ $(2)$ follows by an application of the triangle inequality to $(3)$ and $(4)$. Since the arguments for $(3)$ and $(4)$ are similar, we prove just $(3)$.

Suppose for contradiction that $G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})$ is not $\epsilon(n/2)$-close to $U_{n/2+1}\|G_{n/2}(U_{n/2})$; then we show that $G_{n/2}(U_{n/2})$ is not $\epsilon(n/2)$-close to $U_{n/2}$ contradicting $(1)$. To be precise, given a distinguisher $\mathsf{D}$ for the former, we construct a distinguisher $\mathsf{D}'$ for the latter. The construction of $\mathsf{D}'$ is straightforward: given a challenge $y\in\{0,1\}^{n/2+1}$ (which is either $G_{n/2}(U_{n/2})$ or $U_{n/2+1}$), run $\mathsf{D}$ on $y\|G_{n/2}(U_{n/2})$ and return whatever $\mathsf{D}$ returns. If $y=G_{n/2}(U_{n/2})$ then $\mathsf{D}'$ presents $G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})$ to $\mathsf{D}$; otherwise, it presents $U_{n/2+1}\|G_{n/2}(U_{n/2})$. Thus, $\mathsf{D}$'s ability to distinguish the distributions in $(3)$ helps $\mathsf{D}'$ distinguish the distributions in $(1)$.

A similar argument can be made for odd values of $n$, and together you get that $G'$ is a PRG. The argument can be extended for $G'(s)=G(s_1)||G(s_2)||\ldots G(s_m)$ for $s=s_1||s_2||\ldots s_m$: one has to define a $m-1$ hybrid distributions, where the $i^{th}$ hybrid replaces the first $i$ calls of $G$ with a uniformly random string; i.e., assuming $m$ divides $n$, $$\underbrace{U_{n/m+1}\|\cdots\|U_{n/m+1}}_{i \text{ terms}}\|G_{n/m}(U_{n/m})\|\cdots\|G_{n/m}(U_{n/m}).$$ Also, this PRG is only $m\cdot\epsilon(n/m)$-secure.

$^*$A distribution $X=\{X_n\}$ is $\epsilon(n)$-computationally-close from another distribution $Y=\{Y_n\}$ if for every computationally-bounded distinguisher $\mathsf{D}$, $$\big|\Pr[\mathsf{D}(X_n)=1]-\Pr[\mathsf{D}(Y_n)=1]\big|\leq\epsilon(n).$$ In particular $X$ is computationally indistinguishable from $Y$ if $\epsilon(n)$ is negligible in $n$.

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