# How to prove security of scheme constructed by Hash then PRP

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}.$$

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