wrestlers.tex: Let `\section' act as a section header in the source.

[doc/wrestlers] / wr-backg.tex

\xcalways\section{Cryptographic background}\x

\xcalways\subsection{Groups}\x

\begin{slide}
  \resetseq
  \head{Groups \seq: definition}
  \topic{definitions}

  A \emph{group} is a set $G$ of objects, and a binary operation $\op$, with
  the following properties.
  \begin{description}
  \item [Closure] If $a$ and $b$ are elements of $G$, then so is $a \op b$.
  \item [Associativity] For any $a$, $b$ and $c$ in $G$,
    \[ a \op (b \op c) = (a \op b) \op c. \]
  \item [Identity] There exists an element $e$ so that, for any $a$ in $G$,
    \[ a \op e = a = e \op a. \]
  \item [Inverses] For any $a$ in $G$, there exists a $b$ so that
    \[ a \op b = e = b \op a. \]
  \end{description}
\end{slide}

\begin{slide}
  \head{Groups \seq: abelian groups}

  A group $(G, \op)$ is \emph{commutative}, or \emph{abelian}, if it has the
  following additional property.
  \begin{description}
  \item [Commutativity] For any $a$ and $b$ in $G$,
    \[ a \op b = b \op a. \]
  \end{description}
  We usually write the operator of an abelian group using some familiar
  symbol, like $+$ or $\times$.
\end{slide}

\begin{slide}
  \head{Groups \seq: notation}

  Let $(G, +)$ be a group written additively.  For $A, B \in G$, we do the
  obvious things and write $0_G$, or just $0$, for the identity, and $-A$ for
  the inverse of $A$; we also write
  \[ A - B \equiv A + (- B) \qquad
     2 A \equiv A + A \qquad
     n A \equiv \underbrace{A + A + \cdots + A}_\text{$n$ times}.
  \]
  Similarly, if $(H, \times)$ is a group written multiplicatively, and
  $\alpha, \beta \in H$, we do the obvious things and write $1_H$, or just
  $1$, for the identity, and $\alpha^{-1}$ for the inverse of $\alpha$; we
  also write
  \[ \alpha \beta \equiv \alpha \times \beta \qquad
     \alpha/\beta \equiv \alpha \times \beta^{-1} \qquad
     \alpha^2 \equiv \alpha \times \alpha \qquad
     \alpha^n \equiv \underbrace{\alpha \times \alpha \times \cdots
       \alpha}_\text{$n$ times}.
  \]
  The number of elements of a group $G$ is written $|G|$ (or sometimes
  $\#G$), and is called the \emph{order} of $G$.
\end{slide}

\begin{slide}
  \head{Groups \seq: cyclic groups and discrete logs}
  \topic{cyclic groups and discrete logs}

  A \emph{cyclic} group $(G, +)$ consists only of elements $n P$ for a single
  $P$ and varying $n \in \Z$.  We call $P$ a \emph{generator} of the group.

  Cyclic groups are always abelian.

  If $G$ is finite, then for any $A \in G$, there is a \emph{unique} $a \in
  \Nupto{|G|}$ for which $A = a P$.  We call $a$ the \emph{discrete
  logarithm} of $A$ to the base $P$.

  This makes more sense if you consider a multiplicative group $(H, \times)$.
  Then there's a $\gamma \in H$, and for any $\alpha$, a unique $a \in
  \Nupto{|H|}$ such that $\alpha = \gamma^a$.

  Computing discrete logs seems to be difficult in some kinds of groups.
\end{slide}

\begin{slide}
  \head{Groups \seq: Diffie-Hellman}
  \topic{Diffie-Hellman}

  Fix some cyclic group $(G, +)$, with generator $P$.
  \begin{protocol}
    Alice & Bob \\[\medskipamount]
    $a \getsr \Nupto{|G|}$; & $b \getsr \Nupto{|G|}$; \\
    $A \gets a P$; & $B \gets b P$; \\
    \send{->}{A}
    \send{<-}{B}
    $Z \gets a B$; & $Z \gets b A$;
  \end{protocol}
  This works because
  \[ Z = a B = a (b P) = (a b) P = (b a) P = b (a P) = b A. \]
  Computing $a b P$ from $a P$ and $b P$ seems hard.  This is the
  (computational) \emph{Diffie-Hellman} problem.

  The best way we know is to work out $a$ or $b$ -- i.e., extract a discrete
  logarithm.
\end{slide}

\begin{slide}
  \head{Groups \seq: ElGamal encryption}
  \topic{ElGamal encryption}

  Suppose $H\colon G \to \Bin^n$ is a secure hash function.  Alice has a
  private key~$a \in \Nupto{|G|}$.  Bob knows her public key~$A = a P$.  He
  has an $n$-bit message $m$ he wants to send her.
  \begin{enumerate}
  \item He chooses $r \inr \Nupto{|G|}$.
  \item He computes $R = r P$.
  \item He computes $Z = r A$.
  \item He sends Alice the pair $(R, m \xor H(Z))$.
  \end{enumerate}
  Alice can decrypt because
  \[ a R = (a r) P = r A = Z. \]  
\end{slide}

\begin{slide}
  \head{Groups \seq: Schnorr groups}
  \topic{examples}

  Let $p$ and $q$ be prime, with $p = q f + 1$.  The residues modulo $p$ form
  a \emph{finite field} $\F_p$.  The nonzero elements form a cyclic group
  $\F_p^*$ under multiplication mod~$p$.  Let $\eta$ be a generator of
  $\F_p^*$.

  Set $\gamma = \eta^f$.  Then
  \[ G = \langle \gamma \rangle = \{\, \gamma^n \mid 0 \le n < q \,\} \]
  is a \emph{Schnorr group} of $q$ elements.  $G$ is cyclic, with generator
  $\gamma$.

  In practice, you don't need to find $\eta$.  Pick $\alpha \in \F_p^*$
  arbitrarily (2 is a good first choice); if $\alpha^f \ne 1$ then use
  $\gamma = \alpha^f$.
\end{slide}

\begin{slide}
  \head{Groups \seq: elliptic curves}

  Let $q = p^f$ be a prime power.  Then there is a finite field $\F_q$ with
  $q$ elements.

  Let $E$ be an \emph{elliptic curve} over $\F_q$:
  \[ E(\F_q) = \{\, (x, y) \in \F_q^2 \mid y^2 = x^3 + a x + b \,\} \]
  \begin{tabularx}{\linewidth}{@{}Xl}
    \hrule height 0pt
    The points of $E(\F_q)$ form a group with a peculiar kind of addition
    (pictured right).
    \parskip=1ex

    If $\#E(\F_q)$ has a large prime factor then we can
    use a cyclic subgroup of $E(\F_q)$.  The details are complicated\dots
    &
    \vtop{\hrule height 0pt \hbox{
        \ifpdf
          \includegraphics[scale = 0.6]{ecc-0.pdf}
        \else
          \includegraphics[scale = 0.6]{ecc.0}
        \fi
      }}
  \end{tabularx}
\end{slide}


\xcalways\subsection{Bilinear maps}\x

\begin{slide}
  \resetseq
  \head{Bilinear maps \seq: definition}
  \topic{definition}

  Let $(G, +)$, $(G', +)$ and $(G_T, \times)$ be three cyclic groups with the
  same order.  Let $P$ and $P'$ generate $G$ and $G'$ respectively.

  A map $\hat{e}\colon G \times G' \to G_T$ is \emph{bilinear} if
  \begin{itemize}
  \item for any $R \in G$ and $S', T' \in G'$,
    \[ \hat{e}(R, S' + T') = \hat{e}(R, S') \, \hat{e}(R, T'), \]
    and
  \item for any $R, S \in G$ and $T' \in G'$,
    \[ \hat{e}(R + S, T') = \hat{e}(R, T') \, \hat{e}(S, T'). \]
  \end{itemize}
  We say that $\hat{e}$ is \emph{non-degenerate} if
  \[ \hat{e}(P, P') \ne 1. \]
\end{slide}

\begin{slide}
  \head{Bilinear maps \seq: properties}
  \topic{properties}

  Define
  \[ \gamma = \hat{e}(P, P'). \]
  Then $\gamma$ generates $G_T$.

  For any $a$ and $b$:
  \[ \hat{e}(a P, b P') = \gamma^{a b}. \]
  If $\hat{e}$ is easy to compute then this is like a Diffie-Hellman
  computation combined with an isomorphism to a different group.
\end{slide}

\begin{slide}
  \head{Bilinear maps \seq: the Bilinear Diffie-Hellman problem}
  \topic{bilinear Diffie-Hellman problem}

  The \emph{bilinear} Diffie-Hellman problem is this: given
  \begin{itemize}
  \item $a P$ and $b P$ in $G$, and
  \item $a P'$ and $c P'$ in $G'$,
  \end{itemize}
  compute
  \[ \zeta = \gamma^{abc}. \]

  This can be done if the Diffie-Hellman problem can be solved in \emph{any}
  of $G$, $G'$ or $G_T$.
  \begin{itemize}
  \item If DHP easy in $G$, then compute $\zeta = \hat{e}(a b P, c P')$.
  \item If DHP easy in $G'$, then compute $\zeta = \hat{e}(b P, a c P')$.
  \item If DHP easy in $G_T$, then compute $\alpha = \hat{e}(a P, P') =
    \gamma^a$, $\beta = \hat{e}(b P, c P') = \gamma^{b c}$ and $\zeta$ from
    $\alpha$ and $\beta$.
  \end{itemize}
\end{slide}

\begin{slide}
  \head{Bilinear maps \seq: Boneh-Franklin identity-based encryption}
  \topic{Boneh-Franklin identity-based encryption}

  We need two hashes: $H \colon G_T \to \Bin^n$ and $H_\text{id} \colon
  \Bin^* \to G'$.

  There is a \emph{trusted third party}.  It has a private key $t \inr
  \Nupto{|G|}$ and a public key $T = t P$.

  Alice's public key is $A = H_\text{id}(\texttt{Alice})$.  Her private key
  is $K_A = t A$.

  Bob wants to send Alice a message $m \in \Bin^n$.
  \begin{enumerate}
  \item He chooses $r \inr \Nupto{|G|}$.
  \item He computes $R = r P$.
  \item He computes $\psi = \hat{e}(T, A)^r$.
  \item He sends Alice the pair $(R, m \xor H(\psi))$.
  \end{enumerate}
  Alice can decrypt because
  \[ \hat{e}(R, K_A) = \hat{e}(r P, t A)
                     = \hat{e}(P, A)^{rt}
                     = \hat{e}(t P, A)^r
                     = \hat{e}(T, A)^r
                     = \psi. \]
\end{slide}

\begin{slide}
  \head{Bilinear maps \seq: examples}
  \topic{examples}

  The major examples of bilinear maps are the \emph{Weil} and \emph{Tate
  pairings} on torsion groups of elliptic curves.
\end{slide}


\xcalways\subsection{Zero-knowledge}\x

\begin{slide}
  \resetseq
  \head{Zero-knowledge \seq: interactive proofs}
  \topic{interactive proofs}

  Prover and verifier exchange messages.  Verifier decides whether to
  \emph{accept} or \emph{reject} the proof.

  An interactive proof system must have the following properties.
  \begin{description}
  \item [Completeness] If the prover is honest, the verifier (almost always)
    accepts.
  \item [Soundness] If the prover is \emph{dishonest}, the verifier
    (sometimes) rejects.
  \end{description}
  Repeat protocol several times to reduce soundness error.
\end{slide}

\begin{slide}
  \head{Zero-knowledge \seq: simulation}
  \topic{simulation}

  We have a prover $P$ and a verifier $V$.  Write
  \[ x \gets V^P() \]
  to mean that $V$ outputs $x$ after interacting with $P$.

  Suppose that there is a simulator~$S$ so that, for all $y$,
  \[ |\Pr[x \gets V^P() : x = y] - \Pr[x \gets S() : x = y]| \le \epsilon. \]
  If $\epsilon$ is small, then $V$ is unlikely to be able to persuade anyone
  that he learned anything from $P$.

  in particular, if $\epsilon = 0$ then we say that the proof has
  \emph{perfect zero knowledge}.
\end{slide}

\begin{slide}
  \head{Zero-knowledge \seq: an example}
  \topic{example}

  Prover $P$ knows that $\alpha = \beta^2 \in \Z/n\Z$ for some composite $n$.
  \begin{protocol}
    Prover $P$ & Verifier $V$ \\[\medskipamount]
    $\gamma \getsr \Z/n\Z$; \\
    \send{->}{\kappa = \gamma^2 \alpha}
    \send{<-}{c \inr \Bin}
    \send{->}{\rho = \gamma \beta^c}
    & Check: $\kappa = \rho^2 \alpha^{1 - c}$
  \end{protocol}

  \begin{itemize}
  \item Completeness:
    \[ \rho \alpha^{1 - c} = (\gamma \beta^c)^2 \alpha^{1 - c}
                           = \gamma^2 \beta^{2c} \alpha^{1 - c}
                           = \gamma^2 \alpha^c \alpha^{1 - c}
                           = \gamma^2 \alpha
                           = \kappa.
    \]
  \item Soundness: if $P^*$ convinces $V$ with probability $p > \frac{1}{2}$
    then we can, in theory, run $P^*$ with (say) $c = 0$ and get $\gamma$.
    We then \emph{rewind} $P^*$, give it $c = 1$, and get $\gamma \beta$,
    from which we compute $\beta$.  This works with probability at least $2
    (p - \frac{1}{2})$.
  \end{itemize}
\end{slide}

This statement could use some proof.

Firstly, consider a simple abstract game.  There is a secret table, with two
columns and $r$ rows.  Exactly $n$ of the entries in the table contain $1$;
the remaining entries contain zero.  We have to pick a row, and you win if
both entries in that row contain $1$.

Clearly, if $n \le r$, it's possible to arrange the ones so that each is in a
different row.  If we're playing against someone unscrupulous, we are
guaranteed to lose.

On the other hand, if $n > r$, there must be a winning row, because there are
too many ones to fit otherwise.  In fact, there must be at least $n - r$
winning rows.  So our probability of winning must be at least $(n - r)/r$.

Apply this to the problem of our dishonest prover.  The `table''s rows are
indexed by all the possible inputs to the prover -- the value $\alpha$ and
its own internal coin tosses.  (We only consider provers running in bounded
time, so these are finite.)  The columns are indexed by our coin $c$.  We
know that $2 r p$ of the entries contain $1$.  Hence, the probability that we
win is at least
\[ \frac{2 r p - r}{r} = 2 \biggl( p - \frac{1}{2} \biggr). \]

