Hybrid Sequence:
The starting point is $\lib{prf-real}$.
Since $F$ is a secure PRF, we may replace it with a lazy random dictionary. The standard three-hop maneuver is not shown.
The library uses a dictionary data structure, and one way to implement a dictionary is as a simple list of pairs $(Y,Z)$. To read from the dictionary at position $Y$, simply scan the list to find a record with the correct $Y$. To modify the dictionary, append a new record to the list. This is not a very efficient way to implement a dictionary, but it is correct nonetheless. In this proof it is convenient to store not only $Y$ and $Z$ but also $X$ in each record.
Each record $(X,Y,Z)$ in $\mathcal{D}$ satisfies $Y = H^*(\key_1,X)$. So instead of comparing $Y'$ and $Y$, the library can compare $H^*(\key_1,X')$ and $H^*(\key_1,X)$ with the same effect.
Now the library implements a dictionary in terms of hash comparisons, so we can apply the CRHF security of $H^*$ in a three-hop maneuver.
The $Y$-values, and therefore $\key_1$, are no longer being used. They can be removed.
The resulting library is an (inefficient) implementation of a lazy random dictionary, but this time indexed by $X$ values rather than their hashes. In other words, it is $\lib{prf-rand}$.\FORMATTINGHACK{\pagebreak}
$\lib{prf-real}$
$\key_1 $
$\| \key_2 \gets \bits^{2\secpar}$
${}\gets \bits^\secpar$
${}:= \crhfgetsalt()$
${}\gets \bits^\secpar$
$\prfquery$($X$):
// $F'(\key_1\|\key_2, X)$:
$Y := H^*(\key_1, X)$
$Z $
${}:= {}$
$F(\key_2, Y)$
$\prftable[Y]$
${}\gets \bits^n$
return
$Z$
$\prftable[X]$
$\link$
$\lib{crhf-real}$
$\salt \gets \bits^\secpar$
$\crhfgetsalt$( ):
return $\salt$
$\crhfcmp$($X, X'$):
return $H^*(\salt,X) == H^*(\salt,X')$
$\lib{crhf-ideal}$
$\salt \gets \bits^\secpar$
$\crhfgetsalt$( ):
return $\salt$
$\crhfcmp$($X, X'$):
return $X == X'$