X-Git-Url: https://git.distorted.org.uk/~mdw/doc/wrestlers/blobdiff_plain/d8eb72b5a1f4a69a7066a70057cc595716e0e466..HEAD:/wrestlers.tex

diff --git a/wrestlers.tex b/wrestlers.tex
index 43535d2..4705316 100644
--- a/wrestlers.tex
+++ b/wrestlers.tex
@@ -177,9 +177,9 @@
 \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.
+  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
@@ -201,7 +201,6 @@
 \fi
 
 %%%--------------------------------------------------------------------------
-
 \section{Introduction}
 
 This paper proposes protocols for \emph{identification} and
@@ -242,7 +241,7 @@ Our identification protocol has a number of desirable properties.
 \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.
+  intractability of the computational Diffie--Hellman problem.
 \end{itemize}
 
 Our key-exchange protocol also has a number of desirable
@@ -255,7 +254,7 @@ properties.
   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,
+  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.
@@ -448,7 +447,6 @@ various theorems stated here.
 \fi
 
 %%%--------------------------------------------------------------------------
-
 \section{Preliminaries}
 \label{sec:prelim}
 
@@ -461,8 +459,8 @@ various theorems stated here.
 
 \prelimsec{Miscellaneous notation}
 
-We write $\Func{D}{R}$ for the set of all functions with domain $D$ and range
-$R$.
+We write $\#S$ for the cardinality of a set $S$.  We write $\Func{D}{R}$ for
+the set of all functions with domain $D$ and range $R$.
 
 \prelimsec{Groups}
 
@@ -1307,7 +1305,6 @@ case.
 \fi
 
 %%%--------------------------------------------------------------------------
-
 \section{A zero-knowledge identification scheme}
 \label{sec:zk-ident}
 
@@ -1864,8 +1861,8 @@ 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-franklin-2003:ibe-weil-pairing} gives more detail; also
+a (very brief!) summary of cryptographic pairings.  (The Boneh--Franklin
+paper \cite{boneh-franklin-2003:ibe-weil-pairing} gives more detail; also
 \cite{menezes-2005:intro-pairing-crypto} provides a useful introduction to
 the topic.)
 
@@ -1947,11 +1944,11 @@ a challenge $(\rho, H(\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
+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
+(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,
@@ -1959,7 +1956,7 @@ subgroups, since the cofactor of such subgroups is usually small: indeed,
 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
+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
@@ -1977,7 +1974,7 @@ dishonest verifier managed to guess the correct $h = H(\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
+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.
 
@@ -2012,19 +2009,18 @@ case-analysis which would be the basis of a proof of this.
   \label{tab:wident-active}
 \end{table}
 
-An identity-based analogue of Stinson-Wu can be defined using a bilinear
+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,
+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.
 \fi
 
 %%%--------------------------------------------------------------------------
-
 \section{A simple key-exchange protocol}
 \label{sec:kx}
 
@@ -3085,7 +3081,6 @@ We offer a sketch proof of this claim in appendix~\ref{sec:sc-proof}.
 \fi
 
 %%%--------------------------------------------------------------------------
-
 \section{Conclusions}
 \label{sec:conc}
 
@@ -3096,7 +3091,6 @@ Finally, we have shown how to modify the key-exchange protocol for practical
 use, and proven that this modification is still secure.
 
 %%%--------------------------------------------------------------------------
-
 \section{Acknowledgements}
 
 The Wrestlers Protocol is named after the Wrestlers pub in Cambridge where
@@ -3107,7 +3101,6 @@ Clive Jones and I worked out the initial design.
 \bibliography{mdw-crypto}
 
 %%%--------------------------------------------------------------------------
-
 \ifshort\def\next{\end{document}}\expandafter\next\fi
 \appendix
 \section{Proofs}