\begin{slide}
  \head{Zero-knowledge \seq: an example (cont.)}

  We now show zero-knowledge, by describing a simulator.
  \begin{enumerate}
  \item Simulator chooses $\rho \inr \Z/n\Z$ and $b \inr \Bin$ at random.  It
    runs $V$ and sends it $\kappa = \rho \alpha^{1 - b}$.
  \item Verifier runs, returns bit $c$.
  \item If $b = c$ then simulator sends back $\rho$.  If $b \ne c$ then
    simulator gives up and tries again.
  \item Verifier (presumably) accepts, because
    \[ \rho \alpha^{1 - c} = \rho \alpha^{1 - b}. \]
  \end{enumerate}
  Simulator fails (and retries) with probability $\frac{1}{2}$, because $b$
  is uniform and independent of $c$.
\end{slide}

\begin{slide}
  \head{Aside on KCDSA}
  \topic{KCDSA}

  Let $(G, +)$ be a cyclic group of prime order $q$, with generator $P$.  Let
  $H\colon G \to \Bin^t$ and $H'\colon \Bin^* \to \Bin^t$ be cryptographic
  hash functions.

  Alice's private key is $a \inr \F_q$.  Her public key is $A = a P$.
  Suppose Alice wants to sign a message $m \in \Bin^*$.
  \begin{enumerate}
  \item She chooses a random $k \inr \F_q$.  She computes $K = k P$, and $r =
    H(K)$.
  \item Computes $h = H'(m)$, and $u = (h \xor r) \bmod q$.
  \item Finally, she computes $s = (k - u)/a$.
  \end{enumerate}
  Her signature on $m$ is $\sigma = (r, s)$.

  To verify $(r, s)$, Bob can compute $h = H'(m)$; he checks that
  \[ r = H(s A + u P). \]
  Note that $s a = k - u$, so $s a + u = k$.  Hence $s A + u P = (s
  a + u) P = k P = K$.
