1 \xcalways\section{Cryptographic background
}\x
3 \xcalways\subsection{Groups
}\x
7 \head{Groups
\seq: definition
}
10 A
\emph{group
} is a set $G$ of objects, and a binary operation $
\op$, with
11 the following properties.
13 \item [Closure
] If $a$ and $b$ are elements of $G$, then so is $a
\op b$.
14 \item [Associativity
] For any $a$, $b$ and $c$ in $G$,
15 \
[ a
\op (b
\op c) = (a
\op b)
\op c. \
]
16 \item [Identity
] There exists an element $e$ so that, for any $a$ in $G$,
17 \
[ a
\op e = a = e
\op a. \
]
18 \item [Inverses
] For any $a$ in $G$, there exists a $b$ so that
19 \
[ a
\op b = e = b
\op a. \
]
24 \head{Groups
\seq: abelian groups
}
26 A group $(G,
\op)$ is
\emph{commutative
}, or
\emph{abelian
}, if it has the
27 following additional property.
29 \item [Commutativity
] For any $a$ and $b$ in $G$,
30 \
[ a
\op b = b
\op a. \
]
32 We usually write the operator of an abelian group using some familiar
33 symbol, like $+$ or $
\times$.
37 \head{Groups
\seq: notation
}
39 Let $(G, +)$ be a group written additively. For $A, B
\in G$, we do the
40 obvious things and write $
0_G$, or just $
0$, for the identity, and $-A$ for
41 the inverse of $A$; we also write
42 \
[ A - B
\equiv A + (- B)
\qquad
43 2 A
\equiv A + A
\qquad
44 n A
\equiv \underbrace{A + A +
\cdots + A
}_
\text{$n$ times
}.
46 Similarly, if $(H,
\times)$ is a group written multiplicatively, and
47 $
\alpha,
\beta \in H$, we do the obvious things and write $
1_H$, or just
48 $
1$, for the identity, and $
\alpha^
{-
1}$ for the inverse of $
\alpha$; we
50 \
[ \alpha \beta \equiv \alpha \times \beta \qquad
51 \alpha/
\beta \equiv \alpha \times \beta^
{-
1} \qquad
52 \alpha^
2 \equiv \alpha \times \alpha \qquad
53 \alpha^n
\equiv \underbrace{\alpha \times \alpha \times \cdots
54 \alpha}_
\text{$n$ times
}.
56 The number of elements of a group $G$ is written $|G|$ (or sometimes
57 $\#G$), and is called the
\emph{order
} of $G$.
61 \head{Groups
\seq: cyclic groups and discrete logs
}
62 \topic{cyclic groups and discrete logs
}
64 A
\emph{cyclic
} group $(G, +)$ consists only of elements $n P$ for a single
65 $P$ and varying $n
\in \Z$. We call $P$ a
\emph{generator
} of the group.
67 Cyclic groups are always abelian.
69 If $G$ is finite, then for any $A
\in G$, there is a
\emph{unique
} $a
\in
70 \Nupto{|G|
}$ for which $A = a P$. We call $a$ the
\emph{discrete
71 logarithm
} of $A$ to the base $P$.
73 This makes more sense if you consider a multiplicative group $(H,
\times)$.
74 Then there's a $
\gamma \in H$, and for any $
\alpha$, a unique $a
\in
75 \Nupto{|H|
}$ such that $
\alpha =
\gamma^a$.
77 Computing discrete logs seems to be difficult in some kinds of groups.
81 \head{Groups
\seq: Diffie-Hellman
}
82 \topic{Diffie-Hellman
}
84 Fix some cyclic group $(G, +)$, with generator $P$.
86 Alice & Bob \\
[\medskipamount]
87 $a
\getsr \Nupto{|G|
}$; & $b
\getsr \Nupto{|G|
}$; \\
88 $A
\gets a P$; & $B
\gets b P$; \\
91 $Z
\gets a B$; & $Z
\gets b A$;
94 \
[ Z = a B = a (b P) = (a b) P = (b a) P = b (a P) = b A. \
]
95 Computing $a b P$ from $a P$ and $b P$ seems hard. This is the
96 (computational)
\emph{Diffie-Hellman
} problem.
98 The best way we know is to work out $a$ or $b$ -- i.e., extract a discrete
103 \head{Groups
\seq: ElGamal encryption
}
104 \topic{ElGamal encryption
}
106 Suppose $H
\colon G
\to \Bin^n$ is a secure hash function. Alice has a
107 private key~$a
\in \Nupto{|G|
}$. Bob knows her public key~$A = a P$. He
108 has an $n$-bit message $m$ he wants to send her.
110 \item He chooses $r
\inr \Nupto{|G|
}$.
111 \item He computes $R = r P$.
112 \item He computes $Z = r A$.
113 \item He sends Alice the pair $(R, m
\xor H(Z))$.
115 Alice can decrypt because
116 \
[ a R = (a r) P = r A = Z. \
]
120 \head{Groups
\seq: Schnorr groups
}
123 Let $p$ and $q$ be prime, with $p = q f +
1$. The residues modulo $p$ form
124 a
\emph{finite field
} $
\F_p$. The nonzero elements form a cyclic group
125 $
\F_p^*$ under multiplication mod~$p$. Let $
\eta$ be a generator of
128 Set $
\gamma =
\eta^f$. Then
129 \
[ G =
\langle \gamma \rangle = \
{\,
\gamma^n
\mid 0 \le n < q \,\
} \
]
130 is a
\emph{Schnorr group
} of $q$ elements. $G$ is cyclic, with generator
133 In practice, you don't need to find $
\eta$. Pick $
\alpha \in \F_p^*$
134 arbitrarily (
2 is a good first choice); if $
\alpha^f
\ne 1$ then use
139 \head{Groups
\seq: elliptic curves
}
141 Let $q = p^f$ be a prime power. Then there is a finite field $
\F_q$ with
144 Let $E$ be an
\emph{elliptic curve
} over $
\F_q$:
145 \
[ E(
\F_q) = \
{\, (x, y)
\in \F_q^
2 \mid y^
2 = x^
3 + a x + b \,\
} \
]
146 \begin{tabularx
}{\linewidth}{@
{}Xl
}
148 The points of $E(
\F_q)$ form a group with a peculiar kind of addition
152 If $\#E(
\F_q)$ has a large prime factor then we can
153 use a cyclic subgroup of $E(
\F_q)$. The details are complicated
\dots
155 \vtop{\hrule height
0pt
\hbox{
157 \includegraphics[scale =
0.6]{ecc-
0.pdf
}
159 \includegraphics[scale =
0.6]{ecc
.0}
166 \xcalways\subsection{Bilinear maps
}\x
170 \head{Bilinear maps
\seq: definition
}
173 Let $(G, +)$, $(G', +)$ and $(G_T,
\times)$ be three cyclic groups with the
174 same order. Let $P$ and $P'$ generate $G$ and $G'$ respectively.
176 A map $
\hat{e
}\colon G
\times G'
\to G_T$ is
\emph{bilinear
} if
178 \item for any $R
\in G$ and $S', T'
\in G'$,
179 \
[ \hat{e
}(R, S' + T') =
\hat{e
}(R, S') \,
\hat{e
}(R, T'), \
]
181 \item for any $R, S
\in G$ and $T'
\in G'$,
182 \
[ \hat{e
}(R + S, T') =
\hat{e
}(R, T') \,
\hat{e
}(S, T'). \
]
184 We say that $
\hat{e
}$ is
\emph{non-degenerate
} if
185 \
[ \hat{e
}(P, P')
\ne 1. \
]
189 \head{Bilinear maps
\seq: properties
}
193 \
[ \gamma =
\hat{e
}(P, P'). \
]
194 Then $
\gamma$ generates $G_T$.
197 \
[ \hat{e
}(a P, b P') =
\gamma^
{a b
}. \
]
198 If $
\hat{e
}$ is easy to compute then this is like a Diffie-Hellman
199 computation combined with an isomorphism to a different group.
203 \head{Bilinear maps
\seq: the Bilinear Diffie-Hellman problem
}
204 \topic{bilinear Diffie-Hellman problem
}
206 The
\emph{bilinear
} Diffie-Hellman problem is this: given
208 \item $a P$ and $b P$ in $G$, and
209 \item $a P'$ and $c P'$ in $G'$,
212 \
[ \zeta =
\gamma^
{abc
}. \
]
214 This can be done if the Diffie-Hellman problem can be solved in
\emph{any
}
215 of $G$, $G'$ or $G_T$.
217 \item If DHP easy in $G$, then compute $
\zeta =
\hat{e
}(a b P, c P')$.
218 \item If DHP easy in $G'$, then compute $
\zeta =
\hat{e
}(b P, a c P')$.
219 \item If DHP easy in $G_T$, then compute $
\alpha =
\hat{e
}(a P, P') =
220 \gamma^a$, $
\beta =
\hat{e
}(b P, c P') =
\gamma^
{b c
}$ and $
\zeta$ from
221 $
\alpha$ and $
\beta$.
226 \head{Bilinear maps
\seq: Boneh-Franklin identity-based encryption
}
227 \topic{Boneh-Franklin identity-based encryption
}
229 We need two hashes: $H
\colon G_T
\to \Bin^n$ and $H_
\text{id
} \colon
232 There is a
\emph{trusted third party
}. It has a private key $t
\inr
233 \Nupto{|G|
}$ and a public key $T = t P$.
235 Alice's public key is $A = H_
\text{id
}(
\texttt{Alice
})$. Her private key
238 Bob wants to send Alice a message $m
\in \Bin^n$.
240 \item He chooses $r
\inr \Nupto{|G|
}$.
241 \item He computes $R = r P$.
242 \item He computes $
\psi =
\hat{e
}(T, A)^r$.
243 \item He sends Alice the pair $(R, m
\xor H(
\psi))$.
245 Alice can decrypt because
246 \
[ \hat{e
}(R, K_A) =
\hat{e
}(r P, t A)
254 \head{Bilinear maps
\seq: examples
}
257 The major examples of bilinear maps are the
\emph{Weil
} and
\emph{Tate
258 pairings
} on torsion groups of elliptic curves.
262 \xcalways\subsection{Zero-knowledge
}\x
266 \head{Zero-knowledge
\seq: interactive proofs
}
267 \topic{interactive proofs
}
269 Prover and verifier exchange messages. Verifier decides whether to
270 \emph{accept
} or
\emph{reject
} the proof.
272 An interactive proof system must have the following properties.
274 \item [Completeness
] If the prover is honest, the verifier (almost always)
276 \item [Soundness
] If the prover is
\emph{dishonest
}, the verifier
279 Repeat protocol several times to reduce soundness error.
283 \head{Zero-knowledge
\seq: simulation
}
286 We have a prover $P$ and a verifier $V$. Write
288 to mean that $V$ outputs $x$ after interacting with $P$.
290 Suppose that there is a simulator~$S$ so that, for all $y$,
291 \
[ |
\Pr[x
\gets V^P() : x = y
] -
\Pr[x
\gets S() : x = y
]|
\le \epsilon. \
]
292 If $
\epsilon$ is small, then $V$ is unlikely to be able to persuade anyone
293 that he learned anything from $P$.
295 in particular, if $
\epsilon =
0$ then we say that the proof has
296 \emph{perfect zero knowledge
}.
300 \head{Zero-knowledge
\seq: an example
}
303 Prover $P$ knows that $
\alpha =
\beta^
2 \in \Z/n
\Z$ for some composite $n$.
305 Prover $P$ & Verifier $V$ \\
[\medskipamount]
306 $
\gamma \getsr \Z/n
\Z$; \\
307 \send{->
}{\kappa =
\gamma^
2 \alpha}
308 \send{<-
}{c
\inr \Bin}
309 \send{->
}{\rho =
\gamma \beta^c
}
310 & Check: $
\kappa =
\rho^
2 \alpha^
{1 - c
}$
315 \
[ \rho \alpha^
{1 - c
} = (
\gamma \beta^c)^
2 \alpha^
{1 - c
}
316 =
\gamma^
2 \beta^
{2c
} \alpha^
{1 - c
}
317 =
\gamma^
2 \alpha^c
\alpha^
{1 - c
}
321 \item Soundness: if $P^*$ convinces $V$ with probability $p >
\frac{1}{2}$
322 then we can, in theory, run $P^*$ with (say) $c =
0$ and get $
\gamma$.
323 We then
\emph{rewind
} $P^*$, give it $c =
1$, and get $
\gamma \beta$,
324 from which we compute $
\beta$. This works with probability at least $
2
329 This statement could use some proof.
331 Firstly, consider a simple abstract game. There is a secret table, with two
332 columns and $r$ rows. Exactly $n$ of the entries in the table contain $
1$;
333 the remaining entries contain zero. We have to pick a row, and you win if
334 both entries in that row contain $
1$.
336 Clearly, if $n
\le r$, it's possible to arrange the ones so that each is in a
337 different row. If we're playing against someone unscrupulous, we are
340 On the other hand, if $n > r$, there must be a winning row, because there are
341 too many ones to fit otherwise. In fact, there must be at least $n - r$
342 winning rows. So our probability of winning must be at least $(n - r)/r$.
344 Apply this to the problem of our dishonest prover. The `table''s rows are
345 indexed by all the possible inputs to the prover -- the value $
\alpha$ and
346 its own internal coin tosses. (We only consider provers running in bounded
347 time, so these are finite.) The columns are indexed by our coin $c$. We
348 know that $
2 r p$ of the entries contain $
1$. Hence, the probability that we
350 \
[ \frac{2 r p - r
}{r
} =
2 \biggl( p -
\frac{1}{2} \biggr). \
]
353 \head{Zero-knowledge
\seq: an example (cont.)
}
355 We now show zero-knowledge, by describing a simulator.
357 \item Simulator chooses $
\rho \inr \Z/n
\Z$ and $b
\inr \Bin$ at random. It
358 runs $V$ and sends it $
\kappa =
\rho \alpha^
{1 - b
}$.
359 \item Verifier runs, returns bit $c$.
360 \item If $b = c$ then simulator sends back $
\rho$. If $b
\ne c$ then
361 simulator gives up and tries again.
362 \item Verifier (presumably) accepts, because
363 \
[ \rho \alpha^
{1 - c
} =
\rho \alpha^
{1 - b
}. \
]
365 Simulator fails (and retries) with probability $
\frac{1}{2}$, because $b$
366 is uniform and independent of $c$.
370 \head{Aside on KCDSA
}
373 Let $(G, +)$ be a cyclic group of prime order $q$, with generator $P$. Let
374 $H
\colon G
\to \Bin^t$ and $H'
\colon \Bin^*
\to \Bin^t$ be cryptographic
377 Alice's private key is $a
\inr \F_q$. Her public key is $A = a P$.
378 Suppose Alice wants to sign a message $m
\in \Bin^*$.
380 \item She chooses a random $k
\inr \F_q$. She computes $K = k P$, and $r =
382 \item Computes $h = H'(m)$, and $u = (h
\xor r)
\bmod q$.
383 \item Finally, she computes $s = (k - u)/a$.
385 Her signature on $m$ is $
\sigma = (r, s)$.
387 To verify $(r, s)$, Bob can compute $h = H'(m)$; he checks that
388 \
[ r = H(s A + u P). \
]
389 Note that $s a = k - u$, so $s a + u = k$. Hence $s A + u P = (s
394 \head{Zero-knowledge
\seq: KCDSA as identification protocol
}
396 As before, let $(G, +)$ be a cyclic group, generated by $P$, of prime order
397 $q$, and let $H
\colon G
\to \Bin^t$ be a cryptographic hash function.
400 (private key $a
\inr \F_q$) & (public key $A = a P$) \\
[\medskipamount]
401 $k
\getsr \F_q$; $K
\gets k P$; \\
403 \send{<-
}{m
\inr \Bin^
{t
}}
404 $u
\gets (r
\xor m)
\bmod q$; & $u
\gets (r
\xor m)
\bmod q$; \\
405 \send{->
}{s = (k - u)/x
}
406 & Check: $r = H(s A + u P)$
411 \head{Zero-knowledge
\seq: KCDSA as identification protocol (cont.)
}
414 \item Completeness: as for the KCDSA signature scheme.
415 \item Soundness: suppose some prover manages to impersonate Alice with
416 probability $
\epsilon >
2^
{-t
}$. We choose some $m$ and send it to the
417 prover, getting $s$. Now we
\emph{rewind
} the prover and send it some
418 $m'
\ne m$. With probability at least $
\epsilon(
\epsilon -
2^
{-t
})$, we
419 expect it to give us a valid $s'$. Let $u' = (m'
\xor r)
\bmod q$.
421 \item If $s A + u P
\ne s' A + u' P$ then we have a hash collision. So
422 assume $s a + u = s' a + u'$.
423 \item We chose $m
\ne m'$, so $u = r
\xor m
\ne r
\xor m' = u'$. We'd
424 notice if $a =
0$, so $s
\ne s'$.
425 \item Therefore, we can derive
426 \
[ a =
\frac{u' - u
}{s - s'
}. \
]
428 So our fake prover can compute discrete logs.
431 It's worth proving the probability given above. I use the approach of
432 K\"asper, Laur and Lipmaa
[KLL06
].
434 Let's consider first a simple setting. Let $U$ and $V$ be two finite sets,
435 and let $G
\subseteq U
\times V$ be a set of `good pairs'. Suppose that $|G|
436 =
\epsilon |U| |V|$, i.e.,
437 \
[ \Pr[(u, v)
\getsr U
\times V : (u, v)
\in G
] =
\epsilon. \
]
438 We now perform the following simple experiment. Choose $u$ and $v$ uniformly
439 at random from $U$ and $V$ respectively. If $(u, v)
\notin G$, then give up.
440 Otherwise, choose $v'
\inr V$. If $(u, v')
\in G$ and $v'
\ne v$ then we
441 win. What's the probability that we win?
443 Some more notation would be handy. For each $u
\in U$, let $G_u = \
{\, v
\in
444 V
\mid (u, v)
\in G \,\
}$, and $n_u = |G_u|$. Then
445 \
[ |G| =
\sum_{u
\in U
} n_u. \
]
446 Suppose we're given $(u, v)
\inr G$, and $v'
\inr V$. We want $
\Pr[v'
\in
447 G_u
\setminus \
{v\
}]$. Well,
448 \begin{eqnarray*
}[rl
]
450 & =
\sum_{u^*
\in U
} \Pr[v'
\in G_
{u^*
} \setminus \
{v\
}] \Pr[u = u^*
] \\
451 &
\ge \sum_{u^*
\in U
} \frac{n_
{u^*
} -
1}{|V|
} \frac{n_
{u^*
}}{|G|
} \\
452 & =
\sum_{u^*
\in U
} \frac{n_
{u^*
}^
2 - n_
{u^*
}}{|V| |G|
}
455 This is unpleasant, but the following lemma will sort us out.
457 Let $s_0$, $s_1$,
\dots, $s_
{n-
1}$ be given, such that $
\sum_{0 \le i < n
}
458 s_i = t$. Then $
\sum_{0 \le i < n
} s^
2$ is minimum when $s_i = t/n$ for
462 The proof is by induction. If $n =
1$, the lemma is obviously true. Let
463 $s_i$ be given for $
0 < i < n +
1$ be given, so that $
\sum_i s_i = t$; we
464 claim that $
\sum_i s_i^
2$ is minimum when $s_i = t/(n +
1)$ for all $i$.
466 Without loss of generality, suppose that $s_n
\ge s_i$ for $
0 \le i < n$.
467 Using the induction hypothesis, $
\sum_{0\le i<n
} s_i^
2$ is minimum when
468 $s_i = (t - s_n)/n$ for all $i < n$. Let $s = s_n$. Then
469 \begin{eqnarray*
}[rl
]
470 \sum_{0 \le i
\le n
} s_i^
2
471 & = s^
2 +
\sum_{0 \le i < n
} \biggl(
\frac{t - s
}{n
} \biggr)^
2\\
472 & = s^
2 + n
\biggl(
\frac{t^
2 -
2 s t + s^
2}{n^
2} \biggr) \\
473 & =
\frac{1}{n
} \bigl(t^
2 -
2 s t + s^
2 (
1 + n)
\bigr).
476 \
[ \frac{\d}{\d s
} \bigl( t^
2 -
2 s t + s^
2 (
1 + n)
\bigr) =
477 2 s (
1 + n) -
2 t =
0 \
]
479 \
[ s =
\frac{t
}{n +
1} \
]
483 Recall that $
\sum_{u^*
} n_
{u^*
} = |G|$. The lemma tells us that
484 \
[ \sum_{u^*
\in U
} n_
{u^*
}^
2 \ge \frac{|G|^
2}{|U|
}. \
]
485 Returning to our calculation, then:
487 \ge \sum_{u^*
\in U
} \frac{n_
{u^*
}^
2 - n_
{u^*
}}{|V| |G|
} \\
488 \ge \frac{|G|
}{|U| |V|
} -
\frac{1}{|V|
}\\
489 =
\epsilon -
\frac{1}{|V|
}.
492 Now we have to apply this to the KCDSA impersonation problem. Let $U$ be the
493 set of choices of public key $X$, adversary's random decisions, and the
494 answers to the adversary's random-oracle queries. This is finite, since the
495 running time of the adversary is bounded. Let $V =
\Bin^t$ be the space of
496 our possible challenges. Let $G$ be the set of `good' pairs, where the
497 adversary successfully outputs a forgery. The probability that the adversary
498 impersonates the first time is $
\epsilon$. If this happens, we rewind and
499 give a different response. Since we hold everything else fixed, the
500 adversary's $r$ is the same. We choose a new $m'
\ne m$ and give it to the
501 adversary. Finally, the analysis we did above tells us that the probability
502 that the adversary successfully forges again is at least $
\epsilon -
2^
{-t
}$.
503 The stated result follows.
506 \head{Zero-knowledge
\seq: KCDSA as identification protocol (cont.)
}
509 \item Zero-knowledge: we need a simulator. We work in the random oracle
510 model. The simulator is allowed to make up bits of the random oracle.
512 \item Simulator chooses $r
\inr \Bin^t$ at random, and gives $r$ to the
514 \item Simulator runs verifier, and is given $m$.
515 \item Simulator computes $u = (r
\xor m)
\bmod q$, and chooses $s
\inr
517 \item If verifier has already queried $H(s A + u X)$, then we abort and
518 try again. Otherwise, it arranges that $H(s A + u X) = r$.
520 If the verifier makes $n$ random oracle queries, the failure only occurs
521 with probability $n/q$.
527 \head{Zero-knowledge
\seq: complexity theory and ZK
}
529 A
\emph{language
} $L
\subseteq \Bin^*$ is a set of bit-strings.
531 A
\emph{polynomial-time Turing machine
} is a machine for which there is a
532 polynomial $p(
\cdot)$ such that, on any input $x
\in \Bin^*$, it always
533 halts within $p(|x|)$ steps.
535 A language $L
\in \mathbf{P
}$ if there is a polynomial-time Turing machine
536 $M$ such that $M(x) =
1$ iff $x
\in L$.
538 A language $L
\in \mathbf{NP
}$ if there is a language $L'
\in \mathbf{P
}$
539 and, for any $x$, a $w$ such that $|w|
\le \poly(|x|)$ and $(x, w)
\in L'$
540 iff $x
\in L$. The $w$ is a
\emph{witness
}.
542 Zero-knowledge proof systems exist for all languages in $
\mathbf{NP
}$.
545 \item Two ciphertexts are encryptions of the same plaintext.
546 \item A ciphertext is the encryption of a given plaintext.
550 \xcalways\subsection{Key-exchange security
}\x
554 \head{Key-exchange
\seq: introduction
}
557 Key-exchange seems very difficult. Many protocols have subtle weaknesses.
558 It would be nice to `prove' security. There are two approaches:
560 \item Express messages and beliefs of the participants in a formal logic,
561 and use inference rules to show that the participants believe the right
562 things at the end
[BAN88, Jac97
]. This works if the inference rules are
563 correct, and the protocol is translated correctly.
564 \item Define a model for communication and a notion of security, and bound
565 the probability that any adversary within the model can defeat the
566 security of the protocol
[BR93, BR95, BJM97, BM97, BCK98, Sho99, CK01
].
567 OK if the security notion is right, and the adversary considered is
568 sufficiently powerful.
570 Second approach can give useful, quantitative results, if we believe the
575 \head{Key-exchange
\seq: introduction
}
577 We describe the model of Canetti and Krawczyk
[CK01
] and their notion of
580 \item Earlier models were either too restrictive (
[BR93
] \emph{matching
581 conversations
},
[Sho99
] termination requirement) or flawed (
[BR93
]
583 \item\relax [CK01
] shows that SK-security suffices for implementing
584 \emph{secure channels
} in a plausible model.
585 \item\relax [CK02
] shows that SK-security is equivalent to a (slightly
586 relaxed) notion of security (`implementation of ideal functionality') in
587 Canetti's
\emph{Universal Composition
} (UC) framework
[Can01
], and can be
588 used to implement UC-secure channels.
593 \head{Key-exchange
\seq: model -- basics
}
596 There are two kinds of
\emph{participants
}:
598 \item a number of
\emph{parties
}, $P_0$, $P_1$,
\ldots, $P_
{n-
1}$, and
599 \item an
\emph{adversary
}.
601 A protocol $
\Pi$ defines an
\emph{initialization function
} $I$, which
604 \item a common input $c$ for all participants (all parties and the
606 \item a private input $x_i$ for party $P_i$.
611 \head{Key-exchange
\seq: model -- sessions
}
613 Protocol execution occurs in
\emph{sessions
}. A session $S = (P_i, P_j,
616 \item an
\emph{owner
} $P_i$ -- the session knows $P_i$'s secret input
618 \item a
\emph{partner
} $P_j$; and
619 \item a
\emph{session-id
} $s
\in \Bin^
{\ell_S}$.
621 The adversary can create sessions at will, by specifying $(i, j, s)$.
623 Restriction: sessions must be
\emph{distinct
}.
625 A pair of sessions $S = (P_i, P_j, s)$ and $T = (P_j, P_i, s)$ are said to
630 \head{Key-exchange
\seq: model -- communication
}
632 When a session is created, it may output a message to be sent to its
635 The
\emph{adversary
} is responsible for delivering all messages.
637 When a message is delivered to a session, the session may output
638 another message. It may also
\emph{terminate
}, either successfully
639 (outputting a session-key $K$ --
\emph{completing
}), or unsuccessfully
642 A session which has been created and has not terminated is
\emph{running
}.
646 \head{Key-exchange
\seq: model -- the adversary
}
648 As well as creating sessions and delivering messages, the adversary has
651 \item It can
\emph{expire
} a completed session, wiping out any record of
653 \item It can
\emph{reveal the state
} of a running session.
654 \item It can
\emph{reveal the key
} of a completed, unexpired session.
655 \item It can
\emph{corrupt
} a party, learning all of its internal state,
656 including its long-term secret, the states of its running sessions, etc.
658 A session is
\emph{locally exposed
} if its state or key has been revealed,
659 or if its owner has been corrupted. A session is
\emph{exposed
} if it is
660 locally exposed, or it has a matching session which is exposed.
664 \head{Key-exchange
\seq: model -- session life cycle
}
669 \halign{\hfil\ignorespaces##
\unskip\hfil\cr#1\crcr}%
673 *+
[F
]\node{Create session $(i, j, s)$
}
675 *+
[F:<
6pt>
]\node{\bf Running\\(send message $
\mu$)
} ="run"
677 *+
[F
]\node{Deliver message $
\mu'$
} ="msg"
679 *+
[F:<
6pt>
]\node{\bf Complete\\(output key $K$)
}
681 *+
[F
]\node{Expire session
}
683 *+
[F:<
6pt>
]\node{\bf Expired
}
685 *+
[F:<
6pt>
]\node{\bf Aborted\\(no output)
}
687 \ar @
{->
} @<
1em> "run"; "msg"
688 \ar @
{->
} @<
1em> "msg"; "run"
693 \head{Key-exchange
\seq: model -- SK-security
}
695 We play a game with the adversary. At the beginning, we choose a `hidden
696 bit' $b^*
\inr \Bin$.
698 The adversary can choose a
\emph{challenge session
} -- any completed,
699 unexposed session. If $b^* =
1$, we give the adversary the session's key,
700 just as if it revealed it. If $b^* =
0$, we give the adversary a
701 freshly-generated random key.
703 The adversary may continue to create sessions, deliver messages, etc., but
704 may not
\emph{expose
} the challenge session. When it finishes, the
705 adversary outputs a
\emph{guess
} $b$.
707 A key-exchange protocol $
\Pi$ is
\emph{SK-secure
} if no adversary can
709 \item with non-negligible probability, cause two matching, unexposed
710 sessions to
\emph{accept
}, but output different keys, or
711 \item with probability non-negligibly greater than $
\frac{1}{2}$, guess the
712 \emph{hidden bit
}, i.e., $b = b^*$.
717 \head{Key-exchange
\seq: deniability
}
720 Many key-exchange protocols use digital signatures. For example:
723 (Private key $
\id{sk
}_A$, public key $
\id{pk
}_A$) &
724 (Private key $
\id{sk
}_B$, public key $
\id{pk
}_B$) \\
[\medskipamount]
725 $r_A
\getsr \Nupto{|G|
}$; & $r_B
\getsr \Nupto{|G|
}$; \\
726 $R_A
\gets r_A P$; & $R_B
\gets r_B P$; \\
730 S(
\id{sk
}_A,
\texttt{Alice
},
\texttt{Bob
}, s, R_A, R_B)$; &
731 \llap{$
\sigma_B \gets
732 S(
\id{sk
}_B,
\texttt{Bob
},
\texttt{Alice
}, s, R_B, R_A)$;
} \\
735 Check: $V(
\id{pk
}_B,
\sigma_B,
\texttt{Bob
},
\texttt{Alice
}, s, R_B,
738 \llap{Check: $V(
\id{pk
}_A,
\sigma_A,
739 \texttt{Alice
},
\texttt{Bob
}, s, R_A, R_B)$
}
744 \head{Key-exchange
\seq: deniability (cont.)
}
746 Signatures have the property than anyone can verify them. So we could
747 later prove, to a judge maybe, that Alice and Bob were communicating.
749 This is
\emph{bad
} if you don't want to leave evidence that you were
750 communicating with someone.
752 A key-exchange protocol is
\emph{deniable
} if there's a simulator which
753 produces fake transcripts indistinguishable from real conversations
755 \item \emph{without
} being given the private keys of the parties involved,
757 \item even if some of the participants are corrupt.
765 %%% TeX-master: "wrslides"