fix things and add more notes

1 files changed, 59 insertions, 22 deletions

diff --git a/games/games.tex b/games/games.tex
index eb5a0dc..58413b4 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -10,6 +10,7 @@
 \usepackage{subcaption}
 \usepackage{mathpazo}
 \usepackage{mathtools}
+\usepackage{mdframed}
 % \usepackage[amsmath,thmmarks]{ntheorem}
 \usepackage[usenames,dvipsnames,svgnames,table]{xcolor}
 
@@ -18,7 +19,7 @@
 % not amsthm
 % \theoremseparator{.} % normal theorem
 
-\title{Taler Provable Security}
+\title{Taler Security Proofs}
 \date{\today}
 
 \newtheorem{lemma}{Lemma}
@@ -35,6 +36,8 @@
 
 % oracles
 \newcommand{\ora}[1]{\ensuremath{\mathcal{O}\mathsf{#1}}}
+% oracle set
+\newcommand{\oraSet}[1]{\ensuremath{\mathcal{O}\textsc{#1}}}
 % algorithm
 \newcommand{\algo}[1]{\ensuremath{\mathsf{#1}}}
 % party
@@ -61,9 +64,9 @@ Simplification:  No partial spending, only one denomination.
 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{EKeygen}():  Probabilistic algorithm executed by the exchange, outputs a key pair $(\V{skE}, \V{pkE})$.
 
-  \item \algo{CKeygen}():  Probabilistic algorithm executed by customers, outputs a key pair $(\V{sk}, \V{pk})$.
+  \item \algo{CKeygen}():  Probabilistic algorithm executed by customers, outputs a key pair $(\V{skU}, \V{pkU})$.
   \item \algo{Withdraw}(\prt{E}(\V{skE}, \V{pkE}, \prt{U}(\V{skU}, \V{pkU})):  Interactive protocol between exchange and user.
 
     Increases $countWithdraw[pkU]$ by one, adds the resulting coin to the wallet $wallet[pkU]$.
@@ -75,11 +78,12 @@ The Taler e-cash system is defined by the following algorithms.
   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})):
+  \item \algo{RefreshCommit}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin}, \V{commitData})):
   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})):
+  On success, returns $\gamma$, the index of the commitment that should not be revealed.
+  \item \algo{RefreshReveal}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin}, \V{revealData})):
   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})):
@@ -107,7 +111,7 @@ We define the following oracles:
     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)$
+  \item $\ora{RefreshReveal}(pkClient, refresHandle, revealData)$
 
     Force a client to do a reveal.
     
@@ -132,41 +136,74 @@ We define the following oracles:
     client's private key, wallet and signed contract hashes.
 \end{itemize}
 
