X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/tripe/blobdiff_plain/a50a1fa9e7b97ef6fe4aced1567b0bafdd5f4bd8..1a981bdb7da1f52ca5639e59610425f9d30ae860:/doc/wrestlers.tex

diff --git a/doc/wrestlers.tex b/doc/wrestlers.tex
index 033f9fea..a37b6435 100644
--- a/doc/wrestlers.tex
+++ b/doc/wrestlers.tex
@@ -1,6 +1,6 @@
 %%% -*-latex-*-
 %%%
-%%% $Id: wrestlers.tex,v 1.3 2001/06/22 19:41:31 mdw Exp $
+%%% $Id: wrestlers.tex,v 1.4 2001/06/29 19:36:05 mdw Exp $
 %%%
 %%% Description of the Wrestlers Protocol
 %%%
@@ -10,6 +10,9 @@
 %%%----- Revision history ---------------------------------------------------
 %%%
 %%% $Log: wrestlers.tex,v $
+%%% Revision 1.4  2001/06/29 19:36:05  mdw
+%%% Some progress made on laptop.
+%%%
 %%% Revision 1.3  2001/06/22 19:41:31  mdw
 %%% Restart with different structure and rather more formal objectives.
 %%%
@@ -20,9 +23,11 @@
 %%% Initial versions of documentation.
 %%%
 
-\documentclass{article}
+\documentclass[a4paper]{article}
+\usepackage{a4wide}
 \usepackage{amssymb}
 \usepackage{amstext}
+\usepackage{mdwtab}
 
 \errorcontextlines=999
 \makeatletter
