| 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$, |
| 324 | from which we compute $\beta$. This works with probability at least $2 |
| 325 | (p - \frac{1}{2})$. |
| 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$ |
| 342 | winning rows. So our probability of winning must be at least $(n - r)/r$. |
| 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 |
| 350 | \[ \frac{2 r p - r}{r} = 2 \biggl( p - \frac{1}{2} \biggr). \] |
| 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: |