Merge branch 'master' of ssh://taler.net/papers

1 files changed, 26 insertions, 30 deletions

diff --git a/games/games.tex b/games/games.tex
index c884d79..ce63274 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -32,7 +32,7 @@
 \begin{document}
 
 
-%\newcommand{randsel}{\ensuremath{\xrightarrow[\text{world}]{\text{hello}}}}
+% uniform random selection from set
 \newcommand{\randsel}[0]{\ensuremath{\xleftarrow{\text{\$}}}}
 
 % oracles
@@ -68,13 +68,13 @@ 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{skE}, \V{pkE})$.
+  \item \algo{EKeygen}():  Probabilistic polynomial time 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{skU}, \V{pkU})$.
+  \item \algo{CKeygen}():  Probabilistic polynomial time 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]$.
-  \item \algo{Spend}(contract, pkClient, skCoin, pkReceiver):  Probabilistic algorithm. Signs a deposit permission for a particular contract.
+  \item \algo{Spend}(contract, pkClient, skCoin, pkReceiver):  Probabilistic polynomial time 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).
@@ -140,8 +140,6 @@ While most algorithms in Taler are not probabilistic, we still say that they are
 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.
 
 While we do have a \algo{Deposit} protocol that's used in some of the games, having a deposit oracle is not necessary
 since it does not give the adversary any additional power.
@@ -155,20 +153,21 @@ since it does not give the adversary any additional power.
 
 
 \subsection{Anonymity}
-Anonymity game with adversary $\cal A$.
+Anonymity game with adversary $\prt{A}$, security parameter $\lambda$, cut-and-choose parameter $\kappa$
+and coin flip $b$.
 Let \oraSet{Anon} stand for access to the oracles \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
 \ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient}
 
 \bigskip
-\noindent $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, \kappa, b)$:
+\noindent $\mathit{Exp}_{\prt{A}}^{anon}(1^\lambda, \kappa, b)$:
 \vspace{-0.5\topsep}
 \begin{enumerate}
   \setlength\itemsep{0em}
-  \item $(\V{skE}, \V{pkE}, \V{skM}, \V{pkM}) \leftarrow {\cal A}()$ \\
+  \item $(\V{skE}, \V{pkE}, \V{skM}, \V{pkM}) \leftarrow {\prt{A}}()$ \\
     Our adversary controls the exchange and a merchant.
-    \comment{Note that this only means that $\cal A$ has the exchange secret key, it
+    \comment{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{contract}_0, \V{contract}_1) \leftarrow {\cal A}^{\oraSet{Anon}}()$ \\
+  \item $(\V{pkU}_0, \V{pkU}_1, \V{contract}_0, \V{contract}_1) \leftarrow {\prt{A}}^{\oraSet{Anon}}()$ \\
     Our adversary creates two users and two contract,
     along with some coins open which it calls oracles freely.
   \item Return 0 either if $\V{pkU}_1$ or $\V{pkU}_2$ are not distinct
@@ -186,12 +185,12 @@ Let \oraSet{Anon} stand for access to the oracles \ora{AddClient}, \ora{Withdraw
   \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.
-  \item $\algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), {\cal A}(dp_1))$, \\
-        $\algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), {\cal A}(dp_2))$ \\
-    Deposit these two coins with the adversary controlled merchant.
+  \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.
   \item $b' \leftarrow {\cal A}^{\oraSet{Anon}}()$
     \comment{Ask adversary to find out mapping between users and contracts as determined by $b$}
-  \item Let $\cal U \supseteq \{ \V{pkU}_1, \V{pkU}_2 \}$ consist
+  \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$
@@ -201,23 +200,24 @@ Let \oraSet{Anon} stand for access to the oracles \ora{AddClient}, \ora{Withdraw
 \end{enumerate}
 
 We have stated this game in terms of the anonymity of users to match
-existing ecash literature, but actually any user based formulation is
-insufficient for any ecash schemes' purposes because one users needs
-unlinkability their .  Instead of the two users $\V{pkU}_0$ and $\V{pkU}_1$,
-the adversary $\cal A$ must supply a opaque withdrawal event handle.  
+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$,
+the adversary $\cal A$ must supply a opaque 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.
 \begin{enumerate}
   \setlength\itemsep{0em}
-  \item[2] $(P_0, P_1, \V{contract}_0, \V{contract}_1) \leftarrow {\cal A}^{\oraSet{Anon}}()$ \\
+  \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 invokations, either withdrawals
+    It singles out two coin creating invocations, either withdrawals
     or refreshes, by returning the planchets $P_0$ and $P_1$. 
     It returns two two contracts $\V{contract}_0$ and $\V{contract}_1$ as well.
-  \item[3]
+  \item[3.]
     We demand that valid unspent coins $\V{pkC}_0$ and $\V{pkC}_1$
     have been created from the planchets $P_0$ and $P_1$ respectively.
     Also let $\V{pkU}_1$ and $\V{pkU}_2$ denote the registered users
@@ -225,7 +225,7 @@ with these two lines.
     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] 
+  % \item[5.] 
 \end{enumerate}
 
 
@@ -275,11 +275,12 @@ Let \oraSet{Fair} stand for access to the oracles \ora{AddClient}, \ora{Withdraw
   \setlength\itemsep{0em}
   \item $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ 
   \item $C_0 \leftarrow {\cal A}^{\oraSet{Fair}}(pkExchange)$
-  \item Let $U$ be the user that has $C_0$ in their wallet.  If no such $U$ exists, return 0.
+  \item If $C_0$ is not a coin public key, return 0.  Let $U$ be the user that has $C_0$ in their wallet.  If no such $U$ exists, return 0.
+    \comment{Note however that $C_0$ is not required to be fresh or unspent.}
   \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 $R \leftarrow \algo{Refresh}(\prt{B}(skE, pkE), \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.
     Otherwise return 1.
@@ -548,11 +549,6 @@ any PPT adversary \prt{A}.
 \end{mdframed}
 
 
-\paragraph{``Proof sketch''.}  Proof by looking at withdraw/deposit/refresh transcripts seen by the adversary.  Do game hopping, replace
-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{Fairness}
 
 \begin{theorem}