@@ -34,7 +39,7 @@
 
 \newtheorem{theorem}{Theorem}
 \newenvironment{proof}[1][Proof]{%
-  \par\noindent\textbf{#1.} %
+  \par\noindent\textbf{#1}\ %
 }{%
   \penalty\@M\hfill\vadjust{}%
   \penalty\z@\relax\vadjust{}%
@@ -42,6 +47,21 @@
   \par%
 }
 
+\newcommand{\rgets}{\stackrel{\scriptscriptstyle R}{\gets}}
+\newcommand{\oracle}[1]{\mathcal{#1}}
+
+\newcommand{\expt}[2]{\mathbf{Exp}^{\text{\normalfont#1}}_{#2}}
+\newcommand{\adv}[2]{\mathbf{Adv}^{\text{\normalfont#1}}_{#2}}
+\newcommand{\ord}{\mathop{\operator@font ord}}
+\newcommand{\poly}{\mathrm{poly}}
+\newcommand{\compind}{\stackrel{c}{\approx}}
+
+\newcolumntype{G}{p{0pt}}
+
+\newenvironment{program}
+  {\begin{tabbing}}
+  {\end{tabbing}}
+
 \begin{document}
 
 \maketitle
@@ -65,13 +85,142 @@
 % authentication oracle is useless if the hash function has appropriate
 % properties.
 
-Suppose that $G$ is some cyclic group of order $q$, generated by an element
-$g$, in which the decision Diffie-Hellman problem \cite{Boneh:1998:DDP} is
-hard.  Alice can choose a private key $1 < \alpha < q$ and publish her
-corresponding public key $A = g^\alpha$.  Later, Bob can verify that he's
-talking to Alice by choosing a random $1 < \beta < q$ and sending Alice a
-\emph{challenge} $B = g^\beta$.  If she replies with $B^\alpha$, Bob accepts
-that he's talking to Alice, otherwise he doesn't.
+We start by introducing a simple proof-of-identity protocol, based on the
+Diffie-Hellman key-exchange protocol \cite{Diffie:1976:NDC} and prove some of
+its useful properties.
+
+\subsection{Introduction}
+
+Suppose that $G$ is some cyclic group of prime order $q$, generated by an
+element $g$, in which the decision Diffie-Hellman problem
+\cite{Boneh:1998:DDP} is hard.
+
+Alice can choose a private key $1 < \alpha < q$ and publish her corresponding
+public key $A = g^\alpha$.
+
+A simplistic proof-of-identity protocol might then proceed as follows:
+\begin{enumerate}
+\item Bob chooses a random exponent $1 < \beta < q$, and sends a
+  \emph{challenge} $B = g^\beta$ to Alice.
+\item Alice computes $B^\alpha$ and returns it to Bob.
+\item If Alice's response is equal to $A^\beta$ then Bob is satisfied.
+\end{enumerate}
+This is evidently secure if the Diffie-Hellman problem is hard: computing
+$g^{\alpha\beta}$ given $g^\alpha$ and $g^\beta$ is precisely the
+Diffie-Hellman problem.
+
+This protocol has a flaw, though: by using Alice as an oracle for the
+function $x \mapsto x^\alpha$, he could conceivably acquire information about
+Alice's private key which he could later use to impersonate her.  As an
+example, Bob can submit $-g^\beta$ as a challenge: if the reply
+$(-g^\beta)^\alpha = g^{\alpha\beta}$, Bob can conclude that $\alpha$ is
+even.
+
+We fix this protocol by requiring that Bob prove that he already knows the
+answer to his challenge.  Instead of sending just his challenge $B$, he sends
+the pair $(B, h(A^\beta))$ for some function $h$: Alice verifies that
+$h(B^\alpha) = h(A^\beta)$ before returning her response.  We need to choose
+the function $h$ such that
+\begin{itemize}
+\item $h$ is one-way, so that providing $h(A^\beta)$ doesn't provide an
+  impersonator with an additional clue to guessing the correct response; and
+\item providing $h(A^\beta)$ is hard without previously knowing the value of
+  $A^\beta$.
+\end{itemize}
+
+\subsection{Analysis}
+
+We now examine the protocol in a more formal setting, with the objective of
+characterizing our requirements for the function $\oracle{H}$.  Fix a
+\emph{group description} $\mathcal{G} = (G, q, g)$, where $G$ is a cyclic
+group of prime order $q$ generated by $g \in G$, and a function
+$\oracle{H}\colon \{ 0, 1 \}^* \to \{ 0, 1 \}^L$.  Define the
+\emph{authentication oracle} $\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, x,
+h)$, where $\alpha \in \mathbb{Z} / q \mathbb{Z}$, $x \in g$ and $h \in \{ 0,
+1 \}^L$, to return $x^\alpha$ if $h = \oracle{H}(x^\alpha)$ and the symbol
+$\bot$ otherwise.
+
+We introduce two experiments:
+\begin{tabular}[C]{@{}G|G@{}}
+  \begin{program}
+    \quad \= \quad \= \kill
+    Experiment $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$ \\
+    \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\
+    \> $R \gets
+       A_{\text{cca}}
+        ^{\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, \cdot, \cdot),
+          \oracle{H}
+        (\cdot)}
+       (g^\alpha, g^\tau, \oracle{H}(g^{\alpha\tau}))$; \\
+    \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\
+    \> \textbf{else} \textbf{return} $0$;
+  \end{program}
+  &
+  \begin{program}
+    \quad \= \quad \= \kill
+    Experiment $\expt{uni-no}{A}(\mathcal{G})$ \\
+    \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\
+    \> $R \gets A(g^\alpha, g^\tau)$; \\
+    \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\
+    \> \textbf{else} \textbf{return} $0$;
+  \end{program}
+\end{tabular}
+We mandate that the adversary $A_{\text{cca}}$ never query its authentication
+oracle with the test challenge $g^\tau$.
+
+We will consider a function $\oracle{H}$ to be suitable for our purposes if
+for any adversary $A_{\text{cca}}$, there is an adversary $A$ for which the
+distributions of $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$
+and $\expt{uni-no}{A}(\mathcal{G})$ are computationally indistinguishable.
+Intuitively, this means that the authentication oracle isn't useful in
+attacking the protocol: any adversary which has access to an oracle can be
+replaced by one which has approximately the same probability of success but
+without oracle access.
+
+We first prove that a random oracle \cite{Bellare:1993:ROP} makes a
+`suitable' function.
+
+\begin{theorem}
+  If $\oracle{H}$ is a random oracle with $L$-bit output, where $L$ is some
+  polynomial function of the length of $q$, then, for any adversary
+  $A_{\text{cca}}$, there exists an adversary $A$ such that
+  \[ \expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})
+     \compind \expt{uni-no}{A}(\mathcal{G}) \]
+\end{theorem}
+\begin{proof}
+  The idea behind the proof is that we construct an adversary $A$ in terms of
+  the given adversary $A_{\text{cca}}$ with the same output in all but
+  negligibly few cases.
+
+  Our adversary $A$ isn't provided with either oracle supplied to
+  $A_{\text{cca}}$.
+  
+  Simulating the random oracle is easy.  $A$ maintains a table, initially
+  empty, of pairs $(q, r)$.  When the oracle is invoked on input $q$, we look
+  it up in the table: if there is some entry $(q, r)$, it returns $r$;
+  otherwise we toss coins to choose a new output $r$ and add $(q, r)$ to the
+  table.  This is obviously a polynomial-time activity, since
+  $A_{\text{cca}}$ makes only polynomially many queries, and answering each
+  one takes polynomial time.
+  
+  The authentication oracle is a little harder.  Suppose $A_{\text{cca}}$
+  makes a query $(x, h)$.  If there is an entry $(q, h)$ in the random oracle
+  table, the authentication oracle returns $q$; otherwise it returns $\bot$.
+
+  It remains to show that this is a valid thing to do.  
+\end{proof}
+
+
+
+
+
+
+
+
+
+
+
+
 
 %%%--------------------------------------------------------------------------
 
