I'm studying the Goldreich-Goldwasser-Micali construction from pseudo-random generators to pseudo-random functions. In this specific construction, assume $G:\{0,1\}^n\rightarrow \{0,1\}^{2n}$ is a PRG, mapping $x$ to $G(x)=(G_0(x),G_1(x))$. Then the PRF in this construction is given by $$F_k(x)=G_{x_n}\circ\cdots\circ G_{x_1}(k),$$ with a random key $k$ in the same length as $x$. The proof is a hybrid argument, by replacing $G_{x_j}\circ\cdots\circ G_{x_1}(k)$ with a truly random function $\{0,1\}^j\rightarrow\{0,1\}^n$.

Now I wonder what if we swap the positions of $x$ and $k$ in this construction, that is to define $$F'_k(x)=G_{k_n}\circ\cdots\circ G_{k_1}(x).$$ Intuitively one cannot use similar hybrid techniques like above to prove its pseudo-randomness. However I didn't figure out a counter example, as I wanted to keep some information of $x$ within $G(x)$, but the possiblility that this information is maintained after $n$-round of iterations is always negligible. For instance, if we keep the first bit of $G(x)$ being $x_1$, with only $2^{-n}$ probability we can still see the bit $x_1$ in $F_k'(x)$, when $k$ is random.

Are there any methods to prove or disprove the construction $F'_k(x)$ is pseudo-random? Thanks in advance.


1 Answer 1


$F'_k(x)$ is not necessarily pseudo-random.

Changing one output does not affect PRGness, so if there is a PRG
that stretches by a factor of 2 then there is a PRG that stretches
by a factor of 2 and sends all-zero strings to all-zero strings.
For all $n$ and $k$ and $x$, if $G$ is such a PRG then $F'_k(x)$ is the string of $n$ zeros.
For all $n$, if $\: n\neq 0 \:$ then there are other strings with that length.
Therefore $F'_k(x)$ is not necessarily pseudo-random.

(Of course, this doesn't prove that your construction can't be pseudo-random.)


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.