From 54279b7657aafe8b0ce2af85e1842d21ec9864df Mon Sep 17 00:00:00 2001 From: Jeff Burdges Date: Mon, 23 Apr 2018 02:28:56 +0200 Subject: Minor edits in anonymity proof We never write the anonymity game ending up correctly because we delayed writing the proof so long --- games/games.tex | 51 ++++++++++++++++++++++++++------------------------- 1 file changed, 26 insertions(+), 25 deletions(-) (limited to 'games') diff --git a/games/games.tex b/games/games.tex index f85a6d5..eb40ab0 100644 --- a/games/games.tex +++ b/games/games.tex @@ -648,44 +648,45 @@ Let $G \in \mathbb{E}$ be the generator of the Ed25519 curve (with Edwards coord \begin{theorem} - Assuming the existence of a Pseudo-Random Function Family (PRF), DDH, and a collision-resistant hash function, Taler satisfies \emph{Anonymity}. +If Taler's refresh is instantiated with PRF, a key exchange satisfying DDH, + and a collision-resistant hash function, +then Taler satisfies {anonymity}. \end{theorem} \begin{proof} We give a proof via a sequence of games $\mathbb{G}_0(b), \mathbb{G}_1(b), \mathbb{G}_2(b), \mathbb{G}_3(b)$, where $\mathbb{G}_0(b)$ is the original - anonymity game $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, \kappa, b)$. Let - $\epsilon_{PRF}$ and $\epsilon_{DDH}$ be the advantage of an adversary for - the PRF game and DDH game respectively. + anonymity game $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, \kappa, b)$. We show + the adversary can distinguish between subsequent games with only negligible probability. + Let $\epsilon_{PRF}$ and $\epsilon_{DDH}$ be the advantage of an adversary + for the PRF game and DDH game respectively. - In $\mathbb{G}_1$ the game is modified by replacing the link oracle \ora{LinkAsExchange} - by another oracle that behaves the same as \ora{LinkAsExchange} only if the adversary + We define $\mathbb{G}_1$ by replacing the link oracle \ora{Link} with + another oracle that behaves the same as \ora{Link} only if the adversary responds to the customer with link data that has been observed in a previous refresh. If the link data is not recognized by the simulator, the customer is instead given a uniform random value as link data. - Recall that a coin obtained via refresh is only added to the wallet if the link - secret is constructed as $linkSecret = H(nonce, skOldCoin)$. Link secrets that - do not pass this verification are discarded. - - In order to distinguish $\mathbb{G}_0$ from $\mathbb{G}_1$, the adversary must - find a link secret that results in different behavior by the customer with regards - to accepting/rejecting it. The behaviour with previously seen link secrets is identical. - In order to forge a distinguishing link secret, the adversary must either find a hash collision - or find the coin's private key. \comment{Should we fully carry out this reduction, including tightness bound, and if so where?} + In order to distinguish $\mathbb{G}_0$ from $\mathbb{G}_1$, our adversary + must fake a link secret that causes the oracle to return random data leading + to incorrect behavior by the customer. We recall however that link secrets + were constructed as $(\V{nonce}, \V{linkSecret})$ where + $\V{linkSecret} = H(\V{nonce}, \V{skOldCoin})$, + with the customer rejecting link secrets that fail this test. + So our adversary must either find a hash collision or find the coin's private key. In $\mathbb{G}_2$, the refresh oracle is modified so that the user responds with value drawn from a uniform random distribution for the the $\gamma$-th - commitment instead of using a Diffie-Hellman function. Since $\gamma$ is - chosen by the adversary after seeing the commitments, the simulator first - makes a guess $\gamma^*$ and draws a uniform random value only for the - $\gamma^*$-th commitment. If the $\gamma$ chosen by the adversary does not - match $\gamma^*$, the simulator rewinds \prt{A} to the point where the - refresh oracle was called. Note that this succeeds with probability - $1/\kappa + \epsilon_{DDH}$. Since $\kappa \ll \lambda$, the runtime - complexity of the simulator still says polynomial in $\lambda$. Note that we - only replace the one commitment that will not be opened to the adversary - later. \comment{Tighness bound also missing} + commitment instead of using a Diffie-Hellman function. We must handle the + fact that $\gamma$ is chosen by the adversary after seeing the commitments, + so the simulator first makes a guess $\gamma^*$ and + replaces only the $\gamma^*$-th commitment with a uniform random value. + If the $\gamma$ chosen by the adversary does not match $\gamma^*$, then + the simulator rewinds \prt{A} to the point where the refresh oracle was called. + We see this succeeds with probability $1/\kappa + \epsilon_{DDH}$. + Since $\kappa \ll \lambda$, the runtime complexity of the simulator still says + polynomial in $\lambda$. + Note that we only replace the one commitment that will not be opened to the adversary later. \comment{Tighness bound also missing} We now show that $\left| \Prb{\mathbb{G}_1 = 1} - \Prb{\mathbb{G}_2 = 1} \right| \le \epsilon_{DDH}$ by defining a distinguishing game $\mathbb{G}_{1 -- cgit v1.2.3