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?

  • $\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 '15 at 12:43

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.

  • $\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 '15 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 '15 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 '15 at 9:48

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.