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: Fully deniable variant
}
323 (Private key $a$, public key $A = a P$) &
324 \other (Private key $b$, public key $B = b P$)
326 \other $r_A
\getsr \Nupto{q
}$; & $r_B
\getsr \Nupto{q
}$; \\
327 \other $R_A
\gets r_A P$ & $R_B
\gets r_B P$; \\
330 \send{<-
}{(R_B, r_B
\xor H(
\cookie{check
}, B, s,
\hbox{\diff $R_A$
}, R_B, Y_B))
}
331 \send{->
}{\other (R_A, r_A
\xor H(
\cookie{check
}, A, s,
\hbox{\diff $R_B$
}, R_A, Y_A))
}
332 $Y_B
\gets a R_B$; &
\other $Y_A
\gets b R_B$; \\
333 $(K_0, K_1)
\gets H(
\cookie{key
}, r_A R_B)$; &
334 $(K_0, K_1)
\gets H(
\cookie{key
}, r_B R_A)$; \\
335 \send{->
}{(R_A, E_
{K_0
}(Y_B))
}
336 \send{<-
}{\other (R_B, E_
{K_0
}(Y_A))
}
337 Key is $K_1$ & Key is $K_1$
345 %%% TeX-master: "wrslides"