Suppose there is a scheme where a message is first hashed and then sent to a PRP. If the hash is done using an $\epsilon$-bounded universal hash function and the PRP $K\times \{0,1\}^n\rightarrow\{0,1\}^n$ is a $(q,\delta)$-PRP.

The objective is to show this scheme $K\times K_n\times \{0,1\}^*\rightarrow\{0,1\}^n$ is actually a $$\biggl(q,\delta + \frac{{q\choose 2}\epsilon}{2^n}+{{q\choose 2}\epsilon}\biggr)$$ PRF.

I am able to show this scheme is a $(q,\delta+X)$-PRF, but still not finding a way how to show X to be $$\frac{{q\choose 2}\epsilon}{2^n}+{{q\choose 2}\epsilon}.$$

  • $\begingroup$ What have you tried so far? How did you show that this scheme is a $(q, \delta + X)$-PRF? $\endgroup$ – Squeamish Ossifrage Apr 9 '19 at 4:01
  • $\begingroup$ Also, are you sure you meant to have a factor of $\epsilon$ in the $\binom q 2 \epsilon/2^n$ term? $\endgroup$ – Squeamish Ossifrage Apr 9 '19 at 4:09

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.