Deal with one-more forgery adersary managing multiple denominations.

1 files changed, 15 insertions, 5 deletions

diff --git a/games/games.tex b/games/games.tex
index 22ced86..3df3a95 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -758,7 +758,8 @@ Taler satisfies {Unforgeability}.
 \begin{proof}
 We consider a probabilistic polynomially time adversary $\cal A$ with
 a non-negligible advantage for winning the unforgeability game
- $\mathit{Exp}_{\cal A}^{forge}(1^\lambda, \kappa)$ against Taler.
+ $\mathit{Exp}_{\cal A}^{forge}(1^\lambda, \kappa)$ against Taler
+ instantiated with $d$ denominations.
 %
 % We describe an RSA Chosen-Target Inversion Problem (RSA-CTI)
 %  \cite[Definition 3]{RSA-FDH-KTIvCTI} % or \cite[Definition 6.1]{OneMoreInversion}.
@@ -775,14 +776,23 @@ from the operation of $\cal A$. % Also let $C_{m+1}, ..., C_n$ denote
 % might refines our usage of ROM or something.
 We now know $\cal A$ made at most $m$ withdrawal and refresh oracle
 queries to obtain the $m+1$ RSA signatures %, aka inversions,
- on the $Y_i := \textrm{FDH}_{\V{pkDenom}_i}C_i)$ with $0 \le i \le m$,
- where $\V{pkDenom}_i$ if the denomination key of $C_i$. 
+ on the $Y_i := \textrm{FDH}_{\V{pkDenom}_i}(C_i)$ with $0 \le i \le m$,
+ where $\V{pkDenom}_i$ is the denomination key of $C_i$. 
 
 It follows that $\cal A$ has produced one-more forgery in the sense
  of \cite[Definition 11]{RSA-FDH-KTIvCTI},
  also \cite[Definition 4 \& 5, pp. 369]{Pointcheval_n_Stern},
- for at least one $\V{pkDenom_i} \in \V{pkE}$.
-We conclude that RSA-KTI cannot be hard by \cite[Theorem 12]{RSA-FDH-KTIvCTI},
+ for at least one $\V{pkDenom} \in \V{pkE}$.
+
+We now create an adversary $\cal A^{\textrm{rsa-omf}}$ for the
+ blind FDH-RSA signature one-more forgery game \cite[Definition 11]{RSA-FDH-KTIvCTI}
+by assigning this adversary's target RSA key randomly to one of our $d$ denomination,
+and inventing random new RSA keys for the remaining $d-1$ denominations.
+As this assignment is random, $\cal A^{\textrm{rsa-omf}}$ wins the one-more forgery
+game with $1/d$th the rate $\cal A$ wins the Taler unforgeability game.
+
+We therefore conclude that RSA-KTI cannot be hard itself
+ by \cite[Theorem 12]{RSA-FDH-KTIvCTI},
  and our random oracle assumption.
 %
 % So $\cal A$ wins this RSA-CTI game with its random sampling to produce