From 672c66b9b54ca29cdae44b4045bda26a63f68e2a Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Fri, 17 Nov 2017 02:28:26 +0100 Subject: notation/labels, comment out Jeff's proof for now --- games/games.tex | 219 ++++++++++++++++++++++++++++++-------------------------- 1 file changed, 116 insertions(+), 103 deletions(-) (limited to 'games') diff --git a/games/games.tex b/games/games.tex index b351067..ba9dfef 100644 --- a/games/games.tex +++ b/games/games.tex @@ -155,6 +155,9 @@ Anonymity game with adversary $\prt{A}$. Let \oraSet{Anon} stand for access to the oracles \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend}, \ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient} +\bigskip +\noindent $\mathit{Exp}_{\prt{A}}^{anon}(1^\lambda, \kappa)$: +\vspace{-0.5\topsep} \begin{enumerate} \setlength\itemsep{0em} \item $(\V{skE}, \V{pkE}) \leftarrow \prt{A}()$ @@ -213,11 +216,16 @@ allowing them to talk to themselves does not make sense. \subsection{Fairness} Intuition: Adversary wins if a non-corrupted user can't obtain a proof-of-spending or unlinkable change. +Let \oraSet{Fair} stand for access to the oracles \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend}, +\ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient} +\bigskip +\noindent $\mathit{Exp}_{\prt{A}}^{fair}(1^\lambda, \kappa)$: +\vspace{-0.5\topsep} \begin{enumerate} \setlength\itemsep{0em} \item $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ - \item $C_0 \leftarrow \prt{A}^{\ora{*}}(pkExchange)$ + \item $C_0 \leftarrow \prt{A}^{\oraSet{Fair}}(pkExchange)$ \item Let $U$ be the user that has $C_0$ in their wallet. If no such $U$ exists, return 0. \item Let $C_0, \dots, C_n$ be the coins reachable via \algo{Link} from $C_0$. \comment{When $C_0$ was not refreshed, $n=0$ and $C_n = C_0$} @@ -234,13 +242,19 @@ Intuition: Adversary wins if a non-corrupted user can't obtain a proof-of-spendi \subsection{Income Transparency} Intuition: Adversary wins if money is in exclusive control of corrupted players but the exchange has no record of withdrawal or spending for it. +Let \oraSet{Income} stand for access to the oracles \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend}, +\ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient} + +\bigskip +\noindent $\mathit{Exp}_{\prt{A}}^{income}(1^\lambda, \kappa)$: +\vspace{-0.5\topsep} \begin{enumerate} \setlength\itemsep{0em} - \item $(skExchange, pkExchange) \leftarrow \mathrm{EKeygen}()$ - \item $(C_1, \dots, C_\ell) \leftarrow \mathcal{A}^{\ora{Withdraw}}(pkExchange)$ + \item $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ + \item $(C_1, \dots, C_\ell) \leftarrow \mathcal{A}^{\oraSet{Income}}(pkExchange)$ \item wallets of all non-corrupted users are augmented with their transitive closure via the \algo{Link} protocol \item all coins from wallets of non-corrupted users are marked as spent - \item let $V_r$ be the number of valid non-spent coins in $(C_1, \dots, C_\ell)$ and $V_w$ the number of coins withdrawn by corrupted users + \item let $V_r$ be the number of valid non-spent coins in $(C_1, \dots, C_\ell)$ and $V_w$ the number of coins withdrawn by corrupted users \item adversary wins if $V_r > V_w$. \end{enumerate} @@ -295,105 +309,104 @@ Let $G \in \mathbb{E}$ be the generator of the Ed25519 curve (with Edwards coord - -We can describe a simple blinding game for an RSA key pair $(n,e,d)$ and -generators $M(\cdot)$ and $B(\cdot)$ for elements of $\Z/n\Z$ whose -parameters we need not specify: -We take $m_0,m_1$ from $M$ and $b_0,b_1$ from $B$ and give our adversary -$\cal A$ the unordered pairs of withdrawals $\{ m_0^d b_0, m_1^d b_1 \}$ -and deposits $\{ m_0^d, m_1^d \}$. $\cal A$ wins if it can correctly -match the withdrawals and deposits. - -\begin{lemma}\label{RSA_blind_signatures} -Assume adversary $\cal A$ with an advantage in this blinding game for -some $M_0(\cdot)$ and $B_0(\cdot)$ whatever their parameters. There is -a machine $\cal A'$ that identifies $B_0$ as opposed to a uniform -distribution $U(Z/nZ)$ on $Z/nZ$. -\end{lemma} - -\begin{proof} -$\cal A'$ plays the blinding game with $\cal A$ taking $M$ to be $M_0$ -and $B$ to be $X$. $\cal A$ either guesses correctly or incorrectly. -If $\cal A$ guesses correctly, then $\cal A'$ guesses that yes $X$ is -$B_0$. - -If $X$ is $B_0$ then $\cal A$ guesses correctly with advantage $\epsilon$, meaning - $P[ \textrm{$\cal A$ correct} | X=B_0 ] = 1/2+\epsilon$ -and - $P[ \textrm{$\cal A$ correct} | X=U ] = 1/2$. -We imagine A' is given uniform trials to guess X=F vs X=U, so that - $P[X=F] = 1/2$ too, -and - $P[\textrm{$\cal A$ correct}] = 1/2 + \epsilon/2$. -Now $\cal A'$ has an advantage in guessing if $X$ is $B_0$ or uniform correctly by -Bays rule - $P[ \textrm{$\cal A$ correct} | X=B_0 ] P[X=B_0] = P[ X=B_0 | \textrm{$\cal A$ correct} ] P[A correct]$ -so - $P[ X=F | \textrm{$\cal A$ correct} ] - = 1/2 (1/2+\epsilon) / (1/2 + \epsilon/2) - = (1/2+\epsilon) / (1+\epsilon) - = 1 - 1/2 / (1+\epsilon)$. -\end{proof} - -\begin{lemma}\label{interleaved} -Let $X$ and $Y$ denote generators for elements in $\Z/n\Z$, taking -unspecified parameters. Let $I$ denote an interleaved sequence from -$X$ and $Y$ taking concatenated parameters. If some adversary has -a non-ngeligable advnatage in distinguishing $I$ from $U(Z/nZ)$ -then some adversary has a non-ngeligable advnatage in distinguishing -$J$ from $U(Z/nZ)$ wher eitehr $J=X$ or $J=Y$. -\end{lemma} - -\begin{proof} -Exercise for the reader. -\end{proof} - -\begin{lemma}\label{PRF_composed_wth_ECDH} -... -\end{lemma} - -\begin{proof} -... -\end{proof} - -\begin{theorem} - -... $\cal A$ ... -\end{theorem} - -\newcommand\pkCoin{pkCoin} - -\begin{proof}[Proof-ish] -We consider the coin $\pkCoin$ of $U_b$ selected and spent by the -game/environment starting from line 5, as well as the coin of -$U_{1-b}$ that was unspent unshared in line 5, denoted $\pkCoin'$. - -We cannot corrupt either $U_0$ or $U_1$ nor share either $\pkCoin$ or -$\pkCoin'$. We may however add a spend or refresh of $\pkCoin'$ if -$\cal A$ does not do so. It follows that an advantage for $\cal A$ -in guessing $b'$ for our anonymity game yields an advantage in the -blinding game given by the creation of $\pkCoin$ and $\pkCoin'$ in -line 2 together with spending them in line 6. % and their deposit in line 7 - -In creating each of $\pkCoin$ and $\pkCoin'$, $\cal A$ either -(1) invokes the withdrawal oracle directly, or else (2) applies the -refresh oracle to some previous withdrawn coin. These invokations -together provide the $B_0$ in Lemma \ref{RSA_blind_signatures}. -It follows that a non-negligable advantage for $\cal A$ yields a -non-negligable advantage for the adversary $\cal A'$ who distinguishes -this $B_0$ from a uniform distribution $U(Z/nZ)$ on $Z/nZ$. -We cannot know if $\cal A$ constructs $B_0$ with direct withdrawals, -refresh operations, or both. - -In the direct withdrawal only case, any advantage yields an advantage -in distinguishing the FD-PRNG used from a uniform distribution, - in which case we are done. -In the refresh only case, any advantage yields an advantage -in distinguishing from uniform the compostion of the FD-PRF and ECDH - used, in which case we conclude by Lemma \ref{PRF_composed_wth_ECDH}. -In mixed cases, we obtian one of the same two conclusions, - by Lemma \ref{interleaved}. -\end{proof} +%We can describe a simple blinding game for an RSA key pair $(n,e,d)$ and +%generators $M(\cdot)$ and $B(\cdot)$ for elements of $\Z/n\Z$ whose +%parameters we need not specify: +%We take $m_0,m_1$ from $M$ and $b_0,b_1$ from $B$ and give our adversary +%$\cal A$ the unordered pairs of withdrawals $\{ m_0^d b_0, m_1^d b_1 \}$ +%and deposits $\{ m_0^d, m_1^d \}$. $\cal A$ wins if it can correctly +%match the withdrawals and deposits. +% +%\begin{lemma}\label{RSA_blind_signatures} +%Assume adversary $\cal A$ with an advantage in this blinding game for +%some $M_0(\cdot)$ and $B_0(\cdot)$ whatever their parameters. There is +%a machine $\cal A'$ that identifies $B_0$ as opposed to a uniform +%distribution $U(Z/nZ)$ on $Z/nZ$. +%\end{lemma} +% +%\begin{proof} +%$\cal A'$ plays the blinding game with $\cal A$ taking $M$ to be $M_0$ +%and $B$ to be $X$. $\cal A$ either guesses correctly or incorrectly. +%If $\cal A$ guesses correctly, then $\cal A'$ guesses that yes $X$ is +%$B_0$. +% +%If $X$ is $B_0$ then $\cal A$ guesses correctly with advantage $\epsilon$, meaning +% $P[ \textrm{$\cal A$ correct} | X=B_0 ] = 1/2+\epsilon$ +%and +% $P[ \textrm{$\cal A$ correct} | X=U ] = 1/2$. +%We imagine A' is given uniform trials to guess X=F vs X=U, so that +% $P[X=F] = 1/2$ too, +%and +% $P[\textrm{$\cal A$ correct}] = 1/2 + \epsilon/2$. +%Now $\cal A'$ has an advantage in guessing if $X$ is $B_0$ or uniform correctly by +%Bays rule +% $P[ \textrm{$\cal A$ correct} | X=B_0 ] P[X=B_0] = P[ X=B_0 | \textrm{$\cal A$ correct} ] P[A correct]$ +%so +% $P[ X=F | \textrm{$\cal A$ correct} ] +% = 1/2 (1/2+\epsilon) / (1/2 + \epsilon/2) +% = (1/2+\epsilon) / (1+\epsilon) +% = 1 - 1/2 / (1+\epsilon)$. +%\end{proof} +% +%\begin{lemma}\label{interleaved} +%Let $X$ and $Y$ denote generators for elements in $\Z/n\Z$, taking +%unspecified parameters. Let $I$ denote an interleaved sequence from +%$X$ and $Y$ taking concatenated parameters. If some adversary has +%a non-ngeligable advnatage in distinguishing $I$ from $U(Z/nZ)$ +%then some adversary has a non-ngeligable advnatage in distinguishing +%$J$ from $U(Z/nZ)$ wher eitehr $J=X$ or $J=Y$. +%\end{lemma} +% +%\begin{proof} +%Exercise for the reader. +%\end{proof} +% +%\begin{lemma}\label{PRF_composed_wth_ECDH} +%... +%\end{lemma} +% +%\begin{proof} +%... +%\end{proof} +% +%\begin{theorem} +% +%... $\cal A$ ... +%\end{theorem} +% +%\newcommand\pkCoin{pkCoin} +% +%\begin{proof}[Proof-ish] +%We consider the coin $\pkCoin$ of $U_b$ selected and spent by the +%game/environment starting from line 5, as well as the coin of +%$U_{1-b}$ that was unspent unshared in line 5, denoted $\pkCoin'$. +% +%We cannot corrupt either $U_0$ or $U_1$ nor share either $\pkCoin$ or +%$\pkCoin'$. We may however add a spend or refresh of $\pkCoin'$ if +%$\cal A$ does not do so. It follows that an advantage for $\cal A$ +%in guessing $b'$ for our anonymity game yields an advantage in the +%blinding game given by the creation of $\pkCoin$ and $\pkCoin'$ in +%line 2 together with spending them in line 6. % and their deposit in line 7 +% +%In creating each of $\pkCoin$ and $\pkCoin'$, $\cal A$ either +%(1) invokes the withdrawal oracle directly, or else (2) applies the +%refresh oracle to some previous withdrawn coin. These invokations +%together provide the $B_0$ in Lemma \ref{RSA_blind_signatures}. +%It follows that a non-negligable advantage for $\cal A$ yields a +%non-negligable advantage for the adversary $\cal A'$ who distinguishes +%this $B_0$ from a uniform distribution $U(Z/nZ)$ on $Z/nZ$. +%We cannot know if $\cal A$ constructs $B_0$ with direct withdrawals, +%refresh operations, or both. +% +%In the direct withdrawal only case, any advantage yields an advantage +%in distinguishing the FD-PRNG used from a uniform distribution, +% in which case we are done. +%In the refresh only case, any advantage yields an advantage +%in distinguishing from uniform the compostion of the FD-PRF and ECDH +% used, in which case we conclude by Lemma \ref{PRF_composed_wth_ECDH}. +%In mixed cases, we obtian one of the same two conclusions, +% by Lemma \ref{interleaved}. +%\end{proof} -- cgit v1.2.3