[The Wrestlers Protocol]
{The Wrestlers Protocol%
\ifshort\thanks{This is an extended abstract; the full version
- \cite{Wooding:2006:WP} is available from
+ \cite{wooding-2006:wrestlers} is available from
\texttt{http://eprint.iacr.org/2006/386/}.}\fi \\
A simple, practical, secure, deniable protocol for key-exchange}
\iffancystyle
protocol requires only two messages -- a challenge and a response -- and has
a number of useful properties. It is very similar to, though designed
independently of, a recent protocol by Stinson and Wu
-\cite{cryptoeprint:2006:337}; we discuss their protocol and compare it to
-ours in \ifshort the full version of this paper. \else
+\cite{stinson-wu-2006:two-flow-zero-knowledge}; we discuss their protocol and
+compare it to ours in \ifshort the full version of this paper. \else
section~\ref{sec:stinson-ident}. \fi
Identification protocols are typically less useful than they sound. As Shoup
-\cite{cryptoeprint:1999:012} points out, it provides a `secure ping', by
-which Bob can know that Alice is `there', but provides no guarantee that any
-other communication was sent to or reached her. However, there are
+\cite{shoup-1999:formal-model-key-exchange} points out, it provides a `secure
+ping', by which Bob can know that Alice is `there', but provides no guarantee
+that any other communication was sent to or reached her. However, there are
situations where this an authentic channel between two entities -- e.g., a
device and a smartcard -- where a simple identification protocol can still be
useful.
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{cryptoeprint:2006:229} (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.
+\cite{koblitz-menezes-2006:another-look-provable-security-ii} (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:1997:CST}; see also \cite{Bellare:1999:POP}.
+\cite{bellare-1994:security-cbc,bellare-1995:xor-macs,%
+bellare-rogaway-1995:oaep,bellare-rogaway-1996:exact-security-sigs,%
+bellare-1996:hmac,bellare-1997:concrete-symmetric}; see also
+\cite{bellare-1999:practice-oriented-provable-security}.
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
The first model for studying the \emph{computational} security of
key-exchange protocols (rather than using protocol-analysis logics like that
-of \cite{Burrows:1989:LAa}) was given by Bellare and Rogaway
-\cite{Bellare:1994:EAK}; the model has since been enhanced, both by the
-original authors and others, in \cite{Bellare:1995:PSS,%
-Blake-Wilson:1997:KAP,Blake-Wilson:1998:EAA}. The model defines security
-in terms of a game: key-exchange protocols are secure if an adversary can't
-distinguish the key agreed by a chosen `challenge session' from a key chosen
-independently at random. Other models for key-exchange have been proposed in
-\cite{Bellare:1998:MAD} and \cite{cryptoeprint:1999:012}; these use a
-different notion of security, involving implementation of an ideal
-functionality.
+of \cite{burrows-1989:logic-authn}) was given by Bellare and Rogaway
+\cite{bellare-rogaway-1994:entity-authn-key-distrib}; the model has since
+been enhanced, both by the original authors and others, in
+\cite{bellare-rogaway-1995:session-key-distrib,%
+ blake-wilson-1997:key-agreement,%
+ blake-wilson-menezes-1998:asymm-key-transport}.
+The model defines security in terms of a game: key-exchange protocols are
+secure if an adversary can't distinguish the key agreed by a chosen
+`challenge session' from a key chosen independently at random. Other models
+for key-exchange have been proposed in
+\cite{bellare-1998:modular-key-exchange} and
+\cite{shoup-1999:formal-model-key-exchange}; these use a different notion of
+security, involving implementation of an ideal functionality.
\else
Many proposed key-exchange protocols have turned out to have subtle security
flaws. The idea of using formal methods to analyse key-exchange protocols
-begins with the logic of Burrows, Abadi and Needham \cite{Burrows:1989:LAa}.
-Their approach requires a `formalising' step, in which one expresses in the
-logic the contents of the message flows, and the \emph{beliefs} of the
-participants.
-
-Bellare and Rogaway \cite{Bellare:1994:EAK} describe a model for studying the
-computational security of authentication and key-exchange protocols in a
-concurrent setting, i.e., where multiple parties are running several
-instances of a protocol simultaneously. They define a notion of security in
-this setting, and show that several simple protocols achieve this notion.
-Their original paper dealt with pairs of parties using symmetric
-cryptography; they extended their definitions in \cite{Bellare:1995:PSS} to
-study three-party protocols involving a trusted key-distribution centre.
-
-Blake-Wilson, Johnson and Menezes \cite{Blake-Wilson:1997:KAP} applied the
-model of \cite{Bellare:1994:EAK} to key-exchange protocols using asymmetric
-cryptography, and Blake-Wilson and Menezes \cite{Blake-Wilson:1998:EAA}
-applied it to protocols based on the Diffie-Hellman protocol.
-
-The security notion of \cite{Bellare:1994:EAK} is based on a \emph{game}, in
-which an adversary nominates a \emph{challenge session}, and is given either
-the key agreed by the participants of the challenge session, or a random
-value independently sampled from an appropriate distribution. The
-adversary's advantage -- and hence the insecurity of the protocol -- is
-measured by its success probability in guessing whether the value it was
-given is really the challenge key. This challenge-session notion was also
-used by the subsequent papers described above.
-
-Bellare, Canetti and Krawczyk \cite{Bellare:1998:MAD} described a pair of
-models which they called the \textsc{am} (for `authenticated links model')
-and \textsc{um} (`unauthenticated links model'). They propose a modular
-approach to the design of key-exchange protocols, whereby one first designs a
-protocol and proves its security in the \textsc{am}, and then applies a
-authenticating `compiler' to the protocol which they prove yields a protocol
-secure in the realistic \textsc{um}. Their security notion is new. They
-define an `ideal model', in which an adversary is limited to assigning
-sessions fresh, random and unknown keys, or matching up one session with
-another, so that both have the same key. They define a protocol to be secure
-if, for any adversary~$A$ in the \textsc{am} or \textsc{um}, there is an
-ideal adversary~$I$, such that the outputs of $A$ and $I$ are computationally
-indistinguishable.
-
-In \cite{cryptoeprint:1999:012}, Shoup presents a new model for key-exchange,
-also based on the idea of simulation. He analyses the previous models,
-particularly \cite{Bellare:1994:EAK} and \cite{Bellare:1998:MAD}, and
-highlights some of their inadequacies.
+begins with the logic of Burrows, Abadi and Needham
+\cite{burrows-1989:logic-authn}. Their approach requires a `formalising'
+step, in which one expresses in the logic the contents of the message flows,
+and the \emph{beliefs} of the participants.
+
+Bellare and Rogaway \cite{bellare-rogaway-1994:entity-authn-key-distrib}
+describe a model for studying the computational security of authentication
+and key-exchange protocols in a concurrent setting, i.e., where multiple
+parties are running several instances of a protocol simultaneously. They
+define a notion of security in this setting, and show that several simple
+protocols achieve this notion. Their original paper dealt with pairs of
+parties using symmetric cryptography; they extended their definitions in
+\cite{bellare-rogaway-1995:session-key-distrib} to study three-party
+protocols involving a trusted key-distribution centre.
+
+Blake-Wilson, Johnson and Menezes \cite{blake-wilson-1997:key-agreement}
+applied the model of \cite{bellare-rogaway-1994:entity-authn-key-distrib} to
+key-exchange protocols using asymmetric cryptography, and Blake-Wilson and
+Menezes \cite{blake-wilson-menezes-1998:asymm-key-transport} applied it to
+protocols based on the Diffie-Hellman protocol.
+
+The security notion of \cite{bellare-rogaway-1994:entity-authn-key-distrib}
+is based on a \emph{game}, in which an adversary nominates a \emph{challenge
+session}, and is given either the key agreed by the participants of the
+challenge session, or a random value independently sampled from an
+appropriate distribution. The adversary's advantage -- and hence the
+insecurity of the protocol -- is measured by its success probability in
+guessing whether the value it was given is really the challenge key. This
+challenge-session notion was also used by the subsequent papers described
+above.
+
+Bellare, Canetti and Krawczyk \cite{bellare-1998:modular-key-exchange}
+described a pair of models which they called the \textsc{am} (for
+`authenticated links model') and \textsc{um} (`unauthenticated links model').
+They propose a modular approach to the design of key-exchange protocols,
+whereby one first designs a protocol and proves its security in the
+\textsc{am}, and then applies a authenticating `compiler' to the protocol
+which they prove yields a protocol secure in the realistic \textsc{um}.
+Their security notion is new. They define an `ideal model', in which an
+adversary is limited to assigning sessions fresh, random and unknown keys, or
+matching up one session with another, so that both have the same key. They
+define a protocol to be secure if, for any adversary~$A$ in the \textsc{am}
+or \textsc{um}, there is an ideal adversary~$I$, such that the outputs of $A$
+and $I$ are computationally indistinguishable.
+
+In \cite{shoup-1999:formal-model-key-exchange}, Shoup presents a new model
+for key-exchange, also based on the idea of simulation. He analyses the
+previous models, particularly
+\cite{bellare-rogaway-1994:entity-authn-key-distrib} and
+\cite{bellare-1998:modular-key-exchange}, and highlights some of their inadequacies.
\fi
-Canetti and Krawczyk \cite{cryptoeprint:2001:040,Canetti:2001:AKE} describe a
-new notion of security in the model of \cite{Bellare:1998:MAD}, based on the
-challenge-session notion of \cite{Bellare:1994:EAK}. The security notion,
-called `SK-security', seems weaker in various ways than those of earlier
-works such as \cite{Bellare:1994:EAK} or \cite{cryptoeprint:1999:012}.
-However, the authors show that their notion suffices for constructing `secure
-channel' protocols, which they also define.
-
-\ifshort\else
-In \cite{Canetti:2001:UCS}, Canetti describes the `universal composition'
-framework. Here, security notions are simulation-based: one defines security
-notions by presenting an `ideal functionality'. A protocol securely
-implements a particular functionality if, for any adversary interacting with
-parties who use the protocol, there is an adversary which interacts with
-parties using the ideal functionality such that no `environment' can
-distinguish the two. The environment is allowed to interact freely with the
-adversary throughout, differentiating this approach from that of
-\cite{Bellare:1998:MAD} and \cite{cryptoeprint:1999:012}, where the
-distinguisher was given only transcripts of the adversary's interaction with
-the parties. With security defined in this way, it's possible to prove a
-`universal composition theorem': one can construct a protocol, based upon
-various ideal functionalities, and then `plug in' secure implementations of
-the ideal functionalities and appeal to the theorem to prove the security of
-the entire protocol. The UC framework gives rise to very strong notions of
-security, due to the interactive nature of the `environment' distinguisher.
-\fi
-
-Canetti and Krawczyk \cite{Canetti:2002:UCN} show that the SK-security notion
-of \cite{Canetti:2001:AKE} is \emph{equivalent} to a `relaxed' notion of
-key-exchange security in the UC framework\ifshort\space of
-\cite{Canetti:2001:UCS}\fi, and suffices for the construction of UC secure
-channels.
-
-The result of \cite{Canetti:2002:UCN} gives us confidence that SK-security is
-the `right' notion of security for key-exchange protocols. Accordingly,
-SK-security is the standard against which we analyse our key-exchange
-protocol.
+Canetti and Krawczyk
+\cite{canetti-krawczyk-2001:secure-channels-eprint,%
+ canetti-krawczyk-2001:secure-channels}
+describe a new notion of security in the model of
+\cite{bellare-1998:modular-key-exchange}, based on the challenge-session
+notion of \cite{bellare-rogaway-1994:entity-authn-key-distrib}. The security
+notion, called `SK-security', seems weaker in various ways than those of
+earlier works such as \cite{bellare-rogaway-1994:entity-authn-key-distrib} or
+\cite{shoup-1999:formal-model-key-exchange}. However, the authors show that
+their notion suffices for constructing `secure channel' protocols, which they
+also define.
+
+\ifshort\else In \cite{canetti-2001:uc-security-eprint,%
+ canetti-2001:uc-security},
+Canetti describes the `universal composition' framework. Here, security
+notions are simulation-based: one defines security notions by presenting an
+`ideal functionality'. A protocol securely implements a particular
+functionality if, for any adversary interacting with parties who use the
+protocol, there is an adversary which interacts with parties using the ideal
+functionality such that no `environment' can distinguish the two. The
+environment is allowed to interact freely with the adversary throughout,
+differentiating this approach from that of
+\cite{bellare-1998:modular-key-exchange} and
+\cite{shoup-1999:formal-model-key-exchange}, where the distinguisher was
+given only transcripts of the adversary's interaction with the parties. With
+security defined in this way, it's possible to prove a `universal composition
+theorem': one can construct a protocol, based upon various ideal
+functionalities, and then `plug in' secure implementations of the ideal
+functionalities and appeal to the theorem to prove the security of the entire
+protocol. The UC framework gives rise to very strong notions of security,
+due to the interactive nature of the `environment' distinguisher. \fi
+
+Canetti and Krawczyk \cite{canetti-krawczyk-2002:uc-key-exchange} show that
+the SK-security notion of \cite{canetti-krawczyk-2001:secure-channels} is
+\emph{equivalent} to a `relaxed' notion of key-exchange security in the UC
+framework\ifshort\space of \cite{canetti-2001:uc-security}\fi, and suffices
+for the construction of UC secure channels.
+
+The result of \cite{canetti-krawczyk-2002:uc-key-exchange} gives us
+confidence that SK-security is the `right' notion of security for
+key-exchange protocols. Accordingly, SK-security is the standard against
+which we analyse our key-exchange protocol.
\subsection{Outline of the paper}
\ifshort
The full version of this paper describes how to make our protocols
identity-based by using bilinear pairings using the techniques introduced in
-\cite{Boneh:2003:IBE}. It also contains proofs of the various theorems
-stated here.
+\cite{boneh-franklin-2003:ibe-weil-pairing}. It also contains proofs of the
+various theorems stated here.
\fi
%%%--------------------------------------------------------------------------
distinguish between the two except with very small probability.
Our proofs make frequent use of sequences of games; see
-\cite{cryptoeprint:2004:332,cryptoeprint:2004:331}. The presentation owes
-much to Shoup \cite{cryptoeprint:2004:332}. 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.
+\cite{bellare-rogaway-2006:triple-enc,shoup-2004:sequences-of-games}.
+The presentation owes much to Shoup \cite{shoup-2004:sequences-of-games}. 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:oaep-reconsidered} will be
+frequently useful.
\begin{lemma}[Difference Lemma]
\label{lem:shoup}
Let $S$, $T$, $F$ be events. Suppose $\Pr[S \mid \bar F] =
\ifshort\else
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.)
+model \cite{bellare-rogaway-1993:random-oracles}, 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-rogaway-1993:random-oracles}, 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
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.
+Canetti, Goldreich and Halevi \cite{canetti-2004:rand-oracle-revisit} 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.
\fi
-The random oracle model \ifshort\cite{Bellare:1993:ROP} \fi is useful for
-constructing reductions and simulators for two main reasons.
+The random oracle model \ifshort\cite{bellare-rogaway-1993:random-oracles}
+\fi 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.
\ifshort\else
(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:2003: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.)
+of \cite{boneh-franklin-2003:ibe-weil-pairing}. 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.)
\fi
\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$.
+problem. The converse is not clear, though. Shoup
+\cite{shoup-1997:dh-lower-bounds} 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.)
+Diffie-Hellman problem (DDH), which \cite{shoup-1997:dh-lower-bounds} shows,
+in the generic group model, is about as hard as CDH. (See
+\cite{boneh-1998:ddh} for a survey of the decision Diffie-Hellman problem.)
\par\fi
Our reference problem will be a `multiple-guess computational Diffie-Hellman
problem' (MCDH), which is captured by a game as follows. An adversary is
the challenge).
\end{itemize}
The resulting definition bears a striking similarity to the concept of
-\emph{plaintext awareness} in \cite{Bellare:1998:RAN}.
+\emph{plaintext awareness} in \cite{bellare-1998:pub-enc-notions}.
Such an extractor indeed exists, as the following lemma states.
\begin{lemma}[Effectiveness of extractor $T_\Wident$]
\subsection{An identity-based identification scheme}
\label{sec:wident-id}
-Boneh and Franklin \cite{Boneh:2003: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:1985:PKCb}. 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}
+Boneh and Franklin \cite{boneh-franklin-2003:ibe-weil-pairing} 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-1985:dlog-enc-sign}. 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:2003:IBE} gives more detail; also \cite{Menezes:2005:IPB}
-provides a useful introduction to the topic.)
+\cite{boneh-franklin-2003:ibe-weil-pairing} gives more detail; also
+\cite{menezes-2005:intro-pairing-crypto} 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'$
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 \gf{q}$; his public key is $T =
-t P$.
+We need a trusted authority; following \cite{schneier-1996:applied-crypto} we
+shall call him Trent. Trent's private key is $t \in \gf{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
\label{sec:stinson-ident}
Our protocol is similar to a recent proposal by Stinson and Wu
-\cite{cryptoeprint:2006:337}. 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 \gf{q}$ and her public key is
-$\alpha = \gamma^a$. In their protocol, the challenger chooses
+\cite{stinson-wu-2006:two-flow-zero-knowledge}. 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 \gf{q}$ and her
+public key is $\alpha = \gamma^a$. In their protocol, the challenger chooses
$r \inr \gf{q}$, computes $\rho = \gamma^r$ and $\psi = \alpha^r$, and sends
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
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.)
+\cite{certicom-2000: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:
unnecessary for our protocol, since we can present an \emph{explicit}
extractor.
-The KEA assumption as stated in \cite{cryptoeprint:2006:337} 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(\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'.
+The KEA assumption as stated in
+\cite{stinson-wu-2006:two-flow-zero-knowledge} 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(\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
\label{sec:um}
Our model is very similar to that of Canetti and Krawczyk
-\cite{Canetti:2001:AKE}, though we have modified it in two ways.
+\cite{canetti-krawczyk-2001:secure-channels}, 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.
\ifshort
Readers interested in the details of the model should see Canetti and
-Krawczyk's paper \cite{Canetti:2001:AKE}, or the full version of this paper.
+Krawczyk's paper \cite{canetti-krawczyk-2001:secure-channels}, or the full
+version of this paper.
\else
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 \ifshort in
- \cite{Canetti:2001:AKE}\else previously\fi, where $n$
+ \cite{canetti-krawczyk-2001:secure-channels}\else previously\fi, 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
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{cryptoeprint:1999:012}.
- There it is required that a key-exchange protocol terminate after a
- polynomially-bounded number of messages are delivered to it.}
+ acceptable in the simulation-based model of
+ \cite{shoup-1999:formal-model-key-exchange}. 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}
protocol.
Our notion of deniability is taken from Di~Raimondo, Gennaro and Krawczyk
-\cite{cryptoeprint:2006:280}, except that, as usual, we opt for a concrete
-security approach.
+\cite{raimondo-2006:deniable-authn-key-exchange}, except that, as usual, we
+opt for a concrete security approach.
\subsubsection{Discussion}
Our definition for deniability is that, for any adversary interacting with
since this would be a denial of service. In the strong adversarial model,
this doesn't matter, since the adversary can deny service anyway, but it's a
concern against less powerful adversaries. Most IND-CCA symmetric encryption
-schemes also provide integrity of plaintexts \cite{Bellare:2000:AER} (e.g.,
-the encrypt-then-MAC generic composition approach \cite{Bellare:2000:AER,%
-Krawczyk:2001:OEA}, and the authenticated-encryption modes of
-\cite{Rogaway:2003:OBC,Bellare:2004:EAX,McGrew:2004:SPG}), so this isn't a
-great imposition.
+schemes also provide integrity of plaintexts
+\cite{bellare-namprempre-2000:authn-enc-notions} (e.g., the
+encrypt-then-MAC generic composition approach
+\cite{bellare-namprempre-2000:authn-enc-notions,%
+ krawczyk-2001:order-enc-authn},
+and the authenticated-encryption modes of
+\cite{rogaway-2001:ocb,bellare-2004:eax,%
+ mcgrew-viega-2004:gcm-security-performance}),
+so this isn't a great imposition.
\subsubsection{Optimization and piggybacking}
We can optimize the number of messages sent by combining them. Here's one
\subsubsection{Key reuse}
Suppose our symmetric encryption scheme $\E$ is not only IND-CCA secure
(definition~\ref{def:ind-cca}) but also provides integrity of plaintexts
-\cite{Bellare:2000:AER} (or, alternatively, is an AEAD scheme
-\cite{Rogaway:2002:AEA}. Then we can use it to construct a secure channel,
-by including message type and sequence number fields in the plaintexts, along
-with the message body. If we do this, we can actually get away with just the
-one key $K = H_K(Z)$ rather than both $K_0$ and $K_1$.
+\cite{bellare-namprempre-2000:authn-enc-notions} (or, alternatively,
+is an AEAD scheme \cite{rogaway-2002:aead}. Then we can use it to construct
+a secure channel, by including message type and sequence number fields in the
+plaintexts, along with the message body. If we do this, we can actually get
+away with just the one key $K = H_K(Z)$ rather than both $K_0$ and $K_1$.
To do this, it is essential that the plaintext messages (or additional data)
clearly distinguish between the messages sent as part of the key-exchange
%%%--------------------------------------------------------------------------
-\bibliography{%
- mdw-crypto,%
- eprint,%
- focs1990,stoc1990,tissec,jacm,%
- lncs1997a,lncs1997b,lncs1998a,lncs2001a,%
- cryptography1990,cryptography2000,cryptography2010,cryptography,%
- rfc,std}
+\bibliography{mdw-crypto}
%%%--------------------------------------------------------------------------
provides secure channels.
\subsubsection{Secure channels definition}
-We (very briefly!) recall the \cite{Canetti:2001:AKE} definition of a secure
-channels protocol. We again play a game with the adversary. At the
-beginning, we choose a bit $b^* \inr \{0, 1\}$ at random. We allow the
-adversary the ability to establish \emph{secure channels} sessions within the
-parties. Furthermore, for any running session $S = (P_i, P_j, s)$, we allow
-the adversary to request $S$ to send a message~$\mu$ through its secure
-channel. Finally, the adversary is allowed to choose one ripe
-\emph{challenge} session, and ask for it to send of one of a \emph{pair} of
-messages $(\mu_0, \mu_1)$, subject to the restriction that $|\mu_0| =
+We (very briefly!) recall the \cite{canetti-krawczyk-2001:secure-channels}
+definition of a secure channels protocol. We again play a game with the
+adversary. At the beginning, we choose a bit $b^* \inr \{0, 1\}$ at random.
+We allow the adversary the ability to establish \emph{secure channels}
+sessions within the parties. Furthermore, for any running session $S = (P_i,
+P_j, s)$, we allow the adversary to request $S$ to send a message~$\mu$
+through its secure channel. Finally, the adversary is allowed to choose one
+ripe \emph{challenge} session, and ask for it to send of one of a \emph{pair}
+of messages $(\mu_0, \mu_1)$, subject to the restriction that $|\mu_0| =
|\mu_1|$; the session sends message $\mu_{b^*}$. The adversary may not
expose the challenge session.
~mdw / doc / wrestlers / commitdiff