From 52f7544af0fe33ff9bca40fe98548a7cff2e1536 Mon Sep 17 00:00:00 2001 From: Jeff Burdges Date: Wed, 25 Apr 2018 21:45:16 +0200 Subject: Start adopting optimal adversary langauge --- games/games.tex | 47 ++++++++++++++++++++++++++++++++--------------- 1 file changed, 32 insertions(+), 15 deletions(-) (limited to 'games') 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$, -- cgit v1.2.3