fixes

1 files changed, 53 insertions, 39 deletions

diff --git a/games/games.tex b/games/games.tex
index a9c40dc..22dd209 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -47,14 +47,11 @@
 
 The exchange is one entity, there is only one exchange, there are many clients
 and a client can act as a merchant, a customer or both (no further distinction other than naming in the role).
+By convention, names for private keys begin with $pk$ and $sk$ for secret keys.
 
-Signature over message $m$ with public key $p$ is denoted by $S(m, p)$.  For notational convenience, includes
-both the signature and the message.  By convention, names for private keys begin with $pk$ and $sk$ for secret keys.
-
-We track $countDeposit[pkClient]$ and $countWithdraw[pkClient]$ separately for
-each client.  The private keys of coins certainly known by clients are stored as
-$wallet[pkClient]$.  Contracts are tracked created during deposit are tracked
-as $contractHashes[pkClient]$.  The exchange keeps track of $spent[pkCoin]$ and $refreshCommit[pkCoin]$ and $refreshFail[pkCoin]$.
+We track $\V{countWithdraw}[\V{pkClient}]$ for each client.  The private keys of coins given to clients are stored as
+$\V{wallet}[\V{pkClient}]$.  Contracts are created during deposit are tracked
+as $\V{contractHashes}[\V{pkClient}]$.  The exchange keeps track of $\V{spent}[\V{pkCoin}]$ and $\V{refreshCommit}[\V{pkCoin}]$ and $\V{refreshFail}[\V{pkCoin}]$.
 
 
 Simplification:  No partial spending, only one denomination.
@@ -64,22 +61,29 @@ The Taler e-cash system is defined by the following algorithms.
 
 \begin{itemize}
   \item \algo{EKeygen}():  Probabilistic algorithm executed by the exchange, outputs a key pair $(\V{skExchange}, \V{pkExchange})$.
+
   \item \algo{CKeygen}():  Probabilistic algorithm executed by customers, outputs a key pair $(\V{sk}, \V{pk})$.
   \item \algo{Withdraw}(\prt{E}(\V{skE}, \V{pkE}, \prt{U}(\V{skU}, \V{pkU})):  Interactive protocol between exchange and user.
-  \item \algo{Spend}(contract, skCoin, pkReceiver):  Probabilistic algorithm. Signs a deposit permission for a particular contract.
+
+    Increases $countWithdraw[pkU]$ by one, adds the resulting coin to the wallet $wallet[pkU]$.
+  \item \algo{Spend}(contract, pkClient, skCoin, pkReceiver):  Probabilistic algorithm. Signs a deposit permission for a particular contract.
+    Adds $contract$ to $contractHashes[pkClient]$.
   \item \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{M}(\V{skU}, \V{depositPermission})):
   Interactive protocol between the exchange and a customer (acting as merchant).
 
-  On double-spending, return the protocol transcript of the deposit/refresh.
+  Marks the coin with public key $pkCoin$ in the deposit permission as $spent[pkCoin] := 1$.
+
+  On double-spending, return the protocol transcript of the deposit/refresh.  On success, returns exchange's signature over the request.
   \item \algo{RefreshCommit}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin}, \V{c})):
-  Interactive protocol between exchange and user.
+  Interactive protocol between exchange and user.  Marks the coin with secret key $skCoin$ as spent and uses $c$ as commitment.
 
   If the refresh would be double spending, return the protocol transcript of the deposit/refresh.
   \item \algo{RefreshReveal}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin}, \V{r})):
-  Interactive protocol between exchange and user.
+  Interactive protocol between exchange and user.  If revealed value $r$ does not match commitment or the coin marked as previously failed in $refreshFail$, return
+  protocol transcript of prior refresh.  Otherwise, return fresh coin.
   \item \algo{Link}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin})):
   Interactive protocol between exchange and user.
-  If \v{skCoin} is the secret key of a coin that was refreshed, adds a coin that resulted from the refresh to the user's wallet.
+  If \V{skCoin} is the secret key of a coin that was refreshed, adds a coin that resulted from the refresh to the user's wallet.
 \end{itemize}
 
 \subsection{Oracles}
