Some progress made on laptop.

[tripe] / doc / wrestlers.tex

%%% -*-latex-*-
%%%
%%% $Id: wrestlers.tex,v 1.4 2001/06/29 19:36:05 mdw Exp $
%%%
%%% Description of the Wrestlers Protocol
%%%
%%% (c) 2001 Mark Wooding
%%%

%%%----- 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.
%%%
%%% Revision 1.2  2001/02/22 09:09:05  mdw
%%% Partially through reworking.
%%%
%%% Revision 1.1  2001/02/16 21:43:33  mdw
%%% Initial versions of documentation.
%%%

\documentclass[a4paper]{article}
\usepackage{a4wide}
\usepackage{amssymb}
\usepackage{amstext}
\usepackage{mdwtab}

\errorcontextlines=999
\makeatletter

\title{The Wrestlers Protocol: proof-of-receipt and secure key exchange}
\author{Mark Wooding \and Clive Jones}

\bibliographystyle{alpha}

\newtheorem{theorem}{Theorem}
\newenvironment{proof}[1][Proof]{%
  \par\noindent\textbf{#1}\ %
}{%
  \penalty\@M\hfill\vadjust{}%
  \penalty\z@\relax\vadjust{}%
  \penalty\@M\hfill$\square$%
  \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
\begin{abstract}
  Fill this in later.
\end{abstract}
\tableofcontents
\newpage

%%%--------------------------------------------------------------------------

\section{Introduction}
% Some waffle here about the desirability of a key-exchange protocol that
% doesn't leave signatures lying around, followed by an extended report of
% the various results.

%%%--------------------------------------------------------------------------

\section{A simple authentication protocol}
% Present the basic Diffie-Hellman-based authenticator, and prove that an
% authentication oracle is useless if the hash function has appropriate
% properties.

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}













%%%--------------------------------------------------------------------------

\section{An MT-authenticator}
% Use the protocol of the previous section as an MT-authenticator, within the
% meaning of [Canetti:2001:AKE].

%%%--------------------------------------------------------------------------

\section{A key-exchange protocol}
% Present the Wrestlers protocol in all its glory.  Show, by means of the
% previous proofs, that the Wrestlers protocol is simulatable in the
% authenticated model using a much simpler protocol.  Show that the simpler
% protocol is SK-secure.

%%%----- That's all, folks --------------------------------------------------

\bibliography{cryptography,mdw-crypto}
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "wrestlers"
%%% End: