X-Git-Url: https://git.distorted.org.uk/~mdw/doc/wrestlers/blobdiff_plain/b12a993f2d35076dfc7dd515b8d8f2f5ef1a42dc..4331bf844ebc460672f36174f706e4de144dba6c:/wrestlers.tex

diff --git a/wrestlers.tex b/wrestlers.tex
index 63e428e..8a05c61 100644
--- a/wrestlers.tex
+++ b/wrestlers.tex
@@ -214,16 +214,17 @@ of recognising Alice; for instance, he might know her public key.  Our
 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{Stinson:2006:EST}; we discuss their protocol and compare it to ours in
-\ifshort the full version of this paper. \else
+\cite{cryptoeprint:2006:337}; 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{Shoup:1999:OFM} 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.
+\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
+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.
 
 An authenticated key-exchange protocol lets Alice and Bob agree on a shared
 secret, known to them alone, even if there is an enemy who can read and
@@ -285,8 +286,8 @@ 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
+\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.
 
@@ -294,7 +295,7 @@ 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}.
+Bellare:1996:KHF,Bellare:1997: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
@@ -307,21 +308,22 @@ within given resource bounds.
 
 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:LA}) was given by Bellare and Rogaway
+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{Shoup:1999:OFM}; these use a different
-notion of security, involving implementation of an ideal functionality.
+\cite{Bellare:1998:MAD} and \cite{cryptoeprint:1999:012}; 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:LA}.
+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.
@@ -363,20 +365,20 @@ 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:OFM}, Shoup presents a new model for key-exchange, also
-based on the idea of simulation.  He analyses the previous models,
+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.
 
 \fi
 
-Canetti and Krawczyk \cite{Canetti:2001:AKE} describe a new notion of
-security in the model of \cite{Bellare:1998:MAD}, based on the
+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{Shoup:1999:OFM}.  However, the
-authors show that their notion suffices for constructing `secure channel'
-protocols, which they also define.
+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'
@@ -387,14 +389,14 @@ 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{Shoup:1999:OFM}, 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.
+\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
@@ -542,17 +544,18 @@ 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.
+\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.
@@ -1835,7 +1838,7 @@ The following two trivial lemmata will be useful, both now and later.
 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:PKC}.  We can easily apply their
+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}
@@ -1918,14 +1921,14 @@ through the details.
 \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 \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 response.  They prove their
-protocol's security in the random-oracle model.
+\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
+$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
+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
@@ -1950,11 +1953,12 @@ 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(\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{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'.
 
 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
@@ -2360,8 +2364,8 @@ 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
+  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.}
 
 \begin{figure}
@@ -2573,7 +2577,7 @@ 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
+\cite{cryptoeprint:2006:280}, except that, as usual, we opt for a concrete
 security approach.
 
 \subsubsection{Discussion}
@@ -2913,11 +2917,11 @@ 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{RFC0793} ameliorates this problem because
+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{RFC0768}, for which spoofing is trivial.
+\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
@@ -2984,7 +2988,7 @@ 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:OCB,Bellare:2004:EAX,McGrew:2004:SPG}), so this isn't a
+\cite{Rogaway:2003:OBC,Bellare:2004:EAX,McGrew:2004:SPG}), so this isn't a
 great imposition.
 
 \subsubsection{Optimization and piggybacking}
@@ -3006,7 +3010,7 @@ The combination is safe:
 \end{itemize}
 
 \subsubsection{Unreliable transports}
-The Internet UDP \cite{RFC0768} is a simple, unreliable protocol for
+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).  Since UDP is a best-effort rather than a reliable
@@ -3076,7 +3080,13 @@ Clive Jones and I worked out the initial design.
 
 %%%--------------------------------------------------------------------------
 
-\bibliography{mdw-crypto,cryptography2000,cryptography,rfc,std}
+\bibliography{%
+  mdw-crypto,%
+  eprint,%
+  focs1990,stoc1990,tissec,jacm,%
+  lncs1997a,lncs1997b,lncs1998a,lncs2001a,%
+  cryptography1990,cryptography2000,cryptography2010,cryptography,%
+  rfc,std}
 
 %%%--------------------------------------------------------------------------
 
