2
$\begingroup$

First of all sorry for the bad title, this is an exercise I'm struggling with:
Let $F_k$ be a pseudorandom keyed function (abbreviated to PRF) with key, input and output of length $n$.
Define the following generator $G$ with expansion factor $n^2$:
1) Let $s \in (0,1)^n$ be random seed.
2) Set $x_0 = 0^n$
3) For $i=1$ to $n$, set $x_i = F_s(x_{i-1})$
4) Output $x_1 \cdot x_2 \cdot ...\cdot x_n$
I need to show that $G$ is pseudorandom generator (PRG).
The reduction is pretty obvious, I build a distinguisher $D_F$ for $F$ by using a distinguisher $D_G$ for $G$ in the following way:
Given oracle access $O(.)$ to some function, $D_F$ queries the oracle to compute $X=x_1 \cdot x_2 \cdot ...\cdot x_n$ as defined above, gives it to $D_G$, and returns whatever $D_G$ returns.
A hint is given, and says that in the analysis one should take into account the possibilty that $f(x_i)=f(x_j), i \neq j$ where $f$ is a truly random function.
Why is that matters? If the aforementioned event occurs, does it causes $X$ not to be a truly random string for $D_G$?

$\endgroup$
  • $\begingroup$ If you try to write the proof formally, the issue should become apparent (that's what formal proofs are for). $\endgroup$ – fkraiem Feb 14 '17 at 15:46
  • 1
    $\begingroup$ Formal proofs are not my specialty, but I vaguely see the following: A generator built per the structure of $G$ will never output $x_1\cdot x_2\cdot...\cdot x_n$ such that there exists $i$ and $j$ with $0\le i<j<n$ and $x_i=x_j$ and $x_{i+1}\ne x_{j+1}$ [Note: $i=0$ is intentionally allowed, with the convention that $x_0=0^n$]. A $D_G$ working on that basis alone will have some tiny advantage, but your technique won't turn it into a $D_F$ giving any advantage. That's a (tiny) leak to plug. $\endgroup$ – fgrieu Feb 14 '17 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.