1 \xcalways\section{The Wrestlers Protocol
}\x
3 \xcalways\subsection{Identification using Diffie-Hellman
}\x
7 \head{Identification using Diffie-Hellman
\seq: properties
}
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'
20 \head{Identification using Diffie-Hellman
\seq: basic setting
}
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$
34 \head{Identification using Diffie-Hellman
\seq: na\"
\i ve attempt
}
35 \topic{protocol design
}
39 (Private key $a
\inr \Nupto{q
}$) & (Public key $A = a P$)
41 & $r
\getsr \Nupto{q
}$; \\
52 &
\textbf{Check
} $Y = r A$
57 \head{Identification using Diffie-Hellman
\seq: fix it with a hash
}
62 (Private key $a
\inr \Nupto{q
}$) & (Public key $A = a P$)
64 & $r
\getsr \Nupto{q
}$; \\
67 &
\diff $h
\gets H(
\cookie{check
}, R, Y)$; \\
69 \send{<-
}{(R,
\hbox{\diff $h$
})
}
73 \diff \textbf{Check
} $h = H(
\cookie{check
}, R, Y)$ \\
77 \dots but there are still small-subgroup attacks
81 \head{Identification using Diffie-Hellman
\seq: Stinson-Wu
[SW06
]}
86 (Private key $a
\inr \Nupto{q
}$) & (Public key $A = a P$)
88 & $r
\getsr \Nupto{q
}$; \\
91 & $h
\gets H(
\cookie{check
}, R, Y)$; \\
96 \diff \textbf{Check
} $q R =
0$; \\
97 \textbf{Check
} $h = H(
\cookie{check
}, R, Y)$ \\
101 \dots and apply the Knowledge of Exponent assumption
105 \head{Identification using Diffie-Hellman
\seq: the Wrestlers Protocol
110 (Private key $a
\inr \Nupto{q
}$) & (Public key $A = a P$)
112 & $r
\getsr \Nupto{q
}$; \\
115 & $h
\gets H(
\cookie{check
}, R, Y)$; \\
116 &
\diff $c
\gets h
\xor r$; \\
117 \send{<-
}{(R,
\hbox{\diff $c$
})
}
119 $h
\gets H(
\cookie{check
}, R, Y)$; \\
120 \diff $r
\gets c
\xor h$; \\
121 \diff \textbf{Check
} $R = r P$ \\
128 \head{Identification using Diffie-Hellman
\seq: identification-based
133 (Private key $K_A = t I_A$) &
134 (Public key $I_A = H(
\cookie{id
},
\text{Alice
})$)
136 & $r
\getsr \Nupto{q
}$; \\
138 &
\diff $Y
\gets \hat{e
}(T, I_A)^r$; \\
139 & $h
\gets H(
\cookie{check
}, R, Y)$; \\
140 & $c
\gets h
\xor r$; \\
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$ \\
149 (Trusted authority's private key $t
\inr \Nupto{q
}$; public key $T = t P$)
152 \xcalways\subsection{Key exchange
}\x
156 \head{Mutual identification
\seq: Bob identifies Alice
}
157 \topic{mutual identification
}
161 (Private key $a$, public key $A = a P$)
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))
}
167 $Y_B
\gets a R_B$; \\
174 \head{Mutual identification
\seq: Alice identifies Bob too
}
178 (Private key $a$, public key $A = a P$) &
179 \other (Private key $b$, public key $B = b P$)
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$; \\
188 \send{<-
}{\other Y_A
}
193 \head{Mutual identification
\seq: key exchange?
}
197 (Private key $a$, public key $A = a P$) &
198 \other (Private key $b$, public key $B = b P$)
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$; \\
207 \send{<-
}{\other Y_A
}
208 \diff $Z
\gets r_A R_B$; &
\diff $Z
\gets r_B R_A$;
211 Unfortunately it's not secure.
216 \head{Key exchange
\seq: properties
}
220 \item Simple -- symmetrical; based on mutual identification
221 \item Practical -- three, four or five flows; four multiplications by each
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'
230 \head{Key exchange
\seq: setting
}
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
239 \item Bob's private key is $b
\inr \Nupto{q
}$; his public key is $B = b
241 \item Symmetric IND-CCA encryption scheme $
\E = (
\kappa, E, D)$
242 \item Assume computational Diffie-Hellman problem hard in $G$
247 \head{Key exchange
\seq: broken first attempt
}
248 \topic{protocol design
}
252 (Private key $a$, public key $A = a P$) &
253 \other (Private key $b$, public key $B = b P$)
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$; \\
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$
270 \head{Key exchange
\seq: solution -- encrypt responses
}
274 (Private key $a$, public key $A = a P$) &
275 \other (Private key $b$, public key $B = b P$)
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$; \\
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$
293 \head{Key exchange
\seq: multiple sessions
}
297 (Private key $a$, public key $A = a P$) &
298 \other (Private key $b$, public key $B = b P$)
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$; \\
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$
319 \head{Key exchange
\seq: proof sketch
}
322 \item $
\G0$ is SK-security game.
323 \item In $
\G1$, stop game unless all parties have distinct public keys
325 \item In $
\G2$, use extractor to answer challenges other than from matching
327 \item In $
\G3$, stop game if adversary queries $H(
\cookie{key
}, r_A r_b P)$
329 \item In $
\G4$, stop game if session accepts response except from matching
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$.
341 \head{Key exchange
\seq: security result
}
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}}.
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)$
364 \head{Key exchange
\seq: fully deniable variant
}
368 (Private key $a$, public key $A = a P$) &
369 \other (Private key $b$, public key $B = b P$)
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$; \\
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$
390 %%% TeX-master: "wrslides"