notation changes

1 files changed, 73 insertions, 63 deletions

diff --git a/games/games.tex b/games/games.tex
index 601d7cd..79db455 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -50,6 +50,8 @@
 % probability with square brackets of the right size
 \newcommand{\Prb}[1]{\ensuremath{\Pr\left [#1 \right ]}}
 
+\newcommand{\comment}[1]{~\\ {\small \textcolor{blue}{({#1})}}}
+
 \maketitle
 
 
@@ -75,9 +77,13 @@
 %   whether there should be a separate oracle for it
 %
 
+
+% TODO:
+% - note about double spending vs overspending
+
 \section{Model and Syntax}
 
-We consider a single exchange with many clients.  The clients can act as a
+We consider a single exchange with many users.  The users 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
@@ -106,19 +112,18 @@ they must be spent one-by-one.  The individual spend/deposit operations are corr
 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.
 
-Our model tracks the following data for clients:
+Our model tracks the following data for users:
 \begin{itemize}
-\item $\V{valueWithdrawn}[\V{pkClient}]$ contains of the values
- withdrawn by each client $\V{pkClient}$,
-\item $\V{wallet}[\V{pkClient}]$ contains sets of client coins records,
+\item $\V{valueWithdrawn}[\V{pkUser}]$ contains of the values
+ withdrawn by each user $\V{pkUser}$,
+\item $\V{wallet}[\V{pkUser}]$ contains sets of the users 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
+\item $\V{acceptedContracts}[\V{pkUser}]$ contains the sets of contracts accepted by the user
   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
+The overspending 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.
-\comment{TODO: REPLACE "double-spending" by "overspending"}
 
 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
@@ -138,28 +143,31 @@ $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
+  \item $\algo{ExchangeKeygen}(1^{\lambda}, 1^{\kappa}, \V{M})$:  Algorithm executed by the exchange
     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)$.  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})$.
+  \item $\algo{UserKeygen}(1^\lambda{})$:  Algorithm executed by merchants and customers
+    that outputs a key pair $(\V{skU}, \V{pkU})$.  We refer to this key pair by $(\V{skM}, \V{skM})$ when
+    the user acts as a merchant.
     \comment{pkDenom needs to appear here}
 
-  \item \algo{Withdraw}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{pkDenom})):
+  \item \algo{Withdraw}(\prt{E}(\V{skE}, \V{pkU}), \prt{U}(\V{skU}, \V{pkE}, \V{pkDenom})):
     Interactive protocol between exchange and user to withdraw a single coin of
     a particular denomination.
     \comment{A planchet like pkCoin needs to be an argument here, no?  How do we handle the signature though?  Also skDenom.  }
 
-  \item \algo{Spend}(contract, \V{f}, \V{pkClient}, \V{skCoin}, pkReceiver):
-    Algorithm to produce and sign a deposit permission for a particular contract.
-    The fraction $0 < \V{f} \le 1$ determines the fraction of the coin's value that will
-    be spent.
+    % pkDenom needs to appear in ExchangeKeygen
+
+  \item \algo{Spend}(contract, \V{f}, \V{pkUser}, \V{skCoin}, pkReceiver):
+    Algorithm to produce and sign a deposit permission \V{depositPermission}
+    for a particular contract.  The fraction $0 < \V{f} \le 1$ determines the
+    fraction of the coin's value that will be spent.
 
   \item \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{M}(\V{skU}, \V{depositPermission})):
-    Interactive protocol between the exchange and a client, who acts as a merchant.
+    Interactive protocol between the exchange and a user, who acts as a merchant.
 
     In the deposit permission, there are coin public keys $\V{pkCoin}$
     corresponding to $\V{skCoin}$.
@@ -169,7 +177,7 @@ protocol.
     On success, we mark $\V{pkCoin}$ spent in $\V{deposited}[\V{pkCoin}]$ and
     return the exchange's signature over the request.
 
-  \item \algo{Refresh}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin})):
+  \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
@@ -179,13 +187,13 @@ protocol.
 
     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
+    If \prt{U} is caught playing 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})):
+  \item \algo{Link}(\prt{E}(\V{skE}, \V{pkU}), \prt{U}(\V{skU}, \V{pkE}, \V{skCoin})):
     Interactive protocol between exchange and user.
     If \V{skCoin} is the secret key of a coin that was refreshed, then 
     we recompute the refreshed coin and add it to to the user's wallet $wallet[\V{pkU}]$.
