notation/labels, comment out Jeff's proof for now

1 files changed, 116 insertions, 103 deletions

diff --git a/games/games.tex b/games/games.tex
index b351067..ba9dfef 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -155,6 +155,9 @@ Anonymity game with adversary $\prt{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)$:
+\vspace{-0.5\topsep}
 \begin{enumerate}
   \setlength\itemsep{0em}
   \item $(\V{skE}, \V{pkE}) \leftarrow \prt{A}()$
@@ -213,11 +216,16 @@ allowing them to talk to themselves does not make sense.
 \subsection{Fairness}
 Intuition: Adversary wins if a non-corrupted user can't obtain a proof-of-spending or unlinkable change.
 
+Let \oraSet{Fair} stand for access to the oracles \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
+\ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient}
 
+\bigskip
+\noindent $\mathit{Exp}_{\prt{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}^{\ora{*}}(pkExchange)$
+  \item $C_0 \leftarrow \prt{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$}
@@ -234,13 +242,19 @@ Intuition: Adversary wins if a non-corrupted user can't obtain a proof-of-spendi
 \subsection{Income Transparency}
 Intuition: Adversary wins if money is in exclusive control of corrupted players but the exchange has no record of withdrawal or spending for it.
 
+Let \oraSet{Income} stand for access to the oracles \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
+\ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient}
+
+\bigskip
+\noindent $\mathit{Exp}_{\prt{A}}^{income}(1^\lambda, \kappa)$:
+\vspace{-0.5\topsep}
 \begin{enumerate}
   \setlength\itemsep{0em}
-  \item $(skExchange, pkExchange) \leftarrow \mathrm{EKeygen}()$ 
-  \item $(C_1, \dots, C_\ell) \leftarrow \mathcal{A}^{\ora{Withdraw}}(pkExchange)$
+  \item $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ 
+  \item $(C_1, \dots, C_\ell) \leftarrow \mathcal{A}^{\oraSet{Income}}(pkExchange)$
   \item wallets of all non-corrupted users are augmented with their transitive closure via the \algo{Link} protocol
   \item all coins from wallets of non-corrupted users are marked as spent
-  \item let $V_r$ be the number of valid non-spent coins in $(C_1, \dots, C_\ell)$  and $V_w$ the number of coins withdrawn by corrupted users
+  \item let $V_r$ be the number of valid non-spent coins in $(C_1, \dots, C_\ell)$ and $V_w$ the number of coins withdrawn by corrupted users
   \item adversary wins if $V_r > V_w$.
 \end{enumerate}
 
