Fixed income transperency proof and game

1 files changed, 34 insertions, 57 deletions

diff --git a/games/games.tex b/games/games.tex
index 303be14..f85a6d5 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -499,9 +499,9 @@ Let \oraSet{Income} stand for access to the oracles
   \item Let $w$ be the sum of coins withdrawn by non-corrupted users,
     $w'$ be the sum of coins withdrawn by corruped users, and $s$ be the value marked as spent
     by non-corrupted users.
-    Our adversary wins if $L - w' > 0$.
-  \item Return $(L, w, w', s)$
-  \comment{Big stile break so split into two games.  Return ratio.  Two expectations is wrong. }
+  \item Return $p \over b + p$ where $b := w - s$ gives the lost coins and $p := L - w'$ gives the adversary's winnings.
+    Also, we note our adversary wins the strong income transparency game if $L - w' > 0$.
+  \comment{$(L, w, w', s)$  Big stile break so split into two games.  Return ratio.  Two expectations is wrong. }
 \end{enumerate}
 
 The adversary is said to win the Income Transparency game if $L - w' > 0$.
@@ -825,19 +825,28 @@ We therefore conclude that RSA-KTI cannot be hard itself
 \begin{definition}
 A {\em key exchange failure} consists of two key pairs
  $A = a G$ and $B = b G$ such that $b A \neq a B$.
+\comment{TODO: PPA, ??? = enough for PRF, }
 \comment{TODO: Find this in literature?  Is it related to contributory behavior?}
 \end{definition}
 
+\comment{TODO: Abstract key exchange, also below.  Explain key exchange failures elsewhere.}
+\comment{In theory, our scalar multiplication should be injective, preventing
+	the second case where $t C' \neq c' T$.  In practice, our exchange 
+	might incorrectly have multiple scalar representatives $t$ yield the
+	same curve point $t C'$, while the user's canonical computation of
+	$c' T$ yields a distinct point, like perhaps the exchange accepts and
+	uses an incorrectly clamped scalar $t$ without correcting the clamping itself. 
+}
+
 \begin{theorem}
-Assuming
+We assume Taler both satisfies unforgeability and is instantiated with
 \begin{enumerate}
-\item Unforgeability
-\item a collision-resistant hash function
+\item a collision-resistant hash functions for planchet commitments, and
+\item a key exchange secure against failures in the refresh.
 \end{enumerate}
-Taler satisfies {Weak Income Transparency}.
+Then Taler satisfies {weak income transparency}.
 \end{theorem}
 
-
 \begin{proof}
 In our actual refresh operation, our commitment phase sends only the
 hash of the planchets to reduce bandwidth.  We could however commit
@@ -869,65 +878,33 @@ linking protocol fails to produce $C$ correctly.  In this case, either
       $t C' \neq c' T$ where $T = t G$ is the transfer key.
 \end{enumerate}
 
-TODO: Abstract key exchange, maybe explain key exchange failures elsewhere.
-
-In theory, our scalar multiplication should be injective, preventing
-the second case where $t C' \neq c' T$.  In practice, our exchange 
-might incorrectly have multiple scalar representatives $t$ yield the
-same curve point $t C'$, while the user's canonical computation of
-$c' T$ yields a distinct point, like perhaps the exchange accepts and
-uses an incorrectly clamped scalar $t$ without correcting the clamping itself. 
-
-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$,
+We may assume the first case that $\cal A$ provides a false planchet outright
+ because we produce a key exchange failure in the second case.
+We may also assume $\cal A$ submits a false planchet for at most one choice of $\gamma$,
 as otherwise the refresh always fails.
 
-FIX ALL THE VALUES
-
 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|$, as desired.
-It now follows that
-$E[{b \over l-w}] \ge E[{b \over f}] = 1-{1\over\kappa}$
-where $f \ge l-w$ denotes
-the number of refreshes attempted with false planchets.
+false planchet has only a $1\over\kappa$ chance of succeeding.
+If such a malicious refresh is detected, the coin is unspendable, and
+ contributes to the lost coins $b := w - s$ instead of the winnings $p := L - w'$ aka $|X|$.
+
+We observe $b + p$ gives the value of refreshes attempted with false planchets.
+If we sequentially group runs of the game according to the simulator's random choice of $\gamma$,
+then we conclude that $E({p \over b + p}) = {1\over\kappa}$, as desired.
 \end{proof}
+%%% $L - w' \over (L - w') + (w - s)$
+% $E(b/p) + 1 = E(b/p + p/p) = E((b + p)/p) = \kappa$
+% $E(b/p) = \kappa-1$
+% $E(p/b) = {1 \over \kappa-1}$
 
 \begin{corollary}
 In the random oracle model,
-if the RSA known-target inversion problem (RSA-KTI) is hard, then
-Taler is polynomially-secure against profitable attacks on
-income transparency.
+if the RSA known-target inversion problem (RSA-KTI) is hard,
+and refresh is instantiated with a key exchange secure against failures,
+then Taler satisfies {weak income transparency}.
 \end{corollary}
 
 
-\begin{proof}
-Recall that the adversary must show that they have exclusive control over coins with value $L$. We must assume that either
-\ora{Refresh}, \ora{Link}, \ora{Share} or \ora{Withdraw} was used to obtain these coins, otherwise the adversary could be used to win break unforgeability.  TOO FAST... $L - w'$
-
-Since the adversary only wins if $L - w' > 0$, the adversary could not have
-withdrawn this value with corrupted users.
-
-Access to \ora{LinkAsUser} only gives the adversary access to coins that are already in wallets of (honest) users, and are thus lost in step 3 of the game.
-
-The only remaining possibility to obtain coins is via \ora{RefreshAsExchange} and \ora{Share}.  Specifically the adversary must try to gain exclusive ``ownership''
-of a coin whose private key was previously obtained via \ora{Share}, since sharing alone would result in the adversary losing the coin in step 3 of the game.
-To do this, they must change the transfer private key, so that the Link protocol will fail to recover the refreshed coin for non-corrupted users.
-
-An adversary that can find hash collisions could break the commitment, but this violates our assumption.  The only remaining possibility is
-to inject a transfer public key that would fail verification, and hope that the exchange selects the commitment with this index
-as the one of $\kappa$ indexes that won't be revealed.
-
-This strategy has $1/\kappa$ chance of succeeding.  If such a malicious refresh is detected, the coin is unspendable, and contributes to the lost coins $w - s$.
-Thus in order to gain exclusive control over coins with value $L - w'$, the expected number of lost coins is at least $\kappa * (w - s)$.  This proves
-our bound of $\kappa E[w-s] \ge E[L-w']$.
-
-
-
-\end{proof}
-
-
 \section{Standard Definitions}
 \begin{definition}[One-more forgery]
 For any integer $\ell$, an $(\ell, \ell + 1)$-forgery comes from