2
$\begingroup$

The definition of pseudo randomness that leads to pseudo random function talks about indistingishability of a key-ed function and a random function.

i.e. The key-ed function family $\{F_k\}$ is PRF if $|Pr[D^{F_k}(1^n)=1] - Pr[D^{f}(1^n)=1]|$ is negligible for $k\leftarrow\mathcal{K}$ and $f\leftarrow\mathcal{F}$.

Informally the output of both the function $F_k$ and $f$ at polynomial many points follows same distribution. Since $f$ is a random choice of random function family, $\{f(x)\}$ is uniformly random.

So can I use output $F_k(x)$ as the key to same PRF in next iteration? i.e. say $k1=F_k(x)$ and I can compute $k2=F_{k1}(x)$. But will $\{F_{k1}\}$ still be a PRF?

$\endgroup$
1
  • $\begingroup$ The pseudorandomness of $F^2_k(x) = F(F(k,x),x)$ (or in general of $F^{\mathrm{poly}(n)}_k(x)$) looks like something that could be proved with the hybrid method... It's probably not very useful, however. $\endgroup$
    – fkraiem
    Aug 1, 2015 at 12:43

1 Answer 1

1
$\begingroup$

Well, yes, but you cannot use the key $k_1$ for anything else because knowledge of $k_1$ would mean that an attacker can simply calculate $k_2$. If an attacker can find a direct relation between parts of the output then the function is of course not pseudo random anymore. So although it is possible it seems pretty useless to me.

Even if you would not directly use $k_1$ as output you would need to prove that you use it in such a way that security is not compromised. In general you should try to not reuse keys for different purposes.

$\endgroup$
3
  • $\begingroup$ hi, thanks for the response. Could you please tell me if you have ever come across any encryption scheme construction that uses PRF in this way (ie creates key for next iteration)? I am having some confusion as k1, k2 etc are not exactly uniformly random element. I am unable to formulate a proof due to this confusion. :( $\endgroup$
    – mxant
    Jul 2, 2015 at 14:38
  • $\begingroup$ Not really - usually the output is a hash over the next state, or the output is securely mixed into the state. $\endgroup$
    – Maarten Bodewes
    Jul 2, 2015 at 14:54
  • $\begingroup$ Thanks otus, see you in the >10K group soon (don't forget to signal when you overtake me :) ) $\endgroup$
    – Maarten Bodewes
    Aug 25, 2015 at 9:48

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.