\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
\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
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.
\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.)
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,
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
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.
\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
~mdw / doc / wrestlers / commitdiff