sync

1 files changed, 107 insertions, 93 deletions

diff --git a/games/games.tex b/games/games.tex
index 4d3c7b4..1da4672 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -71,20 +71,25 @@
 %   unforgeability
 % * can we formulate games so they don't refer to "failed refresh" directly?
 %   (since in some instantiations, refreshing can't fail)
+% * at least for fairness, we have to think more about Deposit, and
+%   whether there should be a separate oracle for it
 %
 
 \section{Model and Syntax}
 
-We consider a single exchange with many clients that can act as a merchant, a
-customer or both with no further distinction other than in naming.  We prefix
-public and secret keys with $pk$ and $sk$, following standard convention.  For
-succinctness, the public key of a coin always implicitly has a denomination (in
-form of the exchange's denomination public key) associated with it.
+We consider a single exchange with many clients.  The clients can act as a
+merchant, a customer or both, with no further distinction other than in naming.
+We prefix public and secret keys with $pk$ and $sk$, following standard
+convention.  For succinctness, the public key of a coin always implicitly has a
+denomination (in form of the exchange's denomination public key) associated
+with it.
 
 Every denomination has an associated financial value; this mapping is not
 chosen by the adversary but is a system parameter.  For efficient transactions,
 the denominations should be powers of two.  No change can be given for
-transactions of smaller values than the smallest denominations.
+transactions of smaller values than the smallest denominations.\footnote{
+Though multiple small remaining coins' values can be combined via refreshing,
+real-world implementations impose a refresh fee that makes this useless.  }
 
 We do not include fees taken by the exchange in our model.  Reserves are also
 omitted, conceptually every user has exactly one bank account that they
@@ -94,7 +99,7 @@ without any limit.
 Coins can be partially spent by specifying an arbitrary fraction $f \in
 \mathbb{R}$.
 
-The spending of multiple coins is modeled non-atomically, to spend multipe coins,
+The spending of multiple coins is modeled non-atomically: to spend multipe coins,
 they must be spent one-by-one.  The individual spend/deposit operations are correlated
 by a unique identifier for the transaction.  In practice this identifier is the hash
 of a nonce and the contract terms that merchant and customer agreed upon.
@@ -106,32 +111,35 @@ Our model tracks the following data for clients:
 \item $\V{wallet}[\V{pkClient}]$ contains sets of client coins records,
  which individually consist of the coin private keys and denomination signatures.
 \item $\V{acceptedContracts}[\V{pkClient}]$ contains the sets of contracts accepted by the user
-  during spending operations.
+  during spending operations, together with coins spent for it and their contribution.
 \end{itemize}
 The double-spending database of the exchange is modeled by $\V{deposited}[\V{pkCoin}]$ and
 $\V{refreshed}[\V{pkCoin}]$, which records the protocol transcript of deposit and refresh
 operations respectively.
 
-We say that a coin is \emph{unknown to the exchange} if it does
-not appear in the $\V{deposited}$ or $\V{refreshed}$ lists respectively.
-We say that a coin is being double spent if adding a transcript to
-either list would cause the total value of transcripts in both lists
-to exceed the value of the denomination.
-
+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
+$\V{refreshed}$ would cause the total value of transcripts in both lists to
+exceed the value of the denomination.
 
 
 \subsection{Algorithms}
 
-The Taler e-cash scheme is modely by the following probabilistic polynomial-time algorithms and protocols.
-The notation $\prt{E}(X_1,\dots,X_n)$ / $\prt{U}(X_1,\dots,X_n)$ stands for a party (Exchange or User) in an interactive
-protocol, with $X_1,\dots,X_n$ being the private inputs contributed by the party to the protocol.
+The Taler e-cash scheme is modely by the following probabilistic\footnote{Our
+Taler instantiations are not necessarily probabilistic, but we do not want to
+prohibit this for other instatiations} polynomial-time algorithms and
+protocols.  The notation $\prt{E}(X_1,\dots,X_n)$ / $\prt{U}(X_1,\dots,X_n)$
+stands for a party (Exchange or User) in an interactive protocol, with
+$X_1,\dots,X_n$ being the private inputs contributed by the party to the
+protocol.
 
 \begin{itemize}
   \item $\algo{EKeygen}(1^{\lambda}, 1^{\kappa}, \V{M})$:  Algorithm executed by the exchange
-    that outputs a key pair $(\V{skE}, \V{pkE}, \V{M})$, which contain both the
+    that outputs a key pair $(\V{skE}, \V{pkE})$, which contain both the
     signing key and the denomination keys for the exchange.  The financial
     value assigned to a denomination public key $d$ is determined by
-    $\V{M}(d)$.
+    $\V{M}(d)$.  Both $\lambda$ and $\kappa$ are security parameters.
 
   \item $\algo{CKeygen}(1^\lambda{})$:  Algorithm executed by merchants and customers
     that outputs a key pair $(\V{skU}, \V{pkU})$.
@@ -164,10 +172,14 @@ protocol, with $X_1,\dots,X_n$ being the private inputs contributed by the party
     we return the protocol transcript of the previous deposits and refreshes.
 
     Assuming otherwise, we mark $\V{pkCoin}$ as refreshed in $\V{refreshed}[\V{pkCoin}]$.
-    If the user \prt{U} plays honestly, they will store the unlinkable
-    change they obtain in their wallet $wallet[\V{pkU}]$.
+
+    If the user \prt{U} plays honestly, the unlinkable 
+    change they obtain will be stored in their wallet $wallet[\V{pkU}]$.
     If \prt{U} plays dishonestly, the coin's refresh transcript
     will be marked as spent without anything in return.
+    
+    Note that some instantiation (e.g. those using zero knowledge proofs) might
+    not leave \prt{U} the possibility to play dishonestly.
 
   \item \algo{Link}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin})):
     Interactive protocol between exchange and user.
