Commit | Line | Data |
---|---|---|
a6e375a6 MW |
1 | \xcalways\section{The Wrestlers Protocol}\x |
2 | ||
3 | \xcalways\subsection{Identification using Diffie-Hellman}\x | |
4 | ||
5 | \begin{slide} | |
6 | \resetseq | |
dff0fad2 | 7 | \head{Identification using Diffie-Hellman \seq: properties} |
a6e375a6 MW |
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} | |
dff0fad2 | 20 | \head{Identification using Diffie-Hellman \seq: basic setting} |
a6e375a6 MW |
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} | |
dff0fad2 | 34 | \head{Identification using Diffie-Hellman \seq: na\"\i ve attempt} |
a6e375a6 MW |
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} | |
dff0fad2 | 57 | \head{Identification using Diffie-Hellman \seq: fix it with a hash} |
a6e375a6 MW |
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$; \\ | |
d8139f2c | 91 | & $h \gets H(\cookie{check}, Y)$; \\ |
a6e375a6 MW |
92 | & \\ |
93 | \send{<-}{(R, h)} | |
94 | $Y \gets a R$; \\ | |
95 | \\ | |
96 | \diff \textbf{Check} $q R = 0$; \\ | |
d8139f2c | 97 | \textbf{Check} $h = H(\cookie{check}, Y)$ \\ |
a6e375a6 MW |
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} | |
dff0fad2 | 105 | \head{Identification using Diffie-Hellman \seq: the Wrestlers Protocol |
a6e375a6 MW |
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} | |
dff0fad2 | 128 | \head{Identification using Diffie-Hellman \seq: identification-based |
a6e375a6 MW |
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} | |
dff0fad2 | 193 | \head{Mutual identification \seq: key exchange?} |
a6e375a6 MW |
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 | |
dff0fad2 | 216 | \head{Key exchange \seq: properties} |
a6e375a6 MW |
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} | |
dff0fad2 | 230 | \head{Key exchange \seq: setting} |
a6e375a6 MW |
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} | |
dff0fad2 | 247 | \head{Key exchange \seq: broken first attempt} |
a6e375a6 MW |
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} | |
dff0fad2 | 270 | \head{Key exchange \seq: solution -- encrypt responses} |
a6e375a6 MW |
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} | |
dff0fad2 | 293 | \head{Key exchange \seq: multiple sessions} |
a6e375a6 MW |
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} | |
dff0fad2 MW |
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} | |
a6e375a6 MW |
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: |