Hybrid Sequence:
The starting point of the hybrid proof is $\lib{kem-1cca-real+ro}$.
We can inline all of the calls to $\ro$. The call to $\ro$ that determines $\ptxt^*$ is the first, so its result is always sampled uniformly.
Now we can perform the renaming suggested above. Whatever was previously stored in $\rotable[A]$ is now stored in $\mathcal{D}[A^e]$. Thus, $\rotable[\ctxt^d]$ becomes $\mathcal{D}[\ctxt]$.
We can carve out an exception for the challenge ciphertext $\ctxt^*$, so that $\mathcal{D}[\ctxt^*]$ is never used. Additionally, now the value $R^*$ is used only to compute $\ctxt^*$. Since $R^*$ is uniform, and exponentiation-by-$e$ is a 1-to-1 function, the resulting distribution on $\ctxt^*$ is uniform.\FORMATTINGHACK{\pagebreak}
The special case in $\ro(A)$ is triggered when the calling program provides an $e$-th root of $\ctxt^*$. Since $d$ is no longer used anywhere in the library, we can apply the RSA assumption to argue that this special case never happens.
We can remove the unreachable if-statement and also revert the previous change, replacing $\mathcal{D}[A^e]$ with $\rotable[A]$. The result is $\lib{kem-1cca-rand+ro}$.
$\lib{kem-1cca-real+ro}$
$(\nmod,e, {}$
$d) := \RSA.\KeyGen()$
$\ctxt^*) \gets \rsachallenge()$
$d) := \RSA.\KeyGen()$
$\pk := (\nmod,e)$
// $(\ctxt^*,\ptxt^*) := \Encaps(\pk)$:
$R^* \gets \Z_\nmod$
$\ctxt^* $
${}:= (R^*)^e \pct \nmod$
${}\gets \Z_\nmod$
$\ptxt^* $
${}:= {}$
$\ro(R^*)$
$\rotable[R^*] \gets \bits^\secpar$
$\mathcal{D}[\ctxt^*] \gets \bits^\secpar$
${}\gets \bits^\secpar$
$\ccaonepk$( ):
return $\pk$
$\ccaoneenc$( ):
return $(\ctxt^*, \ptxt^*)$
$\ccaonedec$($\ctxt$):
// $\Decaps(\ctxt)$:
return
$\ro(\ctxt^d \pct \nmod)$
$\rotable[\ctxt^d \pct \nmod]$
$\mathcal{D}[\ctxt]$
$\ro(\ctxt^d \pct \nmod)$
$\ro$($A$):
if
$\rotable[A]$ undefined:
$\mathcal{D}[A^e \pct \nmod]$ undefined:
$\rotable[A] \gets \bits^\secpar$
return
$\rotable[A]$
$\mathcal{D}[A^e \pct \nmod]$
$\rotable[A]$
$\link$
$\lib{rsa-real}$
$(\nmod,e, d) := \RSA.\KeyGen()$
$Y \gets \Z_\nmod$
$\rsachallenge$( ):
return $(\nmod,e,Y)$
$\rsacheck$($X$):
return $Y \equiv_\nmod X^e$
$\lib{rsa-ideal}$
$(\nmod,e, d) := \RSA.\KeyGen()$
$Y \gets \Z_\nmod$
$\rsachallenge$( ):
return $(\nmod,e,Y)$
$\rsacheck$($X$):
return $\myfalse$