@@ -198,19 +206,19 @@ protocol.
 We define the following oracles:
 
 \begin{itemize}
-  \item $\ora{AddClient}()$:
-    Creates a new client, sets $valueWithdrawn$ for the client to $0$, sets $wallet[pkClient] := \{\}$.
-    Returns the public key of the client.
+  \item $\ora{AddUser}()$:
+    Creates a new user, sets $valueWithdrawn$ for the user to $0$, sets $wallet[pkUser] := \{\}$.
+    Returns the public key of the user,
 
-  \item $\ora{WithdrawAsUser}(pkClient, pkDenom)$:  Do a withdraw from the perspective of a user.  The adversary
-    controls the user, the simulator the exchange.
+  \item $\ora{WithdrawAsUser}(pkUser, pkDenom)$:  Do a withdraw from the perspective of a user.  The adversary
+    controls the user, and the simulator the exchange.
 
     Increments $\V{valueWithdrawn}[\V{pkU}]$ appropriately,
     adds the resulting coin to the wallet $\V{wallet}[\V{pkU}]$.
 
     The adversary obtains the protocol transcript.
 
-  \item $\ora{WithdrawAsExchange}(pkClient, pkDenom)$:  Do a withdraw from the perspective of a exchange.
+  \item $\ora{WithdrawAsExchange}(pkUser, 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.
@@ -225,11 +233,11 @@ We define the following oracles:
 
     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
+  \item $\ora{LinkAsExchange}(pkUser)$:  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.
 
-  \item $\ora{LinkAsUser}(pkClient, pkCoin)$:  Force a user to execute the ???
+  \item $\ora{LinkAsUser}(pkUser, pkCoin)$:  Force a user to execute the ???
     \comment{executes what?}
 
   \item $\ora{Spend}(contractHash, pkSpender, \mathcal{T}^C, pkReceiver)$:
@@ -239,21 +247,21 @@ We define the following oracles:
     permission on success, or $\bot$ if the $skSpender$ does not have enough
     coins.
 
-    Adds $\V{contract}$ to $\V{acceptedContracts}[pkClient]$ and
+    Adds $\V{contract}$ to $\V{acceptedContracts}[pkUser]$ and
     initializes $\V{spent}[\V{pkCoin}]$.
 
   \item $\ora{Share}(\mathcal{T}^C, pkReceiver)$:
 
-    Shares a coin (identified by withdraw/refresh/link transcript $\mathcal{T}^C$ with the client identified
+    Shares a coin (identified by withdraw/refresh/link transcript $\mathcal{T}^C$ with the user 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
+    Note that this trivially violates anonymity (by sharing with corrupted user), thus the usage must
     be restricted most other games.
     \comment{ENGLISH to / from ?}
 
-  \item $\ora{AddCorruptClient}(pkClient)$:
-    Used by the adversary to add a corrupted client, giving
-    it permanent access to the client's private key, wallet and accepted contracts.
+  \item $\ora{AddCorruptUser}(pkUser)$:
+    Used by the adversary to add a corrupted user, giving
+    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,
@@ -262,9 +270,13 @@ We define the following oracles:
     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).
+    deposited (even though \ora{Spend} tracks spending, coin sharing can otherwise cause overspending).
 \end{itemize}
 
+% addcorruptuser and adduser+corrupt is the same,
+% since corrupt would give the adversary all previous protocol
+% 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
@@ -302,8 +314,6 @@ spends, which invalidates assumptions in anonymity games.
 
 \section{Games}
 
-\newcommand{\comment}[1]{~\\ {\small \textcolor{blue}{({#1})}}}
-
 We have two seperate security parameters in Taler
 First, our primary security parameter $\lambda$ characterizes
 the security of signatures and blind signatures.
@@ -337,8 +347,8 @@ 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{AddCorruptClient}, \ora{Deposit}.  Let $b$ be the bit that will
+ \ora{AddUser}, \ora{WithdrawAsExchange}, \ora{Spend},
+ \ora{RefreshAsExchange}, \ora{LinkAsExchange}, \ora{AddCorruptUser}, \ora{Deposit}.  Let $b$ be the bit that will
  determine the mapping between users and spend operation, which the adversary must guess.
 
 \bigskip
@@ -380,7 +390,7 @@ 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
+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
@@ -401,7 +411,7 @@ with the following:
     $\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{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.
@@ -444,15 +454,15 @@ The game also covers the case where a malicious exchange pretends the customer
 did a dishonest refresh (in instantiations that allow dishonest refreshes).
 
 Let \oraSet{Fair} stand for access to the oracles
- \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
- \ora{RefreshAsExchange}, \ora{Share}, \ora{AddCorruptClient}, \ora{Deposit}.
+ \ora{AddUser}, \ora{WithdrawAsExchange}, \ora{Spend},
+ \ora{RefreshAsExchange}, \ora{Share}, \ora{AddCorruptUser}, \ora{Deposit}.
 
 \bigskip
 \noindent $\mathit{Exp}_{\cal A}^{fair}(1^\lambda, 1^\kappa)$:
 \vspace{-0.5\topsep}
 \begin{enumerate}
   \setlength\itemsep{0em}
-  \item $(skE, pkE) \leftarrow \mathrm{EKeygen}(1^\lambda, 1^\kappa, M)$ 
+  \item $(skE, pkE) \leftarrow \mathrm{ExchangeKeygen}(1^\lambda, 1^\kappa, M)$ 
   \item $C_0 \leftarrow {\cal A}^{\oraSet{Fair}}(pkExchange)$
   \item If $C_0$ is not a coin public key, return 0.
         Also let $U$ be the user that has $C_0$ in their wallet.  If no such $U$ exists, return 0.
@@ -483,15 +493,15 @@ Intuitively, adversarial customers win if they can forge more valid coins than
 they withdraw.
 
 Let \oraSet{Forge} stand for access to the oracles
- \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
- \ora{RefreshAsExchange}, \ora{Share}, \ora{AddCorruptClient}.
+ \ora{AddUser}, \ora{WithdrawAsExchange}, \ora{Spend},
+ \ora{RefreshAsExchange}, \ora{Share}, \ora{AddCorruptUser}.
 
 \bigskip
 \noindent $\mathit{Exp}_{\cal A}^{forge}(1^\lambda, \kappa)$:
 \vspace{-0.5\topsep}
 \begin{enumerate}
   \setlength\itemsep{0em}
-  \item $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ 
+  \item $(skE, pkE) \leftarrow \mathrm{ExchangeKeygen}()$ 
   \item $(C_0, \dots, C_\ell) \leftarrow \mathcal{A}^{\oraSet{Forge}}(pkExchange)$
   \item Our adversary wins if the sum of the unspend value of valid coins in $C_0 \dots, C_\ell$
     exceeds the amount withdrawn by corrupted peers.
@@ -502,7 +512,7 @@ Let \oraSet{Forge} stand for access to the oracles
 \subsection{Income Transparency}
 
 Intuitively, the adversary wins if money is in exclusive control of corrupted
-clients, but the exchange has no record of withdrawal or spending for it.  This
+users, but the exchange has no record of withdrawal or spending for it.  This
 of course presumes that the adversary cannot delete from non-corrupted
 customer's wallets, even though they can use oracles to force protocol
 interactions of non-corrupted customers.
@@ -514,24 +524,24 @@ introduces the threat of losing exclusive control of coins (despite having the o
 were received without involvement of the exchange.
 
 Let \oraSet{Income} stand for access to the oracles
- \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
- \ora{RefreshAsExchange}, \ora{Share}, \ora{AddCorruptClient}.
+ \ora{AddUser}, \ora{WithdrawAsExchange}, \ora{Spend},
+ \ora{RefreshAsExchange}, \ora{Share}, \ora{AddCorruptUser}.
 
 \bigskip
 \noindent $\mathit{Exp}_{\cal A}^{income}(1^\lambda, 1^\kappa)$:
 \vspace{-0.5\topsep}
 \begin{enumerate}
   \setlength\itemsep{0em}
-  \item $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ 
+  \item $(skE, pkE) \leftarrow \mathrm{ExchangeKeygen}()$ 
   \item $(C_1, \dots, C_\ell) \leftarrow \mathcal{A}^{\oraSet{Income}}(pkExchange)$
   \item Augment the wallets of all non-corrupted users with their
     transitive closure using the \algo{Link} protocol.
     Mark all remaining value on coins in wallets of non-corrupted users as spent (with \algo{Deposit}).
   \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 sum of coins withdrawn by non-corrupted clients,
-    $w'$ be the sum of coins withdrawn by corruped clients, and $s$ be the value marked as spent
-    by non-corrupted clients.
+  \item Let $w$ be the sum of coins withdrawn by non-corrupted users,
+    $w'$ be the sum of coins withdrawn by corruped users, and $s$ be the value marked as spent
+    by non-corrupted users.
     Our adversary wins if $L - w' > 0$.
   \item Return $(L, w, w', s)$
 \end{enumerate}
@@ -564,7 +574,7 @@ independent from whether the adversary wins the game or not.
 \subsubsection{Exculpability}
 Exculpability is not necessary, since coins are spent on-line with the exchange.
 In practice, even offline e-cash systems that provide exculpability are often undesireable, 
-since hardware failures can result in unintentional double spending.
+since hardware failures can result in unintentional overspending.
 
 \subsubsection{Fair Exchange and Endorsements}
 Camenisch and others \cite{camenisch2007endorsed} describes a version of (offline) e-cash where it is possible to
@@ -622,8 +632,8 @@ if the fairness game is neglegible for any polynomial time adversary $\mathcal{A
 Let $G \in \mathbb{E}$ be the generator of the Ed25519 curve (with Edwards coordinates).  
 
 \begin{itemize}
-  \item \algo{EKeygen}():  Generate an RSA key pair of length $\lambda$ and return it.
-  \item \algo{CKeygen}():  Generate an EdDSA key pair and return it.
+  \item \algo{ExchangeKeygen}():  Generate an RSA key pair of length $\lambda$ and return it.
+  \item \algo{UserKeygen}():  Generate an EdDSA key pair and return it.
   \item \algo{Withdraw}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU})):
     \begin{enumerate}
       \item \prt{U} selects blinding factor $r \randsel \Z_N^*$, coin secret $\V{skC} \randsel \Z_{|\mathbb{E}|}$, computes
@@ -661,7 +671,7 @@ Let $G \in \mathbb{E}$ be the generator of the Ed25519 curve (with Edwards coord
       \item (tide denotes item at index $\gamma$ set to zero)
     \end{itemize}
   \item \algo{Link}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{linkSecret}, \V{skCoin})):
-    The client obtains the protocol transcript for the Refresh with coin public key derived from \V{skCoin}.
+    The user obtains the protocol transcript for the Refresh with coin public key derived from \V{skCoin}.
     The refresh protocol is then used to withdraw the planchet $\overline{M}_\kappa$.
 \end{itemize}
 
@@ -704,7 +714,7 @@ Let $G \in \mathbb{E}$ be the generator of the Ed25519 curve (with Edwards coord
   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 $\mathbb{G}_2$, the refresh oracle is modified so that the client responds
+  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
@@ -769,12 +779,12 @@ satisfies \emph{Fairness}.
 
 \begin{proof}
 We replace coin public keys with signing public keys from the EUF-CMA
-challenger, unless the coins are withdrawn by corrupted clients.
+challenger, unless the coins are withdrawn by corrupted users.
 Signature operations with these public keys are replaces with calls to the signing \ora{Sign} oracle of the EUF-CMA challenger.
 
 If the adversary wins in step 6.2, there must be a valid deposit permission over a contract not signed by the user,
 and thus not send to \ora{Sign}.   If the adversary wins in step 6.3, there must be a refresh request not signed
-by the client.  In either case, we can extract a forged signature and use \prt{A} to construct an adversary against EUF-CMA.
+by the user.  In either case, we can extract a forged signature and use \prt{A} to construct an adversary against EUF-CMA.
 \end{proof}
 
 \subsection{Unforgeability}
@@ -842,9 +852,9 @@ Recall that the adversary must show that they have exclusive control over coins
 \ora{Refresh}, \ora{Link}, \ora{Share} or \ora{Withdraw} was used to obtain these coins, otherwise the adversary could be used to win break unforgeability.  TOO FAST... $L - w'$
 
 Since the adversary only wins if $L - w' > 0$, the adversary could not have
-withdrawn this value with corrupted clients.
+withdrawn this value with corrupted users.
 
-Access to \ora{LinkAsUser} only gives the adversary access to coins that are already in wallets of (honest) clients, and are thus lost in step 3 of the game.
+Access to \ora{LinkAsUser} only gives the adversary access to coins that are already in wallets of (honest) users, and are thus lost in step 3 of the game.
 
 The only remaining possibility to obtain coins is via \ora{RefreshAsExchange} and \ora{Share}.  Specifically the adversary must try to gain exclusive ``ownership''
 of a coin whose private key was previously obtained via \ora{Share}, since sharing alone would result in the adversary losing the coin in step 3 of the game.