diff options
author | Jeff Burdges <burdges@gnunet.org> | 2018-04-22 12:54:50 +0200 |
---|---|---|
committer | Jeff Burdges <burdges@gnunet.org> | 2018-04-22 12:54:50 +0200 |
commit | f8313f818306f80a20b2105430208cc013570a53 (patch) | |
tree | 0f4b359bb386ef3c3d8dd6bb7b8c5a299d90c96a /games | |
parent | 7fde0dc1e21c9bfa6971af3ddcae3770534b538e (diff) | |
download | papers-f8313f818306f80a20b2105430208cc013570a53.tar.gz papers-f8313f818306f80a20b2105430208cc013570a53.tar.bz2 papers-f8313f818306f80a20b2105430208cc013570a53.zip |
Start remerging old proof
Diffstat (limited to 'games')
-rw-r--r-- | games/games.tex | 67 |
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'$ |