From 08f94f5c542393f7cb7da5a2fc6d5d45ed7d1aa3 Mon Sep 17 00:00:00 2001 From: Jeff Burdges Date: Sun, 22 Apr 2018 17:05:24 +0200 Subject: Fixed income transperency proof and game --- games/games.tex | 91 +++++++++++++++++++++------------------------------------ 1 file 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 -- cgit v1.2.3