From d7d62ac05815cd1a02569fb83542a16573a5376c Mon Sep 17 00:00:00 2001
From: mdw
Date: Sun, 13 Jan 2002 14:55:31 +0000
Subject: [PATCH] More incomplete stuff.
Organization: Straylight/Edgeware

doc/wrestlers.tex  428 ++++++++++++++++++++++++++++++++++++++
1 file changed, 299 insertions(+), 129 deletions()
diff git a/doc/wrestlers.tex b/doc/wrestlers.tex
index a37b643..c175b1a 100644
 a/doc/wrestlers.tex
+++ b/doc/wrestlers.tex
@@ 1,6 +1,6 @@
%%% *latex*
%%%
%%% $Id: wrestlers.tex,v 1.4 2001/06/29 19:36:05 mdw Exp $
+%%% $Id: wrestlers.tex,v 1.5 2002/01/13 14:55:31 mdw Exp $
%%%
%%% Description of the Wrestlers Protocol
%%%
@@ 10,6 +10,9 @@
%%% Revision history 
%%%
%%% $Log: wrestlers.tex,v $
+%%% Revision 1.5 2002/01/13 14:55:31 mdw
+%%% More incomplete stuff.
+%%%
%%% Revision 1.4 2001/06/29 19:36:05 mdw
%%% Some progress made on laptop.
%%%
@@ 23,13 +26,26 @@
%%% Initial versions of documentation.
%%%
\documentclass[a4paper]{article}
\usepackage{a4wide}
\usepackage{amssymb}
\usepackage{amstext}
\usepackage{mdwtab}
+\newif\iffancystyle\fancystylefalse
+
+\iffancystyle
+ \documentclass
+ [a4paper, article, 10pt, numbering, noherefloats, notitlepage]
+ {strayman}
+ \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
+ \usepackage[margin]{amsthm}
+\else
+ \documentclass[a4paper]{article}
+ \usepackage{a4wide}
+ \usepackage{amsthm}
+\fi
+
+\usepackage{amssymb, amstext}
+\usepackage{mdwtab, mathenv}
\errorcontextlines=999
+\showboxbreadth=999
+\showboxdepth=999
\makeatletter
\title{The Wrestlers Protocol: proofofreceipt and secure key exchange}
@@ 38,29 +54,27 @@
\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}}
+\renewcommand{\qedsymbol}{$\square$}
+
+\newcommand{\getsr}{\stackrel{\scriptscriptstyle R}{\gets}}
+\newcommand{\inr}{\in_{\scriptscriptstyle R}}
\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{\poly}[1]{\mathop{\operator@font poly}({#1})}
+\newcommand{\negl}[1]{\mathop{\operator@font negl}({#1})}
\newcommand{\compind}{\stackrel{c}{\approx}}
\newcolumntype{G}{p{0pt}}
+\newcommand{\xor}{\oplus}
+\renewcommand{\epsilon}{\varepsilon}
+
\newenvironment{program}
 {\begin{tabbing}}
 {\end{tabbing}}
+ {\begin{tabular}[C]{G}\hlx{hv[][\tabcolsep]}\begin{tabbing}}
+ {\end{tabbing}\\\hlx{v[][\tabcolsep]h}\end{tabular}}
\begin{document}
@@ 85,29 +99,34 @@
% authentication oracle is useless if the hash function has appropriate
% properties.
We start by introducing a simple proofofidentity protocol, based on the
+We begin by introducing a simple proofofidentity protocol, based on the
DiffieHellman keyexchange 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 DiffieHellman problem
\cite{Boneh:1998:DDP} is hard.
+We start by selecting a security parameter $k$. We choose a cyclic group $G
+= \langle g \rangle$ with $q = G$ prime, in which the decision
+DiffieHellman problem is assumed to be hard \cite{Boneh:1998:DDP}; we
+require that $q$ is a $k$bit number. Suitable groups include elliptic
+curves over finite fields and primeorder subgroups of prime fields.
+Throughout, we shall write the group operation as multiplication, and we
+shall assume that group elements are interchangeable with their binary
+representations.
Alice can choose a private key $1 < \alpha < q$ and publish her corresponding
public key $A = g^\alpha$.
+Alice can choose a private key $\alpha$ from the set $\{ 1, 2, \ldots, q  1
+\}$ and publish her corresponding public key $a = g^\alpha$.
A simplistic proofofidentity 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.
+\item Bob chooses a random exponent $\beta$, also from $\{ 1, 2, \ldots, q 
+ 1 \}$, and sends a \emph{challenge} $b = g^\beta$ to Alice.
+\item Alice computes her \emph{response} $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 DiffieHellman problem is hard: computing
$g^{\alpha\beta}$ given $g^\alpha$ and $g^\beta$ is precisely the
DiffieHellman problem.
+If Bob always plays by the rules then this protocol is evidently secure,
+since computing $g^{\alpha\beta}$ given $g^\alpha$ and $g^\beta$ is precisely
+the DiffieHellman 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
@@ 116,125 +135,276 @@ 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 oneway, 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]{@{}GG@{}}
 \begin{program}
 \quad \= \quad \= \kill
 Experiment $\expt{unicca}{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{unino}{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{unicca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$
and $\expt{unino}{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.
+We fix the protocol by requiring that Bob prove that he already knows the
+answer to his challenge. We introduce a hash function $h$ whose properties
+we shall investigate later. The \emph{Wrestlers Authentication Protocol} is
+then:
+\begin{enumerate}
+\item Bob chooses a secret $\beta \getsr \{ 1, 2, \ldots, q  1 \}$. He
+ computes his \emph{challenge} $b \gets g^\beta$ and also a \emph{check
+ value} $c \gets \beta \xor h(a^\beta)$. He sends the pair $(b, c)$.
+\item Alice receives $(b', c')$. She computes $r \gets b'^\alpha$ and
+ $\gamma \gets c' \xor h(R)$. If $b' = g^\gamma$, she sends $r$ back as her
+ \emph{response}; otherwise she sends the distinguished value $\bot$.
+\item Bob receives $r'$. If $r' = a^\beta$ then he accepts that he's talking
+ to Alice.
+\end{enumerate}
+We show that the introduction of the check value has indeed patched up the
+weakness described above, and that the check value itself hasn't made an
+impersonator's job much easier.
+
+\subsection{Analysis in the random oracle model}
+
+Here, we prove that the Wrestlers Authentication Protocol is secure if $h$ is
+implemented by a public \emph{random oracle} \cite{Bellare:1993:ROP}.
+
+Fix a private key $\alpha \inr \{ 1, 2, \ldots, q  1\}$ and the corresponding public
+key $a = g^\alpha$, and consider a probabilistic polynomialtime adversary
+$A$, equipped with two oracles. One is a random oracle $\oracle{H}\colon
+\{0, 1\}^* \to \{0, 1\}^k$, which implements a function $h$ randomly selected
+from the set of all functions with that signature; the other is an
+authentication oracle $\oracle{O}\colon G \times \{0, 1\}^k \to G \cup \{
+\bot \}$ defined by:
+\[
+\oracle{O}^(b, c) = \begin{cases}
+ b^\alpha & if $b = g^{c \xor h(b^\alpha)}$ \\
+ \bot & otherwise
+\end{cases}
+\]
+The authentication oracle will play the part of Alice in the following. We
+first show that access to this authentication oracle can't help an adversary
+learn how to impersonate Alice.
\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{unicca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})
 \compind \expt{unino}{A}(\mathcal{G}) \]
+ The Wrestlers Authentication Protocol with random oracle is computational
+ zero knowledge \cite{Brassard:1989:SZK}.
+ \label{thm:wapczk}
\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}}$.
+ \newcommand{\Hlist}{\textit{$\oracle{H}$list}}
+ \newcommand{\Hsim}{\textit{$\oracle{H}$sim}}
+ \newcommand{\Osim}{\textit{$\oracle{O}$sim}}
+ \renewcommand{\H}{\oracle{H}}
+ \renewcommand{\O}{\oracle{O}}
+ %
+ Let $A$ be any probabilistic polynomialtime adversary with access to a
+ random. We shall construct a probabilistic polynomialtime adversary $A'$
+ without either oracle such that the probability distributions on the output
+ of $A$ and $A'$ are equal. Specifically, $A'$ runs $A$ with simulated
+ random and authentication oracles whose behaviour is computationally
+ indistinguishable from the originals. The algorithm for $A'$ and the
+ simulated oracles is shown in figure~\ref{fig:wapczksim}.
+
+ \begin{figure}
+ \begin{program}
+ \quad \= \kill
+ Adversary $A'^{\H(\cdot)}$: \+ \\
+ $\Hlist \gets \emptyset$; \\
+ $r \gets A^{\Hsim(\cdot), \Osim(\cdot, \cdot)}$; \\
+ \textbf{return} $r$; \ \\[\medskipamount]
+ %
+ Simulated random oracle $\Hsim(q)$: \+ \\
+ \textbf{if} $\exists r : (q, r) \in \Hlist$ \textbf{then}
+ \textbf{return} $r$; \\
+ $r \getsr \H(q)$; \\
+ $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\
+ \textbf{return} $r$; \ \\[\medskipamount]
+ %
+ Simulated authentication oracle $\Osim(b, c)$: \+ \\
+ \textbf{if} $\exists q, r : (q, r) \in \Hlist \wedge
+ b = g^{c \xor r} \wedge
+ q = a^{c \xor r}$ \textbf{then}
+ \textbf{return} $a^{c \xor r}$; \\
+ \textbf{else} \textbf{return} $\bot$;
+ \end{program}
+ %
+ \caption{The algorithm and simulated oracles for the proof of
+ theorem~\ref{thm:wapczk}.}
+ \label{fig:wapczksim}
+ \end{figure}
 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 polynomialtime activity, since
 $A_{\text{cca}}$ makes only polynomially many queries, and answering each
 one takes polynomial time.
+ Firstly we show that $A'$ runs in polynomial time. The only modifications
+ to $\Hlist$ are in $\Hsim$, which adds at most one element for each oracle
+ query. Since $\Hlist$ is initially empty and $A$ can only make $\poly{k}$
+ queries to $\Hsim$, this implies that $\Hlist$ is always
+ polynomiallybounded. Each query can be answered in polynomial time:
+ indeed, the search implied by the test $\exists r : (q, r) \in \Hlist$ can
+ be performed in $O(\log q)$ time by indexing $\Hlist$ on $q$ using a radix
+ tree. Now, since $\Hlist$ is polynomially bounded, the test $\exists q,
+ r : (q, r) \in \Hlist \wedge b = g^{c \xor r} \wedge q = a^{c \xor r}$ at
+ the start of $\Osim$ runs in polynomial time even though it requires an
+ exhaustive search of the history of $A$'s queries to its simulated random
+ oracle.
 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.
+ Next, we examine the behaviour of the simulated oracles. Since $\Hsim$ is
+ implemented in terms of the public random oracle $\H$, and returns the same
+ answers to queries, its probability distribution must be identical.
+
+ We turn our attention to the simulation of the authentication oracle.
+ Consider a query $(b, c)$ made by $A$ to its authentication oracle.
+
+ Firstly, suppose that there is a $\beta$ such that $b = g^\beta$ and $c =
+ \beta \xor r$ where $r$ is the response to a previous query made by $A$ to
+ its random oracle on $a^\beta$. Then the true authentication oracle $\O$
+ is satisfied because $b = g^\beta = g^{c \xor r} = g^{c \xor h(a^\beta)} =
+ g^{c \xor h(b^\alpha)}$, and returns $b^\alpha$. Similarly, the simulated
+ authentication oracle $\Osim$ will find the pair $(a^\beta, r) \in \Hlist$,
+ recover $\beta = c \xor r$, confirm that $b = g^\beta$, and return
+ $a^\beta$ as required. These events all occur with probability 1.
+
+ Conversely, suppose that there is no such $\beta$. Then the simulated
+ oracle $\Osim$ will reject the query, returning $\bot$, again with
+ probability 1. However, a genuine authentication oracle $\O$ will succeed
+ and return $b^\alpha$ with probability $2^{k}$. To see this, note that $b
+ = g^\gamma$ for some $\gamma \in \{ 0, 1, \ldots, q  1 \}$, and the
+ probability that $h(b^\alpha) = c \xor \gamma$ is precisely $2^{k}$, since
+ $c$ and $\gamma$ are $k$bit strings. Since this probability is
+ negligible, we have shown that the distributions of the simulated oracles
+ $\Hsim$ and $\Osim$ are computationally indistinguishable from the genuine
+ oracles $\H$ and $\O$. The theorem follows.
\end{proof}
+Our next objective is to show that pretending to be Alice is hard without
+knowledge of her secret $\alpha$. We say that an adversary $A$
+\emph{impersonates} in the Wrestlers Authentication Protocol with probability
+$\epsilon$ if
+\[ \Pr[A^{\oracle{H}(\cdot)}(g^\alpha, g^\beta,
+ \beta \xor h(g^{\alpha\beta}))
+ = g^{\alpha\beta}]
+ = \epsilon
+\]
+where the probability is taken over all choices of $\alpha, \beta \in \{ 1,
+2, \ldots, q  1 \}$ and random oracles $\oracle{H}$.
+\begin{theorem}
+ Assuming that the DiffieHellman problem is hard in $G$, no probabilistic
+ polynomialtime adversary can impersonate in the Wrestlers Authentication
+ Protocol with random oracle with better than negligible probability.
+ \label{thm:wapdhp}
+\end{theorem}
+\begin{proof}
+ \newcommand{\Hlist}{\textit{$\oracle{H}$list}}
+ \newcommand{\Hqueries}{\textit{$\oracle{H}$queries}}
+ \newcommand{\Hsim}{\textit{$\oracle{H}$sim}}
+ \renewcommand{\H}{\oracle{H}}
+ %
+ We prove the theorem by contradiction. Given a polynomialtime adversary
+ $A$ which impersonates Alice with nonnegligible probability $\epsilon$, we
+ construct an adversary which solves the DiffieHellman problem with
+ probability no less than $\epsilon \poly{k}$, i.e.,
+ \[ \Pr[A'(g^\alpha, g^\beta) = g^{\alpha\beta}] \ge \epsilon \poly{k}. \]
+ Thus, if there is any polynomialtime $A$ which impersonates with better
+ than negligible probability, then there is a polynomialtime $A'$ which
+ solves DiffieHellman with essentially the same probability, which would
+ violate our assumption of the hardness of DiffieHellman.
+
+ The idea behind the proof is that the check value is only useful to $A$
+ once it has discovered the correct response to the challenge, which it must
+ have done by solving the DiffieHellman problem. Hence, our DiffieHellman
+
+ \begin{figure}
+ \begin{program}
+ \quad \= \kill
+ Adversary $A'(a, b)$: \+ \\
+ $\Hlist \gets \emptyset$; \\
+ $\Hqueries \gets \emptyset$; \\
+ $r \getsr \{ 0, 1 \}^k$; \\
+ $x \gets A^{\Hsim(\cdot)}(a, b, r)$; \\
+ $c \getsr (\Hlist \cup \{ x \}) \cap G$; \\
+ \textbf{return} $c$; \ \\[\medskipamount]
+ %
+ Simulated random oracle $\Hsim(q)$: \+ \\
+ \textbf{if} $\exists r : (q, r) \in \Hlist$
+ \textbf{then} \textbf{return} $r$; \\
+ $r \gets \{ 0, 1 \}^k$; \\
+ $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\
+ $\Hqueries \gets \Hqueries \cup \{ q \}$; \\
+ \textbf{return} $r$;
+ \end{program}
+ %
+ \caption{The algorithm for the proof of theorem~\ref{thm:wapdhp}}
+ \label{fig:wapdhprdc}
+ \end{figure}
+
+ The adversary $A'$ is shown in figure~\ref{fig:wapdhprdc}. It generates
+ a random checkvalue and runs the impersonator $A$.
+
+ The simulated random oracle $\Hsim$ gathers together the results of all of
+ the random oracle queries made by $A$. The final result returned by $A'$
+ is randomly chosen from among all of the `plausible' random oracle queries
+ and $A$'s output, i.e., those queries which are actually members of the
+ group. The check value given to $A$ is most likely incorrect (with
+ probability $1  2^{k}$): the intuition is that $A$ can only notice if it
+ actually computes the right answer and then checks explicitly.
+
+ If $A$ does compute the correct answer $g^{\alpha\beta}$ and either returns
+ it or queries $\Hsim$ on it, then $A'$ succeeds with probability $\epsilon
+ / (\Hlist \cup \{ x \}) \cap G = \epsilon \poly{k}$, since $\Hlist$ is
+ no greater than the number of random oracle queries made by $A$ (which must
+ be polynomially bounded).\footnote{%
+ This polynomial factor introduces a loss in the perceived security of the
+ authentication protocol. It appears that this loss is only caused by the
+ possibility of the adversary $A$ being deliberately awkward and checking
+ the value of $c$ after having computed the answer. However, we can't see
+ a way to improve the security bound on the scheme without imposing
+ artificial requirements on $A$.} %
+
+ It remains to show that if $A$ never queries its random oracle on
+ $g^{\alpha\beta}$ then it cannot distinguish the random check value $r$
+ from the correct one $\beta \xor \H(g^{\alpha\beta})$, and hence won't
+ notice that $A'$ is lying to it. But this is obvious: $A$'s probability of
+ guessing the random value that would have been returned had it actually
+ queried $\Hsim$ on the input $g^{\alpha\beta}$ is equal to the probability
+ of it guessing $\beta \xor r$ instead, since $\Hsim$ chooses its responses
+ uniformly at random. This completes the proof.
+\end{proof}
+We conclude here that the Wrestlers Authentication Protocol is a secure
+authentication protocol in the random oracle model: impersonation is hard if
+the DiffieHellman problem is hard, and proving one's identity doesn't leak
+secret key information.
+\subsection{Requirements on hash functions}
+Having seen that the Wrestlers Authentication Protocol is secure in the
+random oracle model, we now ask which properties we require from the hash
+function. This at least demonstrates that the protocol isn't deeply flawed,
+and suggests an efficient implementation in terms of conventional hash
+functions.
+Here we investigate more carefully the properties required of the hash
+function, and provide a more quantitative analysis of the protocol.
+Looking at the proofs of the previous two sections, we see that the random
+oracles are mainly a device which allow our constructions to `grab hold' of
+the hashing operations performed by the adversary.
+%%%
+\section{A keyexchange 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 SKsecure.
+% messages
+%
+% prechallenge: g^b
+% cookie: g^b, h(cookie, g^b')
+% challenge: g^b, h(g^b'), b + h(replycheck, g^b, g^b', g^ab')
+% reply: g^b, h(g^b'), b + h(replycheck, g^b, g^b', g^ab'), E_k(g^a'b)
+% switch: h(g^b), h(g^b'), E_k(g^a'b, h(switchrequest, g^a, g^a'))
+% switchok: E_k(g^ab, h(switchconfirm, g^a, g^a'))begin{
%%%
+We now describe the full Wrestlers Protocol, in a multiparty setting. Fix a
+cyclic group $G = \langle g \rangle$ of order $q = G$. Each player $P_i$
+chooses a private key $\alpha_i \in \{ 1, 2, \ldots, q  1 \}$ and publishes
+the corresponding public key $a_i = g^{\alpha_i}$ to the other players.
\section{An MTauthenticator}
% Use the protocol of the previous section as an MTauthenticator, within the
% meaning of [Canetti:2001:AKE].
%%%
\section{A keyexchange 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 SKsecure.
%%% That's all, folks 
@@ 244,4 +414,4 @@ We first prove that a random oracle \cite{Bellare:1993:ROP} makes a
%%% Local Variables:
%%% mode: latex
%%% TeXmaster: "wrestlers"
%%% End:
+%%% End:

2.1.4