sync

1 files changed, 25 insertions, 59 deletions

diff --git a/games/games.tex b/games/games.tex
index 7eadd91..f63e5dd 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -129,7 +129,7 @@ operations respectively.
 
 We say that a coin is \emph{fresh} if it appears in neither the $\V{deposited}$
 or $\V{refreshed}$ lists nor in $\V{acceptedContracts}$.  We say that a coin is
-being $\V{double-spent}$ if adding a transcript to $\V{deposited}$ or
+being $\V{overspent}$ if adding a transcript to $\V{deposited}$ or
 $\V{refreshed}$ would cause the total value of transcripts in both lists to
 exceed the value of the denomination.
 
@@ -173,7 +173,7 @@ protocol.
 
     In the deposit permission, there are coin public keys $\V{pkCoin}$
     corresponding to $\V{skCoin}$.
-    If $\V{pkCoin}$ is being double spent, we return the protocol transcript
+    If $\V{pkCoin}$ is being overspent, we return the protocol transcript
     of the previous deposits and refreshes.  
 
     On success, we mark $\V{pkCoin}$ spent in $\V{deposited}[\V{pkCoin}]$ and
@@ -182,7 +182,7 @@ protocol.
   \item \algo{Refresh}(\prt{E}(\V{skE}, \V{pkU}), \prt{U}(\V{skU}, \V{pkE}, \V{skCoin})):
     Interactive protocol between exchange and user.
 
-    If $\V{pkCoin}$ (derived from \V{skCoin}) is being double spent, then
+    If $\V{pkCoin}$ (derived from \V{skCoin}) is being overspent, then
     we return the protocol transcript of the previous deposits and refreshes.
 
     Assuming otherwise, we mark $\V{pkCoin}$ as refreshed in $\V{refreshed}[\V{pkCoin}]$.
@@ -216,11 +216,6 @@ We define the following oracles:
 
     The adversary obtains the protocol transcript, but does not gain access to the exchange's database directly.
 
-    If the adversary determines the exchange's private key during the
-    setup, invoking this oracle can be seen as the adversary plaing the
-    exchange.  If the adversary calls \ora{Withdraw} with a corrupted
-    user, the adversary plays as the user.
-
     % FIXME: talk about share
 
   \item $\ora{Refresh}()$:  Do a withdraw.
@@ -257,7 +252,7 @@ We define the following oracles:
     it permanent access to the user's private key, wallet and accepted contracts.
 
   \item $\ora{Deposit}(depositPermission)$:
-    Give a deposit permission to the exchange.  If the deposit permission is valid and the coin is not double-spent,
+    Give a deposit permission to the exchange.  If the deposit permission is valid and the coin is not overspent,
     the exchange adds it to $spent[pkU]$ for the user $U$ identified in the deposit permission.
 
     This oracle does not give the adversary new information, but is used to
@@ -271,10 +266,16 @@ We define the following oracles:
 % transcripts, and we don't have any notion of forward security
 
 
-The exchange does not need to be corrupted with an oracle,
-a corrupted exchange is modelled by giving the adversary the appropriate
-oracles ($\ora{\dots{}AsExchange}$) and the exchange private key from the
-exchange key generation.
+The exchange does not need to be corrupted with an oracle. A corrupted exchange
+is modelled by giving the adversary the appropriate oracles and the exchange
+private key from the exchange key generation.
+
+If the adversary determines the exchange's private key during the setup,
+invoking \ora{Withdraw}, \ora{Refresh} or \ora{Link} can be seen as the
+adversary plaing the exchange.  Since the adversary is an active
+man-in-the-middle in these oracles, they can drop messages to the simulated
+exchange and make up their own response.  If the adversary calls these oracles
+with a corrupted user, the adversary plays as the user.
 
 \begin{mdframed}
 The difference between algorithms and interactive protocols
@@ -303,8 +304,6 @@ and hence require a refresh operations.  If this refresh operations also
 provided partial spending, which seems logical, then refreshes can be run after
 spends, which invalidates assumptions in anonymity games.
 
-
-
 \section{Games}
 
 We have two seperate security parameters in Taler
@@ -358,58 +357,25 @@ Let \oraSet{Anon} stand for access to the oracles
     known by the customers.}
   \item $(\V{pkU}_0, \V{pkU}_1, \V{contract}_0, \V{contract}_1) \leftarrow {\prt{A}}^{\oraSet{Anon}}()$ \\
     The adversary creates two users and selects two contract identifiers.
