Minor edits in anonymity proof

We never write the anonymity game ending up correctly because we delayed writing the proof so long

1 files changed, 26 insertions, 25 deletions

diff --git a/games/games.tex b/games/games.tex
index f85a6d5..eb40ab0 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -648,44 +648,45 @@ Let $G \in \mathbb{E}$ be the generator of the Ed25519 curve (with Edwards coord
 
 
 \begin{theorem}
-  Assuming the existence of a Pseudo-Random Function Family (PRF), DDH, and a collision-resistant hash function, Taler satisfies \emph{Anonymity}.
+If Taler's refresh is instantiated with PRF, a key exchange satisfying DDH,
+  and a collision-resistant hash function,
+then Taler satisfies {anonymity}.
 \end{theorem}
 
 \begin{proof}
   We give a proof via a sequence of games $\mathbb{G}_0(b), \mathbb{G}_1(b),
   \mathbb{G}_2(b), \mathbb{G}_3(b)$, where $\mathbb{G}_0(b)$ is the original
-  anonymity game $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, \kappa, b)$.  Let
-  $\epsilon_{PRF}$ and $\epsilon_{DDH}$ be the advantage of an adversary for
-  the PRF game and DDH game respectively.
+  anonymity game $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, \kappa, b)$.  We show 
+  the adversary can distinguish between subsequent games with only negligible probability.
+  Let $\epsilon_{PRF}$ and $\epsilon_{DDH}$ be the advantage of an adversary
+  for the PRF game and DDH game respectively.
 
-  In $\mathbb{G}_1$ the game is modified by replacing the link oracle \ora{LinkAsExchange}
-  by another oracle that behaves the same as \ora{LinkAsExchange} only if the adversary
+  We define $\mathbb{G}_1$ by replacing the link oracle \ora{Link} with
+  another oracle that behaves the same as \ora{Link} only if the adversary
   responds to the customer with link data that has been observed in a previous refresh.
   If the link data is not recognized by the simulator, the customer is instead given
   a uniform random value as link data.
 
-  Recall that a coin obtained via refresh is only added to the wallet if the link
-  secret is constructed as $linkSecret = H(nonce, skOldCoin)$.  Link secrets that
-  do not pass this verification are discarded.
-
-  In order to distinguish $\mathbb{G}_0$ from $\mathbb{G}_1$, the adversary must
-  find a link secret that results in different behavior by the customer with regards
-  to accepting/rejecting it.  The behaviour with previously seen link secrets is identical.
-  In order to forge a distinguishing link secret, the adversary must either find a hash collision
-  or find the coin's private key. \comment{Should we fully carry out this reduction, including tightness bound, and if so where?}
+  In order to distinguish $\mathbb{G}_0$ from $\mathbb{G}_1$, our adversary
+  must fake a link secret that causes the oracle to return random data leading
+  to incorrect behavior by the customer.  We recall however that link secrets
+  were constructed as $(\V{nonce}, \V{linkSecret})$ where
+    $\V{linkSecret} = H(\V{nonce}, \V{skOldCoin})$,
+  with the customer rejecting link secrets that fail this test.
+  So our adversary must either find a hash collision or find the coin's private key. 
   
   In $\mathbb{G}_2$, the refresh oracle is modified so that the user responds
   with value drawn from a uniform random distribution for the the $\gamma$-th
-  commitment instead of using a Diffie-Hellman function.  Since $\gamma$ is
-  chosen by the adversary after seeing the commitments, the simulator first
-  makes a guess $\gamma^*$ and draws a uniform random value only for the
-  $\gamma^*$-th commitment.  If the $\gamma$ chosen by the adversary does not
-  match $\gamma^*$, the simulator rewinds \prt{A} to the point where the
-  refresh oracle was called.  Note that this succeeds with probability
-  $1/\kappa + \epsilon_{DDH}$.  Since $\kappa \ll \lambda$, the runtime
-  complexity of the simulator still says polynomial in $\lambda$.  Note that we
-  only replace the one commitment that will not be opened to the adversary
-  later. \comment{Tighness bound also missing}
+  commitment instead of using a Diffie-Hellman function.  We must handle the
+  fact that $\gamma$ is chosen by the adversary after seeing the commitments,
+  so the simulator first makes a guess $\gamma^*$ and
+    replaces only the $\gamma^*$-th commitment with a uniform random value.  
+  If the $\gamma$ chosen by the adversary does not match $\gamma^*$, then
+  the simulator rewinds \prt{A} to the point where the refresh oracle was called.  
+  We see this succeeds with probability $1/\kappa + \epsilon_{DDH}$.
+  Since $\kappa \ll \lambda$, the runtime complexity of the simulator still says
+  polynomial in $\lambda$.
+  Note that we only replace the one commitment that will not be opened to the adversary later. \comment{Tighness bound also missing}
 
   We now show that $\left| \Prb{\mathbb{G}_1 = 1} - \Prb{\mathbb{G}_2 = 1}
   \right| \le \epsilon_{DDH}$ by defining a distinguishing game $\mathbb{G}_{1