wrestlers.tex: Fix citations to catch up with Bibtex database changes.

diff --git a/wrestlers.tex b/wrestlers.tex
index 63e428e..8a05c61 100644 (file)
--- 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
 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
 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
 
 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
 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.
 
 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,%
 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
 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
 
 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: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
 
 \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.
 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.
 
 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
 
 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
 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'
 
 \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
 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
 \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
 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.
 
 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
 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}
 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
 \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
 
 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.
 
 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
 
 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
 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}
   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
 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}
 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.
 
 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
 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
 
 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
 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}
 great imposition.
 
 \subsubsection{Optimization and piggybacking}


@@ -3006,7 +3010,7 @@ The combination is safe:
 \end{itemize}
 
 \subsubsection{Unreliable transports}
 \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
 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}

 
 %%%--------------------------------------------------------------------------
 
 
 %%%--------------------------------------------------------------------------