Hybrid Sequence:
We use a short sequence of hybrids starting with $\lib{prf-real}$.
First, we apply the security of the PRF to replace $F$ with a lazy random dictionary. The standard three-hop maneuver is not shown.
Next, we apply \definitionref{uhf.def.dict} to replace a dictionary indexed by $U(\key_1, X)$ with a dictionary indexed directly by $X$. The standard three-hop maneuver is not shown. The result is precisely $\lib{prf-rand}$, which completes the proof.
$\lib{prf-real}$
$\key_1 \gets \bits^\secpar$
$\key_2 \gets \bits^\secpar$
$\prfquery$($X$):
// return $F^*\bigl( (\key_1, \key_2), X \bigr)$
$H := U(\key_1, X)$
return
$F(\key_2,H)$
$\prftable[H]$
$\prftable[X]$