$F_k$ is a PRF , $k\in\{ 0,1\}^n$ , is $H_k(x) = F_{k_1}(x)||F_{k_2}(F_{k_1}(x))$ a PRF?
when $k=k_1||k_2$ , $k_1,k_2\in\{ 0,1\}^n$ and $k\in\{ 0,1\}^{2n}$ are random strings ,
im trying to prove it using the hybrid argument such that :

  1. $H_0$ be $F_{k_1}(x)||F_{k_2}(F_{k_1}(x))$
  2. $H_1$ be $f_1(x)||F_{k_2}(f_1(x))$ when $f_1$ is a random function
  3. $H_2$ be $f_1(x)||f_2(f_1(x))$ when $f_1 , f_2$ are a random functions.

$H_0$ is $H_k(x)$ and the underlying assumption between $H_0$ and $H_1$ is $F_k$ .
$H_2$ is equal to a random function and the underlying assumption between $H_1$ and $H_2$ is also $F_k$ .
im not very sure about it so i’m asking for opinions and suggestions or maybe a counter example for not being a PRF.

  • $\begingroup$ What happens when $F_{k_1}(x_i)$ collides with $F_{k_1}(x_j)$? $\endgroup$ – Samuel Neves Jul 14 '17 at 14:00
  • $\begingroup$ @SamuelNeves , what does that matter if $k_1$ is random ? $\endgroup$ – odu9 Jul 14 '17 at 15:03
  • $\begingroup$ @SamuelNeves i think this matters only if $k_1$ was fixed , then you can modify the PRF for this $k_1$ and then distinguish H from random. $\endgroup$ – odu9 Jul 14 '17 at 17:02
  • $\begingroup$ Are you saying that $k_1$ and $k_2$ are distinct for every query? How are they derived? $\endgroup$ – Samuel Neves Jul 15 '17 at 2:22
  • $\begingroup$ @SamuelNeves no they are not , they are randomly picked at first , lets assume that $F_{k1}(x_i)$ collide with $F_{k1}(x_j)$ , but for which $k_1$? for every k? , since $k_1$ is picked at first at random you never know if they collide. $\endgroup$ – odu9 Jul 15 '17 at 8:35

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.