Improve income transperency proof

1 files changed, 38 insertions, 18 deletions

diff --git a/games/games.tex b/games/games.tex
index e3b48b4..d479d6a 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -319,10 +319,11 @@ Let \oraSet{Income} stand for access to the oracles \ora{AddClient}, \ora{Withdr
   \item Augment the wallets of all non-corrupted users with their
     transitive closure using the \algo{Link} protocol.
     Mark all coins in wallets of non-corrupted users as spent.
-  \item Let $w$ denote the number of coins withdrawn by corrupted users.
+  \item Let $w$ and $w'$ denote the number of coins withdrawn by
+    corrupted and non-corrupted users, respectively.
     Also let $b$ denote the number of coins lost in refresh operations
     with false planchets.  Our adversary wins if both $\ell > w$ and 
-    ${b \over \ell - w'} \le 1-{1\over\kappa}$ with $C_1, \dots, C_\ell$
+    ${b \over w'} \le 1-{1\over\kappa}$ with $C_1, \dots, C_\ell$
      all being distinct valid unspent coins.
 \end{enumerate}
 
@@ -576,23 +577,42 @@ rewinding $\cal A$ to try each $\gamma \in 1,\ldots,\kappa$ during
 each refresh operation to obtain all planchets.  We observe a hash 
 collision if this fails to provide the correct coins. 
 
-We consider the refresh operations in which $\cal A$ in which
-$\cal A$ submits a false planchets for some choice of $\gamma$. 
-In these, we may assume $\cal A$ submits a false planchet for at most
-one choice of $\gamma$, as otherwise the refresh always fails.
-We let $f$ denote the number of these in which a non-corrupted user
-could obtain the coin consumed in the refresh via the linking protocol.
-It follows from unforgeability that $\ell \le w + f$ because
-any refresh without a false planchet results in that coin being
-obtainable by a non-corrupted user and thus being marked as spent.
-
-As our $\gamma$ are chosen randomly, any given refresh with a false
-planchet has a $1-{1\over\kappa}$ chance of contributing to $b$,
-so $E[{b \over f}] = 1-{1\over\kappa}$.  It follows that 
-$P[{b \over \ell-w} \ge (1-{1\over\kappa})] = 1/2 > {1\over\kappa}$.
-\end{proof}
+We consider the degree one directed graph on coins induced by the
+refresh protocol.  It follows from unforgeability that any coin
+must originate from some user's withdraw in this graph.  
+Let $X$ denote the coins from $\{C_1,\ldots,C_\ell\}$ that originate
+from a non-corrupted user.  So $\ell \leq w + |X|$.
+
+For any $C \in X$, there is a final refresh operation $R_C$ in which
+a non-corrupted user could obtain the coin $C'$ consumed in the refresh
+via the linking protocol, but no non-corrupted user could obtain the
+coin provided by the refresh, as otherwise $C$ gets marked as spend. 
+
+In each $R_C$, we know $\cal A$ must submit a planchet for which the
+linking protocol fails produce $C$ correctly.  In this case, either
+\begin{enumerate}
+\item the planchet must be false outright, meaning either $C$ itself
+or the blinding factor does not arise form $t C'$, or else
+\item  the exchange would compute the planchet correctly, meaning
+$t C' \neq c' T$ where $T = t G$ is the transfer key.
+\end{enumerate}
 
-% injectivity of the ECDH operation seems like a red herring???
+In the second case, there are scalars being handled incorrectly by
+our implementation, like perhaps the exchange accepts and uses an
+incorrectly clamped scalar $t$ without correcting the clamping. 
+
+We may therefore assume the first case that $\cal A$ provides a
+false planchet outright.  We may assume $\cal A$ submits a false
+planchet for at most one choice of $\gamma$,
+as otherwise the refresh always fails.
+
+As our $\gamma$ are chosen randomly, any given refresh with one
+false planchet has a $1-{1\over\kappa}$ chance of contributing to
+$b$ instead of $|X|$.  So $E[{b \over f}] = 1-{1\over\kappa}$ where
+$f \le w'$ denotes the number of refreshes attempted with false planchets.
+It follows that 
+ $P[{b \over w'} \ge (1-{1\over\kappa})] = 1/2 > {1\over\kappa}$.
+\end{proof}
 
 
 \section{Standard Definitions}