@@ -88,40 +92,43 @@ We define the following oracles:
 
 \begin{itemize}
   \item $\ora{AddClient}()$:
-    Creates a new client, sets $balanceDeposit$ and $balanceWithdraw$ for the client to $0$, sets $wallet[pkClient] := \{\}$.
+    Creates a new client, sets $countWithdraw$ for the client to $0$, sets $wallet[pkClient] := \{\}$.
+    Returns the public key of the client.
 
-  \item $\ora{Withdraw}(pkClient)$:
+  \item $\ora{WithdrawAsUser}(pkClient)$:  Do a withdraw from the perspective of a user.  The adversary
+    controls the user, the simulator the bank.
 
-    Decreases $balanceWithdraw[pkClient]$ by one, adds the resulting coin to the wallet.
+  \item $\ora{WithdrawAsBank}(pkClient)$:  Do a withdraw from the perspective of a bank.  The adversary
+    controls the bank, the user is simulated.
 
   \item $\ora{RefreshCommit}(pkClient, blindedNewCoins, commitData)$
-    Forces the client to execute the refresh protocol, with data provided by the adversary.
-    Returns a handle to the refresh session if the client has at least one coin, or $\bot$ otherwise.
+    Forces the client to execute the refresh protocol, with data provided by
+    the adversary.  Returns a the index to be revealed and a handle to the
+    refresh session if the client has at least one coin, or $\bot$ otherwise.
 
   \item $\ora{RefreshReveal}(pkClient, handle, revealData)$
 
     Force a client to do a reveal.
     
+    Returns the new coin, or transcript of double spending / wrong commit on failure.
+
     Note that the handle is necessary so the adversary
     can make clients refresh without seeing the actual coins.
 
-  \item $\ora{Spend}(contractHash, pkSpender, pkCoin, pkReceiver) \mapsto S(pkCoin, contractHash, pkReceiver)$
-    Make a customer sign a deposit permission.
+  \item $\ora{Spend}(contractHash, pkSpender, pkCoin, pkReceiver)$
+    Make a customer sign a deposit permission.  Returns the deposit permission on success, or $\bot$ if the $skSpender$ does not have enough coins.
 
-    Also adds $contractHash$ to $contractHashes[pkSpender]$.
+  \item $\ora{Share}(pkSender, pkReceiver)$:
 
-  \item $\ora{Share}(pkCoin, pkReceiver)$:
+    Shares one random, previously unshared coin in the wallet of $pkSender$ with $pkReceiver$.
 
-    Adds the coin to the receiver's wallet and reveals the coin secret key.
-
-  \item $\ora{Deposit}(S(pkCoin, contractHash, pkReceiver))$:
-
-    If a coin is double-spent (by spending it on a different $contractHash$) then $receipt = \bot$.  Sets $spent[pkCoin] := 1$.
+  \item $\ora{Deposit}(depositPermission)$:
+    Give a deposit permission to the exchange.  Returns the exchange's response.
 
   \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 and wallet.
+    client's private key, wallet and signed contract hashes.
 \end{itemize}
 
 \section{Games}
@@ -131,7 +138,7 @@ We define the following oracles:
 
 \subsection{Anonymity}
 Anonymity game with adversary $\prt{A}$, where $\ora{*}$ means access to all
