4
$\begingroup$

Let $G(s)=F_{0^n}(s)$ ($ 0^n $ is a fixed key given to the PRF F) for any $n∈\mathbb{N}$ and $s∈\{0,1\}^n$.

Is G, defined via PRF as above, necessarily a pseudorandom generator?

I presume that it is a PRG, since we don't really know what is the seed s. But the fact that $ F_{0^n}() $ is known, makes me doubt myself.

I don't seek for a proof, just an intuition or a hint (i do understand how to prove such claims, i just don't get the "catch" in this specific case).

$\endgroup$
  • $\begingroup$ You mean a function $F$ that starts by generating $n$ bits set to zero? And there is no repetition of $F$ involved? Either I don't get the question or I'm completely in the dark about what is meant. Anything generating a number of bits biased to a certain number, say 0, is certainly not an PR(B)G (B for bit instead of number). $\endgroup$ – Maarten Bodewes Mar 29 '17 at 14:04
  • $\begingroup$ @MaartenBodewes F is a PRF, with a given fixed key $0^n$. I am having some hard time figuring out whether the function G, as defined above via F, is a PRG. $\endgroup$ – Alex Goft Mar 29 '17 at 14:08
  • $\begingroup$ Oh, OK, that makes more sense. $\endgroup$ – Maarten Bodewes Mar 29 '17 at 14:09
  • $\begingroup$ @MaartenBodewes Thank you for your answer. Can you please give me a hint to what a distinguisher for G needs to do? I guess that it has the ability to compute $ F_{0^n}() $, but i am having hard time understanding what inputs to give it, since its input supposed to be the seed used by G which is, of course, not known. $\endgroup$ – Alex Goft Mar 29 '17 at 14:16
4
$\begingroup$

Consider a PRF $F$ which on $n$-bit keys maps $n$-bit inputs to $2n$-bit outputs. Consider $F'$ where $F'_k(x) = F_k(x)$ if $k \ne 0^n$ and $0^{2n}$ otherwise.

$\endgroup$
  • $\begingroup$ When you are having trouble proving that something is true, seriously consider the possibility that it may be false. ;) $\endgroup$ – fkraiem Mar 29 '17 at 18:18
  • $\begingroup$ What does it supposed to show? $\endgroup$ – Alex Goft Mar 31 '17 at 18:15
  • 1
    $\begingroup$ Well, $F'$ is a PRF, but the resulting $G'$ is not a PRG... $\endgroup$ – fkraiem Mar 31 '17 at 23:43
  • $\begingroup$ of course! could you please suggest a way to build a distinguisher D for F, given a distinguisher D' for F' (trying to prove that F' is PRF - assumed by contradiction that it is not a PRF). $\endgroup$ – Alex Goft Apr 2 '17 at 14:29
  • 1
    $\begingroup$ If $D'$ works on $F'$, it will also work on $F$ "as is", without any modification. This is because the PRF experiments for $F$ and $F'$ are identical except with negligible probability, so any distinguisher will have a negligible difference in its success probability between the two experiments. See also this. $\endgroup$ – fkraiem Apr 3 '17 at 3:10
3
$\begingroup$

$G$ defined like this is not necessarily a PRG. The reason is not that the distinguisher can compute $F_{0^n}(x)$ for any $x$ that it wants, as this is also true for a PRG. The reason is that a PRF is a family of functions $\cal F$, and the assumption is that a randomly chosen function from the family is indistinguishable from a truly random function. So, as @fkraiem answered, take any real PRF $\cal F$ (assuming one such family exists), and replace $F_{0^n}\in \cal F$ with a constant function.

This may seem odd, but for a randomly chosen function, they probability that $F_{0^n}$ is chosen is negligible, so $\cal F$ is still a PRF (try to prove this first). Of course, then $F_{0^n}(x)$ for random $x$ is easily distinguishable from a random string.

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