Progress on anonymity proof

1 files changed, 104 insertions, 0 deletions

diff --git a/games/games.tex b/games/games.tex
index 82825cc..c3b88f0 100644
--- a/games/games.tex
+++ b/games/games.tex
@@ -245,6 +245,109 @@ given in literature.
 \section{Proofs}
 
 \subsection{Anonymity}
+
+
+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}
+
+\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 \red{PRF_composed_wth_ECDH}.
+In mixed cases, we obtian one of the same two conclusions,
+ by Lemma \ref{interleaved}.
+\end{proof}
+
+
+
+
+
 \paragraph{``Proof sketch''.}  Proof by looking at withdraw/deposit/refresh transcripts seen by the adversary.  Do game hopping, replace
 everything that's not random by something random (with computationally indistinguishable distribution) until everything that the adversary
 could see in a game has the same probability, and he must win with probability $1/2$.
@@ -314,6 +417,7 @@ From \cite{bellare2003onemore}.  Assumption to prove security of RSA blind signa
   \item We trivially get endorsed e-cash, should we add the games / definitions?
 \end{itemize}
 
+
 \bibliography{lit}
 \bibliographystyle{alpha}