@@ -195,6 +207,8 @@ We define the following oracles:
   \item $\ora{WithdrawAsExchange}(pkClient, pkDenom)$:  Do a withdraw from the perspective of a exchange.
     Effectively the adversary is an active man-in-the middle between the user and the ``real'' exchange.
 
+    The adversary obtains the protocol transcript, but does not gain access to the exchange's database directly.
+
   \item $\ora{RefreshAsUser}()$:  Do a withdraw from the perspective of a user, i.e. the adversary sends messages that the user would send.
 
     The adversary obtains the protocol transcript from the \algo{Refresh} protocol.
@@ -203,6 +217,8 @@ We define the following oracles:
 
     Effectively the adversary is an active man-in-the middle between the user and the ``real'' exchange.
 
+    The adversary obtains the protocol transcript, but does not gain access to the exchange's database directly.
+
   \item $\ora{LinkAsExchange}(pkClient)$:  Force a user to execute the
     link protocol, with the adversary playing the role of the exchange.
     Effectively the adversary is an active man-in-the middle between the user and the ``real'' exchange.
@@ -214,25 +230,35 @@ We define the following oracles:
     permission on success, or $\bot$ if the $skSpender$ does not have enough
     coins.
 
-    Adds $\V{contract}$ to $\V{contractHashes}[pkClient]$ and
+    Adds $\V{contract}$ to $\V{acceptedContracts}[pkClient]$ and
     initializes $\V{spent}[\V{pkCoin}]$.
 
   \item $\ora{Share}(\mathcal{T}^C, pkReceiver)$:
 
