From a6e375a6211f5c082a45c9424a96820054219a55 Mon Sep 17 00:00:00 2001
From: Mark Wooding <mdw@distorted.org.uk>
Date: Wed, 1 Nov 2006 14:51:06 +0000
Subject: [PATCH] Initial commit -- work in progress.

---
 .gitignore     |   13 +
 Makefile       |   10 +
 background.tex |  766 +++++++++++++
 ecc.mp         |  134 +++
 wrestlers.tex  | 3273 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 wrshortsl.tex  |    6 +
 wrslide.tex    |  346 ++++++
 wrslides.cls   |   75 ++
 wrslides.tex   |   32 +
 9 files changed, 4655 insertions(+)
 create mode 100644 .gitignore
 create mode 100644 Makefile
 create mode 100644 background.tex
 create mode 100644 ecc.mp
 create mode 100644 wrestlers.tex
 create mode 100644 wrshortsl.tex
 create mode 100644 wrslide.tex
 create mode 100644 wrslides.cls
 create mode 100644 wrslides.tex

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..79b2cef
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,13 @@
+*.pdf
+*.[0-9]
+*.ps
+*.dvi
+*.log
+*.lof
+*.lot
+*.aux
+*~
+*.bbl
+*.blg
+*.tmp
+*.toc
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..2c5c168
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,10 @@
+all: \
+	wrestlers.ps wrestlers.pdf \
+	wrslides.pdf \
+	wrslides-full.pdf
+
+%.ps: %.dvi
+	dvips -o $@ $+
+
+%.dvi: %.tex
+	latex 
\ No newline at end of file
diff --git a/background.tex b/background.tex
new file mode 100644
index 0000000..f2a6554
--- /dev/null
+++ b/background.tex
@@ -0,0 +1,766 @@
+\xcalways\section{Cryptographic background}\x
+
+\xcalways\subsection{Groups}\x
+
+\begin{slide}
+  \resetseq
+  \head{Groups \seq: definition}
+  \topic{definitions}
+
+  A \emph{group} is a set $G$ of objects, and a binary operation $\op$, with
+  the following properties.
+  \begin{description}
+  \item [Closure] If $a$ and $b$ are elements of $G$, then so is $a \op b$.
+  \item [Associativity] For any $a$, $b$ and $c$ in $G$,
+    \[ a \op (b \op c) = (a \op b) \op c. \]
+  \item [Identity] There exists an element $e$ so that, for any $a$ in $G$,
+    \[ a \op e = a = e \op a. \]
+  \item [Inverses] For any $a$ in $G$, there exists a $b$ so that
+    \[ a \op b = e = b \op a. \]
+  \end{description}
+\end{slide}
+
+\begin{slide}
+  \head{Groups \seq: abelian groups}
+
+  A group $(G, \op)$ is \emph{commutative}, or \emph{abelian}, if it has the
+  following additional property.
+  \begin{description}
+  \item [Commutativity] For any $a$ and $b$ in $G$,
+    \[ a \op b = b \op a. \]
+  \end{description}
+  We usually write the operator of an abelian group using some familiar
+  symbol, like $+$ or $\times$.
+\end{slide}
+
+\begin{slide}
+  \head{Groups \seq: notation}
+
+  Let $(G, +)$ be a group written additively.  For $A, B \in G$, we do the
+  obvious things and write $0_G$, or just $0$, for the identity, and $-A$ for
+  the inverse of $A$; we also write
+  \[ A - B \equiv A + (- B) \qquad
+     2 A \equiv A + A \qquad
+     n A \equiv \underbrace{A + A + \cdots + A}_\text{$n$ times}.
+  \]
+  Similarly, if $(H, \times)$ is a group written multiplicatively, and
+  $\alpha, \beta \in H$, we do the obvious things and write $1_H$, or just
+  $1$, for the identity, and $\alpha^{-1}$ for the inverse of $\alpha$; we
+  also write
+  \[ \alpha \beta \equiv \alpha \times \beta \qquad
+     \alpha/\beta \equiv \alpha \times \beta^{-1} \qquad
+     \alpha^2 \equiv \alpha \times \alpha \qquad
+     \alpha^n \equiv \underbrace{\alpha \times \alpha \times \cdots
+       \alpha}_\text{$n$ times}.
+  \]
+  The number of elements of a group $G$ is written $|G|$ (or sometimes
+  $\#G$), and is called the \emph{order} of $G$.
+\end{slide}
+
+\begin{slide}
+  \head{Groups \seq: cyclic groups and discrete logs}
+  \topic{cyclic groups and discrete logs}
+
+  A \emph{cyclic} group $(G, +)$ consists only of elements $n P$ for a single
+  $P$ and varying $n \in \Z$.  We call $P$ a \emph{generator} of the group.
+
+  Cyclic groups are always abelian.
+
+  If $G$ is finite, then for any $A \in G$, there is a \emph{unique} $a \in
+  \Nupto{|G|}$ for which $A = a P$.  We call $a$ the \emph{discrete
+  logarithm} of $A$ to the base $P$.
+
+  This makes more sense if you consider a multiplicative group $(H, \times)$.
+  Then there's a $\gamma \in H$, and for any $\alpha$, a unique $a \in
+  \Nupto{|H|}$ such that $\alpha = \gamma^a$.
+
+  Computing discrete logs seems to be difficult in some kinds of groups.
+\end{slide}
+
+\begin{slide}
+  \head{Groups \seq: Diffie-Hellman}
+  \topic{Diffie-Hellman}
+
+  Fix some cyclic group $(G, +)$, with generator $P$.
+  \begin{protocol}
+    Alice & Bob \\[\medskipamount]
+    $a \getsr \Nupto{|G|}$; & $b \getsr \Nupto{|G|}$; \\
+    $A \gets a P$; & $B \gets b P$; \\
+    \send{->}{A}
+    \send{<-}{B}
+    $Z \gets a B$; & $Z \gets b A$;
+  \end{protocol}
+  This works because
+  \[ Z = a B = a (b P) = (a b) P = (b a) P = b (a P) = b A. \]
+  Computing $a b P$ from $a P$ and $b P$ seems hard.  This is the
+  (computational) \emph{Diffie-Hellman} problem.
+
+  The best way we know is to work out $a$ or $b$ -- i.e., extract a discrete
+  logarithm.
+\end{slide}
+
+\begin{slide}
+  \head{Groups \seq: ElGamal encryption}
+  \topic{ElGamal encryption}
+
+  Suppose $H\colon G \to \Bin^n$ is a secure hash function.  Alice has a
+  private key~$a \in \Nupto{|G|}$.  Bob knows her public key~$A = a P$.  He
+  has an $n$-bit message $m$ he wants to send her.
+  \begin{enumerate}
+  \item He chooses $r \inr \Nupto{|G|}$.
+  \item He computes $R = r P$.
+  \item He computes $Z = r A$.
+  \item He sends Alice the pair $(R, m \xor H(Z))$.
+  \end{enumerate}
+  Alice can decrypt because
+  \[ a R = (a r) P = r A = Z. \]  
+\end{slide}
+
+\begin{slide}
+  \head{Groups \seq: Schnorr groups}
+  \topic{examples}
+
+  Let $p$ and $q$ be prime, with $p = q f + 1$.  The residues modulo $p$ form
+  a \emph{finite field} $\F_p$.  The nonzero elements form a cyclic group
+  $\F_p^*$ under multiplication mod~$p$.  Let $\eta$ be a generator of
+  $\F_p^*$.
+
+  Set $\gamma = \eta^f$.  Then
+  \[ G = \langle \gamma \rangle = \{\, \gamma^n \mid 0 \le n < q \,\} \]
+  is a \emph{Schnorr group} of $q$ elements.  $G$ is cyclic, with generator
+  $\gamma$.
+
+  In practice, you don't need to find $\eta$.  Pick $\alpha \in \F_p^*$
+  arbitrarily (2 is a good first choice); if $\alpha^f \ne 1$ then use
+  $\gamma = \alpha^f$.
+\end{slide}
+
+\begin{slide}
+  \head{Groups \seq: elliptic curves}
+
+  Let $q = p^f$ be a prime power.  Then there is a finite field $\F_q$ with
+  $q$ elements.
+
+  Let $E$ be an \emph{elliptic curve} over $\F_q$:
+  \[ E(\F_q) = \{\, (x, y) \in \F_q^2 \mid y^2 = x^3 + a x + b \,\} \]
+  \begin{tabularx}{\linewidth}{@{}Xl}
+    \hrule height 0pt
+    The points of $E(\F_q)$ form a group with a peculiar kind of addition
+    (pictured right).
+    \parskip=1ex
+
+    If $\#E(\F_q)$ has a large prime factor then we can
+    use a cyclic subgroup of $E(\F_q)$.  The details are complicated\dots
+    &
+    \vtop{\hrule height 0pt \hbox{
+        \ifpdf
+          \includegraphics[scale = 0.6]{ecc-0.pdf}
+        \else
+          \includegraphics[scale = 0.6]{ecc.0}
+        \fi
+      }}
+  \end{tabularx}
+\end{slide}
+
+
+\xcalways\subsection{Bilinear maps}\x
+
+\begin{slide}
+  \resetseq
+  \head{Bilinear maps \seq: definition}
+  \topic{definition}
+
+  Let $(G, +)$, $(G', +)$ and $(G_T, \times)$ be three cyclic groups with the
+  same order.  Let $P$ and $P'$ generate $G$ and $G'$ respectively.
+
+  A map $\hat{e}\colon G \times G' \to G_T$ is \emph{bilinear} if
+  \begin{itemize}
+  \item for any $R \in G$ and $S', T' \in G'$,
+    \[ \hat{e}(R, S' + T') = \hat{e}(R, S') \, \hat{e}(R, T'), \]
+    and
+  \item for any $R, S \in G$ and $T' \in G'$,
+    \[ \hat{e}(R + S, T') = \hat{e}(R, T') \, \hat{e}(S, T'). \]
+  \end{itemize}
+  We say that $\hat{e}$ is \emph{non-degenerate} if
+  \[ \hat{e}(P, P') \ne 1. \]
+\end{slide}
+
+\begin{slide}
+  \head{Bilinear maps \seq: properties}
+  \topic{properties}
+
+  Define
+  \[ \gamma = \hat{e}(P, P'). \]
+  Then $\gamma$ generates $G_T$.
+
+  For any $a$ and $b$:
+  \[ \hat{e}(a P, b P') = \gamma^{a b}. \]
+  If $\hat{e}$ is easy to compute then this is like a Diffie-Hellman
+  computation combined with an isomorphism to a different group.
+\end{slide}
+
+\begin{slide}
+  \head{Bilinear maps \seq: the Bilinear Diffie-Hellman problem}
+  \topic{bilinear Diffie-Hellman problem}
+
+  The \emph{bilinear} Diffie-Hellman problem is this: given
+  \begin{itemize}
+  \item $a P$ and $b P$ in $G$, and
+  \item $a P'$ and $c P'$ in $G'$,
+  \end{itemize}
+  compute
+  \[ \zeta = \gamma^{abc}. \]
+
+  This can be done if the Diffie-Hellman problem can be solved in \emph{any}
+  of $G$, $G'$ or $G_T$.
+  \begin{itemize}
+  \item If DHP easy in $G$, then compute $\zeta = \hat{e}(a b P, c P')$.
+  \item If DHP easy in $G'$, then compute $\zeta = \hat{e}(b P, a c P')$.
+  \item If DHP easy in $G_T$, then compute $\alpha = \hat{e}(a P, P') =
+    \gamma^a$, $\beta = \hat{e}(b P, c P') = \gamma^{b c}$ and $\zeta$ from
+    $\alpha$ and $\beta$.
+  \end{itemize}
+\end{slide}
+
+\begin{slide}
+  \head{Bilinear maps \seq: Boneh-Franklin identity-based encryption}
+  \topic{Boneh-Franklin identity-based encryption}
+
+  We need two hashes: $H \colon G_T \to \Bin^n$ and $H_\text{id} \colon
+  \Bin^* \to G'$.
+
+  There is a \emph{trusted third party}.  It has a private key $t \inr
+  \Nupto{|G|}$ and a public key $T = t P$.
+
+  Alice's public key is $A = H_\text{id}(\texttt{Alice})$.  Her private key
+  is $K_A = t A$.
+
+  Bob wants to send Alice a message $m \in \Bin^n$.
+  \begin{enumerate}
+  \item He chooses $r \inr \Nupto{|G|}$.
+  \item He computes $R = r P$.
+  \item He computes $\psi = \hat{e}(T, A)^r$.
+  \item He sends Alice the pair $(R, m \xor H(\psi))$.
+  \end{enumerate}
+  Alice can decrypt because
+  \[ \hat{e}(R, K_A) = \hat{e}(r P, t A)
+                     = \hat{e}(P, A)^{rt}
+                     = \hat{e}(t P, A)^r
+                     = \hat{e}(T, A)^r
+                     = \psi. \]
+\end{slide}
+
+\begin{slide}
+  \head{Bilinear maps \seq: examples}
+  \topic{examples}
+
+  The major examples of bilinear maps are the \emph{Weil} and \emph{Tate
+  pairings} on torsion groups of elliptic curves.
+\end{slide}
+
+
+\xcalways\subsection{Zero-knowledge}\x
+
+\begin{slide}
+  \resetseq
+  \head{Zero-knowledge \seq: interactive proofs}
+  \topic{interactive proofs}
+
+  Prover and verifier exchange messages.  Verifier decides whether to
+  \emph{accept} or \emph{reject} the proof.
+
+  An interactive proof system must have the following properties.
+  \begin{description}
+  \item [Completeness] If the prover is honest, the verifier (almost always)
+    accepts.
+  \item [Soundness] If the prover is \emph{dishonest}, the verifier
+    (sometimes) rejects.
+  \end{description}
+  Repeat protocol several times to reduce soundness error.
+\end{slide}
+
+\begin{slide}
+  \head{Zero-knowledge \seq: simulation}
+  \topic{simulation}
+
+  We have a prover $P$ and a verifier $V$.  Write
+  \[ x \gets V^P() \]
+  to mean that $V$ outputs $x$ after interacting with $P$.
+
+  Suppose that there is a simulator~$S$ so that, for all $y$,
+  \[ |\Pr[x \gets V^P() : x = y] - \Pr[x \gets S() : x = y]| \le \epsilon. \]
+  If $\epsilon$ is small, then $V$ is unlikely to be able to persuade anyone
+  that he learned anything from $P$.
+
+  in particular, if $\epsilon = 0$ then we say that the proof has
+  \emph{perfect zero knowledge}.
+\end{slide}
+
+\begin{slide}
+  \head{Zero-knowledge \seq: an example}
+  \topic{example}
+
+  Prover $P$ knows that $\alpha = \beta^2 \in \Z/n\Z$ for some composite $n$.
+  \begin{protocol}
+    Prover $P$ & Verifier $V$ \\[\medskipamount]
+    $\gamma \getsr \Z/n\Z$; \\
+    \send{->}{\kappa = \gamma^2 \alpha}
+    \send{<-}{c \inr \Bin}
+    \send{->}{\rho = \gamma \beta^c}
+    & Check: $\kappa = \rho^2 \alpha^{1 - c}$
+  \end{protocol}
+
+  \begin{itemize}
+  \item Completeness:
+    \[ \rho \alpha^{1 - c} = (\gamma \beta^c)^2 \alpha^{1 - c}
+                           = \gamma^2 \beta^{2c} \alpha^{1 - c}
+                           = \gamma^2 \alpha^c \alpha^{1 - c}
+                           = \gamma^2 \alpha
+                           = \kappa.
+    \]
+  \item Soundness: if $P^*$ convinces $V$ with probability $p > \frac{1}{2}$
+    then we can, in theory, run $P^*$ with (say) $c = 0$ and get $\gamma$.
+    We then \emph{rewind} $P^*$, give it $c = 1$, and get $\gamma \beta$,
+    from which we compute $\beta$.  This works with probability at least $p -
+    \frac{1}{2}$.
+  \end{itemize}
+\end{slide}
+
+This statement could use some proof.
+
+Firstly, consider a simple abstract game.  There is a secret table, with two
+columns and $r$ rows.  Exactly $n$ of the entries in the table contain $1$;
+the remaining entries contain zero.  We have to pick a row, and you win if
+both entries in that row contain $1$.
+
+Clearly, if $n \le r$, it's possible to arrange the ones so that each is in a
+different row.  If we're playing against someone unscrupulous, we are
+guaranteed to lose.
+
+On the other hand, if $n > r$, there must be a winning row, because there are
+too many ones to fit otherwise.  In fact, there must be at least $n - r$
+winning rows.  So our probability of winning must be at least $(n - r)/2r$.
+
+Apply this to the problem of our dishonest prover.  The `table''s rows are
+indexed by all the possible inputs to the prover -- the value $\alpha$ and
+its own internal coin tosses.  (We only consider provers running in bounded
+time, so these are finite.)  The columns are indexed by our coin $c$.  We
+know that $2 r p$ of the entries contain $1$.  Hence, the probability that we
+win is at least
+\[ \frac{2 r p - r}{2 r} = p - \frac{1}{2}. \]
+
+\begin{slide}
+  \head{Zero-knowledge \seq: an example (cont.)}
+
+  We now show zero-knowledge, by describing a simulator.
+  \begin{enumerate}
+  \item Simulator chooses $\rho \inr \Z/n\Z$ and $b \inr \Bin$ at random.  It
+    runs $V$ and sends it $\kappa = \rho \alpha^{1 - b}$.
+  \item Verifier runs, returns bit $c$.
+  \item If $b = c$ then simulator sends back $\rho$.  If $b \ne c$ then
+    simulator gives up and tries again.
+  \item Verifier (presumably) accepts, because
+    \[ \rho \alpha^{1 - c} = \rho \alpha^{1 - b}. \]
+  \end{enumerate}
+  Simulator fails (and retries) with probability $\frac{1}{2}$, because $b$
+  is uniform and independent of $c$.
+\end{slide}
+
+\begin{slide}
+  \head{Aside on KCDSA}
+  \topic{KCDSA}
+
+  Let $(G, +)$ be a cyclic group of prime order $q$, with generator $P$.  Let
+  $H\colon G \to \Bin^t$ and $H'\colon \Bin^* \to \Bin^t$ be cryptographic
+  hash functions.
+
+  Alice's private key is $a \inr \F_q$.  Her public key is $A = a P$.
+  Suppose Alice wants to sign a message $m \in \Bin^*$.
+  \begin{enumerate}
+  \item She chooses a random $k \inr \F_q$.  She computes $K = k P$, and $r =
+    H(K)$.
+  \item Computes $h = H'(m)$, and $u = (h \xor r) \bmod q$.
+  \item Finally, she computes $s = (k - u)/a$.
+  \end{enumerate}
+  Her signature on $m$ is $\sigma = (r, s)$.
+
+  To verify $(r, s)$, Bob can compute $h = H'(m)$; he checks that
+  \[ r = H(s A + u P). \]
+  Note that $s a = k - u$, so $s a + u = k$.  Hence $s A + u P = (s
+  a + u) P = k P = K$.
+\end{slide}
+
+\begin{slide}
+  \head{Zero-knowledge \seq: KCDSA as identification protocol}
+
+  As before, let $(G, +)$ be a cyclic group, generated by $P$, of prime order
+  $q$, and let $H\colon G \to \Bin^t$ be a cryptographic hash function.
+  \begin{protocol}
+    Alice & Bob \\
+    (private key $a \inr \F_q$) & (public key $A = a P$) \\[\medskipamount]
+    $k \getsr \F_q$; $K \gets k P$; \\
+    \send{->}{r = H(K)}
+    \send{<-}{m \inr \Bin^{t}}
+    $u \gets (r \xor m) \bmod q$; & $u \gets (r \xor m) \bmod q$; \\
+    \send{->}{s = (k - u)/x}
+    & Check: $r = H(s A + u P)$
+  \end{protocol}
+\end{slide}
+
+\begin{slide}
+  \head{Zero-knowledge \seq: KCDSA as identification protocol (cont.)}
+
+  \begin{itemize}
+  \item Completeness: as for the KCDSA signature scheme.
+  \item Soundness: suppose some prover manages to impersonate Alice with
+    probability $\epsilon > 2^{-t}$.  We choose some $m$ and send it to the
+    prover, getting $s$.  Now we \emph{rewind} the prover and send it some
+    $m' \ne m$.  With probability at least $\epsilon(\epsilon - 2^{-t})$, we
+    expect it to give us a valid $s'$.  Let $u' = (m' \xor r) \bmod q$.
+    \begin{itemize}
+    \item If $s A + u P \ne s' A + u' P$ then we have a hash collision.  So
+      assume $s a + u = s' a + u'$.
+    \item We chose $m \ne m'$, so $u = r \xor m \ne r \xor m' = u'$.  We'd
+      notice if $a = 0$, so $s \ne s'$.
+    \item Therefore, we can derive
+      \[ a = \frac{u' - u}{s - s'}. \]
+    \end{itemize}
+    So our fake prover can compute discrete logs.
+  \end{itemize}
+\end{slide}
+It's worth proving the probability given above.  I use the approach of
+K\"asper, Laur and Lipmaa [KLL06].
+
+Let's consider first a simple setting.  Let $U$ and $V$ be two finite sets,
+and let $G \subseteq U \times V$ be a set of `good pairs'.  Suppose that $|G|
+= \epsilon |U| |V|$, i.e.,
+\[ \Pr[(u, v) \getsr U \times V : (u, v) \in G] = \epsilon. \]
+We now perform the following simple experiment.  Choose $u$ and $v$ uniformly
+at random from $U$ and $V$ respectively.  If $(u, v) \notin G$, then give up.
+Otherwise, choose $v' \inr V$.  If $(u, v') \in G$ and $v' \ne v$ then we
+win.  What's the probability that we win?
+
+Some more notation would be handy.  For each $u \in U$, let $G_u = \{\, v \in
+V \mid (u, v) \in G \,\}$, and $n_u = |G_u|$.  Then
+\[ |G| = \sum_{u \in U} n_u. \]
+Suppose we're given $(u, v) \inr G$, and $v' \inr V$.  We want $\Pr[v' \in
+G_u \setminus \{v\}]$.  Well,
+\begin{eqnarray*}[rl]
+  \Pr[v \in G_u]
+  & =   \sum_{u^* \in U} \Pr[v' \in G_{u^*} \setminus \{v\}] \Pr[u = u^*] \\
+  & \ge \sum_{u^* \in U} \frac{n_{u^*} - 1}{|V|} \frac{n_{u^*}}{|G|} \\
+  & =   \sum_{u^* \in U} \frac{n_{u^*}^2 - n_{u^*}}{|V| |G|}
+\end{eqnarray*}
+
+This is unpleasant, but the following lemma will sort us out.
+\begin{lemma}
+  Let $s_0$, $s_1$, \dots, $s_{n-1}$ be given, such that $\sum_{0 \le i < n}
+  s_i = t$.  Then $\sum_{0 \le i < n} s^2$ is minimum when $s_i = t/n$ for
+  all $0 \le i < n$.
+\end{lemma}
+\begin{proof}
+  The proof is by induction.  If $n = 1$, the lemma is obviously true.  Let
+  $s_i$ be given for $0 < i < n + 1$ be given, so that $\sum_i s_i = t$; we
+  claim that $\sum_i s_i^2$ is minimum when $s_i = t/(n + 1)$ for all $i$.
+
+  Without loss of generality, suppose that $s_n \ge s_i$ for $0 \le i < n$.
+  Using the induction hypothesis, $\sum_{0\le i<n} s_i^2$ is minimum when
+  $s_i = (t - s_n)/n$ for all $i < n$.  Let $s = s_n$.  Then
+  \begin{eqnarray*}[rl]
+    \sum_{0 \le i \le n} s_i^2
+    & = s^2 + \sum_{0 \le i < n} \biggl( \frac{t - s}{n} \biggr)^2\\
+    & = s^2 + n \biggl( \frac{t^2 - 2 s t + s^2}{n^2} \biggr) \\
+    & = \frac{1}{n} \bigl(t^2 - 2 s t + s^2 (1 + n)\bigr).
+  \end{eqnarray*}
+  This is minimum when
+  \[ \frac{\d}{\d s} \bigl( t^2 - 2 s t + s^2 (1 + n) \bigr) =
+     2 s (1 + n) - 2 t = 0 \]
+  i.e., when
+  \[ s = \frac{t}{n + 1} \]
+  as claimed.
+\end{proof}
+
+Recall that $\sum_{u^*} n_{u^*} = |G|$.  The lemma tells us that
+\[ \sum_{u^* \in U} n_{u^*}^2 \ge \frac{|G|^2}{|U|}. \]
+Returning to our calculation, then:
+\[ \Pr[v \in G_u]
+   \ge \sum_{u^* \in U} \frac{n_{u^*}^2 - n_{u^*}}{|V| |G|} \\
+   \ge \frac{|G|}{|U| |V|} - \frac{1}{|V|}\\
+   =   \epsilon - \frac{1}{|V|}.
+\]
+
+Now we have to apply this to the KCDSA impersonation problem.  Let $U$ be the
+set of choices of public key $X$, adversary's random decisions, and the
+answers to the adversary's random-oracle queries.  This is finite, since the
+running time of the adversary is bounded.  Let $V = \Bin^t$ be the space of
+our possible challenges.  Let $G$ be the set of `good' pairs, where the
+adversary successfully outputs a forgery.  The probability that the adversary
+impersonates the first time is $\epsilon$.  If this happens, we rewind and
+give a different response.  Since we hold everything else fixed, the
+adversary's $r$ is the same.  We choose a new $m' \ne m$ and give it to the
+adversary.  Finally, the analysis we did above tells us that the probability
+that the adversary successfully forges again is at least $\epsilon - 2^{-t}$.
+The stated result follows.
+    
+\begin{slide}
+  \head{Zero-knowledge \seq: KCDSA as identification protocol (cont.)}
+
+  \begin{itemize}
+  \item Zero-knowledge: we need a simulator.  We work in the random oracle
+    model.  The simulator is allowed to make up bits of the random oracle.
+    \begin{enumerate}
+    \item Simulator chooses $r \inr \Bin^t$ at random, and gives $r$ to the
+      verifier.
+    \item Simulator runs verifier, and is given $m$.
+    \item Simulator computes $u = (r \xor m) \bmod q$, and chooses $s \inr
+      \F_q$ at random.
+    \item If verifier has already queried $H(s A + u X)$, then we abort and
+      try again.  Otherwise, it arranges that $H(s A + u X) = r$.
+    \end{enumerate}
+    If the verifier makes $n$ random oracle queries, the failure only occurs
+    with probability $n/q$.
+  \end{itemize}
+\end{slide}
+
+
+\begin{slide}
+  \head{Zero-knowledge \seq: complexity theory and ZK}
+
+  A \emph{language} $L \subseteq \Bin^*$ is a set of bit-strings.
+
+  A \emph{polynomial-time Turing machine} is a machine for which there is a
+  polynomial $p(\cdot)$ such that, on any input $x \in \Bin^*$, it always
+  halts within $p(|x|)$ steps.
+
+  A language $L \in \mathbf{P}$ if there is a polynomial-time Turing machine
+  $M$ such that $M(x) = 1$ iff $x \in L$.
+
+  A language $L \in \mathbf{NP}$ if there is a language $L' \in \mathbf{P}$
+  and, for any $x$, a $w$ such that $|w| \le \poly(|x|)$ and $(x, w) \in L'$
+  iff $x \in L$.  The $w$ is a \emph{witness}.
+
+  Zero-knowledge proof systems exist for all languages in $\mathbf{NP}$.
+  Example statements:
+  \begin{itemize}
+  \item Two ciphertexts are encryptions of the same plaintext.
+  \item A ciphertext is the encryption of a given plaintext.
+  \end{itemize}
+\end{slide}
+
+\xcalways\subsection{Key-exchange security}\x
+
+\begin{slide}
+  \resetseq
+  \head{Key-exchange \seq: introduction}
+  \topic{introduction}
+
+  Key-exchange seems very difficult.  Many protocols have subtle weaknesses.
+  It would be nice to `prove' security.  There are two approaches:
+  \begin{enumerate}
+  \item Express messages and beliefs of the participants in a formal logic,
+    and use inference rules to show that the participants believe the right
+    things at the end [BAN88, Jac97].  This works if the inference rules are
+    correct, and the protocol is translated correctly.
+  \item Define a model for communication and a notion of security, and bound
+    the probability that any adversary within the model can defeat the
+    security of the protocol [BR93, BR95, BJM97, BM97, BCK98, Sho99, CK01].
+    OK if the security notion is right, and the adversary considered is
+    sufficiently powerful.
+  \end{enumerate}
+  Second approach can give useful, quantitative results, if we believe the
+  model is good.
+\end{slide}
+
+\begin{slide}
+  \head{Key-exchange \seq: introduction}
+
+  We describe the model of Canetti and Krawczyk [CK01] and their notion of
+  \emph{SK-security}.
+  \begin{itemize}
+  \item Earlier models were either too restrictive ([BR93] \emph{matching
+    conversations}, [Sho99] termination requirement) or flawed ([BR93]
+    again).
+  \item\relax [CK01] shows that SK-security suffices for implementing
+    \emph{secure channels} in a plausible model.
+  \item\relax [CK02] shows that SK-security is equivalent to a (slightly
+    relaxed) notion of security (`implementation of ideal functionality') in
+    Canetti's \emph{Universal Composition} (UC) framework [Can01], and can be
+    used to implement UC-secure channels.
+  \end{itemize}
+\end{slide}
+
+\begin{slide}
+  \head{Key-exchange \seq: model -- basics}
+  \topic{model}
+
+  There are two kinds of \emph{participants}:
+  \begin{itemize}
+  \item a number of \emph{parties}, $P_0$, $P_1$, \ldots, $P_{n-1}$, and
+  \item an \emph{adversary}.
+  \end{itemize}
+  A protocol $\Pi$ defines an \emph{initialization function} $I$, which
+  outputs:
+  \begin{itemize}
+  \item a common input $c$ for all participants (all parties and the
+    adversary), and
+  \item a private input $x_i$ for party $P_i$.
+  \end{itemize}
+\end{slide}
+
+\begin{slide}
+  \head{Key-exchange \seq: model -- sessions}
+
+  Protocol execution occurs in \emph{sessions}.  A session $S = (P_i, P_j,
+  s)$ specifies
+  \begin{itemize}
+  \item an \emph{owner} $P_i$ -- the session knows $P_i$'s secret input
+    $x_i$;
+  \item a \emph{partner} $P_j$; and
+  \item a \emph{session-id} $s \in \Bin^{\ell_S}$.
+  \end{itemize}
+  The adversary can create sessions at will, by specifying $(i, j, s)$.
+
+  Restriction: sessions must be \emph{distinct}.
+
+  A pair of sessions $S = (P_i, P_j, s)$ and $T = (P_j, P_i, s)$ are said to
+  be \emph{matching}.
+\end{slide}
+
+\begin{slide}
+  \head{Key-exchange \seq: model -- communication}
+
+  When a session is created, it may output a message to be sent to its
+  matching session.
+
+  The \emph{adversary} is responsible for delivering all messages.
+
+  When a message is delivered to a session, the session may output
+  another message.  It may also \emph{terminate}, either successfully
+  (outputting a session-key $K$ -- \emph{completing}), or unsuccessfully
+  (\emph{aborting}).
+
+  A session which has been created and has not terminated is \emph{running}.
+\end{slide}
+
+\begin{slide}
+  \head{Key-exchange \seq: model -- the adversary}
+
+  As well as creating sessions and delivering messages, the adversary has
+  other capabilities.
+  \begin{itemize}
+  \item It can \emph{expire} a completed session, wiping out any record of
+    its key.
+  \item It can \emph{reveal the state} of a running session.
+  \item It can \emph{reveal the key} of a completed, unexpired session.
+  \item It can \emph{corrupt} a party, learning all of its internal state,
+    including its long-term secret, the states of its running sessions, etc.
+  \end{itemize}
+  A session is \emph{locally exposed} if its state or key has been revealed,
+  or if its owner has been corrupted.  A session is \emph{exposed} if it is
+  locally exposed, or it has a matching session which is exposed.
+\end{slide}
+
+\begin{slide}
+  \head{Key-exchange \seq: model -- session life cycle}
+
+  \[ \def\node#1{%
+       \vbox{%
+       \def\\{\small\crcr}%
+       \halign{\hfil\ignorespaces##\unskip\hfil\cr#1\crcr}%
+     }}
+     \begin{xy}
+       \xygraph{
+         *+[F]\node{Create session $(i, j, s)$}
+         :[d]
+         *+[F:<6pt>]\node{\bf Running\\(send message $\mu$)} ="run"
+         [d]
+         *+[F]\node{Deliver message $\mu'$} ="msg"
+         "msg" :[dll]
+         *+[F:<6pt>]\node{\bf Complete\\(output key $K$)}
+         :[d]
+         *+[F]\node{Expire session}
+         :[d]
+         *+[F:<6pt>]\node{\bf Expired}
+         "msg" :[drr]
+         *+[F:<6pt>]\node{\bf Aborted\\(no output)}
+       }
+       \ar @{->} @<1em> "run"; "msg"
+       \ar @{->} @<1em> "msg"; "run"
+     \end{xy} \]
+\end{slide}
+
+\begin{slide}
+  \head{Key-exchange \seq: model -- SK-security}
+
+  We play a game with the adversary.  At the beginning, we choose a `hidden
+  bit' $b^* \inr \Bin$.
+
+  The adversary can choose a \emph{challenge session} -- any completed,
+  unexposed session.  If $b^* = 1$, we give the adversary the session's key,
+  just as if it revealed it.  If $b^* = 0$, we give the adversary a
+  freshly-generated random key.
+
+  The adversary may continue to create sessions, deliver messages, etc., but
+  may not \emph{expose} the challenge session.  When it finishes, the
+  adversary outputs a \emph{guess} $b$.
+
+  A key-exchange protocol $\Pi$ is \emph{SK-secure} if no adversary can
+  \begin{itemize}
+  \item with non-negligible probability, cause two matching, unexposed
+    sessions to \emph{accept}, but output different keys, or
+  \item with probability non-negligibly greater than $\frac{1}{2}$, guess the
+    \emph{hidden bit}, i.e., $b = b^*$.
+  \end{itemize}
+\end{slide}
+
+\begin{slide}
+  \head{Key-exchange \seq: deniability}
+  \topic{deniability}
+
+  Many key-exchange protocols use digital signatures.  For example:
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $\id{sk}_A$, public key $\id{pk}_A$) &
+    (Private key $\id{sk}_B$, public key $\id{pk}_B$) \\[\medskipamount]
+    $r_A \getsr \Nupto{|G|}$; & $r_B \getsr \Nupto{|G|}$; \\
+    $R_A \gets r_A P$; & $R_B \gets r_B P$; \\
+    \send{->}{R_A}
+    \send{<-}{R_B}
+    $\sigma_A \gets
+      S(\id{sk}_A, \texttt{Alice}, \texttt{Bob}, s, R_A, R_B)$; &
+    \llap{$\sigma_B \gets
+      S(\id{sk}_B, \texttt{Bob}, \texttt{Alice}, s, R_B, R_A)$;} \\
+    \send{->}{\sigma_A}
+    \send{<-}{\sigma_B}
+    Check: $V(\id{pk}_B, \sigma_B, \texttt{Bob}, \texttt{Alice}, s, R_B,
+    R_A)$
+    \\ &
+    \llap{Check: $V(\id{pk}_A, \sigma_A,
+      \texttt{Alice}, \texttt{Bob}, s, R_A, R_B)$}
+  \end{protocol}
+\end{slide}
+
+\begin{slide}
+  \head{Key-exchange \seq: deniability (cont.)}
+
+  Signatures have the property than anyone can verify them.  So we could
+  later prove, to a judge maybe, that Alice and Bob were communicating.
+
+  This is \emph{bad} if you don't want to leave evidence that you were
+  communicating with someone.
+
+  A key-exchange protocol is \emph{deniable} if there's a simulator which
+  produces fake transcripts indistinguishable from real conversations
+  \begin{itemize}
+  \item \emph{without} being given the private keys of the parties involved,
+    and
+  \item even if some of the participants are corrupt.
+  \end{itemize}
+\end{slide}
+
+\endinput
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "wrslides"
+%%% End: 
diff --git a/ecc.mp b/ecc.mp
new file mode 100644
index 0000000..03121fc
--- /dev/null
+++ b/ecc.mp
@@ -0,0 +1,134 @@
+%% Elliptic curve messing about
+
+%% y^2 = x^3 + a x^2 + b
+
+numeric u, v;
+numeric a, b;
+numeric minx, maxx, miny, maxy;
+transform gt;
+pair O;
+%% prologues := 1;
+a = -2; b = 1;
+scale = 2 cm;
+labeloffset := 6 pt;
+
+ahlength := 2 mm;
+ahangle := 30;
+
+O = (0, 0);
+
+vardef ecy(expr x) = sqrt (x*x*x + a*x + b) enddef;
+vardef ecadd(expr u, v) =
+  numeric ux, uy, vx, vy;
+  numeric dx, dy;
+  numeric m;
+  ux := xpart u; uy = ypart u; 
+  vx := xpart v; vy = ypart v;
+  if ux = vx:
+    m := (3*ux*ux + a)/(2*uy);
+  else:
+    m := (vy - uy)/(vx - ux);
+  fi
+  dx := m**2 - ux - vx;
+  dy := m * (ux - dx) - uy;
+  (dx, dy)
+enddef;
+ 
+minx = -2; maxx = 3;
+maxy = ecy(maxx); miny = -maxy;
+u = 7/5 cm;
+v = u * (maxx - minx)/(maxy - miny);
+gt = identity xscaled u yscaled v shifted (10 cm, 10 cm);
+
+vardef eclabel@#(expr l, z) =
+  pickup pencircle scaled 1/4 pt;
+  draw fullcircle scaled 1 mm shifted (z transformed gt);
+  draw thelabel@#(l, z transformed gt);
+enddef;
+
+vardef drawcurve =
+  boolean ok;
+  path p;
+  numeric t;
+  pickup pencircle scaled 1/4 pt;
+  drawarrow ((minx, 0) -- (maxx, 0)) transformed gt;
+  drawarrow ((0, miny) -- (0, maxy)) transformed gt;
+  ok := false;
+  pickup pencircle scaled 2/3 pt;
+  for x = minx step 0.01 until maxx:
+    t := x*x*x + a*x + b;
+    if t >= 0:
+      y := sqrt t;
+      if ok:
+	p := p .. (x, y);
+      else:
+	p := (x, y);
+      fi
+      ok := true;
+    else:
+      if ok:
+	draw (reverse p reflectedabout (O, O + right) .. p .. cycle)
+	  transformed gt;
+      fi
+      ok := false;
+    fi
+  endfor
+  if ok:
+    draw (reverse p reflectedabout (O, O + right) .. p) transformed gt;
+  fi
+enddef;
+
+vardef setbackground(expr c) =
+  save bboxmargin;
+  picture pic;
+  bboxmargin := 1/2 cm;
+  pic := currentpicture;
+  currentpicture := nullpicture;
+  fill (bbox pic) withcolor c;
+  draw pic;
+enddef;
+
+beginfig(0);
+  drawcurve;
+  x0 := -5/4; x1 := 1/4;
+  y0 := -ecy(x0); y1 := ecy(x1);
+  z2 = ecadd(z0, z1);
+  x3 := x2; y3 := -y2;
+  pickup pencircle scaled 1/4 pt;
+  draw ((-0.1)[z0, z3] -- 1.1[z0, z3]) transformed gt dashed evenly;
+  draw ((-0.1)[z2, z3] -- 1.1[z2, z3]) transformed gt dashed evenly;
+  eclabel.bot(btex $P_0$ etex, z0);
+  eclabel.top(btex $P_1$ etex, z1);
+  eclabel.rt(btex $P'$ etex, z3);
+  eclabel.lft(btex $P_2 = -P' = P_0 + P_1$ etex, z2);
+  setbackground(white);
+endfig;
+
+beginfig(1);
+  drawcurve;
+  x0 := -18/16;
+  y0 = ecy(x0);
+  z1 = ecadd(z0, z0);
+  x2 := x1; y2 := -y1;
+  pickup pencircle scaled 1/4 pt;
+  draw ((-0.1)[z0, z2] -- 1.1[z0, z2]) transformed gt dashed evenly;
+  draw ((-0.1)[z2, z1] -- 1.1[z2, z1]) transformed gt dashed evenly;
+  eclabel.top(btex $P_0$ etex, z0);
+  eclabel.rt(btex $P'$ etex, z2);
+  eclabel.lft(btex $P_1 = -P' = 2 P_0$ etex, z1);
+  setbackground(white);
+endfig;
+
+beginfig(2);
+  drawcurve;
+  x0 := 5/2;
+  y0 = ecy(x0);
+  x1 := x0; y1 := -y0;
+  pickup pencircle scaled 1/4 pt;
+  draw ((x0, miny) -- (x0, maxy)) transformed gt dashed evenly;
+  eclabel.rt(btex $P_0$ etex, z0);
+  eclabel.rt(btex $P_1$ etex, z1);
+  setbackground(white);
+endfig;
+
+end;
diff --git a/wrestlers.tex b/wrestlers.tex
new file mode 100644
index 0000000..633a93d
--- /dev/null
+++ b/wrestlers.tex
@@ -0,0 +1,3273 @@
+%%% -*-latex-*-
+%%%
+%%% The Wrestlers Protocol: secure, deniable key-exchange
+%%%
+%%% (c) 2006 Mark Wooding
+%%%
+
+\newif\iffancystyle\fancystylefalse
+\fancystyletrue
+\errorcontextlines=\maxdimen
+\showboxdepth=\maxdimen
+\showboxbreadth=\maxdimen
+
+\iffancystyle
+  \documentclass
+    [a4paper, article, 10pt, numbering, noherefloats, notitlepage,
+    runinsubsubsec]
+    {strayman}
+  \usepackage[T1]{fontenc}
+  \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
+  \usepackage[within = subsection, mdwmargin]{mdwthm}
+  \usepackage{mdwlist}
+  \usepackage{sverb}
+  \PassOptionsToPackage{dvips}{xy}
+\else
+  \documentclass[a4paper]{llncs}
+  \usepackage{a4wide}
+\fi
+
+\PassOptionsToPackage{show}{slowbox}
+%\PassOptionsToPackage{hide}{slowbox}
+\usepackage{mdwtab, mathenv, mdwmath, crypto}
+\usepackage{slowbox}
+\usepackage{amssymb, amstext}
+\usepackage{url, multicol}
+\usepackage{tabularx}
+\DeclareUrlCommand\email{\urlstyle{tt}}
+\ifslowboxshow
+  \usepackage[all]{xy}
+  \turnradius{4pt}
+\fi
+
+\iffancystyle
+  \def\next{\title[The Wrestlers Protocol]}
+\else
+  \def\next{\title}
+\fi
+\next
+  {The Wrestlers Protocol \\
+    A simple, practical, secure, deniable protocol for key-exchange}
+\iffancystyle
+  \author{Mark Wooding \\ \email{mdw@distorted.org.uk}}
+\else
+  \author{Mark Wooding}
+  \institute{\email{mdw@distorted.org.uk}}
+\fi
+
+\iffancystyle
+  \bibliographystyle{mdwalpha}
+  \let\epsilon\varepsilon
+  \let\emptyset\varnothing
+  \let\le\leqslant\let\leq\le
+  \let\ge\geqslant\let\geq\ge
+  \numberwithin{table}{section}
+  \numberwithin{figure}{section}
+  \numberwithin{equation}{subsection}
+  \let\random\$
+\else
+  \bibliographystyle{plain}
+  \expandafter\let\csname claim*\endcsname\claim
+  \expandafter\let\csname endclaim*\endcsname\endclaim
+\fi
+
+\iffancystyle
+  \newcommand{\Nupto}[1]{\N_{<{#1}}}
+\else
+  \newcommand{\Nupto}[1]{\{0, 1, \ldots, #1 - 1\}}
+\fi
+\let\Bin\Sigma
+\let\emptystring\lambda
+\edef\Pr{\expandafter\noexpand\Pr\nolimits}
+\newcommand{\bitsto}{\mathbin{..}}
+\newcommand{\E}{{\mathcal{E}}}
+\newcommand{\M}{{\mathcal{M}}}
+\iffancystyle
+  \def\description{%
+    \basedescript{%
+      \let\makelabel\textit%
+      \desclabelstyle\multilinelabel%
+      \desclabelwidth{1in}%
+    }%
+  }
+\fi
+\def\fixme#1{\marginpar{FIXME}[FIXME: #1]}
+\def\hex#1{\texttt{#1}_{x}}
+
+\def\dbox#1{%
+  \vtop{%
+    \def\\{\unskip\egroup\hbox\bgroup\strut\ignorespaces}%
+    \hbox{\strut#1}%
+  }%
+}
+
+\def\Wident{\Xid{W}{ident}}
+\def\Wkx{\Xid{W}{kx}}
+\def\Wdkx{\Xid{W}{dkx}}
+\def\Func#1#2{\mathcal{F}[#1\to#2]}
+\def\diff#1#2{\Delta_{#1, #2}}
+\def\Hid{H_{\textit{ID}}}
+
+%% protocol run diagrams
+\def\PRaction#1{#1\ar[r]}
+\def\PRcreatex#1{\PRaction{\textsf{Create session\space}#1}}
+\def\PRcreate#1#2#3{\PRcreatex{(\text{#1},\text{#2},#3)}}
+\def\PRreceivex#1{\PRaction{\textsf{Receive\space}#1}}
+\def\PRreceive#1#2{\PRreceivex{\msg{#1}{#2}}}
+\def\PRsession#1{\relax\mathstrut#1\ar[r]}
+\def\msg#1#2{(\cookie{#1},#2)}
+\def\PRresult#1{#1}
+\def\PRsendx#1{\PRresult{\textsf{Send\space}#1}}
+\def\PRsend#1#2{\PRsendx{\msg{#1}{#2}}}
+\def\PRcomplete#1{\textsf{Complete:\space}#1}
+\def\PRstate#1{\textsf{State:\space}#1}
+\def\PRignore{\textsf{(ignored)}}
+\def\PRreveal{\textsf{Session-state reveal}\ar[r]}
+\def\protocolrun#1{\[\xymatrix @R=0pt @C=2em {#1}\]}
+
+%% class-ids for proof of extractor lemma
+\let\Cid=\Lambda
+\let\Csession=S
+\let\Cindex=r
+\let\Cquery=Q
+\let\Chash=H
+\let\Ccheck=c
+\let\Ccheckset=V
+\let\Ccount=\nu
+
+\begin{document}
+
+%%%--------------------------------------------------------------------------
+
+\maketitle
+
+\begin{abstract}
+  We describe and prove (in the random-oracle model) the security of a simple
+  but efficient zero-knowledge identification scheme, whose security is based
+  on the computational Diffie-Hellman problem.  Unlike other recent proposals
+  for efficient identification protocols, we don't need any additional
+  assumptions, such as the Knowledge of Exponent assumption.
+
+  From this beginning, we build a simple key-exchange protocol, and prove
+  that it achieves `SK-security' -- and hence security in Canetti's Universal
+  Composability framework.
+
+  Finally, we show how to turn the simple key-exchange protocol into a
+  slightly more complex one which provides a number of valuable `real-life'
+  properties, without damaging its security.
+\end{abstract}
+
+\iffancystyle
+\newpage
+\columnsep=2em \columnseprule=0pt
+\tableofcontents[\begin{multicols}{2}\raggedright][\end{multicols}]
+%%\listoffigures[\begin{multicols}{2}\raggedright][\end{multicols}]
+%% \listoftables[\begin{multicols}{2}\raggedright][\end{multicols}]
+\newpage
+\fi
+
+%%%--------------------------------------------------------------------------
+
+\section{Introduction}
+
+%% Blah...
+%% Very brief discussion of key-exchange
+%% models of secure key exchange
+%% mutter about protocol actually being implemented
+
+
+
+In this paper, we concern ourselves mainly with \emph{authenticated key
+  exchange}.  That is, we present a system whereby two parties, say Alice and
+Bob, can communicate over an insecure channel, and end up knowing a shared
+random key unknown to anyone else.  \fixme{write the rest of this}
+
+
+\subsection{Asymptotic and concrete security results}
+
+Most security definitions for identification (particularly zero-knowledge)
+and key-exchange in the literature are \emph{asymptotic}.  That is, they
+consider a family of related protocols, indexed by a \emph{security
+parameter}~$k$; they that any \emph{polynomially-bounded} adversary has only
+\emph{negligible} advantage.  A polynomially-bounded adversary is one whose
+running time is a bounded by some polynomial~$t(k)$.  The security definition
+requires that, for any such polynomially-bounded adversary, and any
+polynomial $p(k)$, there is a bound~$n$ such that the adversary's advantage
+is less than $p(k)$ for all choices of $k > n$.
+
+Such asymptotic notions are theoretically interesting, and have obvious
+connections to complexity theory.  Unfortunately, such an asymptotic result
+tells us nothing at all about the security of a particular instance of a
+protocol, or what parameter sizes one needs to choose for a given level of
+security against a particular kind of adversary.  Koblitz and Menezes
+\cite{Koblitz:2006:ALP} (among other useful observations) give examples of
+protocols, proven to meet asymptotic notions of security, whose security
+proofs guarantee nothing at all for the kinds of parameters typically used in
+practice.
+
+Since, above all, we're interested in analysing a practical and implemented
+protocol, we follow here the `practice-oriented provable security' approach
+largely inspired by Bellare and Rogaway, and exemplified by
+\cite{Bellare:1994:SCB, Bellare:1995:XMN, Bellare:1995:OAE, Bellare:1996:ESD,
+  Bellare:1996:KHF, Bellare:2000:CST}; see also \cite{Bellare:1999:POP}.
+Rather than attempting to say, formally, whether or not a protocol is
+`secure', we associate with each protocol an `insecurity function' which
+gives an upper bound on the advantage of any adversary attacking the protocol
+within given resource bounds.
+
+
+\subsection{Desirable properties of our protocols}
+
+Our identification protocol has a number of desirable properties.
+\begin{itemize}
+\item It is \emph{simple} to understand and implement.  In particular, it
+  requires only two messages.
+\item It is fairly \emph{efficient}, requiring two scalar multiplications by
+  each of the prover and verifier.
+\item It is provably \emph{secure} (in the random oracle model), assuming the
+  intractability of the computational Diffie-Hellman problem.
+\end{itemize}
+
+Our key-exchange protocol also has a number of desirable properties.
+\begin{itemize}
+\item It is fairly \emph{simple} to understand and implement, though there
+  are a few subtleties.  In particular, it is \emph{symmetrical}.  We have
+  implemented a virtual private network system based on this protocol.
+\item It is \emph{efficient}, requiring four scalar multiplications by each
+  participant.  The communication can be reduced to three messages by
+  breaking the protocol's symmetry.
+\item It is provably \emph{secure} (again, in the random oracle model),
+  assuming the intractability of the computational Diffie-Hellman problem,
+  and the security of a symmetric encryption scheme.
+\item It provides \emph{perfect forward secrecy}.  That is, even if a user's
+  long-term secrets are compromised, past sessions remain secure.
+\item It is \emph{deniable}.  It is possible to construct simulated
+  transcripts of protocol executions between any number of parties without
+  knowing any of their private keys.  The simulated transcripts are (almost)
+  indistinguishable from real protocol transcripts.  Hence, a transcript
+  does not provide useful evidence that a given party was really involved in
+  a given protocol execution.
+\end{itemize}
+
+
+\subsection{Formal models for key-exchange}
+
+Many proposed key-exchange protocols have turned out to have subtle security
+flaws.  Burrows, Abadi and Needham \cite{Burrows:1989:LA} presented a formal
+logic for the analysis of authentication and key-exchange protocols.  Formal
+models for analysing the \emph{computational} security of key-exchange
+protocols began with Bellare and Rogaway \cite{Bellare:1994:EAK}, extended in
+\cite{Bellare:1995:PSS, Blake-Wilson:1997:KAP, Blake-Wilson:1998:EAA,
+  Bellare:1998:MAD}.
+
+
+
+
+\subsection{Outline of the paper}
+
+The remaining sections of this paper are as follows.
+\begin{itemize}
+\item Section \ref{sec:prelim} provides the essential groundwork for the rest
+  of the paper.  It introduces important notation, and describes security
+  notions and intractability assumptions.
+\item Section \ref{sec:zk-ident} describes our zero-knowledge identification
+  protocol and proves its security.
+\item Section \ref{sec:kx} describes the simple version of our key-exchange
+  protocol, and proves its security and deniability.  It also describes some
+  minor modifications which bring practical benefits without damaging
+  security. 
+\item Finally, section \ref{sec:...} presents our conclusions.
+\end{itemize}
+
+%%%--------------------------------------------------------------------------
+
+\section{Preliminaries}
+\label{sec:prelim}
+
+\subsection{Miscellaneous notation}
+
+We write $\Func{D}{R}$ for the set of all functions with domain $D$ and range
+$R$.
+\iffancystyle
+We write $\Nupto{n} = \{\, i \in \Z \mid 0 \le i < n \,\} = \{0, 1, \ldots, n
+- 1\}$ for the set of nonnegative integers less than $n$.
+\fi
+
+
+\subsection{Groups}
+
+Let $(G, +)$ be a cyclic group\footnote{
+  We find that additive group notation is easier to read.  In particular, in
+  multiplicative groups, one ends up with many interesting things tucked away
+  in little superscripts.}%
+of prime order $q$, and generated by an element $P$.  We shall write the
+identity of $G$ as $0_G$, or simply as $0$ when no ambiguity is likely to
+arise.  Thus, we have $\langle P \rangle = G$ and $q P = 0$.  Any $X \in G$
+can be written as $X = x P$ for some $x \in \Nupto{q}$.
+
+
+\subsection{Bit strings and encodings}
+\label{sec:bitenc}
+
+Let $\Bin = \{0, 1\}$ be the set of binary digits.  Then $\Bin^n$ is the set
+of $n$-bit strings, and $\Bin^*$ the set of all (finite) bit strings.  If $x
+\in \Bin^n$ is a bit string, we write its length as $|x| = n$.  For a bit
+string $x \in \Bin^n$, and for $0 \le i < n$, we write $x[i]$ as the $i$th
+bit of $x$.  The empty string is denoted $\emptystring$.
+
+Let $x$ and $y$ be two bit strings.  If $|x| = |y| = n$, we write $x \xor y$
+to mean the bitwise exclusive-or of $x$ and $y$: if $z = x \xor y$ then $|z|
+= n$, and $z[i] = (x[i] + y[i]) \bmod 2$ for $0 \le i < n$.  We write $x \cat
+y$ to mean the concatenation of $x$ and $y$: if $z = x \cat y$ then $|z| =
+|x| + |y|$ and $z[i] = x[i]$ if $0 \le i < |x|$ and $z[i] = y[i - |x|]$ if
+$|x| < i \le |x| + |y|$.
+
+Finally, we let $\bot$ be a value distinct from any bit string.
+
+We shall want to encode group elements $X \in G$ and indices $x \in I =
+\Nupto{|G|}$ as bit strings.  To this end, we shall assume the existence of
+integers $\ell_G, \ell_I > 0$ and functions
+\[
+  e_S\colon S \to \Bin^{\ell_S}
+  \quad \textrm{and} \quad
+  d_S\colon \Bin^{\ell_S} \to S \cup \{ \bot \}
+  \qquad
+  \textrm{for } S \in \{ G, I \}.
+\]
+with the following properties.
+\begin{itemize}
+\item The functions are \emph{unique} and \emph{unambiguous}, i.e., for any
+  $t \in \Bin^{\ell_S}$, we have
+  \[ d_S(t) = \begin{cases}
+       s & if there is some $s \in S$ such that $t = e_S(s)$, or \\
+       \bot & if no such $s$ exists.
+  \end{cases}
+  \]
+\item The functions should be \emph{efficient} to compute.  Indeed, we shall
+  be assuming that the time taken for encoding and decoding is essentially
+  trivial.
+\end{itemize}
+Note that, as we have defined them, all encodings of group elements are the
+same length, and similarly for encodings of indices.  This is necessary for
+the security of our protocols.
+
+We shall frequently abuse notation by omitting the encoding and decoding
+functions where it is obvious that they are required.
+
+
+\subsection{Games, adversaries, and oracles}
+\label{sec:games}
+
+Many of the security definitions and results given here make use of
+\emph{games}, played with an \emph{adversary}.  An adversary is a
+probabilistic algorithm.  In some games, the adversary is additionally
+equipped with \emph{oracles}, which perform computations with values chosen
+by the adversary and secrets chosen by the game but not revealed to the
+adversary.  We impose limits on the adversary's resource usage: in
+particular, the total time it takes, and the number of queries it makes to
+its various oracles.  Throughout, we include the size of the adversary's
+program as part of its `time', in order to model adversaries which contain
+large precomputed tables.
+
+The games provide models of someone trying to attack a construction or
+protocol.  For security, we will either define a notion of `winning' the
+game, and require that all adversaries have only a very small probability of
+winning, or we consider two different games and require that no adversary can
+distinguish between the two except with very small probability.  
+
+Our proofs make frequent use of sequences of games; see
+\cite{Shoup:2004:SGT,Bellare:2004:CBG}.  The presentation owes much to Shoup
+\cite{Shoup:2004:SGT}.  We begin with a game $\G0$ based directly on a
+relevant security definition, and construct a sequence of games $\G1$, $\G2$,
+\dots, each slightly different from the last.  We define all of the games in
+a sequence over the same underlying probability space -- the random coins
+tossed by the algorithms involved -- though different games may have slightly
+differently-defined events and random variables.  Our goal in doing this is
+to bound the probability of the adversary winning the initial game $\G0$ by
+simultaneously (a) relating the probability of this event to that of
+corresponding events in subsequent games, and (b) simplifying the game until
+the probability of the corresponding event can be computed directly.
+
+The following simple lemma from \cite{Shoup:2001:OR} will be frequently
+useful.
+\begin{lemma}[Difference Lemma]
+  \label{lem:shoup}
+  Let $S$, $T$, $F$ be events.  Suppose $\Pr[S|\bar F] = \Pr[T|\bar F]$.
+  Then $|\Pr[S] - \Pr[T]| \le \Pr[F]$.
+\end{lemma}
+\begin{proof}
+  A simple calculation:
+  \begin{eqnarray*}[rl]
+    |\Pr[S] - \Pr[T]|
+    & = |(\Pr[S|F]\Pr[F] + \Pr[S|\bar F]\Pr[\bar F]) -
+         (\Pr[T|F]\Pr[F] + \Pr[T|\bar F]\Pr[\bar F])| \\
+    & = \Pr[F] \cdot |\Pr[S|F] - \Pr[T|F]| \\
+    & \le \Pr[F]
+  \end{eqnarray*}
+  and we're done!
+\end{proof}
+
+
+\subsection{The random oracle model}
+\label{sec:ro}
+
+In particular, most of our results will make use of the \emph{random oracle}
+model \cite{Bellare:1993:ROP}, in which all the participants, including the
+adversary, have access to a number of `random oracles'.  A random oracle with
+domain $D$ and range $R$ is an oracle which computes a function chosen
+uniformly at random from the set of all such functions.  (In the original
+paper \cite{Bellare:1993:ROP}, random oracles are considered having domain
+$\Bin^*$ and range $\Bin^\omega$; we use finite random oracles here, because
+they're easier to work with.)
+
+Given a protocol proven secure in the random oracle model, we can instantiate
+each random oracle by a supposedly-secure hash function and be fairly
+confident that either our protocol will be similarly secure, or one of the
+hash functions we chose has some unfortunate property.
+
+Proofs in the random oracle must be interpreted carefully.  For example,
+Canetti, Goldreich and Halevi \cite{Canetti:2004:ROM} show that there are
+schemes which can be proven secure in the random oracle model but provably
+have no secure instantiation in the standard model.
+
+The random oracle model is useful for constructing reductions and simulators
+for two main reasons.
+\begin{enumerate}
+\item One can use the transcript of an adversary's queries to random oracles
+  in order to extract knowledge from it.
+\item One can `program' a random oracle so as to avoid being bound by prior
+  `commitments', or to guide an adversary towards solving a selected instance
+  of some problem.
+\end{enumerate}
+Our proofs only make use of the first feature.  This becomes particularly
+important when we consider issues of zero-knowledge and deniability in a
+concurrent setting, because we want to be able to claim that we retain these
+features when the random oracle is instantiated using a cryptographic hash
+function, and hash functions definitely aren't `programmable' in this way!
+The former property seems rather more defensible -- one would indeed hope
+that the only sensible way of working out (anything about) the hash of a
+particular string is to actually compute the hash function, and the random
+oracle model is, we hope, just giving us a `hook' into this process.
+
+(Our protocols can be modified to make use of bilinear pairings so as to
+provide identity-based identification and key-exchange, using the techniques
+of \cite{Boneh:2001:IBE}.  Proving the security of the modifications we
+discuss would involve `programming' random oracles, but this doesn't affect
+the zero-knowledge or deniability of the resulting protocols.)
+
+
+\subsection{Notation for algorithms}
+
+We shall have occasion to describe algorithms by means of a pseudocode.  Our
+choice of pseudocode is unlikely to be particularly controversial.  We let $x
+\gets y$ denote the action of setting $x$ to the value $y$; similarly, $x
+\getsr Y$ denotes the action of sampling $x$ from the set $Y$ uniformly at
+random.
+
+The expression $a \gets A^{O(\cdot, x)}(y)$ means `assign to $a$ the value
+output by algorithm $A$ on input $y$, and with oracle access to the algorithm
+which, given input $z$, computes $O(z, x)$'.
+
+We make use of conditional (\IF-\ELSE) and looping (\FOR-\DO and \WHILE-\DO)
+constructions; in order to reduce the amount of space taken up, the bodies of
+such constructions are shown by indentation only.
+
+We don't declare the types of our variables explicitly, assuming that these
+will be obvious by inspection; also, we don't describe our variables' scopes
+explicitly, leaving the reader to determine these from context.
+
+Finally, the notation $\Pr[\textit{algorithm} : \textit{condition}]$ denotes
+the probability that \textit{condition} is true after running the given
+\textit{algorithm}.
+
+
+\subsection{Diffie-Hellman problems}
+\label{sec:dhp}
+
+The security of our protocols is related to the hardness of the
+computational, decisional, and gap Diffie-Hellman problems in the group $G$.
+We define these problems and what it means for them to be `hard' here.
+
+The \emph{computational} Diffie-Hellman problem (CDH) is as follows: given
+two group elements $X = x P$ and $Y = y P$, find $Z = x y P$.
+\begin{definition}[The computational Diffie-Hellman problem]
+  Let $(G, +)$ be a cyclic group generated by $P$.  For any adversary $A$, we
+  say that $A$'s \emph{success probability} at solving the computational
+  Diffie-Hellman problem in $G$ is
+  \[ \Succ{cdh}{G}(A) =
+      \Pr[ x \getsr I; y \getsr \Nupto{|G|} : A(x P, y P) = x y P ]
+  \]
+  where the probability is taken over the random choices of $x$ and $y$ and
+  any random decisions made by $A$.  We say that the \emph{CDH insecurity
+  function} of $G$ is
+  \[ \InSec{cdh}(G; t) = \max_A \Succ{cdh}{G}(A) \]
+  where the maximum is taken over adversaries which complete in time $t$.
+\end{definition}
+Certainly, if one can compute discrete logarithms in the group $G$ (i.e.,
+given $x P$, find $x$), then one can solve the computational Diffie-Hellman
+problem.  The converse is not clear, though.  Shoup \cite{Shoup:1997:LBD}
+gives us some confidence in the difficulty of the problem by showing that a
+\emph{generic} adversary -- i.e., one which makes no use of the specific
+structure of a group -- has success probability no greater than $q^2/|G|$.
+
+This isn't quite sufficient for our purposes.  Our proofs will be able to
+come up with (possibly) a large number of guesses for the correct answer, and
+at most one of them will be correct.  Unfortunately, working out which one is
+right seems, in general, to be difficult.  This is the \emph{decision}
+Diffie-Hellman problem (DDH), which \cite{Shoup:1997:LBD} shows, in the
+generic group model, is about as hard as CDH.  (See \cite{Boneh:1998:DDP} for
+a survey of the decision Diffie-Hellman problem.)
+
+Our reference problem will be a `multiple-guess computational Diffie-Hellman
+problem' (MCDH), which is captured by a game as follows.  An adversary is
+given a pair of group elements $(x P, y P)$, and an oracle $V(\cdot)$ which
+accepts group elements as input.  The adversary wins the game if it queries
+$V(x y P)$.
+\begin{definition}[The multiple-guess computational Diffie-Hellman problem]
+  \label{def:mcdh}
+  Let $(G, +)$ be a cyclic group generated by $P$.  For some adversary $A$,
+  we say that $A$'s \emph{success probability} at solving the multiple-guess
+  computational Diffie-Hellman problem in $G$ is
+  \[ \Succ{mcdh}{G}(A) = \Pr[\Game{mcdh}{G}(A) = 1] \]
+  where $\Game{mcdh}{G}(A)$ is shown in figure~\ref{fig:mcdh}.  We say that
+  the \emph{MCDH insecurity function of $G$} is
+  \[ \InSec{mcdh}(G; t, q_V) = \max_A \Succ{mcdh}{G}(A) \]
+  where the maximum is taken over adversaries which complete in time $t$ and
+  make at most $q_V$-oracle queries.
+\end{definition}
+
+\begin{figure}
+  \begin{program}
+    $\Game{mcdh}{G}(A)$: \+ \\
+      $w \gets 0$; \\
+      $x \getsr \Nupto{|G|}$; $y \getsr \Nupto{|G|}$; \\
+      $A^{V(\cdot)}(x P, y P)$; \\
+      \RETURN $w$;
+    \next
+    Function $V(Z)$: \+ \\
+      \IF $Z = x y P$ \THEN \\ \ind
+        $w \gets 1$; \\
+        \RETURN $1$; \- \\
+      \RETURN $0$;
+  \end{program}
+
+  \caption{The multiple-guess computational Diffie-Hellman problem:
+    $\Game{mcdh}{G}(A)$}
+  \label{fig:mcdh}
+\end{figure}
+
+Note that our MCDH problem is not quite the `gap Diffie-Hellman problem'
+(GDH).  The gap problem measures the intractibility of solving CDH even with
+the assistance of an oracle for solving (restricted) decision Diffie-Hellman
+problems in the group.  Specifically, the adversary is given $(X, Y) = (x P,
+y P)$ and tries to find $Z = x y P$, as for CDH, but now it has access to an
+oracle $D(R, S)$ which answers $1$ if $S = x R$ and $0$ otherwise.
+
+Clearly MCDH is at least as hard as GDH, since our simple verification oracle
+$V(Z)$ can be simulated with the gap problem's DDH oracle, as $D(Y, Z)$.
+However, we can (loosely) relate the difficulty of MCDH to the difficulty of
+CDH.
+\begin{proposition}[Comparison of MCDH and CDH security]
+  For any cyclic group $(G, +)$,
+  \[ \InSec{mcdh}(G; t, q_V) \le q_V\cdot\InSec{cdh}(G; t + O(q_V)). \]
+\end{proposition}
+\begin{proof}
+  Let $A$ be an adversary attacking the multiple-guess computational
+  Diffie-Hellman problem in $G$, and suppose that it runs in time $t$ and
+  issues $q_V$ queries to its verification oracle.
+
+  We use a sequence of games.  Game $\G0$ is the original MCDH attack game.
+  In each game $\G{i}$, we let the event $S_i$ be the probability that the
+  adversary wins the game.
+
+  Game $\G1$ is the same as $\G0$, except that we change the behaviour of the
+  verification oracle.  Specifically, we make the oracle always return $0$.
+  We claim that this doesn't affect the adversary's probability of winning,
+  i.e., $\Pr[S_1] = \Pr[S_0]$.  To see this, note that if none of the
+  adversary's $V(\cdot)$ queries was correct, then there is no change in the
+  game; conversely, if any query was correct, then the adversary will have
+  won regardless of its subsequent behaviour (which may differ arbitrarily
+  between the two games).
+
+  We are now ready to construct from $A$ an adversary $B$ attacking the
+  standard computational Diffie-Hellman problem.
+  \begin{program}
+    Adversary $B(X, Y)$: \+ \\
+      $n \gets 0$; \\
+      \FOR $i \in \Nupto{q_V}$ \DO $Q_i \gets 0$; \\
+      $A^{V(\cdot)}$; \\
+      $r \getsr \Nupto{n}$; \\
+      \RETURN $Q_r$;
+    \next
+    Function $D(Z')$: \+ \\
+      $Q_n \gets Z'$; \\
+      $n \gets n + 1$; \\
+      \RETURN $0$;
+  \end{program}
+  Observe that $B$ provides $A$ with an accurate simulation of game $\G1$.
+  Moreover, at the end of the algorithm, we have $0 < n \le q_V$, the
+  output of $A$ is stored in $Q_{n-1}$ and the values $Q_0$, $Q_1$, \dots,
+  $Q_{n-1}$ are the values of $A$'s oracle queries.  Hence, with probability
+  $Pr[S_1]$, at least of one of the $Q_i$ is the correct answer to the CDH
+  problem.  Let $\epsilon = \Pr[S_1] = \Pr[S_0]$; we claim that $B$'s
+  probability of success is at least $\epsilon/q_V$.  The proposition
+  follows directly from this claim and that, because $A$ was chosen
+  arbitrarily, we can maximize and count resources.
+
+  We now prove the above claim.  For $0 \le i < q_V$, let $W_i$ be the
+  event that $Q_i = x y P$, i.e., that $Q_i$ is the correct response.  A
+  simple union bound shows that
+  \[ \sum_{0\le i<j} \Pr[W_i \mid n = j] \ge \epsilon. \]
+  We now perform a calculation:
+  \begin{eqnarray*}[rl]
+    \Succ{cdh}{G}(B)
+    & =  \sum_{0\le i<q_V} \Pr[W_i \land r = i] \\
+    & =  \sum_{0<j\le q_V} \Pr[n = j]
+         \biggl( \sum_{0\le i<j} \Pr[W_i \land r = i \mid n = j] \biggr) \\
+    & =  \sum_{0<j\le q_V} \Pr[n = j]
+         \biggl( \frac{1}{j} \sum_{0\le i<j} \Pr[W_i \mid n = j] \biggr) \\
+    &\ge \sum_{0<j\le q_V} \Pr[n = j] \frac{\epsilon}{j} \\
+    &\ge \frac{\epsilon}{q_V} \sum_{0<j\le q_V} \Pr[n = j] \\
+    & =  \frac{\epsilon}{q_V}.
+  \end{eqnarray*}
+  which completes the proof.
+\end{proof}
+
+
+\subsection{Example groups and encodings}
+
+For nonnegative integers $0 \le n < 2^\ell$, there is a natural binary
+encoding $N_\ell\colon \Nupto{2^\ell} \to \Bin^\ell$ which we can define
+recursively as follows.
+\[ N_0(0) = \emptystring \qquad
+   N_\ell(n) = \begin{cases}
+     N_{\ell-1}(n) \cat 0              & if $0 \le n < 2^{\ell-1}$ \\
+     N_{\ell-1}(n - 2^{\ell-1}) \cat 1 & if $2^{\ell-1} \le n < 2^\ell$.
+   \end{cases}
+\]
+Given an encoding $a = N_\ell(n)$ we can recover $n$ as
+\[ n = \sum_{0\le i<\ell} a[i] 2^i. \]
+Hence, given some limit $L \le 2^\ell$, we can encode elements of $\Nupto{L}$
+using the functions $(e, d)$:
+\[ e(L, \ell, n) = N_\ell(n) \qquad
+   d(L, \ell, a) = \begin{cases}
+     N_\ell(a) & if $N_\ell(a) < L$ \\
+     \bot      & otherwise
+   \end{cases}
+\]
+The reader can verify that the functions $e(L, \ell, \cdot)$ and $d(L, \ell,
+\cdot)$ satisfy the requirements of section~\ref{sec:bitenc}.
+
+Given some $q < 2^{\ell_I}$ and $I = \Nupto{q}$, then, we can define an
+encoding $(e_I, d_I)$ by $e_I(n) = e(q, \ell_I, n)$ and $d_I(a) = d(q,
+\ell_I, a)$.
+
+Let $p$ and $q$ be primes, with $q|(p - 1)$.  Then there is an order-$q$
+subgroup of $(\Z/p\Z)^*$.  In practice, an order-$q$ element can be found
+easily by taking elements $h \in (\Z/p\Z)^*$ at random and computing $g =
+h^{(p-1)/2}$ until $g \ne 1$; then $G = \langle g \rangle$ is a group of $q$
+elements.  Assuming that $p$ and $q$ are sufficiently large, the
+Diffie-Hellman problems seem to be difficult in $G$.  Some texts recommend
+additional restrictions on $p$, in particular that $(p - 1)/2q$ be either
+prime or the product of large primes.  Primes of this form protect against
+small-subgroup attacks; but our protocols are naturally immune to these
+attacks, so such precautions are unnecessary here.  Elements of $G$ can be
+encoded readily, since each element $n + p\Z$ of $\Z/p\Z$ has an obvious
+`representative' integer $n$ such that $0 \le n < p$, and given $2^{\ell_G} >
+p$, we can encode $n$ as $e(p, \ell_G, n)$, as above.
+
+Alternatively, let $\F = \gf{p^f}$ be a finite field, and $E$ be an elliptic
+curve defined over $\F$ such that the group $E(\F)$ of $\F$-rational points
+of $E$ has a prime-order cyclic subgroup $G$.  Elements of $G$ can be
+represented as pairs of elements of $\F$.  If $f = 1$, i.e., $\F = \Z/p\Z$
+then field elements can be encoded as above.  If $p = 2$, we can represent
+the field as $\F_2/(p(x))$ for some irreducible polynomial $p(x) \in \F_2[x]$
+of degree $f$.  An element $r \in \F$ can then be represented by a polynomial
+$r(x)$ with degree less than $f$, and coefficients $c_i \in \{0, 1\}$, i.e.,
+\[ r(x) = \sum_{0\le i<f} c_i x^i \]
+and hence we can uniquely encode $r$ as an $f$-bit string $a$ such that $a[i]
+= c_i$.
+
+
+\subsection{Symmetric encryption}
+\label{sec:sym-enc}
+
+Our key-exchange protocol requires a symmetric encryption scheme.  Our
+definition is fairly standard, except that, rather than specifying a
+key-generation algorithm, we assume that key generation simply involves
+selecting a string of a given length uniformly at random.
+\begin{definition}[Symmetric encryption schemes]
+  A \emph{symmetric encryption scheme} $\E = (\kappa, E, D)$ consists of:
+  \begin{itemize}
+  \item an integer $\kappa \ge 0$,
+  \item a randomized \emph{encryption algorithm} $E$ which, on input $K \in
+    \Bin^\kappa$ and $p \in \Bin^*$ outputs some $c \in \Bin^*$, written $c
+    \gets E_K(p)$;
+  \item a \emph{decryption algorithm} $D$ which, on input $K \in \Bin^\kappa$
+    and $c \in \Bin^*$ outputs some $p' \in \Bin^* \cup \{\bot\}$, written
+    $p' \gets D_K(c)$.
+  \end{itemize}
+  Furthermore, a symmetric encryption scheme must be \emph{sound}: that is,
+  if $c \gets E_K(p)$ for some $K \in \Bin^\kappa$ and $p \in \Bin^*$, and
+  $p' \gets D_K(c)$ then $p = p'$.
+\end{definition}
+Our security notion for symmetric encryption is the standard notion of
+left-or-right indistinguishability of ciphertexts under chosen-ciphertext
+attack.
+\begin{definition}
+  [Indistinguishability under chosen-ciphertext attack (IND-CCA)]
+  Let $\E = (\kappa, E, D)$ be a symmetric encryption scheme, and $A$ be an
+  adversary.  Let $\id{lr}_b(x_0, x_1) = x_b$ for $b \in \{0, 1\}$.  Let
+  \[ P_b =
+    \Pr[K \getsr \Bin^\kappa;
+    b \gets A^{E_K(\id{lr}_b(\cdot, \cdot)), D_K(\cdot)}() :
+    b = 1]
+  \]
+  An adversary is \emph{valid} if
+  \begin{itemize}
+  \item for any query to its encryption oracle $E_K(\id{lr}_b(x_0, x_1))$ we
+    have $|x_0| = |x_1|$, and
+  \item no query to the decryption oracle $D_K(\cdot)$ is equal to any reply
+    from an encryption query.
+  \end{itemize}
+  If $A$ is valid, then we define its \emph{advantage} in attacking the
+  security of $\E$ as follows
+  \[ \Adv{ind-cca}{\E} = P_1 - P_0. \]
+  Further, we define the \emph{IND-CCA insecurity function of $\E$} to be
+  \[ \InSec{ind-cca}(\E; t, q_E, q_D) = \max_A \Adv{ind-cca}{\E}(A) \]
+  where the maximum is taken over all valid adversaries $A$ which run in time
+  $t$, and issue at most $q_E$ encryption and $q_D$ decryption queries.
+\end{definition}
+
+
+\subsection{Simulations}
+\label{sec:sim}
+
+In section~\ref{sec:zk-ident}, we shall prove that our identification
+protocol is zero-knowledge; in section~\ref{sec:denial}, we show that our
+key-exchange protocol is deniable.  In both of these proofs, we shall need to
+demonstrate \emph{simulatability}.  
+
+\subsubsection{General framework}
+Consider a game in which an adversary~$A$ interacts with some `world'~$W$,
+which we shall represent as a probabilistic algorithm.  The world may in fact
+represent a number of honest parties communicating in a concurrent fashion,
+but we can consider them as a single algorithm for our present purposes.
+
+Initially the world and the adversary are both given the same \emph{common
+input}~$c$; in addition, the world is given a \emph{private input}~$w$.
+Both $c$ and~$w$ are computed by an \emph{initialization function}~$I$, which
+is considered to be part of the definition of the game.  Finally, the
+adversary decides somehow that it has finished interacting, and outputs a
+value~$a$.  All this we notate as
+\[ (w, c) \gets I(); a \gets A^{W(w, c)}(c). \]
+This game is \emph{simulatable} if there is an algorithm~$S$ -- the
+\emph{simulator} -- which can compute the same things as~$A$, but all by
+itself without interacting with the world.  That is, we run the simulator on
+the common input~$c$, allowing it to interact in some way with the
+adversary~$A$, and finally giving us an output~$s$.
+\[ (w, c) \gets I(); s \gets S^A(c). \]
+We shall say that the simulator is \emph{effective} if it's difficult to tell
+whether a given string was output by the adversary after interacting with the
+world, or by the simulator running by itself.  That is, for any algorithm~$D$
+-- a \emph{distinguisher} -- running in some bounded amount of time, its
+advantage
+\begin{spliteqn*}
+  \Pr[(w, c) \gets I(); a \gets A^{W(w, c)}(c);
+        b \gets D(c, a) : b = 1] - {} \\
+  \Pr[(w, c) \gets I(); s \gets S^A(c); b \gets D(c, s) : b = 1]
+\end{spliteqn*}
+is small.  (Note that we gave the distinguisher the common input as well as
+the output of the adversary or the simulator.)
+
+It's usual to study \emph{transcripts} of interactions in these kinds of
+settings.  We are considering arbitrary adversarial outputs here, so this
+certainly includes adversaries which output a transcript of their
+interactions.  Indeed, for any adversary~$A$, we could construct an
+adversary~$A_T$ which performs the same computation, and outputs the same
+result, but also includes a complete transcript of $A$'s interaction with the
+world.  Therefore we're just providing additional generality.
+
+\subsubsection{Random oracles}
+We shall be considering interactions in which all the parties have access to
+several random oracles.  We could simply say that the random oracles are part
+of the world~$W$.  In the setting described above, only the adversary
+actually interacts with the world (and therefore would be able to query
+random oracles).  The simulator would be forced to `make up' its own random
+oracle, and the distinguisher would have to study the distributions of the
+random-oracle queries and their responses to make up its mind about which it
+was given.
+
+However, this would be a poor model for the real world, since once we
+instantiate the random oracle with a hash function, we know that everyone
+would in actually be able to compute the hash function for themselves.  Thus
+a distinguisher in the real world would be able to tell the difference
+immediately between a real interaction and the simulated transcript, since
+the `random oracle' queries recorded in the latter would be wrong!
+
+Therefore we decide not to include the random oracles as part of the world,
+but instead allow all the participants -- adversary, simulator and
+distinguisher -- access to them.  If we denote by~$\mathcal{H} = (H_0, H_1,
+\ldots, H_{n-1})$ the collection of random oracles under consideration, the
+expression for the distinguisher's advantage becomes
+\begin{spliteqn*}
+  \Pr[(w, c) \gets I(); a \gets A^{W(w, c), \mathcal{H}}(c);
+        b \gets D^{\mathcal{H}}(c, a) : b = 1] - {} \\
+  \Pr[(w, c) \gets I(); s \gets S^{A, \mathcal{H}}(c);
+        b \gets D^{\mathcal{H}}(c, s) : b = 1].
+\end{spliteqn*}
+
+\subsubsection{Auxiliary inputs}
+If an adversary's output can be effectively simulated, then we can
+confidently state that the adversary `learnt' very little of substance from
+its interaction, and certainly very little it can \emph{prove} to anyone
+else.  However, as we have described the setting so far, we fix an adversary
+before we choose inputs to the world, so our model says little about what an
+adversary which has already acquired some knowledge might learn beyond that.
+For example, an adversary might overhear some other conversation between
+honest parties and be able to use this to its advantage.
+
+To this end, we give the adversary an \emph{auxiliary input}~$u$, computed by
+an algorithm~$U$.  We give $U$ both $c$ and $w$, in order to allow the
+adversary to gain some (possibly partial) knowledge of the secrets of the
+other parties.  We also allow $U$ access to the random oracles~$\mathcal{H}$,
+because clearly in the `real world' it would be ridiculous to forbid such an
+algorithm from computing a publicly-known hash function.
+
+The simulator and distinguisher are also given the auxiliary input.  The
+simulator is meant to represent the adversary's ability to compute things on
+its own, without interacting with the world, and since the adversary is given
+the auxiliary input, the simulator must be too.  The distinguisher must be
+the auxiliary input because otherwise the simulator could just `make up'
+plausible-looking inputs.
+
+\subsubsection{Resource limits}
+We shall not allow our algorithms to perform completely arbitrary
+computations and interactions.  Instead, we impose limits on the amount of
+time they are allowed to take, the number of random-oracle queries they make,
+and so on.  Specifically, we are interested in
+\begin{itemize}
+\item the time $t_A$ taken by the adversary and $t_D$ taken by the
+  distinguisher,
+\item the number of oracle queries $\mathcal{Q}_A = (q_{A,0}, q_{A,1},
+  \ldots, q_{A,n-1})$ made by the adversary, and $\mathcal{Q}_D$ made by the
+  distinguisher,
+\item a number of resource bounds $\mathcal{R}$ on the adversary's
+  interaction with the world (e.g., number of messages of various kinds sent
+  and received), and
+\item a number of bounds $\mathcal{U}$ on the contents of the adversary's
+  auxiliary input~$u$.
+\end{itemize}
+Sometimes we shall not be interested in proving simulatability of adversaries
+with auxiliary inputs.  We write $\mathcal{U} = 0$ to indicate that auxiliary
+output is not allowed.
+
+\subsubsection{World syntax}
+It will be worth our while being more precise about what a `world' actually
+is, syntactically.  We define a world to be a single, randomized algorithm
+taking inputs $(\iota, \sigma, \tau, \mu) \in (\Bin^*)^4$; the algorithm's
+output is a pair $(\sigma', \rho) \in (\Bin^*)^2$.  We show how the
+adversary's interaction is mapped on to this world algorithm in
+figure~\ref{fig:sim-world}.
+\begin{itemize}
+\item The `input' $\iota$ is the result of the initialization function~$I$.
+  That is, it is the pair $(w, c)$ of the world's private input and the
+  common input.
+\item The `state' $\sigma$ is empty on the world's first invocation; on each
+  subsequent call, the value of the world's output $\sigma'$ is passed back.
+  In this way, the world can maintain state.
+\item The `type $\tau$ is a token giving the type of invocation this is. 
+\item The `message' $\mu$ is any other information passed in; its form will
+  typically depend on the type~$\tau$ of the invocation.
+\item The `new state' $\sigma'$ is the value of $\sigma$ to pass to the next
+  invocation of the world.
+\item The `reply $\rho$ is the actual output of the invocation.
+\end{itemize}
+There are two special invocation types.  The adversary is \emph{forbidden}
+from making special invocations.
+\begin{itemize}
+\item The special invocation type $\cookie{init}$ is used to allow the world to
+  prepare an initial state.  The world is invoked as
+  \[ W^{\mathcal{H}}(\iota, \emptystring, \cookie{init}, \emptystring) \]
+  and should output an initial state $\sigma'$.  The world's reply $\rho$ is
+  ignored.  (Recall that $\emptystring$ represents the empty string.)
+\item The special invocation type $\cookie{random}$ is used to inform the
+  world that the adversary has issued a random oracle query.  The world is
+  invoked as
+  \[ W^{\mathcal{H}}(\iota, \sigma, \cookie{random}, (i, x, h)) \]
+  to indicate that the adversary has queried its random oracle $H_i(\cdot)$
+  on the input $x$, giving output~$h$.  The world may output an updated state
+  $\sigma'$; its reply $\rho$ is ignored.
+\end{itemize}
+The latter special query is a technical device used to allow the `fake-world'
+simulators we define below to be aware of the adversary's random oracle
+queries without being able to `program' the random oracle.  Including it here
+does little harm, and simplifies the overall exposition.
+
+\begin{figure}
+  \begin{program}
+    Interaction $A^{W(w, c), \mathcal{H}}(c, u)$: \+ \\
+      $(\sigma, \rho) \gets
+        W((w, c), \emptystring, \cookie{init}, \emptystring)$; \\
+      $a \gets A^{\id{world}(\cdot, \cdot),
+                  \id{random}(\cdot, \cdot)}(c, u)$; \\
+      \RETURN $a$;
+    \newline
+    Function $\id{world}(\tau, \mu)$: \+ \\
+      \IF $\tau \in \{\cookie{init}, \cookie{random}\}$ \THEN
+        \RETURN $\bot$; \\
+      $(\sigma, \rho) \gets W((w, c), \sigma, \tau, \mu)$; \\
+      \RETURN $\rho$; \-
+    \next
+    Function $\id{random}(i, x)$: \+ \\
+      $h \gets H_i(x)$; \\
+      $(\sigma, \rho) \gets
+        W((w, c), \sigma, \cookie{random}, (i, x, h))$; \\
+      \RETURN $h$;
+  \end{program}
+
+  \caption{Interacting with a world: Interaction $A^{W, \mathcal{H}}$}
+  \label{fig:sim-world}
+\end{figure}
+
+\subsubsection{Definitions}
+We are now ready to begin making definitions.
+\begin{definition}[Simulation security]
+  \label{def:sim}
+  Consider the game described above, with the initialization function~$I$,
+  and the world~$W$: let $A$ be an adversary, and let~$U$ be an
+  auxiliary-input function; let $S$ be a simulator, and let $D$ be a
+  distinguisher.  We define $D$'s \emph{advantage against $S$'s simulation of
+    $A$'s interaction with~$W$ with auxiliary inputs provided by~$U$} to be
+  \[ \Adv{sim}{W, I, S}(A, U, D) =
+       \Pr[\Game{real}{W, I, S}(A, U, D) = 1] -
+       \Pr[\Game{sim}{W, I, S}(A, U, D)= 1]
+  \]
+  where the games are as shown in figure~\ref{fig:sim}.
+  Furthermore, we define the \emph{simulator's insecurity function} to be
+  \[ \InSec{sim}(W, I, S;
+      t_D, t_A, \mathcal{Q}_D, \mathcal{Q}_A, \mathcal{R}, \mathcal{U}) =
+      \max_{D, A, U} \Adv{sim}{W, I, S}(A, U, D)
+  \]
+  where the maximum is taken over all distinguishers~$D$ running in
+  time~$t_D$ and making at most $\mathcal{Q}_D$ random-oracle queries, and
+  all adversaries~$A$ running in time~$t_A$, making at most $\mathcal{Q}_A$
+  random-oracle queries, not exceeding the other stated resource
+  bounds~$\mathcal{R}$ on its interaction with~$W$, and auxiliary-input
+  functions producing output not exceeding the stated bounds~$\mathcal{U}$.
+\end{definition}
+\begin{remark}
+  The usual definitions of zero-knowledge, for example, require the simulator
+  to work for all choices of inputs (common, private and auxiliary), rather
+  than for random choices.  Our definition therefore looks weaker.  Our proof
+  of zero-knowledge actually carries through to the traditional
+  stronger-looking definition.  Critically, however, the standard
+  universal quantification over inputs fails to capture deniability in the
+  random oracle model, since the inputs can't therefore depend on the random
+  oracle.  Our formulation therefore actually gives \emph{stronger}
+  deniability that the usual one.
+\end{remark}
+
+\begin{figure}
+  \begin{program}
+    $\Game{real}{W, I, S}(A, U, D)$: \+ \\
+      $(w, c) \gets I()$; \\
+      $u \gets U^{\mathcal{H}}(w, c)$; \\
+      $a \gets A^{W(w, c), \mathcal{H}}(c, u)$; \\
+      $b \gets D^{\mathcal{H}}(c, u, a)$; \\
+      \RETURN $b$;
+    \next
+    $\Game{sim}{W, I, S}(A, U, D)$: \+ \\
+      $(w, c) \gets I()$; \\
+      $u \gets U^{\mathcal{H}}(w, c)$; \\
+      $s \gets S^{A, \mathcal{H}}(c, u)$; \\
+      $b \gets D^{\mathcal{H}}(c, u, s)$; \\
+      \RETURN $b$;
+  \end{program}
+
+  \caption{Games for simulation: $\Game{real}{W, I}$ and $\Game{sim}{W, I}$}
+  \label{fig:sim}
+\end{figure}
+
+\subsubsection{Fake-world simulators}
+The simulators we shall be considering in the present paper are of a specific
+type which we call `fake-world simulators'.  They work by running the
+adversary in a fake `cardboard cut-out' world, and attempting to extract
+enough information from the adversary's previous interactions and random
+oracle queries to maintain a convincing illusion.
+
+That is, the behaviour of a fake-world simulator~$S$ is simply to allow the
+adversary to interact with a `fake world'~$W'$, which was not given the world
+private input.  That is, there is some world $W'$ such that
+\[ S^{A, \mathcal{H}}(c, u) \equiv A^{W'(u, c), \mathcal{H}}(c, u) \]
+Fake-world simulators are convenient because they allow us to remove from
+consideration the distinguisher~$D$ as the following definition shows.
+\begin{definition}[Fake-world simulation security]
+  \label{def:fakesim}
+  Let $I$, $W$ and $U$ be as in definition~\ref{def:sim}.  Let $A$ be an
+  adversary which outputs a single bit.  Let $S$ be a fake-world simulator.
+  We define $A$'s \emph{advantage against $S$'s fake-world simulation of $W$
+  with auxiliary inputs provided by~$U$} to be
+  \begin{spliteqn*}
+    \Adv{fw}{W, I, S}(A, U) =
+      \Pr[(w, c) \gets I(); u \gets U^{\mathcal{H}}(w, c);
+           b \gets A^{W(w, c), \mathcal{H}}(c, u) : b = 1] - {} \\
+       \Pr[(w, c) \gets I(); u \gets U^{\mathcal{H}}(w, c);
+           b \gets S^{A, \mathcal{H}}(c, u) : b = 1]
+  \end{spliteqn*}
+  Furthermore, we define the \emph{simulator's insecurity function} to be
+  \[ \InSec{fw}(W, I, S;
+      t_D, t, \mathcal{Q}, \mathcal{R}, \mathcal{U}) =
+      \max_{A, U} \Adv{fw}{W, I, S}(A, U)
+  \]
+  where the maximum is taken over all adversaries~$A$ running in time~$t$,
+  making at most $\mathcal{Q}$ random-oracle queries, not exceeding the other
+  stated resource bounds~$\mathcal{R}$ on its interaction with~$W$, and
+  auxiliary-input functions producing output not exceeding the stated
+  bounds~$\mathcal{U}$.
+\end{definition}
+It remains for us to demonstrate that this is a valid way of analysing
+simulators; the following simple proposition shows that this is indeed the
+case.
+\begin{proposition}[Fake-world simulation]
+  \label{prop:fakesim}
+  Let $I$ be an initialization function and let $W$ be a world.  Then, for
+  any fake-world simulator~$S$,
+  \[ \InSec{sim}(W, I, S; t_D, t_A, \mathcal{Q}_D, \mathcal{Q}_A,
+       \mathcal{R}, \mathcal{U}) \le
+     \InSec{fw}(W, I, S; t_A + t_D, \mathcal{Q}_D + \mathcal{Q}_A,
+       \mathcal{R}, \mathcal{U})
+  \]
+  (where addition of query bounds $\mathcal{Q}$ is done elementwise).
+\end{proposition}
+\begin{proof}
+  Let $W$ and $I$ as in the proposition statement be given; also let a
+  distinguisher~$D$ running in time~$t_D$ and making $\mathcal{Q}_D$
+  random-oracle queries, an adversary~$A$ running in time~$t_A$ and making
+  $\mathcal{Q}_A$ random-oracle queries and interacting with its world within
+  the stated bounds~$\mathcal{R}$, an auxiliary-input function~$U$ satisfying
+  the constraints~$\mathcal{U}$ on its output, and a fake-world simulator~$S$
+  all be given.
+
+  We construct an adversary~$B$ outputting a single bit as follows
+  \begin{program}
+    Adversary $B^{W, \mathcal{H}}(c, u)$: \+ \\
+      $a \gets A^{W, \mathcal{H}}(c, u)$; \\
+      $b \gets D^{\mathcal{H}}(c, u, a)$; \\
+      \RETURN $b$;
+  \end{program}
+  A glance at definitions \ref{def:sim} and~\ref{def:fakesim} and the
+  resources used by $B$ shows that
+  \[ \Adv{sim}{W, I, S}(A, U) = \Adv{fw}{W, I, S}(B, U)
+      \le \InSec{fw}(W, I, S;  t_D + t_A, \mathcal{Q}_D + \mathcal{Q}_A,
+       \mathcal{R}, \mathcal{U})
+  \]
+  as required.
+\end{proof}
+
+%%%--------------------------------------------------------------------------
+
+\section{A zero-knowledge identification scheme}
+\label{sec:zk-ident}
+
+
+\subsection{Description}
+
+Here we present a simple zero-knowledge identification scheme.  Fix some
+group $G$.  Suppose Alice chooses a private key $x \inr \Nupto{|G|}$, and
+publishes the corresponding public key $X = x P$.  Let $H_I\colon G^2 \to
+\Bin^{\ell_I}$ be a secure hash function.  Here's a simple protocol which
+lets her prove her identity to Bob.
+\begin{enumerate}
+\item Bob selects a random $r \inr \Nupto{|G|}$, and computes $R = r P$, $Y =
+  r X$, and $c = r \xor H_I(R, Y)$.  He sends the pair $(R, c)$ to Alice as
+  his \emph{challenge}.
+\item Alice receives $(R, c)$.  She computes $Y' = x R$ and $r' = c \xor
+  H_I(R', Y')$, and checks that $R = r' P$.  If so, she sends $Y'$ as her
+  \emph{response}; otherwise she sends $\bot$.
+\item Bob receives $Y'$ from Alice.  He checks that $Y' = Y$.  If so, he
+  accepts that he's talking to Alice; otherwise he becomes suspicious.
+\end{enumerate}
+We name this the Wrestlers Identification Protocol in~$G$, $\Wident^G$ (we
+drop the superscript to refer to the protocol in general, or when no
+ambiguity is likely to result).  A summary is shown in
+figure~\ref{fig:wident}.
+
+\begin{figure}
+  \begin{description}
+  \item[Setup] Group $G = \langle P \rangle$; $|G| = q$ is prime.
+    $H_I(\cdot, \cdot)$ is a secure hash.
+  \item[Private key] $x \inr \Nupto{q}$.
+  \item[Public key] $X = x P$.
+  \item[Challenge] $(R, c)$ where $r \inr \Nupto{q}$, $R = r P$, $c = r \xor
+    H_I(R, r X)$.
+  \item[Response] $x R = r X$ if $R = (c \xor H_I(R, x R)) P$; otherwise
+    $\bot$.
+  \end{description}
+
+  \caption{Summary of the Wrestlers Identification Protocol, $\Wident$}
+  \label{fig:wident}
+\end{figure}
+
+
+\subsection{Security}
+
+In order to evaluate the security of our protocol, we present a formal
+description of the algorithms involved in figure~\ref{fig:wident}.  Here, the
+hash function $H_I(\cdot, \cdot)$ is modelled as a random oracle.
+
+\begin{figure}
+  \begin{program}
+    Function $\id{setup}()$: \+ \\
+      $x \getsr \Nupto{q}$; \\
+      $X \gets x P$; \\
+      \RETURN $(x, X)$;
+    \next
+    Function $\id{challenge}^{H_I(\cdot, \cdot)}(R, c, X)$: \+ \\
+      $r \getsr \Nupto{q}$; \\
+      $R \gets r P$; $Y \gets r X$; \\
+      $h \gets H_I(R, Y)$; $c \gets r \xor h$; \\
+      \RETURN $(Y, R, c)$; \- \\[\medskipamount]
+    Function $\id{verify}(Y, Y')$: \+ \\
+      \IF $Y' = Y$ \THEN \RETURN $1$; \\
+      \RETURN $0$;
+    \next
+    Function $\id{response}^{H_I(\cdot, \cdot)}(R, c, x)$: \+ \\
+      $Y' \gets x R$; \\
+      $h \gets H_I(R', Y')$; $r' \gets c \xor h$; \\
+      \IF $R \ne r' P$ \THEN \RETURN $\bot$; \\
+      \RETURN $Y'$;
+  \end{program}
+
+  \caption{Functions implementing $\Wident$ in the random oracle model}
+  \label{fig:wident-ro}
+\end{figure}
+
+\subsubsection{Completeness}
+Suppose that Bob really is talking to Alice.  Note that $Y' = x R = x (r P) =
+r (x P) = r X = Y$.  Hence $r' = c \xor H_I(R', Y') = c \xor H_I(R, Y) = r$,
+so $r' P = r P = R$, so Alice returns $Y' = Y$ to Bob.  Therefore $\Wident$
+is \emph{complete}: if Bob really is communicating with Alice then he
+accepts.
+
+\subsubsection{Soundness}
+We next show that impersonating Alice is difficult.  The natural way to prove
+this would be to give an adversary a challenge and prove that its probability
+of giving a correct response is very small.  However, we prove a stronger
+result: we show that if the adversary can respond correctly to any of a large
+collection of challenges then it can solve the MCDH problem.
+
+Consider the game $\Game{imp}{\Wident}$ shown in
+figure~\ref{fig:wident-sound}.  An adversary's probability of successfully
+impersonating Alice in our protocol, by correctly responding to any one of
+$n$ challenges, is exactly its probability of winning the game (i.e., causing
+it to return $1$).
+
+\begin{figure}
+  \begin{program}
+    $\Game{imp-$n$}{\Wident}(A)$: \+ \\
+      $H_I \getsr \Func{G^2}{\Bin^{\ell_I}}$; \\
+      $(x, X) \gets \id{setup}()$; \\
+      $\id{win} \gets 0$; \\
+      $\Xid{R}{map} \gets \emptyset$; \\
+      $\mathbf{c} \gets \id{challenges}(n)$; \\
+      $(R', Y') \gets A^{H_I(\cdot, \cdot), \id{check}(\cdot, \cdot)}
+        (X, \mathbf{c})$; \\
+      \RETURN $\id{win}$;
+    \newline
+    Function $\id{challenges}(n)$: \+ \\
+      \FOR $i \in \Nupto{n}$ \DO \\ \ind
+        $(Y, R, c) \gets \id{challenge}^{H_I(\cdot, \cdot)}$; \\
+        $\Xid{R}{map} \gets \Xid{R}{map} \cup \{ R \mapsto Y \}$; \\
+        $\mathbf{c}[i] \gets (R, c)$; \- \\
+      \RETURN $\mathbf{c}$; \next
+    Function $\id{check}(R', Y')$: \\
+      \IF $R' \notin \dom \Xid{R}{map}$ \THEN \RETURN $0$; \\
+      $Y \gets \Xid{R}{map}(R')$; \\
+      \IF $\id{verify}(Y, Y')$ \THEN \\ \ind
+        $\id{win} \gets 1$; \\
+        \RETURN $1$; \- \\
+      \RETURN $0$;
+  \end{program}
+
+  \caption{Soundness of $\Wident$: $\Game{imp-$n$}{\Wident}(A)$}
+  \label{fig:wident-sound}
+\end{figure}
+
+\begin{theorem}[Soundness of $\Wident$]
+  \label{thm:wident-sound}
+  Let $A$ be any adversary running in time $t$ and making $q_I$ queries to
+  its random oracle, and $q_V$ queries to its verification oracle.  Let $G$
+  be a cyclic group.  Then
+  \[ \Pr[\Game{imp-$n$}{\Wident^G}(A) = 1] \le
+     \InSec{mcdh}(G; t', q_I + q_V)
+  \]
+  where $t' = t + O(q_I) + O(q_V)$.
+\end{theorem}
+\begin{remark}
+  Note that the security bound here is \emph{independent} of the value of
+  $n$.
+\end{remark}
+\begin{proof}
+  We prove this by defining a sequence of games $\G{i}$.  The first will be
+  the same as the attack game $\Game{imp-$n$}{\Wident}(A)$ and the others
+  will differ from it in minor ways.  In each game $\G{i}$, let $S_i$ be the
+  event that $A$ wins the game -- i.e., that it successfully impersonates the
+  holder of the private key~$x$.
+  
+  Let game $\G0$ be the attack game $\Game{imp}{\Wident}(A)$, and let $(R',
+  Y')$ be the output of $A$ in the game.
+
+  We define a new game $\G1$ which is the same as $\G0$, except that we query
+  the random oracle $H_I$ at $(R', Y')$ whenever the adversary queries
+  $\id{check}(R', Y')$.  (We don't charge the adversary for this.)  This
+  obviously doesn't affect the adversary's probability of winning, so
+  $\Pr[S_1] = \Pr[S_0]$.
+
+  Game $\G2$ is like $\G1$, except that we change the way we generate
+  challenges and check their responses.  Specifically, we new functions
+  $\id{challenges}_2$ and $\id{check}_2$, as shown in
+  figure~\ref{fig:wident-sound-2}.
+
+  \begin{figure}
+    \begin{program}
+      Function $\id{challenges}_2(n)$: \+ \\
+        $r^* \getsr I$; $R^* \gets r^* P$; $Y^* \gets r^* X$; \\
+        \FOR $i \in \Nupto{n}$ \DO \\ \ind
+          $r \getsr I$; $R \gets r R^*$; $Y \gets r Y^*$; \\
+          $h \gets H_I(R, Y)$; $c \gets r \xor h$; \\
+          $\Xid{R}{map} \gets \Xid{R}{map} \cup \{ R \mapsto r \}$; \\
+          $\mathbf{c}[i] \gets (R, c)$; \- \\
+        \RETURN $\mathbf{c}$;
+      \next
+      Function $\id{check}_2(R', Y')$: \+ \\
+        \IF $R' \notin \dom \Xid{R}{map}$ \THEN \RETURN $0$; \\
+        $r \gets \Xid{R}{map}(R')$; \\
+        \IF $\id{verify}(Y^*, Y'/r)$ \THEN \\ \ind
+          $\id{win} \gets 1$; \\
+          \RETURN $1$; \- \\
+        \RETURN $0$;
+    \end{program}
+
+    \caption{Soundness of $\Wident$: $\id{challenges}_2$ and $\id{check}_2$}
+    \label{fig:wident-sound-2}
+  \end{figure}
+
+  While we're generating and checking challenges in a more complicated way
+  here, we're not actually changing the distribution of the challenges, or
+  changing the winning condition.  Hence $\Pr[S_2] = \Pr[S_1]$.
+
+  Now we change the rules again.  Let $\G3$ be the same as $\G2$ except that
+  we change the winning condition.  Instead, we say that the adversary wins
+  if any of the queries to its random oracle $H_I(R', Y')$ would be a correct
+  response -- i.e., $\id{check}_2(R', Y')$ would return $1$.  Since we query
+  the oracle on $(R', Y')$ on its behalf at the end of the game, no adversary
+  can do worse in this game than it does in $\G2$, so we have $\Pr[S_3] \ge
+  \Pr[S_2]$.  (It's not hard to see that this only helps quite stupid
+  adversaries.  We can transform any adversary into one for which equality
+  holds here.)
+
+  Finally, let $\G4$ be the same as $\G3$ except that we change the way we
+  generate challenges again: rather than computing $h$ and setting $c \gets h
+  \xor r$, we just choose $c$ at random.  Specifically, we use the new
+  function, $\id{challenges}_4$, shown in figure~\ref{fig:wident-sound-4}.
+
+  \begin{figure}
+    \begin{program}
+      Function $\id{challenges}_4(n)$: \+ \\
+        $r^* \getsr I$; $R^* \gets r^* P$; $Y^* \gets r^* X$; \\
+        \FOR $i \in \Nupto{n}$ \DO \\ \ind
+          $r \getsr I$; $R \gets r R^*$; \\
+          $c \getsr \Bin^{\ell_I}$; \\
+          $\Xid{R}{map} \gets \Xid{R}{map} \cup \{ R \mapsto r \}$; \\
+          $\mathbf{c}[i] \gets (R, c)$; \- \\
+        \RETURN $\mathbf{c}$;
+    \end{program}
+
+    \caption{Soundness of $\Wident$: $\id{challenges}_4$}
+    \label{fig:wident-sound-4}
+  \end{figure}
+
+  Since $H_I(\cdot, \cdot)$ is a random function, the adversary can only
+  distinguish $\G4$ from $\G3$ if it queries its random oracle at some $(R, r
+  Y^*)$.  But if it does this, then by the rule introduced in $\G3$ it has
+  already won.  Therefore we must have $\Pr[S_4] = \Pr[S_3]$.
+
+  Our $\id{challenges}_4$ function is interesting, since it doesn't actually
+  make use of $r^*$ or $Y^*$ when generating its challenges.  This gives us
+  the clue we need to bound $\Pr[S_4]$: we can use adversary $A$ to solve the
+  multiple-guess Diffie-Hellman problem in $G$ by simulating the game $\G4$.
+  Specifically, we define the adversary $B$ as shown in
+  figure~\ref{fig:wident-sound-cdh}.  That is, for each query $A$ makes to
+  its random oracle at a new pair $(R', Y')$, we see whether this gives us
+  the answer we're looking for.  We have $\Pr[S_0] \le \Pr[S_4] =
+  \Succ{mcdh}{G}(B) \le \InSec{gdh}(G; t', q_I + q_V)$ as required.
+
+  \begin{figure}
+    \begin{program}
+      Adversary $B^{V(\cdot)}(X, R^*)$: \+ \\
+        $F \gets \emptyset$; $\Xid{R}{map} \gets \emptyset$; \\
+        \FOR $i \in \Nupto{n}$ \DO \\ \ind
+          $r \getsr I$; $R \gets r R^*$; $c \getsr \Bin^{\ell_I}$; \\
+          $\Xid{R}{map} \gets \Xid{R}{map} \cup \{ R \mapsto r \}$; \\
+          $\mathbf{c}[i] \gets (R, c)$; \- \\
+        $(R', Y') \gets A^{H_I(\cdot, \cdot), \id{check}(\cdot, \cdot)}
+          (X, \mathbf{c})$; \\
+        \IF $Y' \neq \bot$ \THEN $H_I(R', Y')$;
+      \next
+      Oracle $H_I(R', Y')$: \+ \\
+        \IF $(R', Y') \in \dom F$ \THEN \\ \quad
+          $h \gets F(x)$; \\
+        \ELSE \\ \ind
+          $\id{check}(R', Y')$; \\
+          $h \getsr \Bin^{\ell_I}$;
+          $F \gets F \cup \{ (R', Y') \mapsto h \}$; \- \\
+        \RETURN $h$;
+      \- \\[\medskipamount]
+      Oracle $\id{check}(R', Y')$: \+ \\
+        \IF $R' \in \dom \Xid{R}{map}$ \THEN
+          $V(Y'/\Xid{R}{map}(R'))$;
+    \end{program}
+
+    \caption{Soundness of $\Wident$: reduction from MCDH}
+    \label{fig:wident-sound-cdh}
+  \end{figure}
+
+\end{proof}
+
+\subsubsection{Zero-knowledge}
+Finally we must prove that $\Wident$ is (statistical) zero-knowledge -- i.e.,
+that, except with very small probability, Bob learns nothing of use to him
+except that he's interacting with Alice.  To do this, we show that, for any
+algorithm $B$ which Bob might use to produce his challenge to the real Alice,
+there exists a simulator $S$ which produces transcripts distributed very
+similarly to transcripts of real conversations between $B$ and Alice, the
+difference being that $S$ doesn't know Alice's key.  We shall show that the
+statistical difference between the two distributions is $2^{-\ell_I}$.
+
+The intuition here is that Bob ought to know what answer Alice is going to
+give him when he constructs his challenge.  This is certainly true if he's
+honest: his challenge is $R = r P$ for some $r$ he knows, so he won't learn
+anything useful when Alice responds with $x R = r X$.  However, if Bob sends
+a challenge $R$ when he doesn't know the corresponding $r$, he learns
+something potentially useful.  The accompanying check value $c = r \xor
+H_I(R, r X)$ keeps him honest.
+
+To show this, we present an \emph{extractor} which, given any challenge $(R,
+c)$ Bob can construct, and his history of random-oracle queries, either
+returns a pair $(r, Y)$ such that $R = r P$ and $Y = r X$, or $\bot$;
+moreover, the probability that Alice returns a response $Y' \ne \bot$ given
+the challenge $(R, c)$ is $2^{-\ell}$.  We can, of course, readily convert
+this extractor into a simulator to prove the zero-knowledge property of our
+protocol.
+
+We shall actually consider a slightly more complex setting.  We grant Bob
+access to an oracle which produces random, correctly-formed challenges.  We
+require this to model the legitimate challenges of other parties when we
+analyse the security of our key exchange protocol.  The extractor is
+permitted to fail given 
+
+\begin{definition}[Discrete-log extractors]
+  Let $T$, $B$ be randomized algorithms.  Define the game
+  $\Game{dl-ext}{G}(T, B)$ as shown in figure~\ref{fig:dlext}.  The
+  \emph{success probability of $T$ as a discrete-log extractor against $B$}
+  is defined as
+  \[ \Succ{dl-ext}{G}(T, B) = \Pr[\Game{dl-ext}{G}(T, B) = 1]. \]
+\end{definition}
+Let's unpack this definition slightly.  We make the following demands of our
+extractor.
+\begin{itemize}
+\item It is given a bare `transcript' of $B$'s execution.  In particular, it
+  is given only its output and a list of $B$'s random-oracle queries in no
+  particular order.
+\item While the extractor is not given the private key~$x$, the adversary~$B$
+  is given the private key.
+\item We require that, if the extractor produces values $r, Y \ne \bot$ then
+  $r$ and $Y$ are \emph{correct}; i.e., that $R = r P$ and $Y = x R$.
+\item The extractor is explicitly \emph{not} given the outputs of the
+  challenge-generation oracle $C()$, nor of the random-oracle queries issued
+  by $C()$.  However, we allow the extractor to fail (i.e., return $\bot$) if
+  $B$ simply parrots one of its $C$-outputs.
+\item The extractor is allowed -- indeed \emph{required} -- to fail if the
+  challenge $(R, c)$ is \emph{invalid} (i.e., Alice would return $\bot$ given
+  the challenge).
+\end{itemize}
+The resulting definition bears a striking similarity to the concept of
+\emph{plaintext awareness} in \cite{Bellare:1998:RAN}.  
+
+\begin{figure}
+  \begin{program}
+    $\Game{dl-ext}{G}(T, B):$ \+ \\
+      $H_I \getsr \Func{G^2}{\Bin^{\ell_I}}$;
+      $Q_H \gets \emptyset$; $Q_C \gets \emptyset$; \\
+      $(x, X) \gets \id{setup}()$; \\
+      $(R, c) \gets B^{\Xid{H_I}{trap}(\cdot, \cdot), C()}(x, X)$; \\
+      $(r, Y) \gets T(R, c, Q_H)$; \\
+      $Y' \gets x R$; $h' \gets H_I(R, Y')$; $r' \gets c \xor h'$; \\
+      \IF $r \ne \bot$ \THEN \\ \quad
+        \IF $Y = \bot \lor R \ne r P \lor Y \ne Y'$ \THEN \RETURN $0$; \\
+      \IF $R = r' P$ \THEN $(r^*, Y^*) = (r', Y')$; \\
+      \ELSE $(r^*, Y^*) \gets (\bot, \bot)$; \\
+      \IF $(R, c) \in Q_C$ \THEN \RETURN $1$; \\
+      \IF $(r, Y) = (r', Y')$ \THEN \RETURN $1$; \\
+      \RETURN $0$;
+    \next
+    Oracle $\Xid{H_I}{trap}(R', Y')$: \+ \\
+      $h \gets H_I(R', Y')$; \\
+      $Q_H \gets Q_H \cup \{(R', Y', h)\}$; \\
+      \RETURN $h$; \- \\[\medskipamount]
+    Oracle $C()$: \+ \\
+      $r \getsr \Nupto{q}$; \\
+      $R \gets r P$; $c \gets r \xor H_I(R, r X)$; \\
+      $Q_C \gets Q_C \cup \{(R, c)\}$; \\
+      \RETURN $(R, c)$    
+  \end{program}
+
+  \caption{Discrete log extraction game: $\Game{dl-ext}{G}(T, B)$}
+  \label{fig:dlext}
+\end{figure}
+
+Such an extractor indeed exists, as the following lemma states.
+\begin{lemma}[Effectiveness of extractor $T_\Wident$]
+  \label{lem:dlext}
+  There exists a \emph{universal discrete-log extractor} $T_\Wident$ which,
+  for any algorithm $B$,
+  \[ \Succ{dl-ext}{G}(T_\Wident, B) \ge 1 - \frac{1}{2^{\ell_I}}. \]
+  Moreover, if $B$ issues at most $q_H$ random-oracle queries, then the
+  running time of $T_\Wident$ is $O(q_H)$.
+\end{lemma}
+We prove this result at the end of the section.  For now, let us see how to
+prove that $\Wident$ is zero-knowledge.
+
+We use the set-up described in section~\ref{sec:sim}.  Our initialization
+function~$I_\Wident$ just chooses a random $x \in \Nupto{q}$ as the world
+private input and sets $X = x P$ as the common input.  In the `real world',
+the adversary is allowed to submit a (single) challenge to the prover; it is
+given the prover's response, and must then compute its output.  This is shown
+on the left hand side of figure~\ref{fig:wident-sim}.
+
+The zero-knowledge property of the scheme is described by the following
+theorem.
+\begin{theorem}[Statistical zero-knowledge of $\Wident$]
+  \label{thm:wident-zk}
+  Let $I_\Wident$, $W_\Wident$ and $S_\Wident$ be the real-prover world and
+  simulator shown in figure~\ref{fig:wident-sim}.  Then, for any~$t$,
+  $q_I$ and $q_C$,
+  \[ \InSec{sim}(W_\Wident, I_\Wident, S_\Wident; t, q_I, q_C, 0) \le
+       \frac{q_C}{2^\ell_I}.
+  \]
+  where $q_C$ is the maximum number of challenges allowed by the adversary.
+\end{theorem}
+\begin{proof}
+  The simulator simply uses the extractor~$T_\Wident$ to extract the answer
+  from the adversary's history of random oracle queries.  Observe that
+  $S_\Wident$ is a fake-world simulator.  By lemma~\ref{lem:dlext}, the
+  extractor fails with probability only $2^{-\ell_I}$.  The theorem follows
+  by a simple union bound and proposition~\ref{prop:fakesim}.
+\end{proof}
+
+\begin{figure}
+  \begin{program}
+    Initialization function $I_\Wident()$: \+ \\
+      $x \getsr \Nupto{|G|}$; \\
+      $X \gets x P$; \\
+      \RETURN $(x, X)$;
+    \- \\[\medskipamount]
+    Real-prover world $W_\Wident^{H_I(\cdot, \cdot)}
+        ((x, X), \sigma, \tau, \mu)$: \+ \\
+      \IF $\tau = \cookie{challenge}$ \THEN \\ \ind
+        $(R, c) \gets \mu$; \\
+        $Y \gets \id{response}^{H_I(\cdot, \cdot)}(R, c, x)$; \\
+        \RETURN $(1, Y)$; \- \\
+      \ELSE \\ \ind
+        \RETURN $(\sigma, \bot)$;
+  \next
+  Simulator $S_\Wident$'s fake world \\
+  \hspace{1in} $W_{\text{sim}}^{H_I(\cdot, \cdot)}
+      ((X, u), \sigma, \tau, \mu)$: \+ \\
+      \IF $\tau = \cookie{init}$ \THEN \\ \ind
+        \RETURN $(\emptyset, \emptystring)$; \- \\
+      $Q_H \gets \sigma$; \\
+      \IF $\tau = \cookie{challenge}$ \THEN \\ \ind
+        $(R, c) \gets \mu$; \\
+        $(r, Y) \gets T_\Wident(R, c, Q_H)$; \\
+        \RETURN $(Q_H, Y)$; \- \\
+      \ELSE \IF $\tau = \cookie{random}$ \THEN \\ \ind
+        $(i, (R', Y'), h) \gets \mu$; \\
+        $Q_H \gets Q_H \cup \{(R', Y', h)\}$; \\
+        \RETURN $(Q_H, \emptystring)$; \- \\
+      \ELSE \\ \ind
+        \RETURN $(\sigma, \bot)$;
+  \end{program}
+
+  \caption{Real-prover and simulator for zero-knowledge of $\Wident$}
+  \label{fig:wident-sim}
+\end{figure}
+
+We now return to proving that our extractor exists and functions as claimed.
+The following two trivial lemmas will be useful, both now and later.
+\begin{lemma}[Uniqueness of discrete-logs]
+  \label{lem:unique-dl}
+  Let $G = \langle P \rangle$ be a cyclic group.  For any $X \in G$ there is
+  a unique integer $x$ where $0 \le x < |G|$ and $X = x P$.
+\end{lemma}
+\begin{proof}
+  Certainly such an $x$ exists, since $G$ is cyclic and finite.  Suppose $X =
+  x P = x' P$: then $0 = x P - x' P = (x - x') P$.  Hence $(x - x')$ is a
+  multiple of $|G|$.
+\end{proof}
+\begin{lemma}[Uniqueness of check values]
+  \label{lem:unique-c}
+  Let $G = \langle P \rangle$ be a cyclic group; let $H_I$ be a function
+  $H_I\colon \Bin^{2\ell_G} \to \Bin^{\ell_I}$.  Fix some $x \in
+  \Nupto{|G|}$ and define the set
+  \[ V_x = \bigl\{\, (R, c) \in G \times \Bin^{\ell_I} \bigm|
+                R = \bigl( c \xor H_I(R, x R) \bigr) P \,\bigr\}.
+  \]
+  Then, for any $R$, $c$, $c'$, if $(R, c) \in V_x$ and $(R, c') \in V_x$
+  then $c = c'$. 
+\end{lemma}
+\begin{proof}
+  From lemma~\ref{lem:unique-dl}, we see that there is a unique $r \in
+  \Nupto{|G|}$ for which $R = r P$.  Now, if $(R, c) \in V_x$, we must have
+  $r = c \xor H_I(R, x R)$.  It follows that $c = r \xor H_I(R, x R)$.
+\end{proof}
+
+\begin{proof}[Proof of lemma~\ref{lem:dlext}]
+  Our extractor $T_\Wident$ is shown in figure~\ref{fig:twident}.
+
+  \begin{figure}
+    \begin{program}
+      Extractor $T_\Wident(R, c, Q_H)$: \+ \\
+        \FOR $(R', Y', h)$ \IN $Q_H$ \DO \\ \ind
+          $r \gets h \xor c$; \\
+          \IF $R = R' = r P \land Y' = r X$ \THEN \RETURN $(r, Y')$; \- \\
+        \RETURN $(\bot, \bot)$;
+    \end{program}
+
+    \caption{The discrete-log extractor $T_\Wident$}
+    \label{fig:twident}
+  \end{figure}
+
+  Let $B$ be any randomized algorithm, and let $(R, c, Q_H)$ be as given to
+  the extractor by $\Game{dl-ext}{G}(T_\Wident, B)$.  Let the quantities
+  $H_I$, $Q_C$, $r$, $r'$, $x$ and $X$ be as in that game.
+
+  Suppose that the extractor returns values $(r, Y) \ne (\bot, \bot)$.  Let
+  $h = r \xor c$; then there must be a query $(R, Y, h) \in Q_H$, and we have
+  $R = r P$ and $Y = r X = r (x P) = x (r P) = x R = Y'$, so the extractor's
+  output must be correct unless it fails.
+
+  Furthermore, in the case where the extractor did not fail, we have $h =
+  H_I(R, Y) = H_I(R, Y')$ and $c = r \xor h$, so the challenge was valid.
+  Therefore, if the challenge was invalid, the extractor will fail.
+
+  We now deal with the challenge-generation oracle.  Suppose that $(R, c')
+  \in Q_C$ for some $c'$.  Now, if $c = c'$ then $(R, c')$ is a repeat of
+  some challenge from the challenge-generation oracle, and the extractor is
+  permitted to fail.  On the other hand, suppose $c \ne c'$; then, the
+  challenge $(R, c)$ must be invalid by lemma~\ref{lem:unique-c}, so the
+  extractor is required to fail, and we have established that indeed it will.
+  From now on, suppose that $R$ is distinct from all the $R$-values returned
+  by $C()$.
+
+  Let $Y = x R$.  Suppose that $B$ queried its random oracle at $(R, Y)$.
+  Let $h = H_I(Y)$, so $r' = c \xor h$.  If the challenge is valid then $R =
+  r' P$; therefore $Y = x R = x r' P = r' X$, so we have $(R, Y, h) \in Q_H$
+  with $R = r P$ and $Y = r X$.  Hence the extractor returns $r = r'$ as
+  required.
+
+  It remains to deal with the case where there is no random-oracle query at
+  $(R, Y)$.  But then $h = H_I(R, Y)$ is uniformly distributed, and
+  independent of the entire game up to this point.  Let $r$ be the correct
+  discrete log of $R$; by lemma~\ref{lem:unique-dl} there is only one
+  possible value.  The extractor always fails under these circumstances, but
+  a correct responder would reply with probability
+  \[ \Pr[h = c \xor r] = \frac{1}{2^{\ell_I}}. \]
+  This concludes the proof.
+\end{proof}
+\begin{remark}
+  Note that the fact that the algorithm~$B$ was given the private key is
+  irrelevant to the above argument.  However, we shall need this property
+  when we come to prove deniability for the key-exchange protocol.
+\end{remark}
+\begin{remark}
+  It's easy to see from the above proof that the extractor works flawlessly
+  on the `honest verifier' algorithm $\id{challenge}$ shown in
+  figure~\ref{fig:wident-ro}.  This shows that $\Wident$ is perfect
+  zero-knowledge against honest verifiers.  We're much more interested in
+  dishonest verifiers, though.
+\end{remark}
+
+
+\subsection{An identity-based identification scheme}
+\label{sec:wident-id}
+
+Boneh and Franklin \cite{Boneh:2001:IBE} showed how to construct an
+identity-based encryption scheme using bilinear pairings.  The resulting
+encryption scheme looks somewhat like a pairing-based version of ElGamal's
+encryption scheme \cite{ElGamal:1984:PKC}.  We can easily apply their
+techniques to our identification protocol, and thereby obtain an
+identity-based identification scheme.  Providing the necessary formalisms to
+prove theorems analogous to our theorems~\ref{thm:wident-sound}
+and~\ref{thm:wident-zk} would take us too far from our objectives; but given
+appropriate security notions, we can readily adapt our existing proofs to the
+new setting.
+
+\subsubsection{Bilinear pairings}
+Before we describe the necessary modifications to the protocol, we first give
+a (very brief!) summary of cryptographic pairings.  (The Boneh-Franklin paper
+\cite{Boneh:2001:IBE} gives more detail; also \cite{Menezes:2006:IPB}
+provides a useful introduction to the topic.)
+
+Let $(G, +)$, $(G', +)$ and $(G_T, \times)$ be cyclic groups with prime order
+$q$; let $P \in G$ and $P' \in G'$ be elements of order $q$ in $G$ and $G'$
+respectively.  We say that a mapping $\hat{e}\colon G \times G' \to G_T$ is a
+\emph{non-degenerate bilinear pairing} if it satisfies the following
+properties.
+\begin{description}
+\item[Bilinearity] For all $R \in G$ and $S', T' \in G'$, we have $\hat{e}(R,
+  S' + T') = \hat{e}(R, S') \hat{e}(R, T')$; and for all $R, S \in G$ and $T'
+  \in G'$ we have $\hat{e}(R + S, T') = \hat{e}(R, T') \hat{e}(S, T')$.
+\item[Non-degeneracy] $\hat{e}(P, P') \ne 1$.
+\end{description}
+For practical use, we also want $\hat{e}(\cdot, \cdot)$ to be efficient to
+compute.  The reader can verify that $\hat{e}(a P, b P') = \hat{e}(P,
+P')^{ab}$.  It is permitted for the two groups $G$ and $G'$ to be equal.
+
+We require a different intractability assumption, specifically that the
+\emph{bilinear} Diffie-Hellman problem (BDH) -- given $(a P, b P, a P', c P')
+\in G^2 \times G'^2$, find $\hat{e}(P, P')^{abc} \in G_T$ -- is difficult.
+This implies the difficulty of the computational Diffie-Hellman problem in
+all three of $G$, $G'$ and~$G_T$.
+
+\subsubsection{The identity-based scheme}
+We need a trusted authority; following \cite{Schneier:1996:ACP} we shall call
+him Trent.  Trent's private key is $t \in \Nupto{q}$; his public key is $T =
+t P$.
+
+Finally, we need cryptographic hash functions $H_I\colon G \times G_T \to
+\Bin^{\ell_I}$ and $\Hid\colon \Bin^* \to G'$; a formal security analysis
+would model these as random oracles.
+
+Alice's public key is $A = \Hid(\texttt{Alice}) \in G'$.  Her private key is
+$K_A = t A \in G'$ -- she needs Trent to give this to her.  Bob can interact
+with Alice in order to verify her identity as follows.
+\begin{enumerate}
+\item Bob computes $\gamma_A = \hat{e}(T, A) \in G_T$.  (He can do this once
+  and store the result if he wants, but it's not that onerous to work it out
+  each time.)
+\item Bob chooses $r \inr \Nupto{q}$, and sets $R = r P$.  He also computes
+  $\psi = \gamma_A^r$, $h = H_I(R, \psi)$ and $c = r \xor h$.  He sends his
+  challenge $(R, c)$ to Alice.
+\item Alice receives $(R', c')$.  She computes $\psi' = \hat{e}(R, K_A)$, $h'
+  = H_I(R', \psi')$, and $r' = c' \xor h')$.  She checks that $R' = r' P$; if
+  so, she sends $\psi'$ back to Bob; otherwise she refuses to talk to him.
+\item Bob receives $\psi'$.  If $\psi = \psi'$ then he accepts that he's
+  talking to Alice.
+\end{enumerate}
+This works because $\psi = \gamma_A^r = \hat{e}(T, A)^r = \hat{e}(t P, A)^r =
+\hat{e}(r P, A)^t = \hat{e}(R, t A) = \psi'$.
+
+\subsubsection{Informal analysis}
+An analogue to lemma~\ref{lem:dlext} can be proven to show how to extract $r$
+from a verifier's random-oracle queries; statistical zero knowledge would
+then follow easily, as in theorem~\ref{thm:wident-zk}.  Soundness is
+intuitively clear, since an adversary must compute $\psi = \hat{e}(P,
+P')^{art}$ given $A = a P'$, $R = r P$ and $T = t P$, which is an instance of
+the BDH problem.  An analogue of theorem~\ref{thm:wident-sound} would have to
+prove this for an adversary capable of making identity requests as well as
+obtaining challenges.  Finally, our key-exchange protocol can be constructed
+out of this identity-based identification scheme, yielding an identity-based
+authenticated key-exchange protocol.  We leave it to the reader to work
+through the details.
+
+
+\subsection{Comparison with the protocol of Stinson and Wu}
+\label{sec:stinson-ident}
+
+Our protocol is similar to a recent proposal by Stinson and Wu
+\cite{Stinson:2006:EST}.  They restrict their attention to Schnorr groups $G
+\subset \F_p^*$.  Let $\gamma$ be an element of order $q = |G|$.  The
+prover's private key is $a \inr \Nupto{q}$ and her public key is $\alpha =
+\gamma^a$.  In their protocol, the challenger chooses $r \inr \Nupto{q}$,
+computes $\rho = \gamma^r$ and $\psi = \alpha^r$, and sends a challenge
+$(\rho, H(\rho, \psi))$.  The prover checks that $\rho^q \ne 1$, computes
+$\psi = \rho^a$, checks the hash, and sends $\psi$ back by way of response.
+They prove their protocol's security in the random-oracle model.
+
+Both the Wrestlers protocol and Stinson-Wu require both prover and verifier
+to compute two exponentiations (or scalar multiplications) each.  The
+sizes of the messages used by the two protocols are also identical.  
+
+(An earlier version of the Stinson-Wu protocol used a cofactor
+exponentiation: if we set $f = (p - 1)/q$, then we use $\psi = \alpha^{rf}) =
+\rho^{af} = \gamma^{afr}$.  This is more efficient in typical elliptic curve
+subgroups, since the cofactor of such subgroups is usually small: indeed,
+\cite{SEC1} recommends rejecting groups with cofactor $f > 4$.  However, in
+the Schnorr groups used by Stinson and Wu, the cofactor is much larger than
+$q$, and their new variant is more efficient.)
+
+We note that the zero-knowledge property of the Stinson-Wu protocol requires
+the Diffie-Hellman knowledge of exponent assumption (KEA).  Very briefly:
+suppose $A$ is a randomized algorithm which takes as input $X \in G$ and
+outputs a pair $(r P, r X)$; intuitively, the KEA asserts $A$ must have done
+this by choosing $r$ somehow and then computing its output from it.
+Formally, it asserts the existence of an `extractor' algorithm which takes as
+input the element $X$ and the random coins used by $A$ and outputs $r$ with
+high probability.  This is a very strong assumption, and one which is
+unnecessary for our protocol, since we can present an \emph{explicit}
+extractor.
+
+The KEA assumption as stated in \cite{Stinson:2006:EST} allows the extractor
+to fail with some negligible probability, over and above the probability that
+a dishonest verifier managed to guess the correct $h = H(\rho, \psi)$ without
+making this random-oracle query.  Not only does our protocol achieve zero-
+knowledge without the KEA, our extractor is, in this sense, `perfect'.
+
+Our protocol is just as strong as Stinson-Wu under attack from active
+intruders: see table~\ref{tab:wident-active} for a very brief sketch of the
+case-analysis which would be the basis of a proof of this.
+
+\begin{table}
+  \begin{tabular}[C]{|*{3}{c|}p{8cm}|}
+    \hlx{hv[1]}
+    \multicolumn{2}{|c|}{\textbf{Challenge}} &
+    \textbf{Response} &
+    \textbf{Security}
+    \\ \hlx{v[1]hv}
+    %% unpleasant hacking to make the R and c columns the same width :-(
+    \settowidth{\dimen0}{\textbf{Challenge}}%
+    \dimen0=.5\dimen0    
+    \advance\dimen0by-\tabcolsep
+    \advance\dimen0by-.5\arrayrulewidth
+    \hbox to\dimen0{\hfil$R$\hfil}
+         & $c$  & $Y$  & Nothing to prove.			\\ \hlx{v}
+    $R$  & $c'$ & ---  & Prover rejects by lemma~\ref{lem:unique-c};
+                         $Y'$ probably wrong by
+                         theorem~\ref{thm:wident-sound}.         \\ \hlx{v}
+    $R$  & $c$  & $Y'$ & Response is incorrect.			\\ \hlx{v}
+    $R'$ & ---  & $Y$  & Response is incorrect.			\\ \hlx{v}
+    $R'$ & $c$  & $Y'$ & Prover rejects with probability $1 - 2^{-\ell_I}$;
+                         $Y'$ probably wrong by
+                         theorem~\ref{thm:wident-sound}.         \\ \hlx{v}
+    $R'$ & $c'$ & $Y'$ & Simulate prover using extractor
+                         (lemma~\ref{lem:dlext}); $Y'$ probably wrong by
+                         theorem~\ref{thm:wident-sound}.         \\ \hlx{vh}
+  \end{tabular}
+  
+  \caption{Security of $\Wident$ against active intruders (summary)}
+  \label{tab:wident-active}
+\end{table}
+
+An identity-based analogue of Stinson-Wu can be defined using a bilinear
+pairing, just as we did in section~\ref{sec:wident-id}.  However, to prove
+the zero-knowledge property, one needs to make a bilinear analogue of the
+knowledge of exponent assumption.
+
+We suspect that a key-exchange protocol like ours can be constructed using
+Stinson-Wu rather than the Wrestlers identification scheme.  We haven't,
+however, gone through all the details, since we believe our protocol is just
+as efficient and is based on much more conservative assumptions.
+
+%%%--------------------------------------------------------------------------
+
+\section{A simple key-exchange protocol}
+\label{sec:kx}
+
+In this section, we describe a simple key-exchange protocol built out of the
+identification protocol shown previously.
+
+The key-exchange protocol arises from the following observation.  If Bob
+sends a challenge, presumably to Alice, and gets a correct response, then not
+only did he really send the challenge to Alice but he knows that she received
+it correctly.
+
+So, if Alice and Bob authenticate each other, by the end of it, they should
+each have chosen a random private value, sent the corresponding public value
+to the other, and been convinced that it arrived safely.
+
+Unfortunately, life isn't quite this kind, and we have to do some more work
+to make this scheme secure.
+
+
+Our key exchange protocol essentially consists of two parallel instances of
+the identification protocol.  If Alice receives a correct response to her
+challenge, she will know that Bob received her challenge correctly, and
+\emph{vice versa}.  If we let Alice's challenge be $R_0 = r_0 P$ and Bob's
+challenge be $R_1 = r_1 P$ then each can compute a shared secret $Z = r_0 R_1
+= r_0 r_1 P = r_1 R_0$ unknown to an adversary.  There are, unfortunately, a
+few subtleties involved in turning this intuition into a secure key-exchange
+protocol, which we now describe.
+
+
+\subsection{Overview}
+\label{sec:kx-overview}
+
+We present a quick, informal description of our basic key-exchange protocol.
+In addition to our group $G$, we shall also need a secure symmetric
+encryption scheme $\E = (\kappa, E, D)$, and two secure hash functions
+$H_I\colon \Bin^{2\ell_G} \to \Bin^{\ell_I}$ and $H_K\colon \Bin^{\ell_G+1}
+\to \Bin^\kappa$.
+
+Suppose that Alice's and Bob's private keys are $a$ and $b$ respectively, and
+their public keys are $A = a P$ and $B = b P$.
+\begin{enumerate}
+\item Alice chooses a random index $r \inr \Nupto{|G|}$.  She computes $R = r
+  P$ and $c = r \xor H_I(R, r B)$.  She sends the pair $(R, c)$ to Bob.
+\item Similarly, Bob chooses a random $s \inr \Nupto{|G|}$.  He computes $S
+  = s P$ and $d = s \xor H_I(S, s A)$.  He sends $(S, d)$ to Alice.
+\item Alice receives $(S', d')$ from Bob.  She computes $s' = d' \xor H_I(S',
+  a S')$, and verifies that $S' = s' P$.  If so, she computes $K_A = H_K(0
+  \cat r S')$, and sends $R, E_{K_A}(a S')$ to Bob.
+\item Similarly, Bob receives $(R', c')$ from Alice.  He verifies that $R' =
+  \bigl( c' \xor H_I(R', b R') \bigr) P$.  If so, he computes $K_B = H_K(0
+  \cat s R')$ and sends S, $E_{K_B}(b R')$ to Alice.
+\item Alice receives a ciphertext $(S'', \chi_B)$ from Bob.  She checks that
+  $S'' = S'$, decrypts $\chi_B$, and checks that $D_{K_A}(\chi_B) = r B$.  If
+  so, she uses $H_K(1 \cat r S')$ as her shared secret.
+\item Similarly, Bob receives $(R'', \chi_A)$ from Alice, and checks $R'' =
+  R'$ and $D_{K_B}(\chi_A) = s A$.  If so, he uses $H_K(1 \cat s R')$ as his
+  shared secret.
+\end{enumerate}
+This is the Wrestlers Key Exchange protocol, $\Wkx^{G, \E}$ (again, we omit
+the superscripts when referring to the general protocol, or when confusion is
+unlikely).  A diagrammatic summary of the protocol is shown in
+figure~\ref{fig:wkx}.
+
+\begin{figure}
+  \begin{description}
+  \item[Setup] Group $G = \langle P \rangle$; $|G| = q$ is prime.
+    $H_I(\cdot, \cdot)$ and $H_K(\cdot)$ are secure hashes.  $\E = (\kappa,
+    E, D)$ is an IND-CCA2 symmetric encryption scheme.
+  \item[Parties] $U_i$ for $0 \le i < n$.
+  \item[Private keys] $x_i \inr \Nupto{q}$.
+  \item[Public keys] $X_i = x_i P$.
+  \end{description}
+  \[ \begin{graph}
+    !{0; <8cm, 0cm>: <0cm, 3cm>::}
+    *+[F]\dbox{$r_i \getsr I$; $R_i \gets r_i P$ \\
+               $c_i \gets r_i \xor H_I(R_i, r_i X_j)$} ="i0"
+    [d]
+    *+[F]\dbox{Check $R_j = \bigl(c_j \xor H_I(x_i R_j)\bigr) P$ \\
+               $Z \gets r_i R_j$; $K \gets H_K(0, Z)$ \\
+               $\chi_i \gets E_K(x_i R_j)$} ="i1"
+    [d]
+    *+[F]\dbox{Check $D_K(\chi_j) = r_i X_j$ \\
+               Shared key is $H_K(1, Z)$} ="i2"
+    "i0" [r]
+    *+[F]\dbox{$r_j \getsr I$; $R_j \gets r_j P$ \\
+               $c_j \gets r_j \xor H_I(R_j, r_j X_i)$} ="j0"
+    [d]
+    *+[F]\dbox{Check $R_i = \bigl(c_i \xor H_I(x_j R_i)\bigr) P$ \\
+               $Z \gets r_j R_i$; $K \gets H_K(0, Z)$ \\
+               $\chi_j \gets E_K(x_j R_i)$} ="j1"
+    [d]
+    *+[F]\dbox{Check $D_K(\chi_i) = r_j X_i$ \\
+               Shared key is $H_K(1, Z)$} ="j2"
+    %
+    "i0" : |(0)/3.25cm/*+{(R_i, c_i)} "j1"
+    "i1" : |(0)/3.25cm/*+{(R_i, \chi_i)} "j2"
+    "j0" : |(0)/3.25cm/*+{(R_j, c_j)} "i1"
+    "j1" : |(0)/3.25cm/*+{(R_j, \chi_j)} "i2"
+  \end{graph} \]
+
+  \caption{Summary of the Wrestlers Key Exchange protocol, $\Wkx$}
+  \label{fig:wkx}
+\end{figure}
+
+Assume, for the moment, that Alice and Bob's messages are relayed honestly.
+Then:
+\begin{itemize}
+\item $a S' = a S = a (s P) = s (a P) = s A$, so $s' = d' \xor H_I(S' a S') =
+  d \xor H_I(S, s A) = s$, and $S' = S = s P = s' P$, and therefore Alice
+  responds to Bob's message;
+\item similarly $b R' = r B$, so $r' = r$ and $R' = r' P$, and therefore Bob
+  responds to Alice's message;
+\item $b R' = b R = b (r P) = r (b P) = r B$, and $a S' = a S = a (s P) = s
+  (a P) = s A$, and therefore both parties compute their responses correctly;
+  and 
+\item $r S' = r S = r (s P) = s (r P) = s R = s R'$, so $K_A = K_B$, and
+  therefore they can decrypt each others' responses, and agree the same
+  shared secret.
+\end{itemize}
+This shows that the protocol is basically valid, but says little about its
+security.  The remainder of this section will describe our protocol in more
+formal detail, and prove its security in a model with multiple parties and an
+adversary who controls the network.
+
+Observe that the protocol as we've presented here is \emph{symmetrical}.
+There's no notion of `initiator' or `responder'.  There are a total of four
+messages which must be sent before both parties accept.  However, this can be
+reduced to three by breaking the symmetry of the protocol and combining one
+or other party's challenge and response messages.  We choose to analyse the
+symmetrical version, since to do so, it suffices to consider only the two
+different kinds of messages.  Since our security model allows the messages to
+be adversarially delayed and reordered, it is easy to show that the security
+of an optimized, asymmetrical protocol is no worse than the symmetrical
+version we present here.
+
+
+\subsection{Security model and security definition}
+\label{sec:um}
+
+Our model is very similar to that of Canetti and Krawczyk
+\cite{Canetti:2002:???}, though we have modified it in two ways.
+\begin{enumerate}
+\item We allow all the participants (including the adversary) in the protocol
+  access to the various random oracles required to implement it.
+\item Since we want to analyse a specific, practical scheme, asymptotic
+  results are useless.  We measure the adversary's resource usage carefully,
+  and produce a quantitative bound on the adversary's advantage in the
+  SK-security game.
+\end{enumerate}
+
+\subsubsection{Overview}
+We briefly describe our modified model, pointing out the changes we have
+made, and how they apply to our protocol.  Much of Canetti and Krawczyk's
+model (for example, the local and global outputs) is useful for proving more
+general security properties such as demonstrating that SK-security suffices
+for constructing secure channels, and we shall not concern ourselves with
+such details.  Other parts deal with issues such as security parameters and
+ensuring that all the computation is polynomially bounded, which are
+irrelevant since we are dealing with a single concrete protocol rather than a
+family of them.
+
+The entities in the model are the \emph{adversary}~$A$, and a (fixed) number
+of \emph{parties}~$P_i$, for $0 \le i < n$.  If the protocol under
+consideration makes use of random oracles, then all the participants -- the
+adversary and the parties -- are all allowed access to the random oracles.
+
+The parties and the adversary play a `game'.  At the beginning of the game,
+the participants are given some inputs computed by a randomized
+\emph{initialization procedure}~$\id{init}$.  This produces as output a pair
+$(i_U, \mathbf{i})$; the value $i_U$ is the \emph{global input}, and is given
+to all the participants including the adversary.  The vector $\mathbf{i}$ has
+$n$ components, and party $P_i$ is given $(i_U, \mathbf{i}[i])$ as input.
+
+\subsubsection{Sessions}
+Parties don't act directly.  Instead, each party runs a number of
+\emph{sessions}.  A session a triple $S = (P_i, P_j, s)$, where $i, j \in
+\Nupto{n}$ identify the owning party and a \emph{partner}, and $s \in
+\Bin^{\ell_S}$ is a \emph{session-id}.  (The original model includes a
+r\^ole, for distinguishing between initiators and responders.  Our protocol
+is symmetrical, so this distinction isn't useful.)  If $P_i$ runs a session
+$S = (P_i, P_j, s)$ and $P_j$ runs a session $S' = (P_j, P_i, s)$ then we say
+that $S$ and $S'$ are \emph{matching}, and that $P_j$ is $P_i$'s
+\emph{partner} for the session.
+
+At most one participant in the game is \emph{active} at any given time.
+Initially the adversary is active.  The adversary may \emph{activate} a
+session in one of two ways.
+\begin{enumerate}
+\item It may \emph{create a session} of a party~$P_i$, by selecting a
+  session-id~$s \in \Bin^{\ell_S}$ and a partner $j$.  There is no
+  requirement that $P_j$ ever have a matching session.  However, all sessions
+  of a party must be distinct, i.e., sessions with the same partner must have
+  different session-ids.
+\item It may \emph{deliver a message}~$\mu \in \Bin^*$, from party~$P_j$, to
+  an existing session~$S = (P_i, P_j, s)$.  There is no requirement that any
+  party previously sent $\mu$: the adversary is free to make up messages as
+  it sees fit.
+\end{enumerate}
+The adversary becomes inactive, and the session becomes active.  The session
+performs some computation, according to its protocol, and may request a
+message~$\mu$ be delivered to the matching session running in its partner
+(which may not exist).  The session may also \emph{terminate}.  In the case
+we are interested in, of key-exchange protocols, a session~$S = (P_i, P_j,
+s)$ may terminate in one of two ways:
+\begin{enumerate}
+\item it may \emph{complete}, outputting $(i, j, s, K)$, for some
+  \emph{session key}~$K$, or
+\item it may \emph{abort}, outputting $(i, j, s, \bot)$.
+\end{enumerate}
+Once it has performed these actions, the session deactivates and the
+adversary becomes active again.  The adversary is given the message~$\mu$, if
+any, and informed of whether the session completed or aborted, but, in the
+case of completion, not of the value of the key~$K$.  A session is
+\emph{running} if it has been created and has not yet terminated.
+
+\subsubsection{Other adversarial actions}
+As well as activating sessions, the adversary has other capabilities, as
+follows.
+\begin{itemize}
+\item It may \emph{expire} any session~$S$, causing the owning party to
+  `forget' the session key output by that session.
+\item It may \emph{corrupt} any party~$P_i$, at will: the adversary learns
+  the entire state of the corrupted party, including its initial
+  input~$\mathbf{i}[i]$, the state of any sessions it was running at the
+  time, and the session keys of any completed but unexpired sessions.  Once
+  corrupted, a party can no longer be activated.  Of course, the adversary
+  can continue to send messages allegedly from the corrupted party.
+\item It may \emph{reveal the state} of a running session~$S$, learning any
+  interesting values specific to that session, but \emph{not} the owning
+  party's long-term secrets.
+\item It may \emph{reveal the session-key} of a completed session~$S$.
+\item It may elect to be \emph{challenged} with a completed session~$S$,
+  provided.  Challenge sessions form part of the security notion for
+  key-exchange protocols.  See below for more details.
+\end{itemize}
+We say that a session $S = (P_i, P_j, s)$ is \emph{locally exposed} if
+\begin{itemize}
+\item it has had its state revealed,
+\item it has had its session-key revealed, or
+\item $P_i$ has been corrupted, and $S$ had not been expired when this
+  happened.
+\end{itemize}
+A session is \emph{exposed} if it is locally exposed, or if its matching
+session exists and has been locally exposed.
+
+At the beginning of the game, a bit $b^*$ is chosen at random.  The adversary
+may choose to be \emph{challenged} with any completed, unexposed
+session;\footnote{%
+  The original Canetti-Krawczyk definition restricts the adversary to a
+  single challenge session, but our proof works independent of the number of
+  challenge sessions, so we get a stronger result by relaxing the requirement
+  here.)}
+the adversary is then given either the session's key -- if $b^* = 1$ -- or a
+string chosen at random and independently of the game so far from a
+protocol-specific distribution -- if $b^* = 0$.  At the end of the game, the
+adversary outputs a single bit~$b$.
+
+\subsubsection{SK-security}
+We've now described the game; it is time to explain the adversary's goal in
+it.  The adversary \emph{wins} the game if either
+\begin{enumerate}
+\item two unexposed, matching sessions complete, but output different
+  keys,\footnote{%
+    The original Canetti-Krawczyk definition differs slightly here.  It
+    requires that `if two \emph{uncorrupted} parties complete matching
+    sessions then they both output the same key' [original emphasis].  This
+    can't be taken at face value, since none of the protocols they claim to
+    be secure actually meet this requirement: they meet only the weaker
+    requirement that parties completing matching sessions output different
+    keys with negligible probability.  We assume here that this is what they
+    meant.}
+  or
+\item the adversary correctly guesses the hidden bit~$b^*$.
+\end{enumerate}
+More formally, we make the following definition.
+\begin{definition}[SK-security]
+  \label{def:sk}
+  Let $\Pi^{H_0(\cdot), H_1(\cdot), \ldots}$ be a key-exchange protocol
+  which makes use of random oracles $H_0(\cdot)$, $H_1(\cdot)$, \dots, and
+  let $A$ be an adversary playing the game described previously, where $n$
+  parties run the protocol~$\Pi$.  Let $V$ be the event that any pair of
+  matching, unexposed sessions completed, but output different session keys.
+  Let $W$ be the event that the adversary's output bit matches the game's
+  hidden bit~$b^*$.  We define the adversary's \emph{advantage against the
+    SK-security of the protocol~$\Pi$} to be
+  \[ \Adv{sk}{\Pi}(A, n) = \max(\Pr[V], 2\Pr[W] - 1). \]
+  Furthermore, we define the \emph{SK insecurity function of the
+  protocol~$\Pi$} to be
+  \[ \InSec{sk}(\Pi; t, n, q_S, q_M, q_{H_0}, q_{H_1}, \dots) =
+       \max_A \Adv{sk}{\Pi}(A, n)
+  \]
+  where the maximum is taken over all adversaries~$A$ with total running
+  time~$t$ (not including time taken by the parties), create at most $q_S$
+  sessions, deliver at most $q_M$~messages, and (if applicable) make at most
+  $q_{H_i}$ random-oracle queries to each random oracle $H_i(\cdot)$.
+\end{definition}
+
+
+\subsection{Security}
+
+In order to analyse our protocol $\Wkx^{G, \E}$ properly, we must describe
+exactly how it fits into the formal model described in our formal model.
+
+\subsubsection{Sessions and session-ids}
+Our formal model introduced the concept of sessions, which the informal
+description of section~\ref{sec:kx-overview} neglected to do.  (One could
+argue that we described a single session only.)  As we shall show in
+section~\ref{sec:kx-insecure}, our protocol is \emph{insecure} unless we
+carefully modify it to distinguish between multiple sessions.
+
+In the model, distinct key-exchange sessions are given distinct partners and
+session-ids.  In order to prevent sessions interfering with each other, we
+shall make explicit use of the session-ids.
+
+Suppose the session-ids are $\ell_S$-bit strings.  We expand the domain of
+the random oracle $H_I$ so that it's now
+\[ H_I\colon G \times \Bin^{\ell_S} \times G \times G \to \Bin_{\ell_I}. \]
+
+\subsubsection{Messages}
+We split the messages our protocols into two parts: a \emph{type}~$\tau$ and
+a \emph{body}~$\mu$.  We assume some convenient, unambiguous encoding of
+pairs $(\tau, \mu)$ as bit-strings.  For readability, we present message
+types as text strings, e.g., `\cookie{challenge}', though in practice one
+could use numerical codes instead.
+
+The message body itself may be a tuple of values, which, again, we assume are
+encoded as bit-strings in some convenient and unambiguous fashion.  We shall
+abuse the notation for the sake of readability by dropping a layer of nesting
+in this case: for example, we write $(\cookie{hello}, x, y, z)$ rather than
+$\bigl(\cookie{hello}, (x, y, z)\bigr)$.
+
+\subsubsection{The protocol}
+Our protocol is represented by three functions, shown in
+figure~\ref{fig:wkx-formal}.
+\begin{itemize}
+\item $\id{init}(n)$ is the initialization function, as described in
+  section~\ref{sec:um}.  It outputs a pair $(\mathbf{p}, \mathbf{i})$, where
+  $\mathbf{i}[i]$ is the private key of party~$P_i$ and $\mathbf{p}[i]$ is
+  the corresponding public key.  Only $P_i$ is given $\mathbf{i}[i]$, whereas
+  all parties and the adversary are given $\mathbf{p}$.
+\item $\id{new-session}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)}
+  (\mathbf{p}, x, i, j, s)$ is the new-session function.  This is executed by
+  party~$P_i$ when the adversary decides to create a new session~$S = (P_i,
+  P_j, s)$.  It is also given the relevant outputs of $\id{init}$, and
+  allowed access to the random oracles $H_I$ and $H_K$.
+\item $\id{message}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)} (\tau,
+  \mu)$ is the incoming-message function.  This is executed by a session when
+  the adversary decides to deliver a message $(\tau, \mu)$ to it.  It makes
+  use of the subsidiary functions $\id{msg-challenge}$ and
+  $\id{msg-response}$ to handle the messages.
+\end{itemize}
+We observe that the protocol never aborts.  We could make it do so if it
+receives an invalid message, but we prefer to ignore invalid messages for the
+sake of robustness.\footnote{%
+  Note that this protocol would therefore require modification before it was
+  acceptable in the simulation-based model of \cite{Shoup:1999:OFM}.  There
+  it is required that a key-exchange protocol terminate after a
+  polynomially-bounded number of messages are delivered to it.}
+
+\begin{figure}
+  \begin{program}
+    Function $\id{init}(n)$: \+ \\
+      \FOR $i \in \Nupto{n}$ \DO \\ \ind
+        $x \getsr \Nupto{|G|}$; \\
+        $\mathbf{i}[i] \gets x$; \\
+        $\mathbf{p}[i] \gets x P$; \- \\
+      \RETURN $(\mathbf{p}, \mathbf{i})$;
+    \- \\[\medskipamount]
+    Function $\id{new-session}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)}
+      (\mathbf{p}, x, i, j, s)$: \+ \\
+      $X \gets \mathbf{p}[i]$;
+      $X' \gets \mathbf{p}[j]$;
+      $C \gets \emptyset$; \\
+      $r \getsr \Nupto{|G|}$;
+      $R \gets r P$;
+      $Y \gets r X'$; \\
+      $h \gets H_I(X, s, R, Y)$;
+      $c \gets r \xor h$; \\
+      \SEND $(\cookie{challenge}, R, c)$;
+    \- \\[\medskipamount]
+    Function $\id{message}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)}
+      (\tau, \mu)$: \+ \\
+      \IF $\tau = \cookie{challenge}$ \THEN $\id{msg-challenge}(\mu)$; \\
+      \ELSE \IF $\tau = \cookie{response}$ \THEN $\id{msg-response}(\mu)$;
+    \next
+    Function $\id{msg-challenge}(\mu)$: \+ \\
+      $(R', c') \gets \mu$; \\
+      $Y' \gets x R'$; \\
+      $h' \gets H_I(X', s, R', Y')$; \\
+      $r' \gets c' \xor h'$; \\
+      \IF $R' \ne r' P$ \THEN \RETURN; \\
+      $C \gets C \cup \{R\}$; \\
+      $Z \gets r R'$; \\
+      $(K_0, K_1) \gets H_K(Z)$; \\
+      $\chi \gets E_{K_0}(Y')$; \\
+      \SEND $(\cookie{response}, R, \chi)$;
+    \- \\[\medskipamount]
+    Function $\id{msg-response}(\mu)$: \+ \\
+      $(R', \chi') \gets \mu$; \\
+      \IF $R' \notin C$ \THEN \RETURN; \\
+      $Z \gets r R'$; \\
+      $(K_0, K_1) \gets H_K(Z)$; \\
+      $Y' \gets D_{K_0}(\chi')$; \\
+      \IF $Y' \ne Y$ \THEN \RETURN; \\
+      \OUTPUT $K_1$;
+      \STOP;
+  \end{program}
+  
+  \caption{Formalization of $\Wkx$}
+  \label{fig:wkx-formal}
+\end{figure}
+
+\subsubsection{Session states}
+We must specify what the adversary obtains when it chooses to reveal a
+session's state.  Given the program in figure~\ref{fig:wkx-formal}, we can
+see that the session state consists of the variables $(x, X, X', r, R, Y,
+C)$.
+
+However, $x$ is the owning party's long-term secret, and it seems
+unreasonable to disclose this to an adversary who stops short of total
+corruption.
+
+The public keys $X$ and $X'$ are part of the adversary's input anyway, so
+revealing them doesn't help.  Similarly, the set $C$ of valid challenges
+could have been computed easily by the adversary, since a group element $R'
+\in C$ if and only if the session $S$ responded to some message
+$(\cookie{challenge}, R', c')$.
+
+The value $R = r P$ is easily computed given $r$, and besides is sent in the
+clear in the session's first message.  The expected response $Y = r X'$ is
+also easily computed from $r$.  The converse is also true, since $r$ can be
+recovered from $R$ and $c$ in the session's challenge message and the value
+$Y$.  Besides, $r$ is necessary for computing $Z$ in response to incoming
+challenges.
+
+We conclude that the only `interesting' session state is $r$.
+
+\subsubsection{Security}
+Having formally presented the protocol, we can now state our main theorem
+about its security.  The proof is given in appendix~\ref{sec:sk-proof}.
+\begin{theorem}[SK-security of $\Wkx$]
+  \label{thm:sk}
+  Let $G$ be a cyclic group.  Let $\E = (\kappa, E, D)$ be a symmetric
+  encryption scheme.  Then
+  \begin{spliteqn*}
+    \InSec{sk}(\Wkx^{G, \E}; t, n, q_S, q_M, q_I, q_K) \le
+      \frac{n (n - 1)}{|G|} +
+      \frac{2 q_M}{2^{\ell_I}} + {}\\
+      2 q_S \bigl( \InSec{mcdh}(G; t', q_K) +
+                   n \cdot \InSec{mcdh}(G; t', q_M + q_I) +
+                   \InSec{ind-cca}(\E; t', q_M, q_M) \bigr)
+  \end{spliteqn*}
+  where $t' = t + O(n) + O(q_S) + O(q_M q_I) + O(q_K)$.
+\end{theorem}
+
+
+\subsection{Insecure protocol variants}
+\label{sec:kx-insecure}
+
+It's important to feed the session-id and verifier's public key to the random
+oracle $H_I$ when constructing the check-value~$c$.  Without these, the
+protocol is vulnerable to attack.  In this section, we consider some variants
+of our protocol which hash less information, and show attacks against them.
+
+To simplify the presentation, we shall consider Alice and Bob, and a third
+character Carol.  We shall be attacking a pair of matching sessions $A$
+and~$B$, run by Alice and Bob respectively.  Let Alice and Bob's private keys
+be $x_A$ and~$x_B$, and let their public keys be $X_A = x_A P$ and $X_B = x_B
+P$ respectively.
+
+\subsubsection{Protocol diagram notation}
+In order to keep the presentation as clear as possible, we use a simple
+diagrammatic notation for describing protocol runs.  A line of the form
+\protocolrun{\textit{action} \ar[r] & \PRsession{S} & \textit{result}}
+states that the adversary performs the given \textit{action} on session~$S$,
+with the stated \textit{result}.  The \textit{action} may be
+\begin{itemize}
+\item \textsf{Create session $(P_i, P_j, s)$}: the session is created,
+  running in party~$P_i$, with partner~$P_j$ and session-id~$s$.
+\item \textsf{Receive $\mu$}: the session is activated with an incoming message~$\mu$.
+\item \textsf{Session-state reveal}: The adversary requests the session's
+  internal state.
+\end{itemize}
+The \textit{result} may be
+\begin{itemize}
+\item \textsf{Send $\mu'$}: the session requests the delivery of the
+  message~$\mu'$.
+\item \textsf{Complete: $K$}: the session completes, outputting the key~$K$.
+\item \textsf{State: $\sigma$}: the session's state is revealed to
+  be~$\sigma$.
+\item \textsf{(Ignore)}: the result of the action is unimportant.
+\end{itemize}
+
+\subsubsection{Omitting the session-id}
+Consider a protocol variant where session $S$ sets $h_S = H_I(X_N, R_S,
+Y_S)$, where $N$ is the session's partner.  That is, we've omitted the
+session-id from the hash.  An adversary can cross over two sessions between
+Alice and Bob.  Here's how.
+
+The attack assumes that Alice and Bob set up two pairs of matching sessions
+with each other, thus.
+\protocolrun{
+  \PRcreate{Alice}{Bob}{s} & \PRsession{A} &
+    \PRsend{challenge}{R_A, c_A} \\
+  \PRcreate{Bob}{Alice}{s} & \PRsession{B} &
+    \PRsend{challenge}{R_B, c_B} \\
+  \PRcreate{Alice}{Bob}{s'} & \PRsession{A'} &
+    \PRsend{challenge}{R_{A'}, c_{A'}} \\
+  \PRcreate{Bob}{Alice}{s'} & \PRsession{B'} &
+    \PRsend{challenge}{R_{B'}, c_{B'}}
+}
+Observe that the session pairs use distinct session-ids $s \ne s'$, so this
+is allowed.  Now the adversary crosses over the challenges, using the second
+pair of sessions to provide responses to the challenges issued by the first
+pair.  By revealing the state in the second pair of sessions, the adversary
+can work out the (probably different) session keys accepted by the first
+pair.
+\protocolrun{
+  \PRreceive{challenge}{R_B, c_B} & \PRsession{A'} &
+    \PRsend{response}{R_{A'}, E_{K_{A'B,0}}(x_A R_B)} \\
+  \PRreceive{challenge}{R_A, c_A} & \PRsession{B'} &
+    \PRsend{response}{R_{B'}, E_{K_{B'A,0}}(x_B R_A)} \\
+  \PRreceive{challenge}{R_{A'}, c_{A'}} & \PRsession{A} & \PRignore \\
+  \PRreceive{challenge}{R_{B'}, c_{B'}} & \PRsession{B} & \PRignore \\
+  \PRreveal & \PRsession{A'} & r_{A'} \\
+  \PRreveal & \PRsession{B'} & r_{B'} \\
+  \PRreceive{response}{R_{B'}, E_{K_{B'A,0}}(x_B R_A)} & \PRsession{A} &
+    \PRcomplete{K_{AB',1}} \\
+  \PRreceive{response}{R_{A'}, E_{K_{A'B,0}}(x_A R_B)} & \PRsession{B} &
+    \PRcomplete{K_{BA',1}} \\
+}
+The adversary can now compute $K_{AB'} = H_K(r_{B'} R_A)$ and $K_{B'A} =
+H_K(r_{A'} R_B)$.  Safely in possession of both keys, the adversary can now
+read and impersonate freely.
+
+\subsubsection{Omitting the partner's public key}
+Now consider a protocol variant where session $S$ sets $h_S = H_I(s, R_S,
+Y_S)$, where $s$ is the session-id.  An adversary can use a sessions with
+Carol to attack a session between Alice and Bob.  Here's how the sessions are
+set up.
+\protocolrun{
+  \PRcreate{Alice}{Bob}{s} & \PRsession{A} &
+    \PRsend{challenge}{R_A, c_A} \\
+  \PRcreate{Bob}{Alice}{s} & \PRsession{B} &
+    \PRsend{challenge}{R_B, c_B} \\
+  \PRcreate{Alice}{Carol}{s} & \PRsession{A'} &
+    \PRsend{challenge}{R_{A'}, c_{A'}} \\
+  \PRcreate{Bob}{Carol}{s} & \PRsession{B'} &
+    \PRsend{challenge}{R_{B'}, c_{B'}}
+}
+Although each of Alice and Bob have two sessions with session-id~$s$, this is
+allowed, since they are with different partners.  The rest of the attack in
+fact proceeds identically to the previous case.
+
+
+\subsection{Deniability}
+\label{sec:denial}
+
+We have claimed that the Wrestlers key-exchange protocol is \emph{deniable}.
+In this section, we define what we mean, explain the limits of the
+deniablility of the protocol as currently presented, fix the protocol with an
+additional pass (which can be collapsed to a single message flow by breaking
+the protocol's symmetry), and prove the deniability of the resulting
+protocol.
+
+Our notion of deniability is taken from Di~Raimondo, Gennaro and Krawczyk
+\cite{DiRaimondo:2006:DAK}, except that, as usual, we opt for a concrete
+security approach.
+
+\subsubsection{Discussion}
+Our definition for deniability is that, for any adversary interacting with
+participants in the protocol, a simulator exists which can compute the same
+things as the adversary.  In particular, since an adversary could output a
+transcript of the interactions between itself and the parties, it would
+follow that a simulator could do this too.  If the simulator is effective,
+its output is indistinguishable from that of the real adversary, and hence no
+`judge' (distinguisher) should be persuaded by evidence presented by someone
+who claims to have witnessed or participated in an interaction.
+
+We work again the model described in~\ref{sec:um}.  That is, our adversary
+has complete control over the ordering and delivery of all messages.  The
+adversary is also able, at any time, to reveal the state of any session.
+However, deniability is obviously impossible against an adversary who can
+\emph{corrupt} other parties, since simulating such an adversary's actions
+would necessarily require the simulator to compute private keys corresponding
+to the known public keys, and this is (we believe) difficult, because an
+efficient algorithm for doing this could easily attack our protocol, which we
+already proved secure.  Therefore, we forbid the adversary from corrupting
+parties.
+
+In order to allow the adversary to participate in the protocol, rather than
+merely observing it, we need to give it one or more private keys.  We could
+modify the initialization function \id{init} from figure~\ref{fig:wkx-formal}
+to give the adversary a private key, but there's an easier way: we can just
+give the adversary a number of private keys in its auxiliary input.
+
+\subsubsection{Definitions}
+Let $\Pi$ be a key-exchange protocol, in the model described in
+section~\ref{sec:um}.  We use the simulation framework of
+section~\ref{sec:sim}.  We define the initialization function $I_\Pi$ to be
+the initialization function of $\Pi$, as before, and the corresponding
+world~$W_\Pi(\iota, \sigma, \tau, \mu)$ is a fairly straightforward mapping
+of the adversary's possible actions to the simulation model:
+\begin{itemize}
+\item The invocation $\cookie{new-session}$ with $\mu = (i, j, s)$ creates a
+  new session on party~$P_i$, with partner~$P_j$ and session-id~$s$.  The
+  reply $\rho = (\delta, m)$ is a \emph{decision} $\delta \in
+  \{\cookie{continue}, \cookie{abort}, \cookie{complete}\}$ and an output
+  message $m \in \Bin^* \cup \{\bot\}$.  If $m \ne \bot$ then $m$ is a
+  message to be sent to the matching session (if any).
+\item The invocation $\cookie{deliver}$ with $\mu = (i, j, s, m)$ delivers
+  message $m$ to the session $S = (P_i, P_j, s)$.  The response $\rho$ is as
+  for $\cookie{new-session}$ invocations.
+\item The invocation $\cookie{reveal-session-state}$ with $\mu = (i, j, s)$
+  reveals to the adversary the state of the running session $S = (P_i, P_j,
+  s)$.  The response $\rho$ is the session's state if $S$ is indeed a running
+  session, or $\bot$ otherwise.
+\item The invocation $\cookie{reveal-session-key}$ with $\mu = (i, j, s)$
+  reveals to the adversary the session-key of the completed session~$S =
+  (P_i, P_j, s)$.  The response $\rho$ is the session key~$K$ if the session
+  is indeed complete, or $\bot$ otherwise.
+\end{itemize}
+There are no invocations corresponding to the adversary actions of corrupting
+parties (since deniability against an corrupting adversary is impossible, as
+discussed earlier), or session expiry or challenging (since they are useless
+in this context).
+
+We measure the deniability of a protocol~$\Pi$, using a given simulator~$S$,
+by the insecurity function $\InSec{sim}(W_\Pi, I_\Pi, S; t_D, t_A,
+\mathcal{Q}_D, \mathcal{Q}_A, \mathcal{R}, \mathcal{U})$ of
+definition~\ref{def:sim}.  The interaction bounds $\mathcal{R} = (q_S, q_M)$
+we place on the adversary are on the number ($q_S$) of \cookie{new-session}
+and ($q_M$) \cookie{deliver} invocations it makes.
+
+We shall (informally) say that a protocol~$\Pi$ is deniable if there is a
+simulator~$S_\Pi$ for which the insecurity function is small for appropriate
+resource bounds on the adversary and distinguisher.
+
+\subsubsection{The current protocol}
+As it stands, $\Wkx$ isn't deniable, according to our definition, for
+arbitrary auxiliary inputs.  Let's see why.
+
+Suppose that Bob is an informant for the secret police, and wants to convince
+a judge that Alice is involved in subversive activities in cyberspace.
+Unfortunately, Bob's job is difficult, because of the strong zero-knowledge
+nature of the Wrestlers identification protocol.  However, Bob can work with
+the judge to bring him the evidence necessary to convict Alice.  Here's how.
+
+Alice's public key is $A$, and Bob's public key is $B$.  The judge chooses
+some session-id $s$, and $r \inr \Nupto{q}$.  He computes $R = r P$ and $c =
+r \xor H_I(B, s, R, r A)$, and gives Bob the triple $(s, R, c)$, keeping $r$
+secret.  Bob can now persuade Alice to enter into a key-exchange with him,
+with session-id $s$.  He uses $(R, c)$ as his challenge message.  When Alice
+sends back her response $(R', \chi)$ (because Bob's challenge is correctly
+formed), Bob aborts and shows $(R', \chi)$ to the judge.  The judge knows $r$
+and can therefore decrypt $\chi$ and check the response.  If it's wrong, then
+Bob was cheating and gets demoted -- he can't get the right answer by himself
+because that would require him to impersonate Alice.  If it's right, Alice is
+really a subversive element and `disappears' in the night.
+
+We shall show in theorem~\ref{thm:denial} below that this is basically the
+only attack against the deniability of the protocol.  However, we can do
+better.
+
+\subsubsection{Fixing deniability}
+We can fix the protocol to remove even the attack discussed above.  The
+change is simple: we feed \emph{both} parties' challenges to the hash
+function~$H_I$ rather than just the sender's.  We use a five-argument hash
+function (random oracle) $H_I\colon G^2 \times \Bin^{\ell_S} \times G^2 \to
+\Bin^{\ell_I}$.  We introduce a new message pass at the beginning of the
+protocol: each session simply sends its challenge point $R = r P$ in the
+clear as a `pre-challenge'.  The actual challenge is $R$ and $c = r \xor
+H_I(X, R', s, R, c)$, where $R'$ is the challenge of the matching session.
+
+By breaking symmetry, we can reduce the communication complexity of this
+variant to four messages.  As before, we analyse the symmetrical version.
+The extra flow might seem a high price to pay, but we shall see that it has
+additional benefits beyond deniability.
+
+A summary of the new protocol is shown in figure~\ref{fig:wdkx}, and the
+formal description is shown in figure~\ref{fig:wdkx-formal}.
+
+\begin{figure}
+  \begin{description}
+  \item[Setup] Group $G = \langle P \rangle$; $|G| = q$ is prime.
+    $H_I(\cdot, \cdot, \cdot, \cdot, \cdot)$ and $H_K(cdot)$ are secure
+    hashes.  $\E = (\kappa, E, D)$ is an IND-CCA2 symmetric encryption
+    scheme.
+  \item[Parties] $U_i$ for $0 \le i < n$.
+  \item[Private keys] $x_i \inr \Nupto{q}$.
+  \item[Public keys] $X_i = x_i P$.
+  \end{description}
+  \[ \begin{graph}
+    !{0; <8cm, 0cm>: <0cm, 3cm>::}
+    *+[F]\dbox{$r_i \getsr I$; $R_i \gets r_i P$} ="i-1"
+    [d]
+    *+[F]\dbox{$c_i \gets r_i \xor H_I(R_j, X_i, s, R_i, r_i X_j)$} ="i0"
+    [d]
+    *+[F]\dbox{Check $R_j = \bigl(c_j \xor H_I(x_i R_j)\bigr) P$ \\
+               $Z \gets r_i R_j$; $K \gets H_K(0, Z)$ \\
+               $\chi_i \gets E_K(x_i R_j)$} ="i1"
+    [d]
+    *+[F]\dbox{Check $D_K(\chi_j) = r_i X_j$ \\
+               Shared key is $H_K(1, Z)$} ="i2"
+    "i-1" [r]
+    *+[F]\dbox{$r_j \getsr I$; $R_j \gets r_j P$} ="j-1"
+    [d]
+    *+[F]\dbox{$c_j \gets r_j \xor H_I(R_i, X_j, s, R_j, r_j X_i)$} ="j0"
+    [d]
+    *+[F]\dbox{Check $R_i = \bigl(c_i \xor H_I(x_j R_i)\bigr) P$ \\
+               $Z \gets r_j R_i$; $K \gets H_K(0, Z)$ \\
+               $\chi_j \gets E_K(x_j R_i)$} ="j1"
+    [d]
+    *+[F]\dbox{Check $D_K(\chi_i) = r_j X_i$ \\
+               Shared key is $H_K(1, Z)$} ="j2"
+    %
+    "i-1" : |(0)/3.25cm/*+{R_i} "j0"
+    "i0" : |(0)/3.25cm/*+{(R_i, c_i)} "j1"
+    "i1" : |(0)/3.25cm/*+{(R_i, \chi_i)} "j2"
+    "j-1" : |(0)/3.25cm/*+{R_j} "i0"
+    "j0" : |(0)/3.25cm/*+{(R_j, c_j)} "i1"
+    "j1" : |(0)/3.25cm/*+{(R_j, \chi_j)} "i2"
+  \end{graph} \]
+
+  \caption{Summary of the Deniable Wrestlers Key Exchange protocol, $\Wdkx$}
+  \label{fig:wdkx}
+\end{figure}
+
+\begin{figure}
+  \begin{program}
+    Function $\id{init}(n)$: \+ \\
+      \FOR $i \in \Nupto{n}$ \DO \\ \ind
+        $x \getsr \Nupto{|G|}$; \\
+        $\mathbf{i}[i] \gets x$; \\
+        $\mathbf{p}[i] \gets x P$; \- \\
+      \RETURN $(\mathbf{p}, \mathbf{i})$;
+    \- \\[\medskipamount]
+    Function $\id{new-session}^{H_I(\cdot, \cdot, \cdot, \cdot, \cdot), H_K(\cdot)}
+      (\mathbf{p}, x, i, j, s)$: \+ \\
+      $X \gets \mathbf{p}[i]$;
+      $X' \gets \mathbf{p}[j]$;
+      $C \gets \emptyset$; \\
+      $r \getsr \Nupto{|G|}$;
+      $R \gets r P$;
+      $Y \gets r X'$; \\
+      \SEND $(\cookie{pre-challange}, R)$;
+    \- \\[\medskipamount]
+    Function $\id{message}^{H_I(\cdot, \cdot, \cdot, \cdot, \cdot), H_K(\cdot)}
+      (\tau, \mu)$: \+ \\
+      \IF $\tau = \cookie{pre-challenge}$ \THEN
+        $\id{msg-pre-challenge}(\mu)$; \\
+      \ELSE \IF $\tau = \cookie{challenge}$ \THEN
+        $\id{msg-challenge}(\mu)$; \\
+      \ELSE \IF $\tau = \cookie{response}$ \THEN $\id{msg-response}(\mu)$;
+    \next
+    Function $\id{msg-pre-challenge}(\mu)$: \+ \\
+      $R' \gets \mu$; \\
+      $h \gets H_I(R', X, s, R, c)$; \\
+      $c \gets r \xor h$; \\
+      \SEND $(\id{msg-challenge}, R, c)$;
+    \- \\[\medskipamount]
+    Function $\id{msg-challenge}(\mu)$: \+ \\
+      $(R', c') \gets \mu$; \\
+      $Y' \gets x R'$; \\
+      $h' \gets H_I(R, X', s, R', Y')$; \\
+      $r' \gets c' \xor h'$; \\
+      \IF $R' \ne r' P$ \THEN \RETURN; \\
+      $C \gets C \cup \{R\}$; \\
+      $Z \gets r R'$; \\
+      $(K_0, K_1) \gets H_K(Z)$; \\
+      $\chi \gets E_{K_0}(Y')$; \\
+      \SEND $(\cookie{response}, R, \chi)$;
+    \- \\[\medskipamount]
+    Function $\id{msg-response}(\mu)$: \+ \\
+      $(R', \chi') \gets \mu$; \\
+      \IF $R' \notin C$ \THEN \RETURN; \\
+      $Z \gets r R'$; \\
+      $(K_0, K_1) \gets H_K(Z)$; \\
+      $Y' \gets D_{K_0}(\chi')$; \\
+      \IF $Y' \ne Y$ \THEN \RETURN; \\
+      \OUTPUT $K_1$;
+      \STOP;
+  \end{program}
+  
+  \caption{Deniable key-exchange: formalization of $\Wdkx$}
+  \label{fig:wdkx-formal}
+\end{figure}
+
+The security of this variant is given by the following theorem, whose proof
+is in appendix~\ref{sec:sk2-proof}.
+\begin{theorem}[SK-security of $\Wdkx$]
+  \label{thm:sk2}
+  Let $G$ be a cyclic group.  Let $\E = (\kappa, E, D)$ be a symmetric
+  encryption scheme.  Then
+  \[ \InSec{sk}(\Wdkx^{G, \E}; t, n, q_S, q_M, q_I, q_K) =
+       \InSec{sk}(\Wkx^{G, \E}; t, n, q_S, q_M, q_I, q_K)
+  \]
+\end{theorem}
+
+\subsubsection{Deniability of the Wrestlers protocols}
+In order to quantify the level of deniability our protocols provide, we shall
+impose a limit on the auxiliary input to the adversary.  In particular, we
+shall use $\mathcal{U}$ of definition~\ref{def:sim} to count the number of
+\emph{challenges} in the auxiliary input.  That is, $\mathcal{U} = n_C$ is
+the number of tuples $(i, j, s, R', R, c)$ for which there is an $r$ such
+that $R = r P$ and $c = r \xor H_I(R', X_j, s, R, r X_i)$ (or without the
+$R'$ for $\Wkx$).
+
+With this restriction in place, we can state the following theorem about the
+deniability of our protocols.
+\begin{theorem}[Deniability of $\Wkx$ and $\Wdkx$]
+  \label{thm:denial}
+  There exist simulators $S_\Wkx$ and $\Wdkx$ such that
+  \[ \InSec{sim}(W_{\Wkx^{G, \E}}, I_{\Wkx^{G, \E}}, S_{\Wkx^{G, \E}};
+                 t_D, t_A, \mathcal{Q}_D, \mathcal{Q}_A, (q_S, q_M), 0) \le
+       \frac{q_M}{2^{\ell_I}}
+  \]
+  and
+  \[ \InSec{sim}(W_{\Wdkx^{G, \E}}, I_{\Wdkx^{G, \E}}, S_{\Wdkx^{G, \E}};
+                 t_D, t_A, \mathcal{Q}_D, \mathcal{Q}_A, (q_S, q_M), n_C) \le
+       \frac{n_C q_S}{|G|} +
+       \frac{q_M}{2^{\ell_I}}.
+  \]
+  The running time of the simulators is $O(t_A) + O(\mathcal{Q}_A q_M)$.
+\end{theorem}
+\begin{proof}
+  The simulators $S_\Wkx$ and $S_\Wdkx$ are very similar.  We describe both
+  here.  Both are fake-world simulators, working as follows.
+  \begin{enumerate}
+  \item Initially, it constructs simulated parties $P_i$, for $0 \le i < n$,
+    giving each the public key $X_i$ from the common input.
+  \item Suppose the adversary requests creation of a new session $S = (P_i,
+    P_j, s)$.  Then the simulator creates a new session, including a random
+    value $r_S \inr \Nupto{|G|}$, and computes $R_S = r_S P$, and $Y_S = r_S
+    X_j$.  For $\Wdkx$, it sends the message $(\cookie{pre-challenge}, R_S)$;
+    for $\Wkx$, it additionally computes $h = H_I(X_i, s, R_S, Y_S)$ and
+    sends $(\cookie{challenge}, R_S, r_S \xor h)$.
+  \item Suppose, for $\Wdkx$, the adversary sends a message
+    $(\cookie{pre-challenge}, R')$ to a session~$S = (P_i, P_j, s)$.  The
+    simulator computes $h = H_I(R', X_i, s, R_S, Y_S)$, and sends
+    $(\cookie{challenge}, R_S, r_S \xor h)$.
+  \item Suppose the adversary sends a message $(\cookie{challenge}, R', c')$
+    to session $S = (P_i, P_j, s)$.  The simulator doesn't know $x_i$.
+    \begin{enumerate}
+    \item If $R' = R_T$ for some other simulated session $T$, then the
+      simulator knows $r_T$ such that $R_T = r_T P$.  Let $Y' = r_T X_i$.
+      The simulator computes $h = H_I(X_j, s, R', Y')$ (resp.\ $h = H_I(R_S,
+      X_j, s, R', Y')$) for $\Wkx$ (resp.\ $\Wdkx$) and checks that $r_T = c'
+      \xor h$.  If not, the simulator discards the message.  Otherwise, it
+      computes $(K_0, K_1) = H_K(r_S R')$, and sends the message
+      $(\cookie{response}, R, E_{K_0}(Y'))$.
+    \item \label{en:simextract} Otherwise the simulator runs the extractor
+      $T_\Wident$ on the adversary's history of queries $H_I(X_j, s, R',
+      \cdot)$ (resp.\ $H_I(R_S, X_j, s, R', \cdot)$) for $\Wkx$ (resp.\
+      $\Wdkx$).  The extractor returns $(r', Y')$.  If $Y' = \bot$ then the
+      simulator ignores the message.  Otherwise, the simulator computes
+      $(K_0, K_1) = H_K(r R')$ and sends back $(\cookie{response}, R,
+      E_{K_0}(Y'))$.
+    \end{enumerate}
+  \item Suppose the adversary sends a message $(\cookie{response}, R', \chi)$
+    to session $S = (P_i, P_j, s)$.  The simulator computes $(K_0, K_1) =
+    H_K(r_S R')$, and decrypts $Y' = D_{K_0}(\chi)$.  If $Y' \ne Y_S$ then
+    the simulator discards the message.  Otherwise, it makes the simulated
+    session complete, and outputs key $K_1$.
+  \item Finally, if the adversary reveals a session's state, the simulator
+    reveals $r_S$ as required; if the adversary reveals a session-key, the
+    simulator reveals the $K_1$ it output.
+  \end{enumerate}
+  The only point where the simulation fails to be perfect is in
+  \ref{en:simextract}.  Let $R'$ and $c'$ be the values from an incoming
+  challenge message to session $S = (P_i, P_j, s)$.  Let $r'$ be such that
+  $R' = r' P$ and let $Y' = r' X_i$.  If a random-oracle query $H_I(X_j, s,
+  R', Y')$ (or $H_I(R_S, X_j, s, R', Y')$ for $\Wdkx$) has been issued, then
+  there are a number of possibilities.  Let $h'$ be the result of this query.
+  \begin{itemize}
+  \item The adversary made this query.  Then the extractor will find it and
+    return $Y'$ if $c' = h' \xor r'$, or $\bot$ otherwise.
+  \item Some simulated session $U = (P_{i'}, P_{j'}, s')$ made this query.
+    But simulated sessions only make $H_I$-queries when constructing
+    challenges, so $R' = R_U$ for some session~$U$.  But the simulator does
+    something different in that case.
+  \item In $\Wdkx$, the quadruple $(s, R_S, R', c')$ came from the
+    adversary's auxiliary input.  In this case the simulator must fail.  But
+    $R_S = r_S P$, and $r_S$ was chosen uniformly at random.  If there are at
+    most $n_C$ challenge sets in the auxiliary input then this happens with
+    probability at most $n_C/|G|$ for any given session.
+  \end{itemize}
+  We conclude that the simulator fails with probability
+  \[ \frac{q_M}{2^{\ell_I}} + \frac{q_S n_C}{|G|}. \]
+  (Note that we only consider $n_C = 0$ for $\Wkx$.)  No adversary can
+  distinguish the simulator from a real interaction unless the simulator
+  fails, and the simulator is a fake-world simulator.  We therefore apply
+  proposition~\ref{prop:fakesim}; the theorem follows.
+\end{proof}
+
+
+\subsection{Practical issues}
+\label{sec:practice}
+
+\subsubsection{Denial of service from spoofers}
+The adversary we considered in~\ref{sec:um} is very powerful.  Proving
+security against such a powerful adversary is good and useful.  However,
+there are other useful security properties we might like against weaker
+adversaries.
+
+Eavesdropping on the Internet is actually nontrivial.  One needs control of
+one of the intermediate routers between two communicating parties.  (There
+are tricks one can play involving subversion of DNS servers, but this is also
+nontrivial.)  However, injecting packets with bogus source addresses is very
+easy.
+
+Layering the protocol over TCP \cite{RFC793} ameliorates this problem because
+an adversary needs to guess or eavesdrop in order to obtain the correct
+sequence numbers for a spoofed packet; but the Wrestlers protocol is
+sufficiently simple that we'd like to be able to run it over UDP
+\cite{RFC768}, for which spoofing is trivial.
+
+Therefore, it's possible for anyone on the 'net to send Alice a spurious
+challenge message $(R, c)$.  She will then compute $Y = a R$, recover $r' = c
+\xor H_I(\ldots, R, Y)$ check that $R = r' P$ and so on.  That's at least two
+scalar multiplications to respond to a spoofed packet, and even with very
+efficient group operations, coping with this kind of simple denial-of-service
+attack might be difficult.
+
+A straightforward solution is to use the Deniable variant of the protocol,
+and require a challenge to quote its matching session's challenge $R'$ in its
+challenge.  That is, upon receiving a $(\cookie{pre-challenge}, R')$, the
+session sends $(\cookie{challenge}, R', R, c)$.  Alice then rejects any
+\emph{incoming} challenge message which doesn't quote her current challenge
+value.  Now only eavesdroppers can force her to perform expensive
+computations.
+
+Indeed, one need not quote the entire challenge $R'$: it suffices to send
+some short hard-to-guess hash of it, maybe just the bottom 128 bits or so.
+
+This can't reduce security.  Consider any adversary attacking this protocol
+variant.  We can construct an adversary which attacks the original protocol
+just as efficiently.  The new adversary attaches fake $R'$ values to
+challenges output by other parties, and strips them off on delivery,
+discarding messages with incorrect $R'$ values.
+
+There's another denial-of-service attack against the Wrestlers protocol.  
+
+\subsubsection{Key confirmation}
+Consider an application which uses the Wrestlers protocol to re-exchange keys
+periodically.  The application can be willing to \emph{receive} incoming
+messages using the new key as soon as the key exchange completes
+successfully; however, it should refrain from \emph{sending} messages under
+the new key until it knows that its partner has also completed.  The partner
+may not have received the final response message, and therefore be unwilling
+to accept a new key; it will therefore (presumably) reject incoming messages
+under this new key.
+
+While key confirmation is unnecessary for \emph{security}, it has
+\emph{practical} value, since it solves the above problem.  If the
+application sends a \cookie{switch} message when it `completes', it can
+signal its partner that it is indeed ready to accept messages under the new
+key.  The \cookie{switch} message can be as simple as $(\cookie{switch},
+E_{K_0}(\cookie{switch}))$.
+
+\subsubsection{Unreliable transports}
+The Internet UDP \cite{RFC768} is a simple, unreliable protocol for
+transmitting datagrams.  However, it's very efficient, and rather attractive
+as a transport for datagram-based applications such as virtual private
+networks (VPNs).
+
+
+
+\subsubsection{Key reuse}
+
+
+%%%--------------------------------------------------------------------------
+
+\section{Acknowledgements}
+
+The Wrestlers Protocol is named after the Wrestlers pub in Cambridge where
+Clive Jones and I worked out the initial design.
+
+%%%--------------------------------------------------------------------------
+
+\bibliography{mdw-crypto,cryptography2000,cryptography,rfc}
+
+%%%--------------------------------------------------------------------------
+
+\appendix
+\section{Proofs}
+
+\subsection{Proof of theorem~\ref{thm:sk}}
+\label{sec:sk-proof}
+
+Before we embark on the proof proper, let us settle on some notation.  Let
+$P_i$ be a party.  Then we write $x_i$ for $P_i$'s private key and $X_i = x_i
+P$ is $P_i$'s public key.  Let $S = (P_i, P_j, s)$ be a session.  We write
+$r_S$ for the random value chosen at the start of the session, and $R_S$,
+$c_S$ etc.\ are the corresponding derived values in that session.
+
+
+The proof uses a sequence of games.  For each game~$\G{i}$, let $V_i$ be the
+event that some pair of unexposed, matching sessions both complete but output
+different keys, and let $W_i$ be the event that the adversary's final output
+equals the game's hidden bit~$b^*$.  To save on repetition, let us write
+\[ \diff{i}{j} = \max(|\Pr[V_i] - \Pr[V_j]|, |\Pr[W_i] - \Pr[W_j]|). \]
+Obviously,
+\[ \diff{i}{j} \le \sum_{i\le k<j} \diff{k}{k + 1}. \]
+
+Here's a quick overview of the games we use.
+\begin{itemize}
+\item $\G0$ is the original SK-security game.
+\item In $\G1$, we abort the game unless all parties' public keys are
+  distinct.  Since keys are generated at random, parties are unlikely to be
+  given the same key by accident.
+\item In $\G2$, we change the way sessions respond to challenge messages, by
+  using the extractor to fake up answers to most challenges.  Since the
+  extractor is good, the adversary is unlikely to notice.
+\item In $\G3$, we abort the game if the adversary ever queries $H_K(\cdot)$
+  on the Diffie-Hellman secret $r_S r_T P$ shared between two unexposed
+  matching sessions.  We show that this is unlikely to happen if the
+  Diffie-Hellman problem is hard.
+\item In $\G4$, we abort the game if any unexposed session \emph{accepts} a
+  response message which wasn't sent by a matching session.
+\end{itemize}
+Finally, we show that the adversary has no advantage in $\G4$.  The theorem
+follows.
+
+For ease of comprehension, we postpone the detailed proofs of some of the
+steps until after we conclude the main proof.
+
+Let $A$ be a given adversary which runs in time~$t$, creates at most~$q_S$
+sessions, delivers at most~$q_M$ messages, and makes at most~$q_I$ queries to
+its $H_I(\cdot, \cdot, \cdot, \cdot)$ oracle and at most~$q_K$ queries to its
+$H_K(\cdot)$ oracle.  Let $\G0$ be the original SK-security game of
+definition~\ref{def:sk}, played with adversary~$A$.
+
+Game~$\G1$ is the same as game~$\G0$ except, if the initialization function
+reports two parties as having the same public key (i.e., we have $X_i \ne
+X_j$ where $0 \le i < j < n$), we stop the game immediately and without
+crediting the adversary with a win.  This only happens when the corresponding
+private keys are equal, i.e., $x_i = x_j$, and since the initialization
+function chooses private keys uniformly at random, this happens with
+probability at most $\binom{n}{2}/|G|$.  Since if this doesn't happen, the
+game is identical to $\G0$, we can apply lemma~\ref{lem:shoup}, and see that
+\begin{equation}
+  \label{eq:sk-g0-g1}
+  \diff{0}{1} \le \frac{1}{|G|} \binom{n}{2} = \frac{n (n - 1)}{2 |G|}.
+\end{equation}
+In game~$\G1$ and onwards, we can assume that public keys for distinct
+parties are themselves distinct.
+
+Game~$\G2$ is the same as game~$\G1$, except that we change the way that we
+make parties respond to \cookie{challenge} messages $(\cookie{challenge}, R,
+c)$.  Specifically, suppose that $S = (P_i, P_j, s)$ is a session.
+\begin{itemize}
+\item Suppose $T = (P_j, P_i, s)$ is the matching session of $S$.  The game
+  proceeds as before if $(R, c) = (R_T, c_T)$ is the challenge issued by $T$.
+\item Otherwise, we run the extractor $T_\Wident$ on the adversary's history
+  so far of oracle queries $H_I(X_i, s, R, \cdot)$ to determine a pair $(r,
+  Y)$.  If $r = \bot$ then we discard the message.  Otherwise, we add $R$ to
+  the list~$C$, and return a fake response to the adversary by computing $K =
+  H_K(r R_S)$ and handing the adversary $(\cookie{response}, R_S, E_K(Y))$.
+\end{itemize}
+The following lemma shows how this affects the adversary's probabilities of
+winning.
+\begin{lemma}
+  \label{lem:sk-g1-g2}
+  \begin{equation}
+    \label{eq:sk-g1-g2}
+    \diff{1}{2} \le \frac{q_M}{2^{\ell_I}}.
+  \end{equation}
+\end{lemma}
+
+Let us say that a session $S = (P_i, P_j, s)$ is \emph{ripe} if
+\begin{itemize}
+\item there is a matching session $T = (P_j, P_i, s)$, and
+\item $S$ is unexposed.
+\end{itemize}
+Suppose that $S$ is a ripe session, and that it has a matching session~$T$:
+let $Z_S = Z_T = r_S r_T P$.
+
+Game~$\G3$ is the same as $\G2$, except that the game is immediately aborted
+if ever the adversary queries its random oracle $H_K(\cdot)$ at a value $Z_S$
+for any ripe session~$S$.  The following lemma shows how this affects the
+adversary's probabilities of winning.
+\begin{lemma}
+  \label{lem:sk-g2-g3}
+  For some $t' = t + O(n) + O(q_S) + O(q_M q_I) + O(q_K)$ not much
+  larger than $t$ we have
+  \begin{equation}
+    \label{eq:sk-g2-g3}
+    \diff{2}{3} \le q_S \InSec{mcdh}(G; t', q_K).
+  \end{equation}
+\end{lemma}
+
+Game~$\G4$ is the same as $\G3$ except that the game is immediately aborted
+if ever the adversary sends a response message to a ripe session~$S$ which
+wasn't output by its matching session as a response to $S$'s challenge, with
+the result that $S$ completes.
+
+Let's make this more precise.  Let $U$ and $V$ be a pair of matching
+sessions.  Let $C_U = (\cookie{challenge}, R_U, c_U$ be the challenge message
+sent by $U$.  Let $M_T$ be the set of messages which $T$ has sent upon
+delivery of $C_U$.  Then, in $\G4$, we abort the game if, for any pair $S$
+and~$T$ of matching, unexposed sessions, $S$ has completed as a result of
+being sent a message $\mu \notin M_T$.  We have the following lemma.
+\begin{lemma}
+  \label{lem:sk-g3-g4}
+  \begin{equation}
+    \label{eq:sk-g3-g4}
+    \diff{3}{4} \le q_S \bigl( \InSec{ind-cca}(\E; t', q_M, q_M) +
+                         n \cdot \InSec{mcdh}(G; t', q_M + q_I) \bigr)
+  \end{equation}
+\end{lemma}
+
+Finally, let us consider the state we're in with $\G4$.
+\begin{itemize}
+\item No ripe session completes except as a result the adversary faithfully
+  delivering messages between it and its matching session.
+\item The adversary never queries $Z_S$ for any ripe session~$S$.  If we set
+  $K_S = (K_{S, 0}, K_{S, 1}) = H_K(Z_S)$, then $K_{S, 1}$ is the key output
+  by $S$ when it completes.
+\item If $S$ and $T$ are matching ripe sessions, then $K_S = K_T$, since $Z_S
+  = r_S R_T = r_T R_S = Z_T$.
+\item For any ripe session~$S$, $K_{S, 1}$ is uniformly distributed in
+  $\Bin^\kappa$ and independent of the adversary's view.
+\item If $S = (P_i, P_j, s)$ and $T = (P_j, P_i, s)$ are matching ripe
+  sessions, then $Z_S$ depends only $r_S$ and $r_T$.  Hence, once $S$ and~$T$
+  complete, and erase their states, $Z_S$ is independent of everything except
+  the messages sent between the two sessions.  In particular, $Z_S$ is
+  independent of the long-term secrets $x_i$ and~$x_j$, so if either player
+  is later corrupted, the key $K_{S, 1}$ remains independent of the
+  adversary's view.
+\item Hence, the keys output by unexposed sessions are indistinguishable from
+  freshly-generated random strings, and remain so indefinitely.
+\end{itemize}
+We conclude that, for any adversary $A$,
+\begin{equation}
+  \label{eq:sk-g4}
+  \Pr[V_4] = 0 \qquad \text{and} \qquad \Pr[W_4] = \frac{1}{2}.
+\end{equation}
+Putting equations~\ref{eq:sk-g0-g1}--\ref{eq:sk-g4} together, we find
+\fixme{format prettily}
+\begin{spliteqn}
+  \Adv{sk}{\Wident^{G, \E}}(A) \le \\
+     q_S \bigl( \InSec{mcdh}(G; t', q_K) +
+                n \cdot \InSec{mcdh}(G; t', q_M + q_I) +
+                \InSec{ind-cca}(\E; t', q_M, q_M) \bigr) + {}\\
+     \frac{n (n - 1)}{|G|} +
+     \frac{2 q_M}{2^{\ell_I}}.
+\end{spliteqn}
+The theorem follows, since $A$ was chosen arbitrarily.
+
+
+\begin{proof}[Proof of lemma~\ref{lem:sk-g1-g2}]
+  The two games $\G1$ and~$\G2$ differ only in whether they accept or reject
+  particular challenge messages $(\cookie{challenge}, R, c)$.
+
+  We claim firstly that no message is \emph{accepted} by $\G2$ which would
+  have been rejected by $\G1$.  To prove the claim, it is sufficient to note
+  that the extractor's output, if not $\bot$, is always correct, and hence if
+  $\G2$ accepts a message then $\G1$ would have done so too.
+
+  Since $\G2$ also behaves identically when the adversary submits to~$S$ the
+  challenge from the matching session~$T$, we have nothing to prove in this
+  case.  Let $F$ be the event that the adversary submits a message
+  $(\cookie{challenge}, R, c)$ to a session~$S$ which $S$ would have accepted
+  in $\G1$ but would be rejected by the new rule in~$\G2$.  By
+  lemma~\ref{lem:shoup} we have $\diff{1}{2} \le \Pr[F]$.  To prove the
+  current lemma, therefore, we must show that $\Pr[F] \le q_M/2^{\ell_I}$.
+
+  Rather than consider individual challenge messages, we consider
+  \emph{classes} of messages.  We shall refer to a quadruple~$\Cid = (i, j,
+  s, R)$ as a \emph{class-id}, and define some useful functions:
+  \begin{itemize}
+  \item the class's \emph{session} $\Csession(\Cid) = (P_i, P_j, s)$;
+  \item the class's \emph{index} $\Cindex(\Cid)$ is $r \in I$ where $R = r
+    P$, which is well-defined by lemma~\ref{lem:unique-dl};
+  \item the class's \emph{query} $\Cquery(\Cid) = (X_j, s, R, x_i R)$;
+  \item the class's \emph{hash} $\Chash(\Cid) = H_I(\Cquery(\Cid)) = H_I(X_j,
+    s, R, x_i R)$;
+  \item the class's \emph{check-value} $\Ccheck(\Cid) = \Chash(\Cid) \xor
+    \Cindex(\Cid)$;
+  \item the class's \emph{check-set} $\Ccheckset(\Cid)$ is the set of
+    check-values $c$ such that a message $(\cookie{challenge}, R, c)$ was
+    sent to session $S = (P_i, P_j, s)$; and
+  \item the class's \emph{count} $\Ccount(\Cid) = |\Ccheckset(\Cid)|$.
+  \end{itemize}
+
+  Consider any class-id~$\Cid = (i, j, s, R)$.  A natural question which
+  arises is: which participants have issued $\Cid$'s query, i.e., queried
+  $H_I$ at $\Cquery(\Cid)$?
+
+  We can characterise the $H_I(\cdot, \cdot, \cdot, \cdot)$ queries of a
+  session $U = (P_{i'}, P_{j'}, s')$ as follows:
+  \begin{itemize}
+  \item computing the check-value for the challenge $R_U$ by querying
+    $H_I(X_{i'}, s', R_U, r_U X_{j'})$, and
+  \item checking an incoming challenge~$R'$ by querying $H_I(X_{j'}, s', R',
+    x_{i'} R')$.
+  \end{itemize}
+  The class~$\Cid$'s query $\Cquery(\Cid)$ is $U$'s check-value query if
+  \[ (j, i, s, R) = (i', j', s', R_U) \]
+  i.e., $U$ is the matching session of $\Csession(\Cid)$, and moreover $R =
+  R_U$ is the challenge value issued by $U$.  For any $c \in
+  \Ccheckset(\Cid)$, if $c = \Ccheck(\Cid)$ then $(\cookie{challenge}, R, c)$
+  is precisely the challenge message issued by~$U$ to $\Csession(\Cid)$; the
+  rules for handling this message didn't change.  However, if $c \ne
+  \Ccheck(\Cid)$ then the message would have been rejected in $\G1$, and we
+  have already shown that $\G2$ continues to reject all messages rejected by
+  $\G1$.
+
+  Let us say that a class-id~$\Cid = (i, j, s, R)$ is \emph{bad} if
+  \begin{enumerate}
+  \item the value $R$ is not the challenge issued by $\Csession(\Cid)$'s
+    matching session, and
+  \item the adversary has not issued $\Cid$'s query $\Cquery(\Cid)$,
+    \emph{but}
+  \item $\Ccheck(\Cid) \in \Ccheckset(\Cid)$, so one of the check-values
+    submitted to $S$ was actually correct.
+  \end{enumerate}
+  We claim that our extractor will work perfectly unless some class-id is
+  bad.  Certainly, if $R$ was issued by the matching session, there is
+  nothing to prove; if the adversary has issued the relevant query then the
+  extractor will recover $\Cindex(\Cid)$ just fine; and if $\Ccheck(\Cid)
+  \notin \Ccheckset(\Cid)$ then all messages in the class would have been
+  rejected by $\G1$ anyway.
+
+  Let $B(\Cid)$ be the event that the class~$\Cid$ is bad.  We claim that
+  \[ \Pr[B(\Cid)] \le \frac{\Ccount(\Cid)}{2^{\ell_I}}. \]
+  The present lemma follows, since
+  \[ \diff{1}{2}
+     \le \Pr[F]
+     \le \sum_\Cid \Pr[B(\Cid)]
+     \le \sum_\Cid \frac{\Ccount(\Cid)}{2^{\ell_I}}
+     =   \frac{1}{2^{\ell_I}} \sum_\Cid \Ccount(\Cid)
+     \le \frac{q_M}{2^{\ell_I}}
+  \]
+  as required.  
+
+  Now observe that, in $\G2$, sessions don't actually check incoming
+  challenges in this way any more -- instead we run the extractor.  So, to
+  prove the claim, we consider a class~$\Cid$ where properties~1 and~2 above
+  hold.  The correct hash $\Chash(\Cid)$ is then independent of the rest of
+  the game, so the probability that $\Ccheck(\Cid) \in \Ccheckset(\Cid)$ is
+  precisely $\Ccount(\Cid)/2^{\ell_I}$ as required.
+
+  This completes the proof the lemma.
+\end{proof}
+
+\begin{proof}[Proof of lemma~\ref{lem:sk-g2-g3}]
+  Let $F$ be the event that the adversary makes a query $H_K(Z_S)$ for some
+  ripe session~$S$.  Since $\G3$ proceeds exactly as $\G2$ did unless $F_2$
+  occurs, we apply lemma~\ref{lem:shoup}, which tells us that $\diff{2}{3}
+  \le \Pr[F_2]$.  We must therefore bound this probability.
+
+  To do this, we consider a new game~$\G3'$, which is the same as $\G3$,
+  except that, at the start of the game, we choose a random number $k \inr
+  \Nupto{q_S}$.  For $0 \le i < q_S$, let $S_i$ be the $i$th session created
+  by the adversary.  We define $F'$ to be the event that the adversary
+  queries $H_K(Z_{S_k})$ when $S_k$ is ripe.
+
+  The lemma now follows from these two claims.
+
+  \begin{claim}
+    $\Pr[F] \le q_S \Pr[F']$.
+  \end{claim}
+  To see this, for any session~$S$, let $F_S$ be the event that the adversary
+  queries~$H_K(Z_S)$ when $S$ is ripe.  Then
+  \[ \Pr[F] \le \sum_{0\le i<q_S} \Pr[F_{S_i}]. \]
+  Hence,
+  \[ \Pr[F'] = \Pr[F_{S_k}] = \sum_{0\le i<q_S} \Pr[F_{S_i}] \Pr[k = i]
+             = \frac{1}{q_S} \sum_{0\le i<q_S} \Pr[F_{S_i}]
+             \ge \frac{\Pr[F]}{q_S}
+  \]
+  proving the claim.
+
+  \begin{claim}
+    For some $t' = t + O(n) + O(q_S q_M) + O(q_I) + O(q_K)$, we have
+    $\Pr[F'] \le \InSec{mcdh}(G; t', q_K).$
+  \end{claim}
+  To prove this claim, we construct an adversary~$B$ which solves the MCDH
+  problem in~$G$.  The adversary works as follows.
+  \begin{enumerate}
+  \item It is given a pair $(R^*, S^*) = (r^* P, s^* P)$ of group elements;
+    its objective is to make a verification-oracle query $V(Z^*)$ where $Z^*
+    = r^* s^* P$.
+  \item It sets up a simulation of the game~$\G3'$, by running the
+    $\id{init}$ function, and simulating all of the parties.  In particular,
+    it chooses a random~$k \in \Nupto{q_S}$.
+  \item It sets up accurate simulations of the random oracles $H_K(\cdot)$
+    and $H_I(\cdot, \cdot, \cdot, \cdot)$, which choose random outputs for
+    new, fresh inputs.  However, whenever $A$ queries $H_K(\cdot)$ on a group
+    element $Z$, $B$ also queries $V(Z)$.
+  \item It runs $A$ in its simulated game.  It responds to all of $A$'s
+    instructions faithfully, until the $k$th session-creation.
+  \item When creating the $k$th session $S = S_k = (P_i, P_j, s)$, $B$ has
+    party~$P_i$ choose $R^*$ as its challenge, rather than choosing $r_S$ and
+    setting $R_S = r_S P$.  Because it simulates all the parties, $B$ can
+    compute $Y_S = x_j R$, which is still correct.
+  \item If $A$ requests the creation of a matching session $T = (P_j, P_i,
+    s)$ then $B$ has party~$P_j$ choose $S^*$ as its challenge.  Again, $B$
+    computes $Y_T = x_i S^*$.
+  \item If $A$ ever corrupts the parties $P_i$ or $P_j$, or reveals the
+    session state of $S$ or $T$ then $B$ stops the simulation abruptly and
+    halts.
+  \end{enumerate}
+  Adversary $B$'s running time is $t' = t + O(n) + O(q_S q_M) + O(q_I) +
+  O(q_K)$, and $B$ makes at most $q_K$ queries to $V(\cdot)$; we therefore
+  have
+  \[ \Pr[F'] \le \Succ{mcdh}{G}(B) \le \InSec{mcdh}(G; t', q_K) \]
+  as required.
+\end{proof}
+
+\begin{proof}[Proof of lemma~\ref{lem:sk-g3-g4}]
+  Let $F_4$ be the event under which we abort the game~$\G4$.  Clearly, if
+  $F$ doesn't occur, games $\G3$ and $\G4$ proceed identically, so we can
+  apply lemma~\ref{lem:shoup} to see that $\diff{3}{4} \le \Pr[F_4]$.
+  Bounding $\Pr[F_4]$, however, is somewhat complicated.  We use a further
+  sequence of games.
+
+  Firstly, let $\G5$ be like $\G4$ with the exception that we choose, at
+  random, an integer~$k \inr \Nupto{q_S}$.  As we did in the proof for
+  lemma~\ref{lem:sk-g3-g4}, let $S_i$ be the $i$th session created by the
+  adversary.  For each session~$S_i$, let $T_i$ be its matching session, if
+  there is one.  We define $F_5$ to be the event that
+  \begin{itemize}
+  \item $S_k$ completes immediately following delivery of a message $\mu
+    \notin M_{T_k}$, and
+  \item $S_k$ was ripe at this point.
+  \end{itemize}
+  For games~$\G{i}$, for $i > 5$, we define the event $F_i$ to be the event
+  corresponding to $F_5$ in $\G{i}$.  Note that if $S_k$ \emph{is} sent a
+  message in $M_{T_k}$ then $S_k$ immediately completes.
+
+  \begin{claim}
+    $\Pr[F_4] \le \Pr[F_5]/q_S$.
+  \end{claim}
+  This claim is proven exactly as we did for claim~1 of
+  lemma~\ref{lem:sk-g2-g3}.
+
+  Let~$\G6$ be the same as $\G5$ except that we change the encrypted
+  responses of session~$S_k$ and its matching session~$T_k$.  Let $K^* =
+  (K_0^*, K_1^*) = H_K(Z_S)$.  Then, rather than sending $(\cookie{response},
+  R_S, E_{K_0^*}(Y_T))$, session~$S$ sends $(\cookie{response}, R_S,
+  E_{K_0^*}(1^{\ell_G}))$.
+  \begin{claim}
+    $|\Pr[F_6] - \Pr[F_5]| \le \InSec{ind-cca}(\E; t', q_M, q_M).$
+  \end{claim}
+  To prove this claim, we construct an adversary~$B$ which attacks the
+  IND-CCA security of our encryption scheme $\E$.  The adversary~$B$ works as
+  follows.
+  \begin{enumerate}
+  \item It is given no input, but a pair of oracles $E(\cdot, \cdot)$ and
+    $D(\cdot)$; the former encrypts either the left or right input, according
+    to a hidden bit, and the latter decrypts ciphertexts other than those
+    returned by $E(\cdot, \cdot)$.  Its goal is to guess the hidden bit.
+  \item It sets up a simulation of the game~$\G5$, by running the $\id{init}$
+    function, and simulating all of the parties.  In particular, it chooses a
+    random $k \in \Nupto{q_S}$.
+  \item It sets up accurate simulations of the random oracles $H_K(\cdot)$
+    and $H_I(\cdot, \cdot, \cdot, \cdot)$.
+  \item It runs $A$ in its simulated game.  It responds to all of $A$'s
+    instructions faithfully, except for the matching sessions $S_k$ and
+    $T_k$.  Let $S = S_k = (P_i, P_j, s)$, and $T = T_k = (P_j, P_i, s)$.
+  \item Suppose $T$ is sent the message $C_S = (\cookie{challenge}, R_S,
+    c_S)$.  Rather than computing $K^* = H_K(r_T R_S)$ and performing the
+    encryption properly, $B$ queries its left-or-right encryption oracle
+    $E(\cdot, \cdot)$ on $E(1^{\ell_G}, x_j R_S)$, and sends the resulting
+    ciphertext~$\chi$ back to~$S$ as part of a message $(\cookie{response},
+    R_T, \chi)$.  The set $M_T$ is precisely the set of messages constructed
+    in this fashion.  (Recall that challenge messages other than $C_S$ aren't
+    actually delivered to $T$, since we simulate the responses using the
+    extractor, as of $\G2$.)
+  \item Suppose $S$ is sent a message $M = (\cookie{response}, R_T, \chi) \in
+    M_T$.  We immediately stop the simulation, and $B$ returns $0$.
+  \item Suppose, instead, that $S$ is sent some message $M' =
+    (\cookie{response}, R, \chi) \notin M_T$.  There are two cases to
+    consider.  If $R = R_T$ then we must have $\chi$ distinct from the
+    ciphertexts returned by the $E(\cdot, \cdot)$ oracle, so we can invoke
+    the decryption oracle $D(\cdot)$ on $\chi$ to obtain a response $Y$.
+    Alternatively, if $R \ne R_T$, we can compute the key $K = (K_0, K_1) =
+    H_K(r_S R)$, and recover $Y = D_{K_0}(\chi)$.  In either case, if $Y =
+    r_S X_j)$ then $S$ would complete at this point: $B$ stops the simulation
+    and returns $1$.
+  \item If $A$ exposes $S$ (by corrupting $P_i$ or~$P_j$, or revealing $S$ or
+    $T$) then we stop the simulation and $B$ returns $0$.
+  \item Finally, if the game stops, either because $A$ halts, or because of
+    one of the special rules introduced in earlier games, $B$ returns $0$.
+  \end{enumerate}
+  It is clear that $B$'s oracle queries are acceptable, since $|x_j R_S| =
+  \ell_G$ by definition, and $B$ never queries $D(\cdot)$ on a ciphertext
+  returned by its encryption oracle.  By the rules of~$\G3$, we know that the
+  game stops immediately if $A$ ever queries $Z_S$, so the key $K^*$ is
+  independent of everything in $A$'s view except the ciphertexts $\chi$
+  output by $S$ and $T$.  Therefore, if the hidden bit of the IND-CCA game is
+  $1$, $B$ accurately simulates $\G5$, whereas if the bit is $0$ then $B$
+  accurately simulates $\G6$.  Finally, we issue no more that $q_M$
+  encryption or decryption queries.  Therefore,
+  \[ \Adv{ind-cca}{\E}(B) = \Pr[F_5] - \Pr[F_6]
+     \le \InSec{ind-cca}(\E; t', q_M, q_M). \]
+  We construct the adversary~$\bar{B}$ which is the same as $B$ above, except
+  that $\bar{B}$ returns $0$ whenever $B$ returns~$1$, and \emph{vice versa}.
+  Clearly
+  \[ \Adv{ind-cca}{\E}(\bar{B})
+     = (1 - \Pr[F_5]) - (1 - \Pr[F_6])
+     = \Pr[F_6] - \Pr[F_5]
+     \le \InSec{ind-cca}(\E; t', q_M, q_M).
+  \]
+  This proves the claim.
+
+  Let $\G7$ be the same as $\G6$, except that at the start of the game we
+  choose a random $m \in \Nupto{n}$, and when the adversary creates the
+  session $S = S_k = (P_i, P_j, s)$, we abort the game unless $j = m$.
+  Clearly we have $\Pr[F_6] = n \Pr[F_7]$.
+  
+  Finally, we can explicitly bound $F_6$.  In $\G6$, the adversary's view is
+  independent of the correct response $Y_S = r_S X_S = x_j R_S$ to $S$'s
+  challenge.  Therefore, if $A$ manages to send any message $\mu \notin M_T$
+  which causes $S$ to complete, then it has impersonated~$P_j$.
+  \begin{claim}
+    $\Pr[F_7] \le \InSec{mcdh}(G; t', q_M + q_I)$.
+  \end{claim}
+  The present lemma follows from this and the previous claims.
+
+  To prove the claim formally, we construct an adversary~$B'$, which behaves
+  as follows.
+  \begin{enumerate}
+  \item It is given as input a public key $X^*$ and a single challenge $(R^*,
+    c^*)$, a random oracle $H^*_I(\cdot, \cdot)$, and an oracle $V(\cdot,
+    \cdot)$, which verifies responses $(R, Y)$.  Its goal is to invoke
+    $V(\cdot, \cdot)$ with a correct response to the challenge.
+  \item It chooses a random $k \in \Nupto{q_S}$ and $m \in \Nupto{n}$. It
+    sets up a simulation of the game~$\G7$, by running the $\id{init}$
+    function, and simulating all of the parties, except that it gives party
+    $P_m$ the public key $X^*$.  This makes no difference, since $P_m$
+    doesn't actually need to give any `honest' responses because of the
+    change we made in $\G6$.
+  \item It sets up accurate simulations of the random oracles $H_K(\cdot)$
+    and $H_I(\cdot, \cdot, \cdot, \cdot)$, with one exception -- see below.
+  \item It runs $A$ in its simulated game.  It responds to all of $A$'s
+    instructions faithfully, except for the session $S_k$.  Let $S = S_k =
+    (P_i, P_j, s)$, and let $T = T_k = (P_j, P_i, s)$ be its matching
+    session.
+  \item When session~$S$ is created, $B'$ checks that $j = m$, and if not
+    stops the simulation and halts.  Otherwise, $B'$ invokes its oracle~$C()$
+    to obtain a pair $(R, c)$.  Session~$S$ sends $C_S = (\cookie{challenge},
+    R, c)$ as its challenge to~$T$.
+  \item When $A$ makes a query $H_I(X^*, s, R, Y)$, $B$ answers it by
+    querying its \emph{own} random oracle $H^*_I(R, Y)$.
+  \item When $S$ receives a message $(\cookie{response}, R, \chi)$, we
+    compute $(K_0, K_1) = r_S R$, and $Y = D_{K_0}(\chi)$.  If $Y \ne \bot$
+    then $B'$ calls $V(R, Y)$.
+  \item If $A$ reveals $S$ or corrupts $P_i$ or $P_j$ then $B'$ stops the
+    simulation immediately and halts.
+  \end{enumerate}
+  Clearly $B'$ succeeds whenever $F_7$ occurs; hence we can apply
+  theorem~\ref{thm:wident-sound}.  The claim follows.
+\end{proof}
+
+
+\subsection{Proof of theorem~\ref{thm:sk2}}
+\label{sec:sk2-proof}
+
+The proof is almost identical to the proof of theorem~\ref{thm:sk}, in
+appendix~\ref{sec:sk-proof}.  Unfortunately a black-box reduction doesn't
+seem possible.  
+
+We use the games and notation of section~\ref{sec:sk-proof}.
+
+The change to the check-value calculation doesn't affect key-generation at
+all, so the transition to $\G1$ goes through as before.
+
+The transition from $\G1$ to $\G2$ -- answering challenges using the
+extractor -- needs a little care.  Let $S = (P_i, P_j, s)$ be a session, and
+consider an incoming message $(\cookie{challenge}, R, c)$.
+\begin{itemize}
+\item If $T = (P_j, P_i, s)$ is the matching session to $S$, and $R = R_T$ is
+  the public challenge value of $T$, and $c = r_T \xor H_I(R_S, X_j, s, R_T,
+  r_T X_i)$ is the check-value output by $T$ when it received
+  $(\cookie{pre-challenge}, R_S)$ as input, then $S$ replies as it did in
+  $\G1$.
+\item If the challenge message is any other message, then we use the
+  extractor.
+\end{itemize}
+As in lemma~\ref{lem:sk-g1-g2}, we examine which sessions could have queried
+$H_I(R_S, X_j, s, R, x_i R)$, and for the same reasons conclude that only the
+matching session would have done this, and only in response to the
+pre-challenge $R_S$.  It follows that $\diff{1}{2} \le q_M/2^{\ell_I}$ as
+before.
+
+The remaining game steps go through unchanged.  In particular, we conclude
+that a ripe session will only complete if the adversary has transmitted
+messages from its matching session correctly, and the session key is
+independent of the adversary's view.  The theorem follows.
+
+\end{document}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: 
diff --git a/wrshortsl.tex b/wrshortsl.tex
new file mode 100644
index 0000000..ad79cb3
--- /dev/null
+++ b/wrshortsl.tex
@@ -0,0 +1,6 @@
+\let\short\relax
+\input wrslides
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "wrslides"
+%%% End: 
diff --git a/wrslide.tex b/wrslide.tex
new file mode 100644
index 0000000..96bbe36
--- /dev/null
+++ b/wrslide.tex
@@ -0,0 +1,346 @@
+\xcalways\section{The Wrestlers Protocol}\x
+
+\xcalways\subsection{Identification using Diffie-Hellman}\x
+
+\begin{slide}
+  \resetseq
+  \head{Identification using Diffie-Hellman \seq: Properties}
+  \topic{properties}
+
+  \begin{itemize}
+  \item Simple -- easy to remember, analyse and implement
+  \item Practical -- two scalar multiplications for each party
+  \item Secure -- under Computational Diffie-Hellman assumption
+  \item Zero-knowledge -- statistical ZK
+  \item Proofs in random oracle model -- but without `programming'
+  \end{itemize}
+\end{slide}
+
+\begin{slide}
+  \head{Identification using Diffie-Hellman \seq: Basic setting}
+  \topic{setting}
+
+  \begin{itemize}
+  \item Cyclic group $(G, +)$
+  \item $|G| = q$ is prime
+  \item $P$ generates $G$
+  \item Alice's private key is $a \inr \Nupto{q}$
+  \item Alice's public key is $A = a P$
+  \item Assume computational Diffie-Hellman problem hard in $G$
+  \end{itemize}
+\end{slide}
+
+\begin{slide}
+  \head{Identification using Diffie-Hellman \seq: Na\"\i ve attempt}
+  \topic{protocol design}
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$)
+    \\[\medskipamount]
+    & $r \getsr \Nupto{q}$; \\
+    & $R \gets r P$; \\
+    \\
+    \\
+    \\
+    \send{<-}{R}
+    $Y \gets a R$; \\
+    \\
+    \\
+    \\
+    \send{->}{Y}
+    & \textbf{Check} $Y = r A$
+  \end{protocol}
+\end{slide}
+
+\begin{slide}
+  \head{Identification using Diffie-Hellman \seq: Fix it with a hash}
+  \protocolskip0pt
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$)
+    \\[\medskipamount]
+    & $r \getsr \Nupto{q}$; \\
+    & $R \gets r P$; \\
+    & $Y \gets r A$; \\
+    & \diff $h \gets H(\cookie{check}, R, Y)$; \\
+    & \\
+    \send{<-}{(R, \hbox{\diff $h$})}
+    $Y \gets a R$; \\
+    \\
+    \\
+    \diff \textbf{Check} $h = H(\cookie{check}, R, Y)$ \\
+    \send{->}{Y}
+    & \textbf{Check} $Y$
+  \end{protocol}
+  \dots but there are still small-subgroup attacks
+\end{slide}
+
+\begin{slide}
+  \head{Identification using Diffie-Hellman \seq: Stinson-Wu [SW06]}
+  \protocolskip0pt
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$)
+    \\[\medskipamount]
+    & $r \getsr \Nupto{q}$; \\
+    & $R \gets r P$; \\
+    & $Y \gets r A$; \\
+    & $h \gets H(\cookie{check}, R, Y)$; \\
+    & \\
+    \send{<-}{(R, h)}
+    $Y \gets a R$; \\
+    \\
+    \diff \textbf{Check} $q R = 0$; \\
+    \textbf{Check} $h = H(\cookie{check}, R, Y)$ \\
+    \send{->}{Y}
+    & \textbf{Check} $Y$
+  \end{protocol}
+  \dots and apply the Knowledge of Exponent assumption
+\end{slide}
+
+\begin{slide}
+  \head{Identification using Diffie-Hellman \seq: The Wrestlers Protocol
+  $\Wident$}
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$)
+    \\[\medskipamount]
+    & $r \getsr \Nupto{q}$; \\
+    & $R \gets r P$; \\
+    & $Y \gets r A$; \\
+    & $h \gets H(\cookie{check}, R, Y)$; \\
+    & \diff $c \gets h \xor r$; \\
+    \send{<-}{(R, \hbox{\diff $c$})}
+    $Y \gets a R$; \\
+    $h \gets H(\cookie{check}, R, Y)$; \\
+    \diff $r \gets c \xor h$; \\
+    \diff \textbf{Check} $R = r P$ \\
+    \send{->}{Y}
+    & \textbf{Check} $Y$
+  \end{protocol}
+\end{slide}
+
+\begin{slide}
+  \head{Identification using Diffie-Hellman \seq: Identification-based
+  $\Wident$}
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $K_A = t I_A$) &
+    (Public key $I_A = H(\cookie{id}, \text{Alice})$)
+    \\[\medskipamount]
+    & $r \getsr \Nupto{q}$; \\
+    & $R \gets r P$; \\
+    & \diff $Y \gets \hat{e}(T, I_A)^r$; \\
+    & $h \gets H(\cookie{check}, R, Y)$; \\
+    & $c \gets h \xor r$; \\
+    \send{<-}{(R, c)}
+    \diff $Y \gets \hat{e}(R, K_A)$; \\
+    $h \gets H(\cookie{check}, R, Y)$; \\
+    $r \gets c \xor h$; \\
+    \textbf{Check} $R = r P$ \\
+    \send{->}{Y}
+    & \textbf{Check} $Y$
+  \end{protocol}
+  (Trusted authority's private key $t \inr \Nupto{q}$; public key $T = t P$)
+\end{slide}
+
+\xcalways\subsection{Key exchange}\x
+
+\begin{slide}
+  \resetseq
+  \head{Mutual identification \seq: Bob identifies Alice}
+  \topic{mutual identification}
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $a$, public key $A = a P$)
+    \\[\medskipamount]
+    & $r_B \getsr \Nupto{q}$; \\
+    & $R_B \gets r_B P$; \\
+    \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))}
+    \\
+    $Y_B \gets a R_B$; \\
+    \\
+    \send{->}{Y_B}
+  \end{protocol}
+\end{slide}
+    
+\begin{slide}
+  \head{Mutual identification \seq: Alice identifies Bob too}
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $a$, public key $A = a P$) &
+    \other (Private key $b$, public key $B = b P$)
+    \\[\medskipamount]
+    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
+    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
+    \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))}
+    \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))}
+    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
+    \\
+    \send{->}{Y_B}
+    \send{<-}{\other Y_A}
+  \end{protocol}
+\end{slide}
+    
+\begin{slide}
+  \head{Mutual identification \seq: Key exchange?}
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $a$, public key $A = a P$) &
+    \other (Private key $b$, public key $B = b P$)
+    \\[\medskipamount]
+    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
+    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
+    \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))}
+    \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))}
+    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
+    \\
+    \send{->}{Y_B}
+    \send{<-}{\other Y_A}
+    \diff $Z \gets r_A R_B$; & \diff $Z \gets r_B R_A$;
+  \end{protocol}
+  \bigskip
+  Unfortunately it's not secure.
+\end{slide}
+
+\begin{slide}
+  \resetseq
+  \head{Key exchange \seq: Properties}
+  \topic{properties}
+
+  \begin{itemize}
+  \item Simple -- symmetrical; based on mutual identification
+  \item Practical -- three, four or five flows; four multiplications by each
+    party
+  \item Secure -- provides SK-security in model of [CK01]
+  \item Deniable -- simulator can produce convincing transcripts
+  \item Proofs in random oracle model -- again without `programming'
+  \end{itemize}
+\end{slide}
+
+\begin{slide}
+  \head{Key exchange \seq: Setting}
+  \topic{setting}
+
+  \begin{itemize}
+  \item Cyclic group $(G, +)$
+  \item $|G| = q$ is prime
+  \item $P$ generates $G$
+  \item Alice's private key is $a \inr \Nupto{q}$; her public key is $A = a
+    P$
+  \item Bob's private key is $b \inr \Nupto{q}$; his public key is $B = b
+    P$
+  \item Symmetric IND-CCA encryption scheme $\E = (\kappa, E, D)$
+  \item Assume computational Diffie-Hellman problem hard in $G$
+  \end{itemize}
+\end{slide}
+
+\begin{slide}
+  \head{Key exchange \seq: Broken first attempt}
+  \topic{protocol design}
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $a$, public key $A = a P$) &
+    \other (Private key $b$, public key $B = b P$)
+    \\[\medskipamount]
+    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
+    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
+    \\
+    \\
+    \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))}
+    \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))}
+    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
+    $Z \gets r_A R_B$; & $Z \gets r_B R_A$; \\
+    \send{->}{(R_A, Y_B)}
+    \send{<-}{\other (R_B, Y_A)}
+    Key is $Z$ & Key is $Z$
+  \end{protocol}
+\end{slide}
+
+\begin{slide}
+  \head{Key exchange \seq: Solution -- encrypt responses}
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $a$, public key $A = a P$) &
+    \other (Private key $b$, public key $B = b P$)
+    \\[\medskipamount]
+    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
+    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
+    \\
+    \\
+    \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))}
+    \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))}
+    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
+    \diff $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; &
+    \diff $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\
+    \send{->}{(R_A, \hbox{\diff $E_{K_0}(Y_B)$})}
+    \send{<-}{\other (R_B, \hbox{\diff $E_{K_0}(Y_A)$})}
+    Key is $K_1$ & Key is $K_1$
+  \end{protocol}
+\end{slide}
+
+\begin{slide}
+  \head{Key exchange \seq: Multiple sessions}
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $a$, public key $A = a P$) &
+    \other (Private key $b$, public key $B = b P$)
+    \\[\medskipamount]
+    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
+    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
+    \\
+    \\
+    \send{<-}{(R_B, r_B \xor H(\cookie{check},
+      \hbox{\diff $B$}, \hbox{\diff $s$}, R_B, Y_B))}
+    \send{->}{\other (R_A, r_A \xor H(\cookie{check},
+      \hbox{\diff $A$}, \hbox{\diff $s$}, R_A, Y_A))}
+    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
+    $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; &
+    $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\
+    \send{->}{(R_A, E_{K_0}(Y_B))}
+    \send{<-}{\other (R_B, E_{K_0}(Y_A))}
+    Key is $K_1$ & Key is $K_1$
+  \end{protocol}
+  (Session id is $s$)
+\end{slide}
+
+\begin{slide}
+  \head{Key exchange \seq: Fully deniable variant}
+
+  \begin{protocol}
+    Alice & Bob \\
+    (Private key $a$, public key $A = a P$) &
+    \other (Private key $b$, public key $B = b P$)
+    \\[\medskipamount]
+    \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\
+    \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\
+    \send{->}{\diff R_A}
+    \send{<-}{\diff R_B}
+    \send{<-}{(R_B, r_B \xor H(\cookie{check}, B, s, \hbox{\diff $R_A$}, R_B, Y_B))}
+    \send{->}{\other (R_A, r_A \xor H(\cookie{check}, A, s, \hbox{\diff $R_B$}, R_A, Y_A))}
+    $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\
+    $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; &
+    $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\
+    \send{->}{(R_A, E_{K_0}(Y_B))}
+    \send{<-}{\other (R_B, E_{K_0}(Y_A))}
+    Key is $K_1$ & Key is $K_1$
+  \end{protocol}
+\end{slide}
+
+\endinput
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "wrslides"
+%%% End: 
diff --git a/wrslides.cls b/wrslides.cls
new file mode 100644
index 0000000..1d7913e
--- /dev/null
+++ b/wrslides.cls
@@ -0,0 +1,75 @@
+\PassOptionsToClass{a4, article}{mdwslides}
+\LoadClass{mdwslides}
+
+\newif\ifpdf
+\if0\ifx\pdfoutput\@@undefined0\else\the\expandafter\pdfoutput\fi
+  \PassOptionsToPackage{dvips}{xy}
+  \pdffalse
+\else
+  \AtBeginDocument{
+    \ifarticle\else
+    \setslidelength{\pdfpagewidth}{\paperheight}
+    \setslidelength{\pdfpageheight}{\paperwidth}
+    \pdfhorigin=1 true in
+    \pdfvorigin=1 true in
+    \fi
+  }
+  \pdftrue
+\fi
+
+
+\RequirePackage{mdwlist}
+\RequirePackage[T1]{fontenc}
+\RequirePackage{colour}
+\RequirePackage{mdwmath}
+\RequirePackage{crypto}
+\RequirePackage[all]{xy}
+\RequirePackage{tabularx}
+\RequirePackage{mathenv}
+\RequirePackage{graphicx}
+\RequirePackage[palatino, helvetica, courier, maths = cmr]{mdwfonts}
+\RequirePackage{mdwthm}
+
+\def\Nupto#1{\{0, 1, \ldots, #1 - 1\}}
+\def\Bin{\{0, 1\}}
+\let\op\star
+\let\le\leqslant
+\let\ge\geqslant
+\let\epsilon\varepsilon
+
+\def\poly{\mathop{\operator@font{poly}}}
+
+\def\description{%
+  \basedescript{%
+    \let\makelabel\textit%
+    \desclabelstyle\multilinelabel%
+    \desclabelwidth{1in}%
+  }%
+}
+
+\let\protocolstyle\small
+\newskip\protocolskip
+\protocolskip\parskip
+\def\protocol{%
+  \protocolstyle%
+  \vskip\protocolskip%
+  \begin{tabular*}{\linewidth}{@{\qquad}l@{\extracolsep{0ptplus1fil}}r@{\qquad}}}
+\def\endprotocol{\end{tabular*}}
+
+\makeatother
+\def\send#1#2{\noalign{%
+    \centerline{\xy\ar @{#1}|*+{\mathstrut#2}<.5\linewidth, 0pt>\endxy}}}
+\makeatletter
+\errorcontextlines=999
+
+\newcommand{\E}{{\mathcal{E}}}
+
+\def\Wident{\Xid{W}{ident}}
+\def\Wkw{\Xid{W}{kx}}
+
+\def\other{\colour{blue}}
+\def\diff{\colour{red}}
+
+\title{The Wrestlers Protocol}
+
+\endinput
diff --git a/wrslides.tex b/wrslides.tex
new file mode 100644
index 0000000..a444f79
--- /dev/null
+++ b/wrslides.tex
@@ -0,0 +1,32 @@
+\documentclass{wrslides}
+\ifx\short\xxundefined\else
+  \includeonly{wrslide}
+\fi
+
+\begin{document}
+
+\begin{slide}
+  \emptyslide
+  \hrule height0pt
+  \vfill
+  \centerline{\Huge\sffamily\bfseries The Wrestlers Protocol}
+  \medskip
+  \centerline{\itshape A simple, practical, secure, deniable protocol for
+    key-exchange}
+  \vskip 1in
+  \tabskip=0ptplus1fil
+  \halign to \linewidth{\tabskip=0pt\hfil\ignorespaces#\unskip\cr
+    Mark Wooding\cr
+    \texttt{mdw@distorted.org.uk}\cr}
+  \bigskip
+\end{slide}
+
+\include{background}
+\include{wrslide}
+
+\end{document}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: 
-- 
2.11.0

