Fairness theorem

I donno if I'm missing something around this \prt{A} but looks like \cal A is normally easier to read.

1 files changed, 34 insertions, 27 deletions

diff --git a/games/games.tex b/games/games.tex
index 8d2255f..675d4e5 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -152,20 +152,20 @@ since it does not give the adversary any additional power.
 
 
 \subsection{Anonymity}
-Anonymity game with adversary $\prt{A}$.
+Anonymity game with adversary $\cal A$.
 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}_{\prt{A}}^{anon}(1^\lambda, \kappa)$:
+\noindent $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, \kappa)$:
 \vspace{-0.5\topsep}
 \begin{enumerate}
   \setlength\itemsep{0em}
-  \item $(\V{skE}, \V{pkE}, \V{skM}, \V{pkM}) \leftarrow \prt{A}()$ \\
+  \item $(\V{skE}, \V{pkE}, \V{skM}, \V{pkM}) \leftarrow {\cal A}()$ \\
     Our adversary controls the exchange and a merchant.
-    \comment{Note that this only means that \prt{A} has the exchange secret key, it
+    \comment{Note that this only means that $\cal 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 \prt{A}^{\oraSet{Anon}}()$ \\
+  \item $(\V{pkU}_0, \V{pkU}_1, \V{contract}_0, \V{contract}_1) \leftarrow {\cal 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
@@ -185,15 +185,15 @@ 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}), \prt{A}(dp_1))$, \\
-        $\algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{A}(dp_2))$ \\
+  \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 $b' \leftarrow \prt{A}^{\oraSet{Anon}}()$
+  \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
     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 \prt{A}
+    Return 0 if $\cal U$ contains either any user corrupted by $\cal A$
     or any user who ran the linking protocol.
     \comment{TODO: Add linking protocol to \oraSet{Anon}, but simplify this text if the linking protocol can be restricted to corrupted users}
   \item if $b = b'$ return 1, otherwise return 0
@@ -203,14 +203,14 @@ 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 $\prt{A}$ must supply a opaque withdrawal event handle.  
+the adversary $\cal A$ must supply a opaque withdrawal 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 \prt{A}^{\oraSet{Anon}}()$ \\
+  \item[2] $(P_0, P_1, \V{contract}_0, \V{contract}_1) \leftarrow {\cal A}^{\oraSet{Anon}}()$ \\
     Our creates invokes oracles to create users and give them coins.
     It returns two planchets $P_0$ and $P_1$ and two contracts
     $\V{contract}_0$ and $\V{contract}_1$.
@@ -251,7 +251,7 @@ allowing them to talk to themselves does not make sense.
 %\begin{enumerate}
 %  \setlength\itemsep{0em}
 %  \item $(skExchange, pkExchange) \leftarrow \algo{EKeygen}()$ 
-%  \item $(r_1, r_2) = \prt{A}^{\ora{*}}()$
+%  \item $(r_1, r_2) = {\cal A}^{\ora{*}}()$
 %    \comment{Two different receipts for deposit from the exchange / relayed by merchant}
 %  \item return $1$ if $r_1, r_2 \neq \bot$, $r_1 \neq r_2$ and $r_1 = S(pkExchange, pkCoin, h_1)$ but $r_2 = S(pkExchange, pkCoin, h_2)$
 %    with $h_1 \neq h_2$ for some $pkCoin$.
@@ -267,12 +267,12 @@ Let \oraSet{Fair} stand for access to the oracles \ora{AddClient}, \ora{Withdraw
 \ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient}
 
 \bigskip
-\noindent $\mathit{Exp}_{\prt{A}}^{fair}(1^\lambda, \kappa)$:
+\noindent $\mathit{Exp}_{\cal A}^{fair}(1^\lambda, \kappa)$:
 \vspace{-0.5\topsep}
 \begin{enumerate}
   \setlength\itemsep{0em}
   \item $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ 
