Hybrid Sequence:
The starting point is $\lib{sig-real+ro}$:
The library can remember signatures produced by $\sigsign$; they don't need to be verified later in $\sigver$.\FORMATTINGHACK{\pagebreak}
Inline the call made to $\ro$ inside $\sigsign$.
Make the if-statement in $\sigsign$ unconditional. This changes the library's behavior only in the bad event that $\rotable[\ptxt\|R]$ is already defined. However, $R$ is sampled uniformly each time. If the adversary makes at most $q$ calls to the library's subroutines, then there are most $q$ entries in $\rotable[\cdot]$, so at most $q$ ``bad'' values of $R$ that can be chosen. Overall, across at most $q$ calls to $\sigsign$, the bad event has negligible probability at most $q^2/2^\secpar$.
Instead of uniformly sampling $\rotable[\ptxt\|R]$ and setting $S := \rotable[\ptxt\|R]^d$, we can uniformly sample $S$ and set $\rotable[\ptxt\|R] := S^e$. The two methods induce the same joint distribution over $(S, \rotable[\ptxt\|R])$.
When $\sigver$ checks whether $Y = S^e$, it always uses a $Y$ that was chosen uniformly in $\ro$, not chosen with a known $e$-th root in $\sigsign$ (the if-statement in $\sigver$ catches these cases). \FORMATTINGHACK{\pagebreak}If we let $\mathcal{Y}$ denote the set of all $\ro$-outputs, then the condition $Y = S^e$ \emph{implies} $S^e \in \mathcal{Y}$. Hence, it has no effect on the library to add the additional check $S^e \in \mathcal{Y}$ in $\sigver$.
The library no longer uses the private RSA exponent $d$; it maintains a set $\mathcal{Y}$ of uniformly sampled values; it later checks whether the adversary has provided an $e$-th root of \emph{any} of these values. Hence, we can apply \claimref{sig.clm.rsa-self-reduce}:
After removing the now-unreachable if-statement, and reversing several earlier changes, the result is $\lib{sig-fake+ro}$. This completes the proof.
$\lib{sig-real+ro}$
$(\nmod,e,d) := \RSA.\KeyGen()$
$\sigpk$( ):
return
$(\nmod,e)$
$\rsapk^*()$
$(\nmod,e)$
$\sigsign$($\ptxt$):
// $\Sign(\sk,\ptxt)$:
$R \gets \bits^\secpar$
$S := {}$
$\ro(\ptxt\|R)^d \pct \nmod $
$\rotable[\ptxt\|R]^d \pct \nmod $
return $(R,S)$
$\sigver$($\ptxt,(R,S)$):
// $\Verify(\pk,\ptxt,(R,S))$:
$Y := \ro(\ptxt\|R)$
return
$Y == S^e \pct \nmod$
$\myfalse$
$\ro$($A$):
if $\rotable[A]$ undefined:
$\rotable[A] $
${}\gets \Z_\nmod$
${}:= \rsachallenge^*()$
${}\gets \Z_\nmod$
return $\rotable[A]$
$\link$
$\lib{rsa*-real}$
$(\nmod,e,d) := \RSA.\KeyGen()$
$\rsapk^*$( ):
return $(\nmod,e)$
$\rsachallenge^*$( ):
$Y \gets \Z_\nmod$
$\mathcal{Y} := \mathcal{Y} \cup \{Y\}$
return $Y$
$\rsacheck^*$($X$):
if $X^e \pct \nmod \in \mathcal{Y}$: return $\mytrue$
else: return $\myfalse$
$\lib{rsa*-ideal}$
$(\nmod,e,d) := \RSA.\KeyGen()$
$\rsapk^*$( ):
return $(\nmod,e)$
$\rsachallenge^*$( ):
$Y \gets \Z_\nmod$
return $Y$
$\rsacheck^*$($X$):
return $\myfalse$