-oracles (\ora{AddClient}, \ora{Withdraw}, \ora{Deposit}, \ora{Spend},
+oracles (\ora{AddClient}, \ora{WithdrawAsBank}, \ora{WithdrawAsUser}, \ora{Deposit}, \ora{Spend},
 \ora{RefreshCommit}, \ora{RefreshReveal}, \ora{Share}, \ora{CorruptClient}).
 
 \begin{enumerate}
@@ -144,7 +151,7 @@ oracles (\ora{AddClient}, \ora{Withdraw}, \ora{Deposit}, \ora{Spend},
   \item $b \randsel{} \{0,1\}$
     \comment{Random bit selected by challenger}
   \item select unspent coin $pkCoin$ from wallet of $\V{pkU}_b$.
-  \item $\V{dp} \leftarrow \algo{Spend}(\V{contract}, \V{pkCoin}, \V{pkM})$
+  \item $\V{dp} \leftarrow \algo{Spend}(\V{contract}, \V{pkU}_b \V{pkCoin}, \V{pkM})$
   \item $\algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{A}())$
     \comment{Role of merchant is played by adversary}
   \item sign a fresh coin and add it to the wallet of $\V{pkU}_b$
@@ -169,8 +176,8 @@ the other one on simulation.  The latter is claimed to be more powerful in \cite
 %    with $h_1 \neq h_2$ for some $pkCoin$.
 %\end{enumerate}
 
-Is this the right game?  We could also base it on not being able to spend more than was withdrawn.  Note that in the game above, we only look
-at receipts and the coin doesn't even need to be valid directly.
+%Is this the right game?  We could also base it on not being able to spend more than was withdrawn.  Note that in the game above, we only look
+%at receipts and the coin doesn't even need to be valid directly.
 
 \subsection{Fairness}
 Intuition: Adversary wins if a non-corrupted user can't obtain a proof-of-spending or unlinkable change.
@@ -179,12 +186,14 @@ Intuition: Adversary wins if a non-corrupted user can't obtain a proof-of-spendi
 \begin{enumerate}
   \setlength\itemsep{0em}
   \item $(skExchange, pkExchange) \leftarrow \mathrm{EKeygen}()$ 
-  \item $C \leftarrow \prt{A}^{\ora{*}}(pkExchange)$
-  \item Let $U$ be the user that has $C$ in their wallet.  If no such $U$ exists, return 0.
-  \item If $U$ was corrupted or \ora{Share} was called with $C$, return 0.
-  \item $R \rightarrow \algo{Refresh}(\prt{B}(skExchange, pkExchange), \prt{U}(U, C))$
+  \item $C_0 \leftarrow \prt{A}^{\ora{*}}(pkExchange)$
+  \item Let $U$ be the user that has $C_0$ in their wallet.  If no such $U$ exists, return 0.
+  \item Let $C_0, \dots, C_n$ be the coins reachable via \algo{Link} from $C_0$.
+    \comment{When $C_0$ was not refreshed, $n=0$ and $C_n = C_0$}
+  \item If $U$ was corrupted or \ora{Share} was called with any of $C_0, \dots, C_n$, return 0.
+  \item $R \rightarrow \algo{Refresh}(\prt{B}(skExchange, pkExchange), \prt{U}(U, C_n))$
   \item If $R$ indicates a successful refresh, return $0$.
-    If $R$ indicates double spending with contract $h$ and $h \in contractHashes[U]$, return 0.
+    If $R$ indicates double spending with contract $h$ and $h \in contractHashes[U_n]$, return 0.
     Otherwise return 1.
 \end{enumerate}
 
@@ -237,9 +246,13 @@ given in literature.
 everything that's not random by something random (with computationally indistinguishable distribution) until everything that the adversary
 could see in a game has the same probability, and he must win with probability $1/2$.
 
-\subsection{Unforgeability}
-\paragraph{``Proof sketch''.}  Relatively straigt reduction to RSA-KTI and unforgeability of EdDSA.  Either
-the exchange must have accepted the coin, and the co
+
+\subsection{Fairness}
+\paragraph{``Proof sketch''.}  We enumerate all things that can lead to a failure in the refresh step.
+\begin{itemize}
+  \item double-spending with different contract hash $\Rightarrow$ merchant can forge/modify deposit permission
+  \item double-spending with refresh $\Rightarrow$ linking protocol must be broken
+\end{itemize}
 
 \subsection{Income Transparency}
 To win the game, the adversary must produce coins that are not in the wallet of any non-corrupted user.
@@ -292,6 +305,7 @@ From \cite{bellare2003onemore}.  Assumption to prove security of RSA blind signa
 \section{Questions/Todo}
 \begin{itemize}
   \item Some authors first present the protocol and then oracles, others directly use the protocol syntax as oracles.  What should we do?
+  \item We trivially get endorsed e-cash, should we add the games / definitions?
 \end{itemize}
 
 \bibliography{lit}