Hybrid Sequence:
The starting point is $\lib{prf-real+ro}$.
$\prfquery$ calls $\ro$, and we can inline the logic of $\ro$ into $\prfquery$.
$\ro$ is implemented by a lazy random dictionary $H$. We can partition $H$ into two separate dictionaries, based on whether the input starts with the prefix $\key$. Values of the form $\rotable[\key\|X]$ are now stored in $\prftable[X]$. Calls to $\ro$ made within $\prfquery$ \emph{always} include the $\key$ prefix, but the adversary's direct calls to $\ro$ may or may not.\FORMATTINGHACK{\pagebreak}
Modify $\ro$ to act as if its inputs never have a prefix $\key$. The library's behavior will change only in the bad event that the calling program calls $\ro$ on an input that begins with $\key$. We must later show that this bad event has negligible probability.
The value $\key$ is used \emph{only} to decide whether to trigger the bad event, so we can move the choice of $\key$ and all the bad event logic to the end of time without affecting its probability.\FORMATTINGHACK{\pagebreak}
$\lib{prf-real+ro}$
$\key \gets \bits^\secpar$
$\prfquery$($X$):
// $F(\key,X) = \ro(\key\|X)$
return
$\ro(\key \| X)$
$\rotable[\key\|X]$
$\prftable[X]$
$\ro$($A$):
if $\rotable[A]$ undefined:
$\rotable[A] \gets \bits^n$
return $\rotable[A]$