summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJeff Burdges <burdges@gnunet.org>2018-04-25 21:45:16 +0200
committerJeff Burdges <burdges@gnunet.org>2018-04-25 21:45:16 +0200
commit52f7544af0fe33ff9bca40fe98548a7cff2e1536 (patch)
tree3856f0558134f7692347cd50708398fc296e646a
parentbad189ee87a5724a79622b0fe0e07ed3620fe068 (diff)
downloadpapers-52f7544af0fe33ff9bca40fe98548a7cff2e1536.tar.gz
papers-52f7544af0fe33ff9bca40fe98548a7cff2e1536.tar.bz2
papers-52f7544af0fe33ff9bca40fe98548a7cff2e1536.zip
Start adopting optimal adversary langauge
-rw-r--r--games/games.tex47
1 files changed, 32 insertions, 15 deletions
diff --git a/games/games.tex b/games/games.tex
index a609624..72c1793 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -899,27 +899,44 @@ linking protocol fails to produce $C$ correctly. In this case, either
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.
-As our $\gamma$ are chosen randomly, any given refresh with one
-false planchet has only a $1\over\kappa$ chance of succeeding.
-% We recall ... MAYBE COPY FROM REMOVED TEXT IN cf4086163362d68011d093bc683732bacac5aba1
-If such a malicious refresh is detected, the coin becomes 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. Of course $p = 0$ and $b = 0$ if the adversary never
-uses false planchets, i.e. no $R_C$ occur, leaving $p \over b + p$ undefined.
+We shall prove $E({p \over b + p} | X \neq \emptyset) \le {1\over\kappa}$ (\dag)
+with the expectation taken over games with false planchets, meaning
+ any probability space used by the adversary,
+ times the uniform distribution on exchange keys $\V{skE}$,
+ times the space of $\gamma$ choices by the exchange,
+ i.e. the uniform distribution on $\kappa^X$.
+
+We shall optimizes our adversary in ways that improve its $p \over b + p$.
+We cannot actually produce this optimized adversary ourselves,
+ but its existence suffices to prove the inequality (\dag).
+
+As a reminder,
+if a refresh $R_C$ with $C\in X$ is observed using a false planchet,
+then the coin $C$ becomes unspendable, and contributes to
+the lost coins $b := w - s$ instead of the winnings $p := L - w'$ aka $|X|$.
+We also note $b + p$ gives the value of refreshes attempted with
+false planchets. As these are positive, $p \over b + p$ undefined
+if and only if $p = 0$ and $b = 0$, which happens if and only if
+the adversary does not use false planchets, i.e. $X = \emptyset$.
+
+We may now assume for optimality that $\cal A$ submits a false planchet
+for at most one choice of $\gamma$ in $R_C$,
+ as otherwise the refresh always fails.
+
+% As our $\gamma$ are chosen randomly, any given refresh with one
+% false planchet has only a $1\over\kappa$ chance of succeeding.
+% % We recall ... MAYBE COPY FROM REMOVED TEXT IN cf4086163362d68011d093bc683732bacac5aba1
We defined $R_C$ to be an anti-chain in the refresh forest, but
-emphasize that an adversary who wins an $R_C$ should not gamble again,
-while an adversary who looses an $R_C$ looses $C$ completely.
+emphasize that an adversary who looses an $R_C$ looses $C$ completely,
+while an optimal adversary who wins an $R_C$ should not gamble again.
There is no way to influence $p$ or $b$ through withdrawals or spends
by corrupted users of course. In principle, one could decrease $b$ by
sharing from a corrupted user to a non-corrupted users,
-but we may assume this does not occur either.
+but we may assume this does not occur either, again by optimality.
+
+
We obtain a valid game run by terminating a game early, or even by
blocking oracle calls on decedents of a particular coin $C$,