Commit | Line | Data |
---|---|---|
a6e375a6 MW |
1 | \xcalways\section{Cryptographic background}\x |
2 | ||
3 | \xcalways\subsection{Groups}\x | |
4 | ||
5 | \begin{slide} | |
6 | \resetseq | |
7 | \head{Groups \seq: definition} | |
8 | \topic{definitions} | |
9 | ||
10 | A \emph{group} is a set $G$ of objects, and a binary operation $\op$, with | |
11 | the following properties. | |
12 | \begin{description} | |
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. \] | |
20 | \end{description} | |
21 | \end{slide} | |
22 | ||
23 | \begin{slide} | |
24 | \head{Groups \seq: abelian groups} | |
25 | ||
26 | A group $(G, \op)$ is \emph{commutative}, or \emph{abelian}, if it has the | |
27 | following additional property. | |
28 | \begin{description} | |
29 | \item [Commutativity] For any $a$ and $b$ in $G$, | |
30 | \[ a \op b = b \op a. \] | |
31 | \end{description} | |
32 | We usually write the operator of an abelian group using some familiar | |
33 | symbol, like $+$ or $\times$. | |
34 | \end{slide} | |
35 | ||
36 | \begin{slide} | |
37 | \head{Groups \seq: notation} | |
38 | ||
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}. | |
45 | \] | |
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 | |
49 | also write | |
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}. | |
55 | \] | |
56 | The number of elements of a group $G$ is written $|G|$ (or sometimes | |
57 | $\#G$), and is called the \emph{order} of $G$. | |
58 | \end{slide} | |
59 | ||
60 | \begin{slide} | |
61 | \head{Groups \seq: cyclic groups and discrete logs} | |
62 | \topic{cyclic groups and discrete logs} | |
63 | ||
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. | |
66 | ||
67 | Cyclic groups are always abelian. | |
68 | ||
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$. | |
72 | ||
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$. | |
76 | ||
77 | Computing discrete logs seems to be difficult in some kinds of groups. | |
78 | \end{slide} | |
79 | ||
80 | \begin{slide} | |
81 | \head{Groups \seq: Diffie-Hellman} | |
82 | \topic{Diffie-Hellman} | |
83 | ||
84 | Fix some cyclic group $(G, +)$, with generator $P$. | |
85 | \begin{protocol} | |
86 | Alice & Bob \\[\medskipamount] | |
87 | $a \getsr \Nupto{|G|}$; & $b \getsr \Nupto{|G|}$; \\ | |
88 | $A \gets a P$; & $B \gets b P$; \\ | |
89 | \send{->}{A} | |
90 | \send{<-}{B} | |
91 | $Z \gets a B$; & $Z \gets b A$; | |
92 | \end{protocol} | |
93 | This works because | |
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. | |
97 | ||
98 | The best way we know is to work out $a$ or $b$ -- i.e., extract a discrete | |
99 | logarithm. | |
100 | \end{slide} | |
101 | ||
102 | \begin{slide} | |
103 | \head{Groups \seq: ElGamal encryption} | |
104 | \topic{ElGamal encryption} | |
105 | ||
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. | |
109 | \begin{enumerate} | |
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))$. | |
114 | \end{enumerate} | |
115 | Alice can decrypt because | |
116 | \[ a R = (a r) P = r A = Z. \] | |
117 | \end{slide} | |
118 | ||
119 | \begin{slide} | |
120 | \head{Groups \seq: Schnorr groups} | |
121 | \topic{examples} | |
122 | ||
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 | |
126 | $\F_p^*$. | |
127 | ||
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 | |
131 | $\gamma$. | |
132 | ||
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 | |
135 | $\gamma = \alpha^f$. | |
136 | \end{slide} | |
137 | ||
138 | \begin{slide} | |
139 | \head{Groups \seq: elliptic curves} | |
140 | ||
141 | Let $q = p^f$ be a prime power. Then there is a finite field $\F_q$ with | |
142 | $q$ elements. | |
143 | ||
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} | |
147 | \hrule height 0pt | |
148 | The points of $E(\F_q)$ form a group with a peculiar kind of addition | |
149 | (pictured right). | |
150 | \parskip=1ex | |
151 | ||
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 | |
154 | & | |
155 | \vtop{\hrule height 0pt \hbox{ | |
156 | \ifpdf | |
157 | \includegraphics[scale = 0.6]{ecc-0.pdf} | |
158 | \else | |
159 | \includegraphics[scale = 0.6]{ecc.0} | |
160 | \fi | |
161 | }} | |
162 | \end{tabularx} | |
163 | \end{slide} | |
164 | ||
165 | ||
166 | \xcalways\subsection{Bilinear maps}\x | |
167 | ||
168 | \begin{slide} | |
169 | \resetseq | |
170 | \head{Bilinear maps \seq: definition} | |
171 | \topic{definition} | |
172 | ||
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. | |
175 | ||
176 | A map $\hat{e}\colon G \times G' \to G_T$ is \emph{bilinear} if | |
177 | \begin{itemize} | |
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'), \] | |
180 | and | |
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'). \] | |
183 | \end{itemize} | |
184 | We say that $\hat{e}$ is \emph{non-degenerate} if | |
185 | \[ \hat{e}(P, P') \ne 1. \] | |
186 | \end{slide} | |
187 | ||
188 | \begin{slide} | |
189 | \head{Bilinear maps \seq: properties} | |
190 | \topic{properties} | |
191 | ||
192 | Define | |
193 | \[ \gamma = \hat{e}(P, P'). \] | |
194 | Then $\gamma$ generates $G_T$. | |
195 | ||
196 | For any $a$ and $b$: | |
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. | |
200 | \end{slide} | |
201 | ||
202 | \begin{slide} | |
203 | \head{Bilinear maps \seq: the Bilinear Diffie-Hellman problem} | |
204 | \topic{bilinear Diffie-Hellman problem} | |
205 | ||
206 | The \emph{bilinear} Diffie-Hellman problem is this: given | |
207 | \begin{itemize} | |
208 | \item $a P$ and $b P$ in $G$, and | |
209 | \item $a P'$ and $c P'$ in $G'$, | |
210 | \end{itemize} | |
211 | compute | |
212 | \[ \zeta = \gamma^{abc}. \] | |
213 | ||
214 | This can be done if the Diffie-Hellman problem can be solved in \emph{any} | |
215 | of $G$, $G'$ or $G_T$. | |
216 | \begin{itemize} | |
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$. | |
222 | \end{itemize} | |
223 | \end{slide} | |
224 | ||
225 | \begin{slide} | |
226 | \head{Bilinear maps \seq: Boneh-Franklin identity-based encryption} | |
227 | \topic{Boneh-Franklin identity-based encryption} | |
228 | ||
229 | We need two hashes: $H \colon G_T \to \Bin^n$ and $H_\text{id} \colon | |
230 | \Bin^* \to G'$. | |
231 | ||
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$. | |
234 | ||
235 | Alice's public key is $A = H_\text{id}(\texttt{Alice})$. Her private key | |
236 | is $K_A = t A$. | |
237 | ||
238 | Bob wants to send Alice a message $m \in \Bin^n$. | |
239 | \begin{enumerate} | |
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))$. | |
244 | \end{enumerate} | |
245 | Alice can decrypt because | |
246 | \[ \hat{e}(R, K_A) = \hat{e}(r P, t A) | |
247 | = \hat{e}(P, A)^{rt} | |
248 | = \hat{e}(t P, A)^r | |
249 | = \hat{e}(T, A)^r | |
250 | = \psi. \] | |
251 | \end{slide} | |
252 | ||
253 | \begin{slide} | |
254 | \head{Bilinear maps \seq: examples} | |
255 | \topic{examples} | |
256 | ||
257 | The major examples of bilinear maps are the \emph{Weil} and \emph{Tate | |
258 | pairings} on torsion groups of elliptic curves. | |
259 | \end{slide} | |
260 | ||
261 | ||
262 | \xcalways\subsection{Zero-knowledge}\x | |
263 | ||
264 | \begin{slide} | |
265 | \resetseq | |
266 | \head{Zero-knowledge \seq: interactive proofs} | |
267 | \topic{interactive proofs} | |
268 | ||
269 | Prover and verifier exchange messages. Verifier decides whether to | |
270 | \emph{accept} or \emph{reject} the proof. | |
271 | ||
272 | An interactive proof system must have the following properties. | |
273 | \begin{description} | |
274 | \item [Completeness] If the prover is honest, the verifier (almost always) | |
275 | accepts. | |
276 | \item [Soundness] If the prover is \emph{dishonest}, the verifier | |
277 | (sometimes) rejects. | |
278 | \end{description} | |
279 | Repeat protocol several times to reduce soundness error. | |
280 | \end{slide} | |
281 | ||
282 | \begin{slide} | |
283 | \head{Zero-knowledge \seq: simulation} | |
284 | \topic{simulation} | |
285 | ||
286 | We have a prover $P$ and a verifier $V$. Write | |
287 | \[ x \gets V^P() \] | |
288 | to mean that $V$ outputs $x$ after interacting with $P$. | |
289 | ||
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$. | |
294 | ||
295 | in particular, if $\epsilon = 0$ then we say that the proof has | |
296 | \emph{perfect zero knowledge}. | |
297 | \end{slide} | |
298 | ||
299 | \begin{slide} | |
300 | \head{Zero-knowledge \seq: an example} | |
301 | \topic{example} | |
302 | ||
303 | Prover $P$ knows that $\alpha = \beta^2 \in \Z/n\Z$ for some composite $n$. | |
304 | \begin{protocol} | |
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}$ | |
311 | \end{protocol} | |
312 | ||
313 | \begin{itemize} | |
314 | \item Completeness: | |
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} | |
318 | = \gamma^2 \alpha | |
319 | = \kappa. | |
320 | \] | |
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$, | |
dff0fad2 MW |
324 | from which we compute $\beta$. This works with probability at least $2 |
325 | (p - \frac{1}{2})$. | |
a6e375a6 MW |
326 | \end{itemize} |
327 | \end{slide} | |
328 | ||
329 | This statement could use some proof. | |
330 | ||
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$. | |
335 | ||
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 | |
338 | guaranteed to lose. | |
339 | ||
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$ | |
dff0fad2 | 342 | winning rows. So our probability of winning must be at least $(n - r)/r$. |
a6e375a6 MW |
343 | |
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 | |
349 | win is at least | |
dff0fad2 | 350 | \[ \frac{2 r p - r}{r} = 2 \biggl( p - \frac{1}{2} \biggr). \] |
a6e375a6 MW |
351 | |
352 | \begin{slide} | |
353 | \head{Zero-knowledge \seq: an example (cont.)} | |
354 | ||
355 | We now show zero-knowledge, by describing a simulator. | |
356 | \begin{enumerate} | |
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}. \] | |
364 | \end{enumerate} | |
365 | Simulator fails (and retries) with probability $\frac{1}{2}$, because $b$ | |
366 | is uniform and independent of $c$. | |
367 | \end{slide} | |
368 | ||
369 | \begin{slide} | |
370 | \head{Aside on KCDSA} | |
371 | \topic{KCDSA} | |
372 | ||
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 | |
375 | hash functions. | |
376 | ||
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^*$. | |
379 | \begin{enumerate} | |
380 | \item She chooses a random $k \inr \F_q$. She computes $K = k P$, and $r = | |
381 | H(K)$. | |
382 | \item Computes $h = H'(m)$, and $u = (h \xor r) \bmod q$. | |
383 | \item Finally, she computes $s = (k - u)/a$. | |
384 | \end{enumerate} | |
385 | Her signature on $m$ is $\sigma = (r, s)$. | |
386 | ||
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 | |
390 | a + u) P = k P = K$. | |
391 | \end{slide} | |
392 | ||
393 | \begin{slide} | |
394 | \head{Zero-knowledge \seq: KCDSA as identification protocol} | |
395 | ||
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. | |
398 | \begin{protocol} | |
399 | Alice & Bob \\ | |
400 | (private key $a \inr \F_q$) & (public key $A = a P$) \\[\medskipamount] | |
401 | $k \getsr \F_q$; $K \gets k P$; \\ | |
402 | \send{->}{r = H(K)} | |
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)$ | |
407 | \end{protocol} | |
408 | \end{slide} | |
409 | ||
410 | \begin{slide} | |
411 | \head{Zero-knowledge \seq: KCDSA as identification protocol (cont.)} | |
412 | ||
413 | \begin{itemize} | |
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$. | |
420 | \begin{itemize} | |
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'}. \] | |
427 | \end{itemize} | |
428 | So our fake prover can compute discrete logs. | |
429 | \end{itemize} | |
430 | \end{slide} | |
431 | It's worth proving the probability given above. I use the approach of | |
432 | K\"asper, Laur and Lipmaa [KLL06]. | |
433 | ||
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? | |
442 | ||
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] | |
449 | \Pr[v \in G_u] | |
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|} | |
453 | \end{eqnarray*} | |
454 | ||
455 | This is unpleasant, but the following lemma will sort us out. | |
456 | \begin{lemma} | |
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 | |
459 | all $0 \le i < n$. | |
460 | \end{lemma} | |
461 | \begin{proof} | |
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$. | |
465 | ||
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). | |
474 | \end{eqnarray*} | |
475 | This is minimum when | |
476 | \[ \frac{\d}{\d s} \bigl( t^2 - 2 s t + s^2 (1 + n) \bigr) = | |
477 | 2 s (1 + n) - 2 t = 0 \] | |
478 | i.e., when | |
479 | \[ s = \frac{t}{n + 1} \] | |
480 | as claimed. | |
481 | \end{proof} | |
482 | ||
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: | |
486 | \[ \Pr[v \in G_u] | |
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|}. | |
490 | \] | |
491 | ||
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. | |
504 | ||
505 | \begin{slide} | |
506 | \head{Zero-knowledge \seq: KCDSA as identification protocol (cont.)} | |
507 | ||
508 | \begin{itemize} | |
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. | |
511 | \begin{enumerate} | |
512 | \item Simulator chooses $r \inr \Bin^t$ at random, and gives $r$ to the | |
513 | verifier. | |
514 | \item Simulator runs verifier, and is given $m$. | |
515 | \item Simulator computes $u = (r \xor m) \bmod q$, and chooses $s \inr | |
516 | \F_q$ at random. | |
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$. | |
519 | \end{enumerate} | |
520 | If the verifier makes $n$ random oracle queries, the failure only occurs | |
521 | with probability $n/q$. | |
522 | \end{itemize} | |
523 | \end{slide} | |
524 | ||
525 | ||
526 | \begin{slide} | |
527 | \head{Zero-knowledge \seq: complexity theory and ZK} | |
528 | ||
529 | A \emph{language} $L \subseteq \Bin^*$ is a set of bit-strings. | |
530 | ||
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. | |
534 | ||
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$. | |
537 | ||
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}. | |
541 | ||
542 | Zero-knowledge proof systems exist for all languages in $\mathbf{NP}$. | |
543 | Example statements: | |
544 | \begin{itemize} | |
545 | \item Two ciphertexts are encryptions of the same plaintext. | |
546 | \item A ciphertext is the encryption of a given plaintext. | |
547 | \end{itemize} | |
548 | \end{slide} | |
549 | ||
550 | \xcalways\subsection{Key-exchange security}\x | |
551 | ||
552 | \begin{slide} | |
553 | \resetseq | |
554 | \head{Key-exchange \seq: introduction} | |
555 | \topic{introduction} | |
556 | ||
557 | Key-exchange seems very difficult. Many protocols have subtle weaknesses. | |
558 | It would be nice to `prove' security. There are two approaches: | |
559 | \begin{enumerate} | |
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. | |
569 | \end{enumerate} | |
570 | Second approach can give useful, quantitative results, if we believe the | |
571 | model is good. | |
572 | \end{slide} | |
573 | ||
574 | \begin{slide} | |
575 | \head{Key-exchange \seq: introduction} | |
576 | ||
577 | We describe the model of Canetti and Krawczyk [CK01] and their notion of | |
578 | \emph{SK-security}. | |
579 | \begin{itemize} | |
580 | \item Earlier models were either too restrictive ([BR93] \emph{matching | |
581 | conversations}, [Sho99] termination requirement) or flawed ([BR93] | |
582 | again). | |
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. | |
589 | \end{itemize} | |
590 | \end{slide} | |
591 | ||
592 | \begin{slide} | |
593 | \head{Key-exchange \seq: model -- basics} | |
594 | \topic{model} | |
595 | ||
596 | There are two kinds of \emph{participants}: | |
597 | \begin{itemize} | |
598 | \item a number of \emph{parties}, $P_0$, $P_1$, \ldots, $P_{n-1}$, and | |
599 | \item an \emph{adversary}. | |
600 | \end{itemize} | |
601 | A protocol $\Pi$ defines an \emph{initialization function} $I$, which | |
602 | outputs: | |
603 | \begin{itemize} | |
604 | \item a common input $c$ for all participants (all parties and the | |
605 | adversary), and | |
606 | \item a private input $x_i$ for party $P_i$. | |
607 | \end{itemize} | |
608 | \end{slide} | |
609 | ||
610 | \begin{slide} | |
611 | \head{Key-exchange \seq: model -- sessions} | |
612 | ||
613 | Protocol execution occurs in \emph{sessions}. A session $S = (P_i, P_j, | |
614 | s)$ specifies | |
615 | \begin{itemize} | |
616 | \item an \emph{owner} $P_i$ -- the session knows $P_i$'s secret input | |
617 | $x_i$; | |
618 | \item a \emph{partner} $P_j$; and | |
619 | \item a \emph{session-id} $s \in \Bin^{\ell_S}$. | |
620 | \end{itemize} | |
621 | The adversary can create sessions at will, by specifying $(i, j, s)$. | |
622 | ||
623 | Restriction: sessions must be \emph{distinct}. | |
624 | ||
625 | A pair of sessions $S = (P_i, P_j, s)$ and $T = (P_j, P_i, s)$ are said to | |
626 | be \emph{matching}. | |
627 | \end{slide} | |
628 | ||
629 | \begin{slide} | |
630 | \head{Key-exchange \seq: model -- communication} | |
631 | ||
632 | When a session is created, it may output a message to be sent to its | |
633 | matching session. | |
634 | ||
635 | The \emph{adversary} is responsible for delivering all messages. | |
636 | ||
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 | |
640 | (\emph{aborting}). | |
641 | ||
642 | A session which has been created and has not terminated is \emph{running}. | |
643 | \end{slide} | |
644 | ||
645 | \begin{slide} | |
646 | \head{Key-exchange \seq: model -- the adversary} | |
647 | ||
648 | As well as creating sessions and delivering messages, the adversary has | |
649 | other capabilities. | |
650 | \begin{itemize} | |
651 | \item It can \emph{expire} a completed session, wiping out any record of | |
652 | its key. | |
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. | |
657 | \end{itemize} | |
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. | |
661 | \end{slide} | |
662 | ||
663 | \begin{slide} | |
664 | \head{Key-exchange \seq: model -- session life cycle} | |
665 | ||
666 | \[ \def\node#1{% | |
667 | \vbox{% | |
668 | \def\\{\small\crcr}% | |
669 | \halign{\hfil\ignorespaces##\unskip\hfil\cr#1\crcr}% | |
670 | }} | |
671 | \begin{xy} | |
672 | \xygraph{ | |
673 | *+[F]\node{Create session $(i, j, s)$} | |
674 | :[d] | |
675 | *+[F:<6pt>]\node{\bf Running\\(send message $\mu$)} ="run" | |
676 | [d] | |
677 | *+[F]\node{Deliver message $\mu'$} ="msg" | |
678 | "msg" :[dll] | |
679 | *+[F:<6pt>]\node{\bf Complete\\(output key $K$)} | |
680 | :[d] | |
681 | *+[F]\node{Expire session} | |
682 | :[d] | |
683 | *+[F:<6pt>]\node{\bf Expired} | |
684 | "msg" :[drr] | |
685 | *+[F:<6pt>]\node{\bf Aborted\\(no output)} | |
686 | } | |
687 | \ar @{->} @<1em> "run"; "msg" | |
688 | \ar @{->} @<1em> "msg"; "run" | |
689 | \end{xy} \] | |
690 | \end{slide} | |
691 | ||
692 | \begin{slide} | |
693 | \head{Key-exchange \seq: model -- SK-security} | |
694 | ||
695 | We play a game with the adversary. At the beginning, we choose a `hidden | |
696 | bit' $b^* \inr \Bin$. | |
697 | ||
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. | |
702 | ||
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$. | |
706 | ||
707 | A key-exchange protocol $\Pi$ is \emph{SK-secure} if no adversary can | |
708 | \begin{itemize} | |
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^*$. | |
713 | \end{itemize} | |
714 | \end{slide} | |
715 | ||
716 | \begin{slide} | |
717 | \head{Key-exchange \seq: deniability} | |
718 | \topic{deniability} | |
719 | ||
720 | Many key-exchange protocols use digital signatures. For example: | |
721 | \begin{protocol} | |
722 | Alice & Bob \\ | |
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$; \\ | |
727 | \send{->}{R_A} | |
728 | \send{<-}{R_B} | |
729 | $\sigma_A \gets | |
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)$;} \\ | |
733 | \send{->}{\sigma_A} | |
734 | \send{<-}{\sigma_B} | |
735 | Check: $V(\id{pk}_B, \sigma_B, \texttt{Bob}, \texttt{Alice}, s, R_B, | |
736 | R_A)$ | |
737 | \\ & | |
738 | \llap{Check: $V(\id{pk}_A, \sigma_A, | |
739 | \texttt{Alice}, \texttt{Bob}, s, R_A, R_B)$} | |
740 | \end{protocol} | |
741 | \end{slide} | |
742 | ||
743 | \begin{slide} | |
744 | \head{Key-exchange \seq: deniability (cont.)} | |
745 | ||
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. | |
748 | ||
749 | This is \emph{bad} if you don't want to leave evidence that you were | |
750 | communicating with someone. | |
751 | ||
752 | A key-exchange protocol is \emph{deniable} if there's a simulator which | |
753 | produces fake transcripts indistinguishable from real conversations | |
754 | \begin{itemize} | |
755 | \item \emph{without} being given the private keys of the parties involved, | |
756 | and | |
757 | \item even if some of the participants are corrupt. | |
758 | \end{itemize} | |
759 | \end{slide} | |
760 | ||
761 | \endinput | |
762 | ||
763 | %%% Local Variables: | |
764 | %%% mode: latex | |
765 | %%% TeX-master: "wrslides" | |
766 | %%% End: |