@@ -295,105 +309,104 @@ Let $G \in \mathbb{E}$ be the generator of the Ed25519 curve (with Edwards coord
 
 
 
-
-We can describe a simple blinding game for an RSA key pair $(n,e,d)$ and
-generators $M(\cdot)$ and $B(\cdot)$ for elements of $\Z/n\Z$ whose
-parameters we need not specify: 
-We take $m_0,m_1$ from $M$ and $b_0,b_1$ from $B$ and give our adversary
-$\cal A$ the unordered pairs of withdrawals $\{ m_0^d b_0, m_1^d b_1 \}$
-and deposits $\{ m_0^d, m_1^d \}$.  $\cal A$ wins if it can correctly
-match the withdrawals and deposits.
-
-\begin{lemma}\label{RSA_blind_signatures}
-Assume adversary $\cal A$ with an advantage in this blinding game for
-some $M_0(\cdot)$ and $B_0(\cdot)$ whatever their parameters.  There is
-a machine $\cal A'$ that identifies $B_0$ as opposed to a uniform
-distribution $U(Z/nZ)$ on $Z/nZ$.
-\end{lemma}
-
-\begin{proof}
-$\cal A'$ plays the blinding game with $\cal A$ taking $M$ to be $M_0$
-and $B$ to be $X$.  $\cal A$ either guesses correctly or incorrectly.
-If $\cal A$ guesses correctly, then $\cal A'$ guesses that yes $X$ is
-$B_0$.
-
-If $X$ is $B_0$ then $\cal A$ guesses correctly with advantage $\epsilon$, meaning
-  $P[ \textrm{$\cal A$ correct} | X=B_0 ] = 1/2+\epsilon$
-and
-  $P[ \textrm{$\cal A$ correct} | X=U ] = 1/2$.
-We imagine A' is given uniform trials to guess X=F vs X=U, so that
-  $P[X=F] = 1/2$ too,
-and 
-  $P[\textrm{$\cal A$ correct}] = 1/2 + \epsilon/2$.
-Now $\cal A'$ has an advantage in guessing if $X$ is $B_0$ or uniform correctly by
-Bays rule
-  $P[ \textrm{$\cal A$ correct} | X=B_0 ] P[X=B_0] = P[ X=B_0 | \textrm{$\cal A$ correct} ] P[A correct]$
-so
-  $P[ X=F | \textrm{$\cal A$ correct} ]
-  = 1/2 (1/2+\epsilon) / (1/2 + \epsilon/2)
-  = (1/2+\epsilon) / (1+\epsilon)
-  = 1 - 1/2 / (1+\epsilon)$.
-\end{proof}
-
-\begin{lemma}\label{interleaved}
-Let $X$ and $Y$ denote generators for elements in $\Z/n\Z$, taking
-unspecified parameters.  Let $I$ denote an interleaved sequence from
-$X$ and $Y$ taking concatenated parameters.  If some adversary has
-a non-ngeligable advnatage in distinguishing $I$ from $U(Z/nZ)$
-then some adversary has a non-ngeligable advnatage in distinguishing
-$J$ from $U(Z/nZ)$ wher eitehr $J=X$ or $J=Y$.
-\end{lemma}
-
-\begin{proof}
-Exercise for the reader.
-\end{proof}
-
-\begin{lemma}\label{PRF_composed_wth_ECDH}
-...
-\end{lemma}
-
-\begin{proof}
-...
-\end{proof}
-
-\begin{theorem}
-
-... $\cal A$ ...
-\end{theorem}
-
-\newcommand\pkCoin{pkCoin}
-
-\begin{proof}[Proof-ish]
-We consider the coin $\pkCoin$ of $U_b$ selected and spent by the
-game/environment starting from line 5, as well as the coin of
-$U_{1-b}$ that was unspent unshared in line 5, denoted $\pkCoin'$.
-
-We cannot corrupt either $U_0$ or $U_1$ nor share either $\pkCoin$ or
-$\pkCoin'$.  We may however add a spend or refresh of $\pkCoin'$ if
-$\cal A$ does not do so.  It follows that an advantage for $\cal A$
-in guessing $b'$ for our anonymity game yields an advantage in the
-blinding game given by the creation of $\pkCoin$ and $\pkCoin'$ in
-line 2 together with spending them in line 6. % and their deposit in line 7 
-
-In creating each of $\pkCoin$ and $\pkCoin'$, $\cal A$ either
-(1) invokes the withdrawal oracle directly, or else (2) applies the
-refresh oracle to some previous withdrawn coin.  These invokations
-together provide the $B_0$ in Lemma \ref{RSA_blind_signatures}.
-It follows that a non-negligable advantage for $\cal A$ yields a
-non-negligable advantage for the adversary $\cal A'$ who distinguishes
-this $B_0$ from a uniform distribution $U(Z/nZ)$ on $Z/nZ$.
-We cannot know if $\cal A$ constructs $B_0$ with direct withdrawals,
-refresh operations, or both.
-
-In the direct withdrawal only case, any advantage yields an advantage
-in distinguishing the FD-PRNG used from a uniform distribution,
- in which case we are done. 
-In the refresh only case, any advantage yields an advantage
-in distinguishing from uniform the compostion of the FD-PRF and ECDH
- used, in which case we  conclude by Lemma \ref{PRF_composed_wth_ECDH}.
-In mixed cases, we obtian one of the same two conclusions,
- by Lemma \ref{interleaved}.
-\end{proof}
+%We can describe a simple blinding game for an RSA key pair $(n,e,d)$ and
+%generators $M(\cdot)$ and $B(\cdot)$ for elements of $\Z/n\Z$ whose
+%parameters we need not specify: 
+%We take $m_0,m_1$ from $M$ and $b_0,b_1$ from $B$ and give our adversary
+%$\cal A$ the unordered pairs of withdrawals $\{ m_0^d b_0, m_1^d b_1 \}$
+%and deposits $\{ m_0^d, m_1^d \}$.  $\cal A$ wins if it can correctly
+%match the withdrawals and deposits.
+%
+%\begin{lemma}\label{RSA_blind_signatures}
+%Assume adversary $\cal A$ with an advantage in this blinding game for
+%some $M_0(\cdot)$ and $B_0(\cdot)$ whatever their parameters.  There is
+%a machine $\cal A'$ that identifies $B_0$ as opposed to a uniform
+%distribution $U(Z/nZ)$ on $Z/nZ$.
+%\end{lemma}
+%
+%\begin{proof}
+%$\cal A'$ plays the blinding game with $\cal A$ taking $M$ to be $M_0$
+%and $B$ to be $X$.  $\cal A$ either guesses correctly or incorrectly.
+%If $\cal A$ guesses correctly, then $\cal A'$ guesses that yes $X$ is
+%$B_0$.
+%
+%If $X$ is $B_0$ then $\cal A$ guesses correctly with advantage $\epsilon$, meaning
+%  $P[ \textrm{$\cal A$ correct} | X=B_0 ] = 1/2+\epsilon$
+%and
+%  $P[ \textrm{$\cal A$ correct} | X=U ] = 1/2$.
+%We imagine A' is given uniform trials to guess X=F vs X=U, so that
+%  $P[X=F] = 1/2$ too,
+%and 
+%  $P[\textrm{$\cal A$ correct}] = 1/2 + \epsilon/2$.
+%Now $\cal A'$ has an advantage in guessing if $X$ is $B_0$ or uniform correctly by
+%Bays rule
+%  $P[ \textrm{$\cal A$ correct} | X=B_0 ] P[X=B_0] = P[ X=B_0 | \textrm{$\cal A$ correct} ] P[A correct]$
+%so
+%  $P[ X=F | \textrm{$\cal A$ correct} ]
+%  = 1/2 (1/2+\epsilon) / (1/2 + \epsilon/2)
+%  = (1/2+\epsilon) / (1+\epsilon)
+%  = 1 - 1/2 / (1+\epsilon)$.
+%\end{proof}
+%
+%\begin{lemma}\label{interleaved}
+%Let $X$ and $Y$ denote generators for elements in $\Z/n\Z$, taking
+%unspecified parameters.  Let $I$ denote an interleaved sequence from
+%$X$ and $Y$ taking concatenated parameters.  If some adversary has
+%a non-ngeligable advnatage in distinguishing $I$ from $U(Z/nZ)$
+%then some adversary has a non-ngeligable advnatage in distinguishing
+%$J$ from $U(Z/nZ)$ wher eitehr $J=X$ or $J=Y$.
+%\end{lemma}
+%
+%\begin{proof}
+%Exercise for the reader.
+%\end{proof}
+%
+%\begin{lemma}\label{PRF_composed_wth_ECDH}
+%...
+%\end{lemma}
+%
+%\begin{proof}
+%...
+%\end{proof}
+%
+%\begin{theorem}
+%
+%... $\cal A$ ...
+%\end{theorem}
+%
+%\newcommand\pkCoin{pkCoin}
+%
+%\begin{proof}[Proof-ish]
+%We consider the coin $\pkCoin$ of $U_b$ selected and spent by the
+%game/environment starting from line 5, as well as the coin of
+%$U_{1-b}$ that was unspent unshared in line 5, denoted $\pkCoin'$.
+%
+%We cannot corrupt either $U_0$ or $U_1$ nor share either $\pkCoin$ or
+%$\pkCoin'$.  We may however add a spend or refresh of $\pkCoin'$ if
+%$\cal A$ does not do so.  It follows that an advantage for $\cal A$
+%in guessing $b'$ for our anonymity game yields an advantage in the
+%blinding game given by the creation of $\pkCoin$ and $\pkCoin'$ in
+%line 2 together with spending them in line 6. % and their deposit in line 7 
+%
+%In creating each of $\pkCoin$ and $\pkCoin'$, $\cal A$ either
+%(1) invokes the withdrawal oracle directly, or else (2) applies the
+%refresh oracle to some previous withdrawn coin.  These invokations
+%together provide the $B_0$ in Lemma \ref{RSA_blind_signatures}.
+%It follows that a non-negligable advantage for $\cal A$ yields a
+%non-negligable advantage for the adversary $\cal A'$ who distinguishes
+%this $B_0$ from a uniform distribution $U(Z/nZ)$ on $Z/nZ$.
+%We cannot know if $\cal A$ constructs $B_0$ with direct withdrawals,
+%refresh operations, or both.
+%
+%In the direct withdrawal only case, any advantage yields an advantage
+%in distinguishing the FD-PRNG used from a uniform distribution,
+% in which case we are done. 
+%In the refresh only case, any advantage yields an advantage
+%in distinguishing from uniform the compostion of the FD-PRF and ECDH
+% used, in which case we  conclude by Lemma \ref{PRF_composed_wth_ECDH}.
+%In mixed cases, we obtian one of the same two conclusions,
+% by Lemma \ref{interleaved}.
+%\end{proof}