| 1 | \xcalways\section{The Wrestlers Protocol}\x |
| 2 | |
| 3 | \xcalways\subsection{Identification using Diffie-Hellman}\x |
| 4 | |
| 5 | \begin{slide} |
| 6 | \resetseq |
| 7 | \head{Identification using Diffie-Hellman \seq: properties} |
| 8 | \topic{properties} |
| 9 | |
| 10 | \begin{itemize} |
| 11 | \item Simple -- easy to remember, analyse and implement |
| 12 | \item Practical -- two scalar multiplications for each party |
| 13 | \item Secure -- under Computational Diffie-Hellman assumption |
| 14 | \item Zero-knowledge -- statistical ZK |
| 15 | \item Proofs in random oracle model -- but without `programming' |
| 16 | \end{itemize} |
| 17 | \end{slide} |
| 18 | |
| 19 | \begin{slide} |
| 20 | \head{Identification using Diffie-Hellman \seq: basic setting} |
| 21 | \topic{setting} |
| 22 | |
| 23 | \begin{itemize} |
| 24 | \item Cyclic group $(G, +)$ |
| 25 | \item $|G| = q$ is prime |
| 26 | \item $P$ generates $G$ |
| 27 | \item Alice's private key is $a \inr \Nupto{q}$ |
| 28 | \item Alice's public key is $A = a P$ |
| 29 | \item Assume computational Diffie-Hellman problem hard in $G$ |
| 30 | \end{itemize} |
| 31 | \end{slide} |
| 32 | |
| 33 | \begin{slide} |
| 34 | \head{Identification using Diffie-Hellman \seq: na\"\i ve attempt} |
| 35 | \topic{protocol design} |
| 36 | |
| 37 | \begin{protocol} |
| 38 | Alice & Bob \\ |
| 39 | (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) |
| 40 | \\[\medskipamount] |
| 41 | & $r \getsr \Nupto{q}$; \\ |
| 42 | & $R \gets r P$; \\ |
| 43 | \\ |
| 44 | \\ |
| 45 | \\ |
| 46 | \send{<-}{R} |
| 47 | $Y \gets a R$; \\ |
| 48 | \\ |
| 49 | \\ |
| 50 | \\ |
| 51 | \send{->}{Y} |
| 52 | & \textbf{Check} $Y = r A$ |
| 53 | \end{protocol} |
| 54 | \end{slide} |
| 55 | |
| 56 | \begin{slide} |
| 57 | \head{Identification using Diffie-Hellman \seq: fix it with a hash} |
| 58 | \protocolskip0pt |
| 59 | |
| 60 | \begin{protocol} |
| 61 | Alice & Bob \\ |
| 62 | (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) |
| 63 | \\[\medskipamount] |
| 64 | & $r \getsr \Nupto{q}$; \\ |
| 65 | & $R \gets r P$; \\ |
| 66 | & $Y \gets r A$; \\ |
| 67 | & \diff $h \gets H(\cookie{check}, R, Y)$; \\ |
| 68 | & \\ |
| 69 | \send{<-}{(R, \hbox{\diff $h$})} |
| 70 | $Y \gets a R$; \\ |
| 71 | \\ |
| 72 | \\ |
| 73 | \diff \textbf{Check} $h = H(\cookie{check}, R, Y)$ \\ |
| 74 | \send{->}{Y} |
| 75 | & \textbf{Check} $Y$ |
| 76 | \end{protocol} |
| 77 | \dots but there are still small-subgroup attacks |
| 78 | \end{slide} |
| 79 | |
| 80 | \begin{slide} |
| 81 | \head{Identification using Diffie-Hellman \seq: Stinson-Wu [SW06]} |
| 82 | \protocolskip0pt |
| 83 | |
| 84 | \begin{protocol} |
| 85 | Alice & Bob \\ |
| 86 | (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) |
| 87 | \\[\medskipamount] |
| 88 | & $r \getsr \Nupto{q}$; \\ |
| 89 | & $R \gets r P$; \\ |
| 90 | & $Y \gets r A$; \\ |
| 91 | & $h \gets H(\cookie{check}, Y)$; \\ |
| 92 | & \\ |
| 93 | \send{<-}{(R, h)} |
| 94 | $Y \gets a R$; \\ |
| 95 | \\ |
| 96 | \diff \textbf{Check} $q R = 0$; \\ |
| 97 | \textbf{Check} $h = H(\cookie{check}, Y)$ \\ |
| 98 | \send{->}{Y} |
| 99 | & \textbf{Check} $Y$ |
| 100 | \end{protocol} |
| 101 | \dots and apply the Knowledge of Exponent assumption |
| 102 | \end{slide} |
| 103 | |
| 104 | \begin{slide} |
| 105 | \head{Identification using Diffie-Hellman \seq: the Wrestlers Protocol |
| 106 | $\Wident$} |
| 107 | |
| 108 | \begin{protocol} |
| 109 | Alice & Bob \\ |
| 110 | (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) |
| 111 | \\[\medskipamount] |
| 112 | & $r \getsr \Nupto{q}$; \\ |
| 113 | & $R \gets r P$; \\ |
| 114 | & $Y \gets r A$; \\ |
| 115 | & $h \gets H(\cookie{check}, R, Y)$; \\ |
| 116 | & \diff $c \gets h \xor r$; \\ |
| 117 | \send{<-}{(R, \hbox{\diff $c$})} |
| 118 | $Y \gets a R$; \\ |
| 119 | $h \gets H(\cookie{check}, R, Y)$; \\ |
| 120 | \diff $r \gets c \xor h$; \\ |
| 121 | \diff \textbf{Check} $R = r P$ \\ |
| 122 | \send{->}{Y} |
| 123 | & \textbf{Check} $Y$ |
| 124 | \end{protocol} |
| 125 | \end{slide} |
| 126 | |
| 127 | \begin{slide} |
| 128 | \head{Identification using Diffie-Hellman \seq: identification-based |
| 129 | $\Wident$} |
| 130 | |
| 131 | \begin{protocol} |
| 132 | Alice & Bob \\ |
| 133 | (Private key $K_A = t I_A$) & |
| 134 | (Public key $I_A = H(\cookie{id}, \text{Alice})$) |
| 135 | \\[\medskipamount] |
| 136 | & $r \getsr \Nupto{q}$; \\ |
| 137 | & $R \gets r P$; \\ |
| 138 | & \diff $Y \gets \hat{e}(T, I_A)^r$; \\ |
| 139 | & $h \gets H(\cookie{check}, R, Y)$; \\ |
| 140 | & $c \gets h \xor r$; \\ |
| 141 | \send{<-}{(R, c)} |
| 142 | \diff $Y \gets \hat{e}(R, K_A)$; \\ |
| 143 | $h \gets H(\cookie{check}, R, Y)$; \\ |
| 144 | $r \gets c \xor h$; \\ |
| 145 | \textbf{Check} $R = r P$ \\ |
| 146 | \send{->}{Y} |
| 147 | & \textbf{Check} $Y$ |
| 148 | \end{protocol} |
| 149 | (Trusted authority's private key $t \inr \Nupto{q}$; public key $T = t P$) |
| 150 | \end{slide} |
| 151 | |
| 152 | \xcalways\subsection{Key exchange}\x |
| 153 | |
| 154 | \begin{slide} |
| 155 | \resetseq |
| 156 | \head{Mutual identification \seq: Bob identifies Alice} |
| 157 | \topic{mutual identification} |
| 158 | |
| 159 | \begin{protocol} |
| 160 | Alice & Bob \\ |
| 161 | (Private key $a$, public key $A = a P$) |
| 162 | \\[\medskipamount] |
| 163 | & $r_B \getsr \Nupto{q}$; \\ |
| 164 | & $R_B \gets r_B P$; \\ |
| 165 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} |
| 166 | \\ |
| 167 | $Y_B \gets a R_B$; \\ |
| 168 | \\ |
| 169 | \send{->}{Y_B} |
| 170 | \end{protocol} |
| 171 | \end{slide} |
| 172 | |
| 173 | \begin{slide} |
| 174 | \head{Mutual identification \seq: Alice identifies Bob too} |
| 175 | |
| 176 | \begin{protocol} |
| 177 | Alice & Bob \\ |
| 178 | (Private key $a$, public key $A = a P$) & |
| 179 | \other (Private key $b$, public key $B = b P$) |
| 180 | \\[\medskipamount] |
| 181 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 182 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 183 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} |
| 184 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} |
| 185 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 186 | \\ |
| 187 | \send{->}{Y_B} |
| 188 | \send{<-}{\other Y_A} |
| 189 | \end{protocol} |
| 190 | \end{slide} |
| 191 | |
| 192 | \begin{slide} |
| 193 | \head{Mutual identification \seq: key exchange?} |
| 194 | |
| 195 | \begin{protocol} |
| 196 | Alice & Bob \\ |
| 197 | (Private key $a$, public key $A = a P$) & |
| 198 | \other (Private key $b$, public key $B = b P$) |
| 199 | \\[\medskipamount] |
| 200 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 201 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 202 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} |
| 203 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} |
| 204 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 205 | \\ |
| 206 | \send{->}{Y_B} |
| 207 | \send{<-}{\other Y_A} |
| 208 | \diff $Z \gets r_A R_B$; & \diff $Z \gets r_B R_A$; |
| 209 | \end{protocol} |
| 210 | \bigskip |
| 211 | Unfortunately it's not secure. |
| 212 | \end{slide} |
| 213 | |
| 214 | \begin{slide} |
| 215 | \resetseq |
| 216 | \head{Key exchange \seq: properties} |
| 217 | \topic{properties} |
| 218 | |
| 219 | \begin{itemize} |
| 220 | \item Simple -- symmetrical; based on mutual identification |
| 221 | \item Practical -- three, four or five flows; four multiplications by each |
| 222 | party |
| 223 | \item Secure -- provides SK-security in model of [CK01] |
| 224 | \item Deniable -- simulator can produce convincing transcripts |
| 225 | \item Proofs in random oracle model -- again without `programming' |
| 226 | \end{itemize} |
| 227 | \end{slide} |
| 228 | |
| 229 | \begin{slide} |
| 230 | \head{Key exchange \seq: setting} |
| 231 | \topic{setting} |
| 232 | |
| 233 | \begin{itemize} |
| 234 | \item Cyclic group $(G, +)$ |
| 235 | \item $|G| = q$ is prime |
| 236 | \item $P$ generates $G$ |
| 237 | \item Alice's private key is $a \inr \Nupto{q}$; her public key is $A = a |
| 238 | P$ |
| 239 | \item Bob's private key is $b \inr \Nupto{q}$; his public key is $B = b |
| 240 | P$ |
| 241 | \item Symmetric IND-CCA encryption scheme $\E = (\kappa, E, D)$ |
| 242 | \item Assume computational Diffie-Hellman problem hard in $G$ |
| 243 | \end{itemize} |
| 244 | \end{slide} |
| 245 | |
| 246 | \begin{slide} |
| 247 | \head{Key exchange \seq: broken first attempt} |
| 248 | \topic{protocol design} |
| 249 | |
| 250 | \begin{protocol} |
| 251 | Alice & Bob \\ |
| 252 | (Private key $a$, public key $A = a P$) & |
| 253 | \other (Private key $b$, public key $B = b P$) |
| 254 | \\[\medskipamount] |
| 255 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 256 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 257 | \\ |
| 258 | \\ |
| 259 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} |
| 260 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} |
| 261 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 262 | $Z \gets r_A R_B$; & $Z \gets r_B R_A$; \\ |
| 263 | \send{->}{(R_A, Y_B)} |
| 264 | \send{<-}{\other (R_B, Y_A)} |
| 265 | Key is $Z$ & Key is $Z$ |
| 266 | \end{protocol} |
| 267 | \end{slide} |
| 268 | |
| 269 | \begin{slide} |
| 270 | \head{Key exchange \seq: solution -- encrypt responses} |
| 271 | |
| 272 | \begin{protocol} |
| 273 | Alice & Bob \\ |
| 274 | (Private key $a$, public key $A = a P$) & |
| 275 | \other (Private key $b$, public key $B = b P$) |
| 276 | \\[\medskipamount] |
| 277 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 278 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 279 | \\ |
| 280 | \\ |
| 281 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} |
| 282 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} |
| 283 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 284 | \diff $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; & |
| 285 | \diff $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\ |
| 286 | \send{->}{(R_A, \hbox{\diff $E_{K_0}(Y_B)$})} |
| 287 | \send{<-}{\other (R_B, \hbox{\diff $E_{K_0}(Y_A)$})} |
| 288 | Key is $K_1$ & Key is $K_1$ |
| 289 | \end{protocol} |
| 290 | \end{slide} |
| 291 | |
| 292 | \begin{slide} |
| 293 | \head{Key exchange \seq: multiple sessions} |
| 294 | |
| 295 | \begin{protocol} |
| 296 | Alice & Bob \\ |
| 297 | (Private key $a$, public key $A = a P$) & |
| 298 | \other (Private key $b$, public key $B = b P$) |
| 299 | \\[\medskipamount] |
| 300 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 301 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 302 | \\ |
| 303 | \\ |
| 304 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, |
| 305 | \hbox{\diff $B$}, \hbox{\diff $s$}, R_B, Y_B))} |
| 306 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, |
| 307 | \hbox{\diff $A$}, \hbox{\diff $s$}, R_A, Y_A))} |
| 308 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 309 | $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; & |
| 310 | $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\ |
| 311 | \send{->}{(R_A, E_{K_0}(Y_B))} |
| 312 | \send{<-}{\other (R_B, E_{K_0}(Y_A))} |
| 313 | Key is $K_1$ & Key is $K_1$ |
| 314 | \end{protocol} |
| 315 | (Session id is $s$) |
| 316 | \end{slide} |
| 317 | |
| 318 | \begin{slide} |
| 319 | \head{Key exchange \seq: proof sketch} |
| 320 | |
| 321 | \begin{itemize} |
| 322 | \item $\G0$ is SK-security game. |
| 323 | \item In $\G1$, stop game unless all parties have distinct public keys |
| 324 | (collision bound). |
| 325 | \item In $\G2$, use extractor to answer challenges other than from matching |
| 326 | session. |
| 327 | \item In $\G3$, stop game if adversary queries $H(\cookie{key}, r_A r_b P)$ |
| 328 | (CDH in $G$). |
| 329 | \item In $\G4$, stop game if session accepts response except from matching |
| 330 | session. |
| 331 | \begin{itemize} |
| 332 | \item In $\G5$, focus on a single session (factor of $q_S$). |
| 333 | \item In $\G6$, encrypt $1^{|Y|}$ instead of $Y = x R$ (IND-CCA of $\E$). |
| 334 | \item In $\G7$, focus on a single party (factor of $n$). |
| 335 | \item Now if party accepts, reduce from impersonating in $\Wident$. |
| 336 | \end{itemize} |
| 337 | \end{itemize} |
| 338 | \end{slide} |
| 339 | |
| 340 | \begin{slide} |
| 341 | \head{Key exchange \seq: security result} |
| 342 | \begin{spliteqn*} |
| 343 | \InSec{sk}(\Wkx^{G, \E}; t, n, q_S, q_M, q_I, q_K) \le |
| 344 | 2 q_S \bigl( \InSec{ind-cca}(\E; t', q_M, q_M) + {} \\ |
| 345 | \InSec{mcdh}(G; t', q_K) + |
| 346 | n \,\InSec{mcdh}(G; t', q_M + q_I) \bigr) + {} \\ |
| 347 | \frac{n (n - 1)}{|G|} + |
| 348 | \frac{2 q_M}{2^{\ell_I}}. |
| 349 | \end{spliteqn*} |
| 350 | \begin{multicols}{2} |
| 351 | \begin{itemize} |
| 352 | \item $t$ is running time of adversary |
| 353 | \item $n$ is number of parties |
| 354 | \item $q_S$ is number of new sessions |
| 355 | \item $q_M$ is number of messages sent |
| 356 | \item $q_I$ is number of $H(\cookie{check}, \cdot)$ queries |
| 357 | \item $q_K$ is number of $H(\cookie{key}, \cdot)$ queries |
| 358 | \item $t' = t + O(q_S) + O(q_M q_I) + O(q_K)$ |
| 359 | \end{itemize} |
| 360 | \end{multicols} |
| 361 | \end{slide} |
| 362 | |
| 363 | \begin{slide} |
| 364 | \head{Key exchange \seq: fully deniable variant} |
| 365 | |
| 366 | \begin{protocol} |
| 367 | Alice & Bob \\ |
| 368 | (Private key $a$, public key $A = a P$) & |
| 369 | \other (Private key $b$, public key $B = b P$) |
| 370 | \\[\medskipamount] |
| 371 | \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ |
| 372 | \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ |
| 373 | \send{->}{\diff R_A} |
| 374 | \send{<-}{\diff R_B} |
| 375 | \send{<-}{(R_B, r_B \xor H(\cookie{check}, B, s, \hbox{\diff $R_A$}, R_B, Y_B))} |
| 376 | \send{->}{\other (R_A, r_A \xor H(\cookie{check}, A, s, \hbox{\diff $R_B$}, R_A, Y_A))} |
| 377 | $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ |
| 378 | $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; & |
| 379 | $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\ |
| 380 | \send{->}{(R_A, E_{K_0}(Y_B))} |
| 381 | \send{<-}{\other (R_B, E_{K_0}(Y_A))} |
| 382 | Key is $K_1$ & Key is $K_1$ |
| 383 | \end{protocol} |
| 384 | \end{slide} |
| 385 | |
| 386 | \endinput |
| 387 | |
| 388 | %%% Local Variables: |
| 389 | %%% mode: latex |
| 390 | %%% TeX-master: "wrslides" |
| 391 | %%% End: |