Fix end of anonumity proof

1 files changed, 27 insertions, 26 deletions

diff --git a/games/games.tex b/games/games.tex
index a277255..4ec9e94 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -647,14 +647,9 @@ Let $G \in \mathbb{E}$ be the generator of the Ed25519 curve (with Edwards coord
 \subsection{Anonymity}
 
 \begin{theorem}
-If Taler's refresh is instantiated with a PRF, a key exchange satisfying DDH,
+If Taler's refresh is instantiated with PRFs, a key exchange satisfying DDH,
   and a collision-resistant hash function,
-then Taler satisfies the {anonymity} property of its blind signature scheme.
-
-In particular if Taler uses RSA then such the adversary can violate the PRF assumption
-on the has functions used to produce the message hashes and blinding factors.
-Also if Taler uses blind BLS signatures then such an adversary can violate the
-computational Diffie-Hellman assumption.
+then Taler satisfies {anonymity}.
 \end{theorem}
 
 \begin{proof}
@@ -710,29 +705,35 @@ computational Diffie-Hellman assumption.
       use the matching tuple.}
   \end{enumerate}
   
-  We observe that depending on the coin flip $b$, we either simulate $\mathbb{G}_1$ or $\mathbb{G}_2$ perfectly for
-  adversary $\cal A$ against $\mathbb{G}_1$.  At the same time $b$ determines whether \prt{A} receives $(g^a, g^b, g^{ab})$ or $(g^a, g^b, g^c)$.
-  Thus $\left| \Prb{\mathbb{G}_1 = 1} - \Prb{\mathbb{G}_2 = 1} \right| = \epsilon_{DDH}$ is exactly the DDH advantage of $\mathbb{G}_{1 \sim 2}$.
-
-  In the hop between $\mathbb{G}_2$ and $\mathbb{G}_3$ we replace the PRFs with a random uniform function. \comment{Does this need a proof?
-  Do we need to do this for the next step?  If so, we just use exactly the same technique as in the last hop with PRF instead of DDH.}
-
-  The coins obtained from refresh and from withdraw have now the same distribution in $\mathbb{G}_3$, as desired.
-  
-  
-  Since the blinding is perfect, the adversary has no information to associate a withdraw/refresh transcript
-  with a spend transcript.  Thus the success probability for $\mathbb{G}_3$ is $1/2$.
-
-  We conclude that that the success probability for $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, \kappa, b)$ is at most $1/2 + \epsilon_{DDH} + \epsilon_{PRF}$.
-
+  We observe that depending on the coin flip $b$,
+  we either simulate $\mathbb{G}_1$ or $\mathbb{G}_2$ perfectly for
+  our adversary $\cal A$ against $\mathbb{G}_1$.  At the same time $b$
+  determines whether \prt{A} receives $(g^a, g^b, g^{ab})$ or $(g^a, g^b, g^c)$.
+  Thus $\left| \Prb{\mathbb{G}_1 = 1} - \Prb{\mathbb{G}_2 = 1} \right| = \epsilon_{DDH}$
+  is exactly the DDH advantage of $\mathbb{G}_{1 \sim 2}$.  
+  At this point, the planchets used in refresh and withdraw differ only
+  in the source of their blinding factor.
+
+  In the hop between $\mathbb{G}_2$ and $\mathbb{G}_3$
+  we replace the FD-PRF that produces the blinding factor with
+  a uniformly random function, also on the full domain of the RSA modulus.
+  At this point, any advantage of our adversary amounts to an advantage in
+  distinguishing our random blinding factor from
+    $\textrm{FDH}_N(C_1) / \textrm{FDH}(C_2) \mod N$,
+  which violates the FD-PRF assumption inherent in our FDH assumption. 
+
+  We conclude the success probability for $\mathbb{G}_3$ is $1/2$ and hence .
+  the success probability for $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, \kappa, b)$
+    is at most $1/2 + \epsilon_{DDH} + \epsilon_{PRF}$, as desired.
   \comment{The DDH game we use here is non-standard (stream of values to decide on instead of one, so maybe we need to use the number of refresh oracle invocations
   as a factor in front of $\epsilon_{DDH}$?}
-
-  This concludes the proof, since we observe in $\mathbb{G}_3$ all blinding factors and coin private keys are independent and uniformly random.
-  Thus the blinding is information-theoretically secure in $\mathbb{G}_3$.
-
 \end{proof}
 
+We observe that if Taler were instantiated with blind BLS signatures,
+ instead of blind RSA signatures, then
+our adversary must violate the computational Diffie-Hellman assumption
+as well as the PRF assumption to compromise $\mathbb{G}_2$. 
+
 
 \begin{mdframed}
   Note that the order of the hops does matter, since it's important that we feed the PRF