-  \item Return 0 if \\
-    $\V{pkU}_1$ or $\V{pkU}_2$ are not distinct uncorrupted registered users or \\
-    $\V{contract}_1 = \V{contract}_2$
-    \comment{0 and 1, NOT 1 and 2}
-  \item Select fresh coins $\V{pkC}_0$ and $\V{pkC}_1$
-    from the wallets of $\V{pkU}_0, \V{pkU}_1$, respectively.
+  \item Return 0 if $\V{pkU}_0$ or $\V{pkU}_1$ are not uncorrupted registered users.
+  \item Select distinct fresh coins $\V{pkC}_0$ and $\V{pkC}_1$
+    from the wallets of $\V{pkU}_0$ and $\V{pkU}_1$, respectively.
     \footnote{In principle, we might anonymously refresh coins before
     or concurrently with spending them, but if our adversary directs a
     non-anonymous refresh then they can mark coins with it}
-    Return 0 if either $\V{pkU}_0$ or $\V{pkU}_1$ has no unspent unrefreshed coin.
-  \item $\V{dp_1} \leftarrow \algo{Spend}(\V{contract}_b, \V{pkU}_0, \V{pkC}_0, \V{pkM})$, \\
-        $\V{dp_2} \leftarrow \algo{Spend}(\V{contract}_{(1-b)}, \V{pkU}_1, \V{pkC}_1, \V{pkM})$ \\
-    Spend these two coins without revealing the mapping between users and coins.
-  \item $r_1 \leftarrow \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), {\prt{A}}(dp_1))$, \\
-    $r_2 \leftarrow \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), {\prt{A}}(dp_2))$ \\
-    Deposit these two coins with the adversary controlled exchange.  Return 0 if $r_1$ or $r_2$ indicate a failure.
+    Return 0 if either $\V{pkU}_0$ or $\V{pkU}_1$ has insufficient unspent unrefreshed coins.
+  \item $\V{dp_0} \leftarrow \algo{Spend}(\V{contract}_0, \V{pkU}_b, \V{pkC}_b, \V{pkM})$, \\
+      $\V{dp_1} \leftarrow \algo{Spend}(\V{contract}_1, \V{pkU}_{1-b}, \V{pkC}_{1-b}, \V{pkM})$ \\
+      Spend these two coins without revealing the mapping between users and coins.
+  \item $r_0 \leftarrow \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), {\prt{A}}(dp_0))$, \\
+    $r_1 \leftarrow \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), {\prt{A}}(dp_1))$ \\
+    Deposit these two coins with the adversary controlled exchange.  Return 0 if $r_0$ or $r_1$ indicate a failure.
   \item $b' \leftarrow {\cal A}^{\oraSet{Anon}}()$ \\
     The adversary makes one guess $b' \in \{0,1\}$ for $b$, which determines the mapping between users and contracts.
   \item if $b = b'$ return 1, otherwise return 0
 \end{enumerate}
 
-We have stated this game in terms of the anonymity of users to match existing
-e-cash literature, but actually any user based formulation is insufficient for
-practical anonymous e-cash schemes because it does not cover unlinkability
-between payments that the same user made.  It can be argued that a real-world
-user \emph{could} be mapped to multiple users in the model, but this would
-imply that partially spent coins can't be used and must be discarded.
-
-Thus the user-based formulation allows instantiations that formally fulfill the
-``anonymity'' property, but either makes payment between the same user linkable
-or introduces the impracticality of being unable to use change if no fresh
-coins that perfectly match the amount being spent are available.
-
-We prove the stronger (and arguably simpler) anonymity game that replaces lines 2--5
-with the following:
-\begin{enumerate}
-  \setlength\itemsep{0em}
-  \item[2.] $(\mathcal{T}_{C_0}, \mathcal{T}_{C_1}, \V{contract}_0, \V{contract}_1) \leftarrow {\cal A}^{\oraSet{Anon}}()$ \\
-    The adversary (having access to the oracles in \oraSet{Anon}) reveals two coin transcripts (refresh or withdraw)
-    and two contract identifiers.
-  \item[3.]
-    Return 0 if \\
-    $\V{pkU}_1$ or $\V{pkU}_2$ are not distinct coin transcripts refering to distinct fresh coins \\
-    $\V{contract}_1 = \V{contract}_2$
-  \item[4.] (step empty / not necessary)
-  \item[5.]
-      $\V{skU}_0, \V{pku}_0 \leftarrow \algo{UserKeygen}(\lambda)$, $\V{skU}_0, \V{pku}_0 \leftarrow \algo{UserKeygen}(\lambda)$\\
-        $\V{dp_1} \leftarrow \algo{Spend}(\V{contract}_b, \V{pkU}_0, \V{pkC}_0, \V{pkM})$, \\
-        $\V{dp_2} \leftarrow \algo{Spend}(\V{contract}_{(1-b)}, \V{pkU}_1, \V{pkC}_1, \V{pkM})$ \\
-    Spend the two coins, with fresh users given to the adversary.
-\end{enumerate}
-
+We do not assume distinct users because ... FIXME
 
 \begin{mdframed}
 There are two kinds of games found for anonymity in the