Hybrid Sequence:
The starting point is $\lib{kem-1cca-real+ro}$
Inline first call to $\ro$; the result is always chosen uniformly since it is the first call.
Replace every expression of the form $\rotable[\ctxt^*, \pk^{r^*}]$ with $\ptxt^*$. Similarly, introduce a new associative array $U[\cdot]$ and replace every expression of the form $\rotable[A,A^{\sk}]$ with $U[A]$.
Inline the call to $\ro$ made in $\ccaonedec$. Note that $\ccaonedec$ always calls $\ro$ with an input of the form $(A,A^{\sk})$, and this includes the case that $A = \ctxt^*$, where we have $(A,A^{\sk}) = (\ctxt^*,\pk^{r^*})$.
Apply gap CDH: $\sk$ becomes $x$; $\pk$ becomes $g^x$; $r^*$ becomes $y$; and $\ctxt^*$ becomes $g^y$.
Remove unreachable case in $\ro$
Rewrite expressions of the form $U[A]$ as $U[A,A^{\sk}]$, and rewrite $\ccaonedec$ in terms of a call to $\ro$ as before. The result is $\lib{kem-1cca-rand+ro}$, which completes the proof.
$\lib{kem-1cca-real+ro}$
// $\KeyGen$:
$\sk \gets \Z_n$
$\pk := g^{\sk}$
// $(\ctxt^*, \ptxt^*) := \Encaps(\pk)$:
$r^* \gets \Z_n$
$\ctxt^* := g^{r^*}$
$\ptxt^* $
${}:= \ro( \ctxt^*, \pk^{r^*} )$
${}\gets \bits^n$
$\ccaonepk$( ):
return $\pk$
$\ccaoneenc$( ):
return $(\ctxt^*, \ptxt^*)$
$\ccaonedec$($\ctxt$):
// $\Decaps(\sk,\ctxt)$:
return
$\ro( \ctxt, \ctxt^{\sk} )$
$U[\ctxt]$
$\ro(\ctxt, \ctxt^{\sk})$
// random oracle expecting two group elements:
$\ro$($A,B$):
if $\rotable[A,B]$ undefined:
$\rotable[A,B] \gets \bits^n$
return $\rotable[A,B]$
$\link$
$\lib{gapcdh-real}$
$x \gets \Z_n$
$y \gets \Z_n$
$Y := g^y$
gapcdh.get( ):
return $(g^x, g^y)$
gapcdh.ddh($S,T$):
return $S^x == T$
gapcdh.test($Z$):
return $Z == g^{xy}$
$\lib{gapcdh-fake}$
$x \gets \Z_n$
$Y \gets \G$
gapcdh.get( ):
return $(g^x, Y)$
gapcdh.ddh($S,T$):
return $S^x == T$
gapcdh.test($Z$):
return $\myfalse$