2
$\begingroup$

This exercise comes from Coursera's "Cryptography" course.

Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| ... ||F_{1…1}(x)$ a PRG?

$F$ is a PRF with $n$ bit key, input, and output length. I know the answer is “NO it isn't!”, but I can't understand why.

Is that because on any input $x$, the keys for every $F$ in the concatenation sequence are fixed, which implies that the $F$ functions are not randomly chosen over $2^{-n}$? Could this be a possible answer?

|improve this question|||||
$\endgroup$
  • $\begingroup$ Hint: $G(x)$ is much larger than $x$. $\endgroup$ – fkraiem Jul 31 '15 at 0:43
  • 1
    $\begingroup$ Actually, maybe not. Can you clarify how the sequence of keys is constructed? For example, if we take $n = 3$, is it $000, 001, 010, 011, 100, 101, 110, 111$ or $000, 001, 011, 111$, or something else? $\endgroup$ – fkraiem Jul 31 '15 at 0:46
  • $\begingroup$ Yes, and $G(x)$ has to be much larger than $x$ otherwise it's worthless. $\endgroup$ – pa5h1nh0 Jul 31 '15 at 0:47
  • $\begingroup$ See my other comment. $\endgroup$ – fkraiem Jul 31 '15 at 0:57
  • 1
    $\begingroup$ Well then my previous hint stands, but I'll make it more precise. The length of $G(x)$ is exponential in the length of $x$. Remember that a distinguisher which attempts to distinguish $G(x)$ from a uniform string runs in time polynomial in the length of $G(x)$. $\endgroup$ – fkraiem Jul 31 '15 at 1:08
2
$\begingroup$

@fkraiem's answer is basically correct, but it only says that $G$ does not match the "syntax" of a PRG. But this is not entirely satisfactory for understanding what's really wrong with $G$ as a PRG.

In addition, $G$ may not be pseudorandom. For example, it could be the case that $F_{00\cdots 0}(x) = 0$ for every $x$, i.e., the all-zeros key is a "weak" key for $F$. This would not contradict the fact that $F$ is a PRF, and this can be proved formally. But now notice that the first bit of $G(x)$ is zero for every seed $x$, which means that $G$ is clearly not a pseudorandom generator.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Ahm, you're saying "it could be the case that $F_{00...0}(x)=0$ for every $x$". I would reply that this is highly unlikely, it would occur with negligible probability. However, my focus is on every chosen $F$, from the definition for a function $F$ to be pseudorandom: if for all PPT distinguishers $D$, there exists a negligible function $negl$ such that $|Pr[D^{F_k()}(1^n)=1] - Pr[D^{f()}(1^n)=1]| \leq negl(n)$, where $k\leftarrow\{0,1\}^n$ is chosen uniformly at random, and $f$ is chosen uniformly at random from the set of all the functions mapping $n$-bit string to $n$-bit strings. $\endgroup$ – pa5h1nh0 Jul 31 '15 at 13:05
  • $\begingroup$ In this case all the keys are fixed $\Rightarrow$ $F$ is not pseudorandom, and the concatenation of all such $F$s results in a not random looking string. So $G$ is not pseudorandom. Correct me if I'm wrong. $\endgroup$ – pa5h1nh0 Jul 31 '15 at 13:08
  • 1
    $\begingroup$ One can design a "pathological" PRF $F$ having the property I described, which nonetheless satisfies the definition of a PRF. A PRF can have a small number of weak keys (e.g., the all-zeros key) because the probability of getting such a key when choosing uniformly at random is negligible. $\endgroup$ – Chris Peikert Jul 31 '15 at 13:12
  • 1
    $\begingroup$ When $F$ is a secure PRF having the "pathological" property I described, $G$ is not a PRG because it is not pseudorandom -- the first bit of $G(x)$ is 0 no matter what the seed $x$ is. That's all there is to it. $\endgroup$ – Chris Peikert Jul 31 '15 at 13:23
  • 1
    $\begingroup$ I'm not dismissing it, but a natural reaction to the exponential-length criticism is just to truncate the definition of $G$. But that doesn't really help, because there is more fundamental problem with $G$'s design. $\endgroup$ – Chris Peikert Jul 31 '15 at 18:27
2
$\begingroup$

Because the key-, input- and output-length of $F$ are equal, if the length of the seed $x$ is $n$, there are $2^n$ keys and so $G$ must compute $F$ $2^n$ times and output a string of length $n\cdot 2^n$. Hence, $G$ runs in time exponential in $n$, which means it can't be a pseudorandom generator because a pseudorandom generator is a deterministic polynomial-time algorithm.

(In addition, since a distinguisher runs in time polynomial in the length of $G(x)$, it runs in time exponential in the length of $x$, and brute force through all possible seeds is allowed.)

|improve this answer|||||
$\endgroup$
1
$\begingroup$

It's not even necessary to consider a pathological/contrived PRF as in @ChrisPeikert's answer. Just consider $F$ = AES. Recall that some PRFs (including AES) are also pseudorandom permutations. Since this is a homework problem, I'll just give a hint to think about how the existence of an $F^{-1}$ helps to easily distinguish this output from random. This attack works even if the output is truncated to not be exponentially long.

|improve this answer|||||
$\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.