+\begin{mdframed}
+The difference between algorithms and interactive protocols
+is that the ``pure'' algorithms only deal with data, while the interactive protocols
+take ``handles'' to parties that are communicating in the protocol.  The adversary can
+always execute algorithms that don't depend on handles to communication partners.
+However the adversary can't run the interactive protocols directly, instead it must
+rely on the interaction oracles for it.  Different interaction oracles might allow the
+adversary to play different roles in the same interactive protocol.
+
+While most algorithms in Taler are not probabilistic, we still say that they are, since
+somebody else might come up with an instantiation of Taler that uses probabilistic algorithms,
+and then the games should still apply.
+
+All algorithms need to be polynomial time, but this is already implied by the
+definition of the adversary and simulator.
+\end{mdframed}
+
+
+
 \section{Games}
 
 \newcommand{\comment}[1]{\\ {\small \textcolor{blue}{({#1})}}}
 
 
 \subsection{Anonymity}
-Anonymity game with adversary $\prt{A}$, where $\ora{*}$ means access to all
-oracles (\ora{AddClient}, \ora{WithdrawAsExchange}, \ora{WithdrawAsUser}, \ora{Deposit}, \ora{Spend},
-\ora{RefreshCommit}, \ora{RefreshReveal}, \ora{Share}, \ora{CorruptClient}).
+Anonymity game with adversary $\prt{A}$.
+Let \oraSet{Anon} stand for access to the oracles \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{WithdrawAsUser}, \ora{Deposit}, \ora{Spend},
+\ora{RefreshCommit}, \ora{RefreshReveal}, \ora{Share}, \ora{CorruptClient}
 
 \begin{enumerate}
   \setlength\itemsep{0em}
   \item $(\V{skE}, \V{pkE}) \leftarrow \prt{A}()$
-    \comment{Adversary controls the exchange}
-  \item $(\V{pkU}_1, \V{pkU}_2, \V{skM}, \V{pkM}, \V{contract}) \leftarrow \prt{A}^{\ora{*}}()$
-    \comment{Adversary must create two users, a merchant and a contract identifier}
-  \item if $\V{pkU}_1$ or $\V{pkU}_2$ are not registered as users, return 0
+    \comment{``Adversary controls the exchange.''  Note that this only means that \prt{A} has the exchange secret key, it
+    does not automatically receive transcripts and it does not have access to any exchange data structures \textit{unless} indicated by the oracles}
+  \item $(\V{pkU}_0, \V{pkU}_1, \V{skM}, \V{pkM}, \V{contract_0}, \V{contract_1}) \leftarrow \prt{A}^{\oraSet{Anon}}()$
+    \comment{Adversary must create two users, a merchant and two contract identifiers}
+  \item if $\V{pkU}_1$ or $\V{pkU}_2$ are not registered as distinct users, return 0
   \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{pkU}_b \V{pkCoin}, \V{pkM})$
-  \item $\algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{A}())$
+  \item select unspent coins $pkC_0, pkC_1$, from wallets of $\V{pkU}_0, \V{pkU}_1$ respectively.
+  \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})$
+  \item $\algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{A}(dp_1))$, \\
+        $\algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{A}(dp_2))$
     \comment{Role of merchant is played by adversary}
-  \item sign a fresh coin and add it to the wallet of $\V{pkU}_b$
-    \comment{We must do this, otherwise adversary can distinguish users by exhausting their wallets}
-  \item $b' \leftarrow \prt{A}^{\ora{*}}()$
+  \item $b' \leftarrow \prt{A}^{\oraSet{Anon}}()$
+    \comment{Ask adversary to find out mapping between users and contracts as determined by $b$}
   \item if $\V{pkU}_1$ or $\V{pkU}_2$ were corrupted by \prt{A}, return 0
   \item if \ora{Share} was used with $\V{pkU}_1$ or $\V{pkU}_2$ as source, return 0
   \item if $b = b'$ return 1, otherwise return 0
 \end{enumerate}
 
-\paragraph{Notes:} There are two kinds of games found for anonymity in the
+\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.
+
+\paragraph{Todo:}  Show that/how in our model, this also implies that anonymous purchases are independent from \emph{each other}.
+
+\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
 the other one on simulation.  The latter is claimed to be more powerful in \cite{izabachene2013divisible}.
 
+Note that our game lets both users spend, which means we don't need to ``magically'' come up for
+a fresh coin for the only user who just spent one.  If only one coin is spend and we don't replace it,
+the adversary can exhaust wallets to see who spent.  We can avoid this, since we have contract identifiers
+and can rely on those.
+\end{mdframed}
+
 %\subsection{Unforgeability}
 %\begin{enumerate}
 %  \setlength\itemsep{0em}
@@ -186,7 +223,7 @@ 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 $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ 
   \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$.
@@ -194,7 +231,7 @@ Intuition: Adversary wins if a non-corrupted user can't obtain a proof-of-spendi
   \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_n]$, return 0.
+    If $R$ indicates double spending with contract $h$ and $h \in contractHashes[U]$, return 0.
     Otherwise return 1.
 \end{enumerate}