Hybrid Sequence:
The starting point for the proof is $\lib{rsa*-real}$.
First, we rewrite the check for membership in $\mathcal{Y}$ as a for-loop involving explicit comparisons.
Suppose we initially choose one value $Y^*$ and later define each $Y \in \mathcal{Y}$ as $Y = Y^* \cdot \Delta^e$. If each $\Delta$ is uniformly distributed, then the $Y$'s are also uniformly distributed. In $\rsacheck^*$, we can then replace each $Y$ with its equivalent expression $Y^* \cdot \Delta^e$. Instead of keeping track of a collection of $Y$-values, it is then enough to keep track of their $\Delta$ values.
Now we can rearrange the equation $X^e \equiv_\nmod Y^* \cdot \Delta^e$ to obtain the equivalent equation $(X \Delta^{-1})^e \equiv_\nmod Y^*$.
Now the library has a single target value $Y^*$ and repeatedly checks whether a certain expression ($X \cdot \Delta^{-1}$) is its $e$-th root. We can therefore apply the RSA assumption, with $Y^*$ playing the role of its single target value. The standard three-hop maneuver is not shown.
As we argued above, each $Y$ value is sampled uniformly. Now that the $\Delta$ values are not needed, we can simply sample the $Y$ values uniformly in a more direct way, as they were previously. After simplifying its code, the result is $\lib{rsa*-ideal}$, which completes the proof.\FORMATTINGHACK{\pagebreak}
$\lib{rsa*-real}$
$(\nmod,e,d) := \RSA.\KeyGen()$
$\rsapk^*$( ):
return $(\nmod,e)$
$\rsachallenge^*$( ):
$Y $
${}\gets \Z_\nmod$
${}:= Y^* \cdot \Delta^e \pct \nmod$
${}\gets \Z_\nmod$
$\mathcal{Y} := \mathcal{Y} \cup \{Y\}$
return $Y$
$\rsacheck^*$($X$):
if
$X^e $
${}\pct \nmod \in \mathcal{Y}$: return $\mytrue$
$\equiv_\nmod $
$Y$: return $\mytrue$
$Y^* \cdot \Delta^e$: return $\mytrue$
$(X \cdot \Delta^{-1})^e \equiv_\nmod Y^*$: return $\mytrue$
$\myfalse$: return $\mytrue$
else: return $\myfalse$