\end{slide}

\begin{slide}
  \head{Zero-knowledge \seq: KCDSA as identification protocol}

  As before, let $(G, +)$ be a cyclic group, generated by $P$, of prime order
  $q$, and let $H\colon G \to \Bin^t$ be a cryptographic hash function.
  \begin{protocol}
    Alice & Bob \\
    (private key $a \inr \F_q$) & (public key $A = a P$) \\[\medskipamount]
    $k \getsr \F_q$; $K \gets k P$; \\
    \send{->}{r = H(K)}
    \send{<-}{m \inr \Bin^{t}}
    $u \gets (r \xor m) \bmod q$; & $u \gets (r \xor m) \bmod q$; \\
    \send{->}{s = (k - u)/x}
    & Check: $r = H(s A + u P)$
  \end{protocol}
\end{slide}

\begin{slide}
  \head{Zero-knowledge \seq: KCDSA as identification protocol (cont.)}

  \begin{itemize}
  \item Completeness: as for the KCDSA signature scheme.
  \item Soundness: suppose some prover manages to impersonate Alice with
    probability $\epsilon > 2^{-t}$.  We choose some $m$ and send it to the
    prover, getting $s$.  Now we \emph{rewind} the prover and send it some
    $m' \ne m$.  With probability at least $\epsilon(\epsilon - 2^{-t})$, we
    expect it to give us a valid $s'$.  Let $u' = (m' \xor r) \bmod q$.
    \begin{itemize}
    \item If $s A + u P \ne s' A + u' P$ then we have a hash collision.  So
      assume $s a + u = s' a + u'$.
    \item We chose $m \ne m'$, so $u = r \xor m \ne r \xor m' = u'$.  We'd
      notice if $a = 0$, so $s \ne s'$.
    \item Therefore, we can derive
      \[ a = \frac{u' - u}{s - s'}. \]
    \end{itemize}
    So our fake prover can compute discrete logs.
  \end{itemize}
\end{slide}
It's worth proving the probability given above.  I use the approach of
K\"asper, Laur and Lipmaa [KLL06].

Let's consider first a simple setting.  Let $U$ and $V$ be two finite sets,
and let $G \subseteq U \times V$ be a set of `good pairs'.  Suppose that $|G|
= \epsilon |U| |V|$, i.e.,
\[ \Pr[(u, v) \getsr U \times V : (u, v) \in G] = \epsilon. \]
We now perform the following simple experiment.  Choose $u$ and $v$ uniformly
at random from $U$ and $V$ respectively.  If $(u, v) \notin G$, then give up.
Otherwise, choose $v' \inr V$.  If $(u, v') \in G$ and $v' \ne v$ then we
win.  What's the probability that we win?

Some more notation would be handy.  For each $u \in U$, let $G_u = \{\, v \in
V \mid (u, v) \in G \,\}$, and $n_u = |G_u|$.  Then
\[ |G| = \sum_{u \in U} n_u. \]
Suppose we're given $(u, v) \inr G$, and $v' \inr V$.  We want $\Pr[v' \in
G_u \setminus \{v\}]$.  Well,
\begin{eqnarray*}[rl]
  \Pr[v \in G_u]
  & =   \sum_{u^* \in U} \Pr[v' \in G_{u^*} \setminus \{v\}] \Pr[u = u^*] \\
  & \ge \sum_{u^* \in U} \frac{n_{u^*} - 1}{|V|} \frac{n_{u^*}}{|G|} \\
  & =   \sum_{u^* \in U} \frac{n_{u^*}^2 - n_{u^*}}{|V| |G|}
\end{eqnarray*}

This is unpleasant, but the following lemma will sort us out.
\begin{lemma}
  Let $s_0$, $s_1$, \dots, $s_{n-1}$ be given, such that $\sum_{0 \le i < n}
  s_i = t$.  Then $\sum_{0 \le i < n} s^2$ is minimum when $s_i = t/n$ for
  all $0 \le i < n$.
\end{lemma}
\begin{proof}
  The proof is by induction.  If $n = 1$, the lemma is obviously true.  Let
  $s_i$ be given for $0 < i < n + 1$ be given, so that $\sum_i s_i = t$; we
  claim that $\sum_i s_i^2$ is minimum when $s_i = t/(n + 1)$ for all $i$.

  Without loss of generality, suppose that $s_n \ge s_i$ for $0 \le i < n$.
  Using the induction hypothesis, $\sum_{0\le i<n} s_i^2$ is minimum when
  $s_i = (t - s_n)/n$ for all $i < n$.  Let $s = s_n$.  Then
  \begin{eqnarray*}[rl]
    \sum_{0 \le i \le n} s_i^2
    & = s^2 + \sum_{0 \le i < n} \biggl( \frac{t - s}{n} \biggr)^2\\
    & = s^2 + n \biggl( \frac{t^2 - 2 s t + s^2}{n^2} \biggr) \\
    & = \frac{1}{n} \bigl(t^2 - 2 s t + s^2 (1 + n)\bigr).
  \end{eqnarray*}
  This is minimum when
  \[ \frac{\d}{\d s} \bigl( t^2 - 2 s t + s^2 (1 + n) \bigr) =
     2 s (1 + n) - 2 t = 0 \]
  i.e., when
  \[ s = \frac{t}{n + 1} \]
  as claimed.
\end{proof}

Recall that $\sum_{u^*} n_{u^*} = |G|$.  The lemma tells us that
\[ \sum_{u^* \in U} n_{u^*}^2 \ge \frac{|G|^2}{|U|}. \]
Returning to our calculation, then:
\[ \Pr[v \in G_u]
   \ge \sum_{u^* \in U} \frac{n_{u^*}^2 - n_{u^*}}{|V| |G|} \\
   \ge \frac{|G|}{|U| |V|} - \frac{1}{|V|}\\
   =   \epsilon - \frac{1}{|V|}.
\]

Now we have to apply this to the KCDSA impersonation problem.  Let $U$ be the
set of choices of public key $X$, adversary's random decisions, and the
answers to the adversary's random-oracle queries.  This is finite, since the
running time of the adversary is bounded.  Let $V = \Bin^t$ be the space of
our possible challenges.  Let $G$ be the set of `good' pairs, where the
adversary successfully outputs a forgery.  The probability that the adversary
impersonates the first time is $\epsilon$.  If this happens, we rewind and
give a different response.  Since we hold everything else fixed, the
adversary's $r$ is the same.  We choose a new $m' \ne m$ and give it to the
adversary.  Finally, the analysis we did above tells us that the probability
that the adversary successfully forges again is at least $\epsilon - 2^{-t}$.
The stated result follows.
    
\begin{slide}
  \head{Zero-knowledge \seq: KCDSA as identification protocol (cont.)}

  \begin{itemize}
  \item Zero-knowledge: we need a simulator.  We work in the random oracle
    model.  The simulator is allowed to make up bits of the random oracle.
    \begin{enumerate}
    \item Simulator chooses $r \inr \Bin^t$ at random, and gives $r$ to the
      verifier.
    \item Simulator runs verifier, and is given $m$.
    \item Simulator computes $u = (r \xor m) \bmod q$, and chooses $s \inr
      \F_q$ at random.
    \item If verifier has already queried $H(s A + u X)$, then we abort and
      try again.  Otherwise, it arranges that $H(s A + u X) = r$.
    \end{enumerate}
    If the verifier makes $n$ random oracle queries, the failure only occurs
    with probability $n/q$.
  \end{itemize}
\end{slide}


\begin{slide}
  \head{Zero-knowledge \seq: complexity theory and ZK}

  A \emph{language} $L \subseteq \Bin^*$ is a set of bit-strings.

  A \emph{polynomial-time Turing machine} is a machine for which there is a
  polynomial $p(\cdot)$ such that, on any input $x \in \Bin^*$, it always
  halts within $p(|x|)$ steps.

  A language $L \in \mathbf{P}$ if there is a polynomial-time Turing machine
  $M$ such that $M(x) = 1$ iff $x \in L$.

  A language $L \in \mathbf{NP}$ if there is a language $L' \in \mathbf{P}$
  and, for any $x$, a $w$ such that $|w| \le \poly(|x|)$ and $(x, w) \in L'$
  iff $x \in L$.  The $w$ is a \emph{witness}.

  Zero-knowledge proof systems exist for all languages in $\mathbf{NP}$.
  Example statements:
  \begin{itemize}
  \item Two ciphertexts are encryptions of the same plaintext.
  \item A ciphertext is the encryption of a given plaintext.
  \end{itemize}
\end{slide}

\xcalways\subsection{Key-exchange security}\x

\begin{slide}
  \resetseq
  \head{Key-exchange \seq: introduction}
  \topic{introduction}

  Key-exchange seems very difficult.  Many protocols have subtle weaknesses.
  It would be nice to `prove' security.  There are two approaches:
  \begin{enumerate}
  \item Express messages and beliefs of the participants in a formal logic,
    and use inference rules to show that the participants believe the right
    things at the end [BAN88, Jac97].  This works if the inference rules are
    correct, and the protocol is translated correctly.
  \item Define a model for communication and a notion of security, and bound
    the probability that any adversary within the model can defeat the
    security of the protocol [BR93, BR95, BJM97, BM97, BCK98, Sho99, CK01].
    OK if the security notion is right, and the adversary considered is
    sufficiently powerful.
  \end{enumerate}
  Second approach can give useful, quantitative results, if we believe the
  model is good.
\end{slide}

\begin{slide}
  \head{Key-exchange \seq: introduction}

  We describe the model of Canetti and Krawczyk [CK01] and their notion of
  \emph{SK-security}.
  \begin{itemize}
  \item Earlier models were either too restrictive ([BR93] \emph{matching
    conversations}, [Sho99] termination requirement) or flawed ([BR93]
    again).
  \item\relax [CK01] shows that SK-security suffices for implementing
    \emph{secure channels} in a plausible model.
  \item\relax [CK02] shows that SK-security is equivalent to a (slightly
    relaxed) notion of security (`implementation of ideal functionality') in
    Canetti's \emph{Universal Composition} (UC) framework [Can01], and can be
    used to implement UC-secure channels.
  \end{itemize}
\end{slide}

\begin{slide}
  \head{Key-exchange \seq: model -- basics}
  \topic{model}

  There are two kinds of \emph{participants}:
  \begin{itemize}
  \item a number of \emph{parties}, $P_0$, $P_1$, \ldots, $P_{n-1}$, and
  \item an \emph{adversary}.
  \end{itemize}
  A protocol $\Pi$ defines an \emph{initialization function} $I$, which
  outputs:
  \begin{itemize}
  \item a common input $c$ for all participants (all parties and the
    adversary), and
  \item a private input $x_i$ for party $P_i$.
  \end{itemize}
\end{slide}

\begin{slide}
  \head{Key-exchange \seq: model -- sessions}

  Protocol execution occurs in \emph{sessions}.  A session $S = (P_i, P_j,
  s)$ specifies
  \begin{itemize}
  \item an \emph{owner} $P_i$ -- the session knows $P_i$'s secret input
    $x_i$;
  \item a \emph{partner} $P_j$; and
  \item a \emph{session-id} $s \in \Bin^{\ell_S}$.
  \end{itemize}
  The adversary can create sessions at will, by specifying $(i, j, s)$.

  Restriction: sessions must be \emph{distinct}.

  A pair of sessions $S = (P_i, P_j, s)$ and $T = (P_j, P_i, s)$ are said to
  be \emph{matching}.
\end{slide}

\begin{slide}
  \head{Key-exchange \seq: model -- communication}

  When a session is created, it may output a message to be sent to its
  matching session.

  The \emph{adversary} is responsible for delivering all messages.

  When a message is delivered to a session, the session may output
  another message.  It may also \emph{terminate}, either successfully
  (outputting a session-key $K$ -- \emph{completing}), or unsuccessfully
  (\emph{aborting}).

  A session which has been created and has not terminated is \emph{running}.
\end{slide}

\begin{slide}
  \head{Key-exchange \seq: model -- the adversary}

  As well as creating sessions and delivering messages, the adversary has
  other capabilities.
  \begin{itemize}
  \item It can \emph{expire} a completed session, wiping out any record of
    its key.
  \item It can \emph{reveal the state} of a running session.
  \item It can \emph{reveal the key} of a completed, unexpired session.
  \item It can \emph{corrupt} a party, learning all of its internal state,
    including its long-term secret, the states of its running sessions, etc.
  \end{itemize}
  A session is \emph{locally exposed} if its state or key has been revealed,
  or if its owner has been corrupted.  A session is \emph{exposed} if it is
  locally exposed, or it has a matching session which is exposed.
\end{slide}

\begin{slide}
  \head{Key-exchange \seq: model -- session life cycle}

  \[ \def\node#1{%
       \vbox{%
       \def\\{\small\crcr}%
       \halign{\hfil\ignorespaces##\unskip\hfil\cr#1\crcr}%
     }}
     \begin{xy}
       \xygraph{
         *+[F]\node{Create session $(i, j, s)$}
         :[d]
         *+[F:<6pt>]\node{\bf Running\\(send message $\mu$)} ="run"
         [d]
         *+[F]\node{Deliver message $\mu'$} ="msg"
         "msg" :[dll]
         *+[F:<6pt>]\node{\bf Complete\\(output key $K$)}
         :[d]
         *+[F]\node{Expire session}
         :[d]
         *+[F:<6pt>]\node{\bf Expired}
         "msg" :[drr]
         *+[F:<6pt>]\node{\bf Aborted\\(no output)}
       }
       \ar @{->} @<1em> "run"; "msg"
       \ar @{->} @<1em> "msg"; "run"
     \end{xy} \]
\end{slide}

\begin{slide}
  \head{Key-exchange \seq: model -- SK-security}

  We play a game with the adversary.  At the beginning, we choose a `hidden
  bit' $b^* \inr \Bin$.

  The adversary can choose a \emph{challenge session} -- any completed,
  unexposed session.  If $b^* = 1$, we give the adversary the session's key,
  just as if it revealed it.  If $b^* = 0$, we give the adversary a
  freshly-generated random key.

  The adversary may continue to create sessions, deliver messages, etc., but
  may not \emph{expose} the challenge session.  When it finishes, the
  adversary outputs a \emph{guess} $b$.

  A key-exchange protocol $\Pi$ is \emph{SK-secure} if no adversary can
  \begin{itemize}
  \item with non-negligible probability, cause two matching, unexposed
    sessions to \emph{accept}, but output different keys, or
  \item with probability non-negligibly greater than $\frac{1}{2}$, guess the
    \emph{hidden bit}, i.e., $b = b^*$.
  \end{itemize}
\end{slide}

\begin{slide}
  \head{Key-exchange \seq: deniability}
  \topic{deniability}

  Many key-exchange protocols use digital signatures.  For example:
  \begin{protocol}
    Alice & Bob \\
    (Private key $\id{sk}_A$, public key $\id{pk}_A$) &
    (Private key $\id{sk}_B$, public key $\id{pk}_B$) \\[\medskipamount]
    $r_A \getsr \Nupto{|G|}$; & $r_B \getsr \Nupto{|G|}$; \\
    $R_A \gets r_A P$; & $R_B \gets r_B P$; \\
    \send{->}{R_A}
    \send{<-}{R_B}
    $\sigma_A \gets
      S(\id{sk}_A, \texttt{Alice}, \texttt{Bob}, s, R_A, R_B)$; &
    \llap{$\sigma_B \gets
      S(\id{sk}_B, \texttt{Bob}, \texttt{Alice}, s, R_B, R_A)$;} \\
    \send{->}{\sigma_A}
    \send{<-}{\sigma_B}
    Check: $V(\id{pk}_B, \sigma_B, \texttt{Bob}, \texttt{Alice}, s, R_B,
    R_A)$
    \\ &
    \llap{Check: $V(\id{pk}_A, \sigma_A,
      \texttt{Alice}, \texttt{Bob}, s, R_A, R_B)$}
  \end{protocol}
\end{slide}

\begin{slide}
  \head{Key-exchange \seq: deniability (cont.)}

  Signatures have the property than anyone can verify them.  So we could
  later prove, to a judge maybe, that Alice and Bob were communicating.

  This is \emph{bad} if you don't want to leave evidence that you were
  communicating with someone.

  A key-exchange protocol is \emph{deniable} if there's a simulator which
  produces fake transcripts indistinguishable from real conversations
  \begin{itemize}
  \item \emph{without} being given the private keys of the parties involved,
    and
  \item even if some of the participants are corrupt.
  \end{itemize}
\end{slide}

\endinput

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "wrslides"
%%% End: