summaryrefslogtreecommitdiff
path: root/games
diff options
context:
space:
mode:
authorJeff Burdges <burdges@gnunet.org>2018-04-22 12:54:50 +0200
committerJeff Burdges <burdges@gnunet.org>2018-04-22 12:54:50 +0200
commitf8313f818306f80a20b2105430208cc013570a53 (patch)
tree0f4b359bb386ef3c3d8dd6bb7b8c5a299d90c96a /games
parent7fde0dc1e21c9bfa6971af3ddcae3770534b538e (diff)
downloadpapers-f8313f818306f80a20b2105430208cc013570a53.tar.gz
papers-f8313f818306f80a20b2105430208cc013570a53.tar.bz2
papers-f8313f818306f80a20b2105430208cc013570a53.zip
Start remerging old proof
Diffstat (limited to 'games')
-rw-r--r--games/games.tex67
1 files changed, 66 insertions, 1 deletions
diff --git a/games/games.tex b/games/games.tex
index 9767403..f5c7b8e 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -761,7 +761,7 @@ by the user. In either case, we can extract a forged signature and use \prt{A}
\begin{theorem}
In the random oracle model,
if the RSA known-target inversion problem (RSA-KTI) is hard, then
-Taler satisfies {Unforgeability}.
+Taler satisfies {unforgeability}.
% by probabilistic polynomially time adversaries.
\end{theorem}
@@ -834,6 +834,71 @@ Assuming
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
+to the full planchets without damaging anything else, including
+unforgeability. We may thus transform our our adversary $\cal A$ into
+any adversary for the protocol that commits to full planchets by
+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 directed tree 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 to 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, but not
+ users employing the linking protocol, meaning
+ $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$,
+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.
+\end{proof}
+
+\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.
+\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'$