-    Shares a coin (identified by transcript $\mathcal{T}^C$ with the client identified
-    by $pkReceiver$.
+    Shares a coin (identified by withdraw/refresh/link transcript $\mathcal{T}^C$ with the client identified
+    by $pkReceiver$.  Used by the adversary in attempts to violate income transparency.
+
+    Note that this trivially violates anonymity (by sharing with corrupted client), thus the usage must
+    be restricted most other games.
 
   \item $\ora{CorruptClient}(pkClient)$:
 
     Used by the adversary to corrupt a client.
-    Marks the client as corrupted and gives the adversary the
-    client's private key, wallet and signed contract hashes. 
+    Marks the client as corrupted and gives the adversary permanent access to the
+    client'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,
+    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
+    model the situation where there might be multiple conflicting deposit
+    permissions generated via $\algo{Spend}$, but only a limited number can be
+    deposited (even though \ora{Spend} tracks spending, coin sharing can otherwise cause double spending).
 \end{itemize}
 
 
-Note that there is no oracle for deposit, since it does not give the adversary
-any new information and does not change the simulator's state in a way that
-affects the games.  The exchange does not need to be corrupted with an oracle,
+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.
@@ -264,25 +290,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.
 
-As refreshes consume only a single coin and return several,
-we define {\em refresh trees} with root given by a withdrawal operation
-and vertices given by refresh and spend operations, and with
-directed hyper-edges being coins that go from a the withdrawal or refresh
-that created them to all the spends or refreshes that consumed them.  
-In particular, our double spending protections ensure the value ascribed
-to each refresh or spend by a coin does not exceed the coin's denomination
-and that all coins's leaving a particular refresh have denominations that
-together do not exceed the refresh's value.
-
-As a result, this hyper-tree becomes simply a path when we only have one
-denomination, which simplifies both the games and proofs.  We views this
-simplification as instructive for financial games, so we only provide
-hints as to the value formulation.  Anonymity warrants our careful
-attention however, so we give a full proof there.
-
-We note that leaf edges might only have an origin operation with no
-destination operations in either formulation. 
-
 
 
 \section{Games}
@@ -316,13 +323,14 @@ We still characterize Income Transparency as a game, since it might be useful
 for other instantiations that provide more absolute guarantees.
 
 \subsection{Anonymity}
-Intuitively, an adversary $\prt{A}$ including an exchange and merchant
-win the anonymity game if they have any advantage in correlating spending
-operations with the withdrawal or refresh operations that created the coin.
+Intuitively, an adversary $\prt{A}$ (controlling the exchange and merchants) wins the
+anonymity game if they have a non-neglegible advantage in correlating spending operations
+with the withdrawal or refresh operations that created a coin used in the
+spending operation.
 
 Let \oraSet{Anon} stand for access to the oracles
  \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
- \ora{RefreshAsExchange}, \ora{LinkAsExchange}, \ora{Share}, \ora{CorruptClient}.  Let $b$ be the bit that will
+ \ora{RefreshAsExchange}, \ora{LinkAsExchange}, \ora{CorruptClient}, \ora{Deposit}.  Let $b$ be the bit that will
  determine the mapping between users and spend operation, which the adversary must guess.
 
 \bigskip
@@ -342,7 +350,7 @@ Let \oraSet{Anon} stand for access to the oracles
   \item Return 0 if \\
     $\V{pkU}_1$ or $\V{pkU}_2$ are not distinct uncorrupted registered users or \\
     $\V{contract}_1 = \V{contract}_2$
-  \item Select unspent unrefreshed coins $\V{pkC}_0$ and $\V{pkC}_1$
+  \item Select fresh coins $\V{pkC}_0$ and $\V{pkC}_1$
     from the wallets of $\V{pkU}_0, \V{pkU}_1$, respectively.
     \footnote{In principle, we might anonymously refresh coins before
     or concurrently with spending them, but if our adversary directs a
@@ -350,55 +358,47 @@ Let \oraSet{Anon} stand for access to the oracles
     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 customer's identity to the adversary.
+    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 merchant.  Return 0 if $r_1$ or $r_2$ indicate a failure.
+    Deposit these two coins with the adversary controlled exchange.  Return 0 if $r_1$ or $r_2$ 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 Let $\mathcal{U} \supseteq \{ \V{pkU}_{1}, \V{pkU}_{2} \}$ consist
-    of the users who know, or could learn through linking, either
-    $\V{skC}_0$ or $\V{skC}_1$, aka these coin's {\em ownership set}.
-    Return 0 if $\cal U$ contains either any user corrupted by $\cal A$
-    or any user who ran the linking protocol.
   \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 any anonymous e-cash schemes because it does not
-cover unlinkability between payments that the same user made.
-Instead of the two users $\V{pkU}_0$ and $\V{pkU}_1$,
-our adversary $\cal A$, and hence the oracles it calls, must supply
- a withdrawal (or refresh) event handle.  
-
-In our case, planchets work well for this, but they do not exist in all scheme.
-We prove the stronger anonymity game that replaces lines 2,3, and 5
-with these two lines.
+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 clients 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.] $(P_0, P_1, \V{contract}_0, \V{contract}_1) \leftarrow {\cal A}^{\oraSet{Anon}}()$ \\
-    Our adversary invokes oracles to create users, as well as
-    create and manipulate their coins.
-    It singles out two coin creating invocations, either withdrawals
-    or refreshes, by returning the planchets $\mathcal{T}_{C_0}$ and $\mathcal{T}_{C_1}$. 
-    It returns two two contracts $\V{contract}_0$ and $\V{contract}_1$ as well.
+  \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.]
-    We demand that valid unspent unrefreshed coins $\V{pkC}_0$ and $\V{pkC}_1$
-    have been created from the coins identified by $\mathcal{T}_{C_0}$ and $\mathcal{T}_{C_1}$ respectively.
-    Also let $\V{pkU}_1$ and $\V{pkU}_2$ denote the registered users
-    who obtained these respective coins coins through withdrawal or
-    refresh, but note $\V{pkU}_1$ and $\V{pkU}_2$ need not be distinct.
-    Return 0 either if any of these do not exist, including
-    if $\V{pkC}_0$ or $\V{pkC}_1$ were spent.
-  % \item[5.] 
+    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{CKeygen}(\lambda)$, $\V{skU}_0, \V{pku}_0 \leftarrow \algo{CKeygen}(\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}
 
 
-\paragraph{Intuition:}  Users are anonymous if there is no adversary that can win this game,
-since then two users can spend money, but the adversary is not able to say who purchased what.
-
-
 \begin{mdframed}
 There are two kinds of games found for anonymity in the
 literature, one is based in indistinguishability (between two users or coins) and
@@ -410,16 +410,23 @@ the adversary can exhaust wallets to see who spent.  We can avoid this, since we
 and can rely on those.
 
 The ``\dots AsUser'' oracles are not given to the adversary, since they play as the exchange and thus
-allowing them to talk to themselves does not make sense.
+allowing them to talk to themselves does not make sense / does not give them more power.
 \end{mdframed}
 
 \subsection{Fairness}
+\begin{mdframed}
+  Fairness is a very overloaded term in crypto, can we come up with something better?
+  It's already used for (a) protocols where either none or all parties obtain a result and
+  (b) as fair e-cash, which is e-cash with selective tracability for e.g. law enforcement.
+\end{mdframed}
 
 Intuitively, the adversary wins if a non-corrupted user is unable to obtain a
 proof-of-spending or unlinkable change for a coin.  This can happen, for
 example, when the merchant is able to spend a coin in a way not anticipated by
 the customer, keep the coin in a state that neither gives the customer a
-receipt nor allows the customer to refresh it.  
+receipt nor allows the customer to refresh it.
+
+In practice, this
 
 The game also covers the case where the exchange pretends the customer did a
 bad refresh.
@@ -429,7 +436,7 @@ the reader may replace $C_n$ by the leaf coins in the refresh tree.
 
 Let \oraSet{Fair} stand for access to the oracles
  \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
- \ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient}.
+ \ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient}, \ora{Deposit}.
 
 \bigskip
 \noindent $\mathit{Exp}_{\cal A}^{fair}(1^\lambda, \kappa)$:
@@ -508,7 +515,7 @@ Let \oraSet{Income} stand for access to the oracles
   \item Let $L$ be the sum of unspent value for valid coins in $C_1, \dots\, C_\ell$, after
     accounting for the previous spending step.
   \item Let $w'$ be the number of coins withdrawn by corrupted clients.
-    Our adversary wins if $L - w > 0$.
+    Our adversary wins if $L - w' > 0$.
     (Intuitively, the expenses for getting untaxed money are less or equal to the gained
     untaxed money)
 \end{enumerate}
@@ -521,6 +528,13 @@ Then the expected loss $E[w-s]$ for obtaining untaxed coins of value $L$ is
 bounded by $E[w - s] \ge \kappa \cdot E[L - w']$, independent from whether the
 adversary wins the game or not.
 
+% In the proof, we look at fixed values of L and w'.
+% The value of L-w' prime can't come from withdraw directly,
+% it can't come from forging coins (or we could win the unforgeability game)
+% It can't come from linking
+% If it is to come from refresh, either we must find a hash collision
+% or guess 
+
 \begin{mdframed}
   Older formulations were talking about ``value lost during refresh'', but this concept does
   not necessarily exist for other instantiations (and the game was more complicated with it).