-  \item $C_0 \leftarrow \prt{A}^{\oraSet{Fair}}(pkExchange)$
+  \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 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$}
@@ -292,7 +292,7 @@ Let \oraSet{Forge} stand for access to the oracles \ora{AddClient}, \ora{Withdra
 \ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient} ???
 
 \bigskip
-\noindent $\mathit{Exp}_{\prt{A}}^{forge}(1^\lambda, \kappa)$:
+\noindent $\mathit{Exp}_{\cal A}^{forge}(1^\lambda, \kappa)$:
 \vspace{-0.5\topsep}
 \begin{enumerate}
   \setlength\itemsep{0em}
@@ -311,7 +311,7 @@ Let \oraSet{Income} stand for access to the oracles \ora{AddClient}, \ora{Withdr
 \ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient}
 
 \bigskip
-\noindent $\mathit{Exp}_{\prt{A}}^{income}(1^\lambda, \kappa)$:
+\noindent $\mathit{Exp}_{\cal A}^{income}(1^\lambda, \kappa)$:
 \vspace{-0.5\topsep}
 \begin{enumerate}
   \setlength\itemsep{0em}
@@ -490,31 +490,38 @@ could see in a game has the same probability, and he must win with probability $
 
 \subsection{Fairness}
 
-\begin{proof}[Proof-sketch]
+\begin{theorem}
+If our signature scheme used for coins signing contracts is
+ polynomially-secure, 
+then Taler is polynomially-secure against attacks on fairness.
+\end{theorem}
+
+\begin{proof}
 We required that any refresh operations were run to conclusion, 
-which makes sense with our adversary $\prt{A}$ being a merchant
+which makes sense with our adversary $\cal A$ being a merchant
 unable to control either the customer or exchange.  It follows 
-that $\prt{A}$ never called the refresh oracle on $C_n$.
+that $\cal{A}$ never called the refresh oracle on $C_n$.
 
-As the refresh $R$ must fail, $\prt{A}$ must have the customer
+As the refresh $R$ must fail, $\cal A$ must have the customer
 spend $C_n$, and then either deposit $C_n$, refresh $C_n$, or
 spend $C_n$ with another merchant.
-In any case, $\prt{A}$ must not return the correct receipt to
+In any case, $\cal A$ must not return the correct receipt to
 the customer, doing so concludes the transaction honestly.  
 
-If $\prt{A}$ deposits $C_n$, then the customer would also obtain
+If $\cal A$ deposits $C_n$, then the customer would also obtain
 the correct receipt from exchange by doing a refresh, so the
 adversary must distract them with signed message from the exchange
 indicating double spending or previous refresh. In either subcase,
-$\prt{A}$ provides signatures by both $C_n$ and $\V{pkE}$.
+$\cal A$ provides signatures by both $C_n$ and $\V{pkE}$.
 
-If $\prt{A}$ either refreshes or spends $C_n$, then they provide
+If $\cal A$ either refreshes or spends $C_n$, then they provide
 a signature by $C_n$ too.
 
-TODO: Anything more about signature reduction?
+In all cases, we discover a forged signature by $C_n$, yielding
+an adversary who could attack the coin signature scheme.
 \end{proof}
 
-We have stated the game and theorem with $\prt{A}$ controlling only
+We have stated the game and theorem with $\cal A$ controlling only
 the merchant, but even if they control the exchange as well they
 still cannot forge the signature by $C_n$.  An exchange has access
 to more oracles however so they can take actions like dropping the
@@ -536,7 +543,7 @@ Taler is polynomially-secure against one-more forgery attacks.
 \begin{proof}
 We consider a probabilistic polynomially time adversary $\cal A$ with
 a non-negligible advantage for winning the unforgeability game
- $\mathit{Exp}_{\prt{A}}^{forge}(1^\lambda, \kappa)$.
+ $\mathit{Exp}_{\cal A}^{forge}(1^\lambda, \kappa)$.
 We describe an RSA Chosen-Target Inversion Problem (RSA-CTI)
  \cite[Definition 3]{RSA-FDH-KTIvCTI} % or \cite[DEfinition 6.1]{OneMoreInversion}.
 won by $\cal A$.