Hybrid Sequence:
The starting point of the proof is $\lib{pk-1cca-real+ro}$.
We can inline the calls to $\ro$ made in $\ccaoneenc$ and $\ccaonedec$. We can also remember the decryption of the challenge ciphertext $\ctxt^*$, as $\mathcal{D}[\ctxt^*]$, so that $\ccaonedec$ does not need to recompute it. The reason we introduce a dictionary $\mathcal{D}[\cdot]$, even though the library assigns only one position in it, is because later hybrids will use more of it.
Suppose that in some call to $\ccaonedec(\ctxt)$, we see that $\rotable[\ptxt\|S]$ is undefined; the adversary has not called the random oracle on this input. The library will return an error unless the adversary has somehow successfully anticipated the result of $\Sigma.\Enc$, with \emph{fresh randomness} $\rotable[\ptxt\|S]$. Following the reasoning described earlier, such a prediction is successful only with negligible probability at most $1/2^\secpar$, when $\Sigma$ has unique randomness. It makes a negligible difference to simply always return an error in this case.
Now $\ccaonedec()$ returns an error \emph{unless} the ciphertext has the form $\Enc(\pk,X; \ro(X))$, \emph{and} the adversary has already called $\ro(X)$. So instead of decrypting ciphertexts the usual way in $\ccaonedec()$, we can compute the associated ciphertext at the time $\ro(X)$ is called, and store its decryption for later use in $\ccaonedec()$. The change has no effect on the calling program.\FORMATTINGHACK{\pagebreak}
Modify $\ccaoneenc()$ so that, instead of using $\ro(\ptxt\|S^*)$ as randomness for $\Sigma.\Enc$, it uses a freshly sampled value $R$ unrelated to the random oracle. This changes the library's overall behavior \emph{only} in the bad event that the adversary also queries $\ro(\ptxt\|S^*)$. We can mark the change with a bad event, and later argue that it has negligible probability.\FORMATTINGHACK{\pagebreak}
Now $\ccaoneenc()$ uses randomness for $\Sigma.\Enc$ that is used for nothing else. This is exactly equivalent to calling $\Sigma.\Enc()$ the usual way (\ie, as a randomized algorithm, without externally fixing its randomness). Furthermore, the secret key of $\Sigma$ is no longer used anywhere in the library. Hence, we can apply the CPA security of $\Sigma$ to replace ciphertext $\ctxt^*$ with a uniformly chosen one. The three-hop maneuver is not shown.\FORMATTINGHACK{\pagebreak}
Now $S^*$ in $\ccaoneenc()$ is used only to trigger the bad event, and does not affect what the adversary sees. We can therefore defer the choice of $S^*$ to the end of time.
Finally, we can undo a previous change, moving decryption logic from $\ro()$ back to $\ccaonedec()$. Then the only value in $\mathcal{D}[\cdot]$ that is used is $\mathcal{D}[\ctxt^*]$, which \FORMATTINGHACK{\pagebreak}we rename simply to $\ptxt^*$. As a result, we obtain $\lib{pk-1cca-rand+ro}$, plus some end-of-time logic relating to a bad event.
$\lib{pk-1cca-real+ro}$
$(\pk,\sk) := {}$
$\Sigma.\KeyGen()$
$\Sigma.\KeyGen$
$\Sigma.\KeyGen()$
$\ccaonepk$( ):
return $\pk$
$\ccaoneenc$($\ptxt$):
if $\ctxt^*$ undefined:
// $\ctxt^* := \Enc(\pk,\ptxt)$
$S^* \gets \bits^\secpar$
$R $
${}:= {}$
$\ro(\ptxt \| S^*)$
$\rotable[\ptxt \| S^*]$
${}\gets \bits^\secpar$
$\ctxt^* $
${}:= \Sigma.\Enc(\pk, \ptxt \| S^*; R) $
${}\gets \Sigma.\C\bigr( |\ptxt| + \secpar \bigr)$
return $\ctxt^*$
$\ccaonedec$($\ctxt$):
// return
$\Dec(\sk,\ctxt)$
$\Dec(\ctxt)$:
$\ptxt \| S := \Sigma.\Dec(\sk,\ctxt)$
$R := \ro(\ptxt \| S)$
if $\ctxt \ne \Sigma.\Enc(\pk,\ptxt\|S; $
$R)$:
$\rotable[\ptxt\|S])$:
$R)$:
return $\myerr$
return $\ptxt$
$\ro$($A$):
if $\rotable[A]$ undefined:
$\rotable[A] \gets \bits^\secpar$
return $\rotable[A]$