Hybrid Sequence:
The starting point is $\lib{crhf-real+ro}$.
A random oracle samples its outputs with replacement, but this behavior is indistinguishable from a function that samples without replacement. The simple three-hop maneuver involving \lemmaref{comp.lem.birthday-lib} has been omitted:
After making this change, distinct inputs are guaranteed to have distinct random-oracle outputs. Thus, $\ro(X)==\ro(X')$ \emph{if and only if} $X==X'$.
Finally, $\ro$ can be returned to its original behavior. The result is $\lib{crhf-idea+ro}$, completing the proof.
$\lib{crhf-real+ro}$
$\crhfcmp$($X,X'$):
return
$\ro(X) == \ro(X')$
$X == X'$
$\ro$($A$):
if $\rotable[A]$ undefined:
$\rotable[A] \gets \bits^\secpar$
$$
${} \setminus \mathcal{Y}$
$$
return $\rotable[A]$