Commit | Line | Data |
---|---|---|
888f8938 MW |
1 | %%% Deniably authenticated asymmetric encryption |
2 | %%% | |
3 | %%% Copyright (c) 2010 Mark Wooding | |
4 | %%% Licence: CC-BY | |
5 | ||
6 | \documentclass[t]{beamer} | |
7 | \usetheme{Madrid} | |
8 | \usefonttheme{professionalfonts} | |
9 | \usefonttheme[stillsansseriflarge, stillsansserifsmall]{serif} | |
10 | \usepackage[T1]{fontenc} | |
11 | \usepackage[utf8]{inputenc} | |
12 | \usepackage[palatino, helvetica, courier, maths = cmr]{mdwfonts} | |
13 | \usepackage{tikz} | |
14 | \usepackage{crypto, mdwmath} | |
15 | \usetikzlibrary{% | |
16 | shapes.symbols,shapes.callouts,% | |
17 | decorations.pathreplacing,positioning,calc} | |
18 | ||
19 | \title{Deniably authenticated asymmetric encryption} | |
20 | \author[Mark Wooding]{Mark Wooding \\ \texttt{mdw@distorted.org.uk}} | |
21 | \institute{} | |
22 | ||
23 | \def\Xid#1#2{\textsc{$#1$}-#2} | |
24 | \def\proto#1{\Pi_\textsc{#1}} | |
25 | \def\mugshot{\includegraphics[width = 2cm, height = 2.5cm, keepaspectratio]} | |
26 | \def\random{\$} | |
27 | ||
28 | \tikzset{ | |
29 | mugshot/.style = {draw, fill = white, inner sep = 0, outer sep = \jot}, | |
30 | thought/.style = { | |
31 | shape = cloud callout, cloud ignores aspect, draw, fill = white, | |
32 | cloud puffs = 20, cloud puff arc = 110, | |
33 | callout absolute pointer = (#1) | |
34 | }, | |
35 | box/.style = {draw, minimum size = 16pt, fill = #1}, | |
36 | op/.style = {box = #1, shape = circle}, | |
37 | rounded/.style = {rounded corners = 2mm}, | |
38 | offset/.style = {transform canvas = {shift = {#1}}}, | |
39 | > = stealth | |
40 | } | |
41 | ||
42 | \newcount\f | |
43 | ||
44 | \begin{document} | |
45 | \frame{\titlepage} | |
46 | \frame{\frametitle{Outline}\tableofcontents} | |
47 | \AtBeginSubsection{\frame{% | |
48 | \frametitle{Outline}% | |
49 | \tableofcontents[% | |
50 | sectionstyle = show/shaded,% | |
51 | subsectionstyle = show/shaded/shaded]% | |
52 | }} | |
53 | ||
54 | %%%-------------------------------------------------------------------------- | |
55 | \section{Introduction} | |
56 | ||
57 | \subsection{Motivation: sign-then-encrypt failures} | |
58 | ||
59 | \begin{frame}{Sign-then-encrypt} | |
60 | \animate<10-14> | |
61 | \begin{block}{} | |
62 | \begin{tikzpicture} | |
63 | \node[mugshot] (bob) at (0, 0) { | |
64 | \only<1-18>{\mugshot{bob.png}}% | |
65 | \only<19->{\mugshot{bob-unthrilled.png}} | |
66 | }; | |
67 | \visible<2->{ | |
68 | \node[thought = bob.north] at ($(bob) + (2, 3)$) | |
69 | {\begin{tabular}{l} | |
70 | Private key $b$ \\ | |
71 | \visible<5->{Alice's public key $A$} \\ | |
72 | \end{tabular}}; | |
73 | } | |
74 | \visible<3->{ | |
75 | \node[mugshot] (alice) at (10, 0){ | |
76 | \only<3-16>{\mugshot{alice.png}}% | |
77 | \only<17->{\mugshot{alice-fallen.png}} | |
78 | }; | |
79 | } | |
80 | \visible<18->{ | |
81 | \node[mugshot] (julian) at ($(bob)!1/2!(alice)$) | |
82 | {\mugshot{wl.png}}; | |
83 | } | |
84 | \visible<4->{ | |
85 | \node[thought = alice.north] at ($(alice) + (-2, 3)$) | |
86 | {\begin{tabular}{l} | |
87 | Private key $a$ \\ | |
88 | \visible<5->{Bob's public key $B$} \\ | |
89 | \end{tabular}}; | |
90 | } | |
91 | \animatevalue<9-15>{\f}{2}{8} | |
92 | \only<1-8>{\tikzset{message/.style = {}}} | |
93 | \only<9->{\tikzset{message/.style = {draw, fill = white}}} | |
94 | \visible<6->{ | |
95 | \node[message] at ($(bob.east)!\f/10!(alice.west)$) | |
96 | { $\visible<8-15>{E_A(} | |
97 | m \visible<7->{, S_b(m)} \visible<8-15>{)} $}; | |
98 | } | |
99 | \end{tikzpicture} | |
100 | \end{block} | |
101 | \begin{block}{} | |
102 | \begin{overprint} | |
103 | \onslide<+-+(1)> Meet Bob. \visible<+>{Bob has a private key.} | |
104 | \onslide<+-+(1)> Bob meets Alice online. \visible<+>{Alice has a | |
105 | private key too.} | |
106 | \onslide<+> Magically, they know each other's public keys. | |
107 | \onslide<+> Bob knows a secret. He wants to send it to Alice. | |
108 | \onslide<+> Bob signs his message so that Alice knows it's from him. | |
109 | \onslide<+> He encrypts so nobody else knows what he's telling her. | |
110 | \onslide<+-+(6)> And then he sends the whole lot to Alice. | |
111 | \addtocounter{beamerpauses}{6} | |
112 | \onslide<+> Alice decrypts and verifies. | |
113 | \onslide<+> Alice isn't exactly a night in shining armour. | |
114 | \onslide<+> She publishes Bob's message and his signature. | |
115 | \onslide<+> Bob is not completely thrilled. | |
116 | \end{overprint} | |
117 | \end{block} | |
118 | \end{frame} | |
119 | ||
120 | \begin{frame}{Signatures and public-key encryption} | |
121 | \begin{itemize}[<+->] | |
122 | \item Lots of other problematic scenarios [Davis~2001]. | |
123 | \item Encrypt-then-sign doesn't help much: recipient can publish NIZK proof | |
124 | of correct decryption. | |
125 | \item Signatures are universally verifiable. Non-repudiation is | |
126 | undesirable when you're up to no good. | |
127 | \item Authenticated encryption is still valuable. \visible<+>{Especially | |
128 | when you're up to no good.} | |
129 | \end{itemize} | |
130 | \end{frame} | |
131 | ||
132 | \subsection{Our contributions} | |
133 | ||
134 | \begin{frame}{Deniably authenticated asymmetric encryption} | |
135 | \begin{block}{The basic idea} | |
136 | \begin{itemize}[<+->] | |
137 | \item Bob sends a message to Alice. | |
138 | \item Nobody else can read it (\emph{secrecy}). | |
139 | \item Alice knows that Bob sent it (\emph{authenticity}). | |
140 | \item Neither Alice nor Bob can prove that Bob sent it to anyone else | |
141 | (\emph{deniability}). | |
142 | \end{itemize} | |
143 | \end{block} | |
144 | \begin{block}<+->{We provide} | |
145 | \begin{itemize}[<+->] | |
146 | \item Formal definitions of security and deniability. | |
147 | \item Three constructions with various properties. | |
148 | \end{itemize} | |
149 | \end{block} | |
150 | \end{frame} | |
151 | ||
152 | \subsection{Previous work} | |
153 | ||
154 | \begin{frame}{Previous and related work} | |
155 | \begin{itemize}[<+->] | |
156 | \item Deniable authentication since [Dolev, Dwork, Naor~1991]; also [Dwork, | |
157 | Naor, Sahai~19991], [Di~Raimondo, Gennaro~2005]. Intrinsically | |
158 | \emph{interactive}. | |
159 | \item Deniably authenticated key exchange [Di~Raimondo, Gennaro, | |
160 | Krawczyk~2006], e.g., SKEME [Krawczyk~1996], \emph{Off the Record} | |
161 | [Borisov, Goldberg, Brewer~2004], Wrestlers [Wooding~2006]. Also | |
162 | interactive. | |
163 | \item Chameleon signatures [Krawczyk, Rabin~1998]. | |
164 | \item Ring signatures [Rivest, Shamir, Tauman~2001]. | |
165 | \end{itemize} | |
166 | \end{frame} | |
167 | ||
168 | %%%-------------------------------------------------------------------------- | |
169 | \section{Definitions} | |
170 | ||
171 | \subsection{Secrecy and authenticity} | |
172 | ||
173 | \begin{frame}{Formal definitions}{Secrecy and authenticity} | |
174 | Multiparty outsider \alert<5-7>{secrecy} and \alert<8>{authenticity} [An, | |
175 | Dodis, Rabin~2002]. | |
176 | \begin{block}{} | |
177 | \centering | |
178 | \begin{tikzpicture} | |
179 | \node[mugshot] (adv) at (0, 0) {\mugshot{adv.png}}; | |
180 | \visible<2->{ | |
181 | \node[mugshot] (alice) at (-5, 2) {\mugshot{alice.png}}; | |
182 | } | |
183 | \visible<3->{ | |
184 | \node[mugshot] (bob) at (+5, 2) {\mugshot{bob.png}}; | |
185 | } | |
186 | \visible<2->{ | |
187 | \path node[above = of adv] | |
188 | {{$A$\visible<3->{, $B$}}} edge[->] (adv); | |
189 | } | |
190 | \visible<4->{ | |
191 | \draw[->, offset = {(0mm, 5mm)}] | |
192 | (adv) to node[above, sloped] {$m$, $Z$} (alice); | |
193 | \draw[->, offset = {(0mm, 2mm)}] | |
194 | (alice) to node[below, sloped] {$E_a(Z, m)$} (adv); | |
195 | \draw[->, offset = {(0mm, 5mm)}] | |
196 | (adv) to node[above, sloped] {$c$, $Z$} (bob); | |
197 | \draw[->, offset = {(0mm, 2mm)}] | |
198 | (bob) to node[below, sloped] {$D_b(Z, c)$} (adv); | |
199 | } | |
200 | \visible<5-7>{ | |
201 | \path[offset = {(0mm, -2mm)}] node[right = of adv] | |
202 | {$m_0$, $m_1$} edge[<-] (adv); | |
203 | } | |
204 | \visible<6-7>{ | |
205 | \path[offset = {(0mm, -6mm)}] node[right = of adv] | |
206 | {$c^* = E_a(B, m_\sigma)$} | |
207 | edge[->] (adv); | |
208 | } | |
209 | \visible<7>{ | |
210 | \path[offset = {(0mm, -10mm)}] node[right = of adv] | |
211 | {Guess $\sigma = \textbf?$} | |
212 | edge[<-] (adv); | |
213 | } | |
214 | \visible<8>{ | |
215 | \path[offset = {(0mm, -6mm)}] node[right = of adv, text width = 40mm] | |
216 | {New $c^*$ with \\ $D_b(A, c^*) \ne \bot$} | |
217 | edge[<-] (adv); | |
218 | } | |
219 | \end{tikzpicture} | |
220 | \end{block} | |
221 | \begin{block}{} | |
222 | \begin{overprint} | |
223 | \onslide<+> There is always an adversary. | |
224 | \onslide<+> We add a sender, Alice: private key $a$, public key $A$. | |
225 | \onslide<+> And a recipient, Bob: private key $b$, public key $B$. | |
226 | \onslide<+> Makes encryption and decryption queries with arbitrary public | |
227 | keys $Z$. | |
228 | \onslide<+> Adversary chooses two messages of equal length. | |
229 | \onslide<+> We encrypt one of them. | |
230 | \onslide<+> Adversary tries to guess which. | |
231 | \onslide<+> Adversary tries to construct forgery. | |
232 | \end{overprint} | |
233 | \end{block} | |
234 | \end{frame} | |
235 | ||
236 | \subsection{Strong deniability} | |
237 | ||
238 | \begin{frame}<1-8>[label = deny]{Formal definitions}{Deniability} | |
239 | \kern-2ex | |
240 | \begin{block}{} | |
241 | \centering | |
242 | \begin{tikzpicture}[every to/.style = {sloped, font = \footnotesize}] | |
243 | \node[mugshot] (alice) at (-5, -1.5) {\mugshot{alice.png}}; | |
244 | \node[mugshot] (bob) at (+5, +1.5) {\mugshot{bob.png}}; | |
245 | \visible<2->{ | |
246 | \node[mugshot] (justin) at ( 0, 0) {\mugshot{judge.png}}; | |
247 | } | |
248 | \visible<4-8,10->{ | |
249 | \node[mugshot] (robot-bob) at (+5, -1.5) {\mugshot{robot-bob.png}}; | |
250 | } | |
251 | \visible<12->{ | |
252 | \node[mugshot] (robot-alice) at (-5, +1.5) | |
253 | {\mugshot{robot-alice.png}}; | |
254 | } | |
255 | ||
256 | \visible<3-8>{ | |
257 | \draw[->, offset = {(0mm, +4mm)}] (bob) to | |
258 | node[above] {$m$} node[below] {$c = E_a(B, m)$} | |
259 | (justin); | |
260 | } | |
261 | \visible<4->{ | |
262 | \draw[dashed] | |
263 | ($(bob.east |- justin) - (3\jot, 0pt)$) -- (justin.east); | |
264 | } | |
265 | \visible<4-8>{ | |
266 | \draw[<->, offset = {(0mm, -2.5mm)}] (robot-bob) to | |
267 | node[above] {$m'$} | |
268 | (justin); | |
269 | \draw[->, offset = {(0mm, -5.5mm)}] (robot-bob) to | |
270 | node[below] {$c' = R_b(A, \only<7->{\alert<7>{c},} m')$} | |
271 | (justin); | |
272 | } | |
273 | \visible<5-8,13>{ | |
274 | \node[below = of justin] {$a$, $b$} edge[->] (justin); | |
275 | } | |
276 | \visible<6,13>{ | |
277 | \node[thought = justin.north] at ($(justin.north) + (1/3, 1/2)$) | |
278 | {\large\bfseries ?}; | |
279 | } | |
280 | ||
281 | \visible<9->{ | |
282 | \draw[dashed] | |
283 | ($(alice.west |- justin) + (3\jot, 0pt)$) -- (justin.west); | |
284 | } | |
285 | \visible<10->{ | |
286 | \draw[->, offset = {(0mm, -4mm)}] (alice) to | |
287 | node[above] {$m_0$} node[below] {$c_0 = E_a(B, m_0)$} | |
288 | (justin); | |
289 | \draw[<->, offset = {(0mm, -2.5mm)}] (robot-bob) to | |
290 | node[above] {$m_1$} | |
291 | (justin); | |
292 | \draw[->, offset = {(0mm, -5.5mm)}] (robot-bob) to | |
293 | node[below] {$c_1 = R_b(A, c_0, m_1)$} | |
294 | (justin); | |
295 | } | |
296 | \visible<11->{ | |
297 | \draw[->, offset = {(0mm, +4mm)}] (bob) to | |
298 | node[above] {$m_1$} node[below] {$c'_1 = E_a(B, m_1)$} | |
299 | (justin); | |
300 | } | |
301 | \visible<12->{ | |
302 | \draw[<->, offset = {(0mm, +5.5mm)}] (robot-alice) to | |
303 | node[above] {$m_0$} | |
304 | (justin); | |
305 | \draw[->, offset = {(0mm, +2.5mm)}] (robot-alice) to | |
306 | node[below] {$c'_0 = S_a(A, c'_1, m_0)$} | |
307 | (justin); | |
308 | } | |
309 | \end{tikzpicture} | |
310 | \end{block} | |
311 | \begin{block}{} | |
312 | \begin{overprint} | |
313 | \onslide<+> Start with a sender (Alice) and recipient (Bob). | |
314 | \onslide<+> Bob will try to convince a \emph{judge} (Justin) that Alice | |
315 | created a message. | |
316 | \onslide<+> Bob gives Justin the ciphertext $c$ and message $m$. | |
317 | \onslide<+> Simulator constructs ciphertext $c'$ for another message | |
318 | $m'$. | |
319 | \onslide<+> We give Alice and Bob's private keys to Justin. | |
320 | \onslide<+> \emph{Strong deniability} if Justin can't distinguish. | |
321 | \onslide<+> Useful relaxation: allow simulator a sample ciphertext. | |
322 | \onslide<+> Unfortunately, this definition is now too simplistic. | |
323 | \onslide<+> We need a richer model. | |
324 | \onslide<+> Scenario $A$: Bob's ciphertext is simulated; Alice has the | |
325 | genuine one. | |
326 | \onslide<+> Scenario $B$: Bob's ciphertext is genuine. | |
327 | \onslide<+> Alice must construct her own simulated ciphertext. | |
328 | \onslide<+> \emph{Weak deniability} if Justin can't distinguish. | |
329 | \end{overprint} | |
330 | \end{block} | |
331 | \end{frame} | |
332 | ||
333 | \subsection{Weak deniability} | |
334 | ||
335 | \begin{frame}{Weak deniability}{What goes wrong?} | |
336 | \kern-2ex | |
337 | \begin{block}{} | |
338 | \begin{itemize}[<+->] | |
339 | \item Simulator accepts sample ciphertext as input. | |
340 | \item If the simulator was used, there must be two related ciphertexts. | |
341 | \item If no simulator was used, \dots | |
342 | \end{itemize} | |
343 | \end{block} | |
344 | \begin{block}<+->{Example: chameleon signatures [Krawczyk, Rabin 1998]} | |
345 | \begin{itemize}[<+->] | |
346 | \item Trapdoor commitments: public key $T$, private key $t$. | |
347 | \begin{itemize}[<+->] | |
348 | \item Commitment: choose random $\rho$, commitment is $c = C_T(m; | |
349 | \rho)$. | |
350 | \item Binding property: hard to find $(m', \rho') \ne (m, \rho)$ with | |
351 | $c = C_T(m'; \rho')$. | |
352 | \item Trapdoor opening: given $t$ and any $m'$, it's easy to find | |
353 | $\rho'$ with $c = C_T(m'; \rho')$. | |
354 | \end{itemize} | |
355 | \item Signatures: recipient (Bob) has trapdoor $t$. | |
356 | \begin{itemize}[<+->] | |
357 | \item To sign $m$ for Bob: $c \gets C_T(m; \rho)$; $\sigma \gets S_a(c, | |
358 | B)$: signature is $(c, \rho, \sigma)$. | |
359 | \item Bob can forge using his trapdoor. Alice repudiates forgeries by | |
360 | revealing collision in $C_T$. | |
361 | \item But Alice can't repudiate genuine signature: deniability failure. | |
362 | \end{itemize} | |
363 | \end{itemize} | |
364 | \end{block} | |
365 | \end{frame} | |
366 | ||
367 | \againframe<9-13>{deny} | |
368 | ||
369 | \begin{frame}{Weak deniability}{Security and authenticity revisited} | |
370 | \kern-2ex | |
371 | \begin{block}{} | |
372 | \centering | |
373 | \begin{tikzpicture} | |
374 | \node[mugshot] (adv) at (0, 0) {\mugshot{adv.png}}; | |
375 | \node[mugshot] (alice) at (-5, 1.5) {\mugshot{alice.png}}; | |
376 | \node[mugshot] (bob) at (+5, 1.5) {\mugshot{bob.png}}; | |
377 | \path node[above = of adv] {$A$, $B$} edge[->] (adv); | |
378 | \draw[->, offset = {(0mm, 5.5mm)}] | |
379 | (adv) to node[above, sloped] {$m$, $Z$} (alice); | |
380 | \draw[->, offset = {(0mm, 2.5mm)}] | |
381 | (alice) to node[below, sloped] {$E_a(Z, m)$} (adv); | |
382 | \draw[->, offset = {(0mm, 5.5mm)}] | |
383 | (adv) to node[above, sloped] {$c$, $Z$} (bob); | |
384 | \draw[->, offset = {(0mm, 2.5mm)}] | |
385 | (bob) to node[below, sloped] {$D_b(Z, c)$} (adv); | |
386 | \path[offset = {(0mm, -2mm)}] node[right = of adv] {} edge[<-] (adv); | |
387 | \path[offset = {(0mm, -6mm)}] node[right = of adv] {} edge[->] (adv); | |
388 | \path[offset = {(0mm, -10mm)}] node[right = of adv] {} edge[<-] (adv); | |
389 | \visible<2->{ | |
390 | \node[mugshot] (robot-bob) at (-5, -1.5) {\mugshot{robot-bob.png}}; | |
391 | \draw[->, offset = {(0mm, -2.5mm)}] | |
392 | (adv) to node[above, sloped] {$m$, $Z$, $c$} (robot-bob); | |
393 | \draw[<-, offset = {(0mm, -5.5mm)}] | |
394 | (adv) to node[below, sloped] {$R_b(Z, c, m)$} (robot-bob); | |
395 | } | |
396 | \end{tikzpicture} | |
397 | \end{block} | |
398 | \begin{block}{} | |
399 | \begin{overprint} | |
400 | \onslide<+> With weak deniability, simulator works on an input | |
401 | ciphertext. | |
402 | \onslide<+> Must therefore allow adversary access to the simulator. | |
403 | \end{overprint} | |
404 | \end{block} | |
405 | \end{frame} | |
406 | ||
407 | %%%-------------------------------------------------------------------------- | |
408 | \section{Constructions} | |
409 | ||
410 | \subsection{Authentication tokens} | |
411 | ||
412 | \begin{frame}{Authentication tokens}{The basic idea} | |
413 | \kern-2ex | |
414 | \begin{block}{} | |
415 | \centering | |
416 | \begin{tikzpicture} | |
417 | \node[mugshot] (alice) {\mugshot{alice.png}}; | |
418 | \node[mugshot] (bob) at (10, 0) {\mugshot{bob.png}}; | |
419 | \node[mugshot] (eve) at (5, -1.5) {\mugshot{adv.png}}; | |
420 | \visible<2->{ | |
421 | \draw[->] (alice) to | |
422 | node[above] | |
423 | {$E_B(\visible<3->{\textrm{`\texttt{Eve is nosey}'},} m)$} | |
424 | (bob); | |
425 | } | |
426 | \end{tikzpicture} | |
427 | \end{block} | |
428 | \setcounter{beamerpauses}{3} | |
429 | \begin{block}{} | |
430 | \begin{itemize}[<+->] | |
431 | \item Alice and Bob can agree a password to be included in their | |
432 | encrypted messages. | |
433 | \item If the encryption is any good, an adversary can't work out the | |
434 | password. | |
435 | \item So he can't impersonate them to each other. | |
436 | \end{itemize} | |
437 | \end{block} | |
438 | \end{frame} | |
439 | ||
440 | \begin{frame}{Authentication tokens}{Definition} | |
441 | \kern-2ex | |
442 | \begin{block}{} | |
443 | \begin{itemize}[<+->] | |
444 | \item Key generation: $G() \to (x, X)$. | |
445 | \item<9-> \alert{Binding:} $B_x(X') \to \beta$. | |
446 | \item Token construction: $T_x(\only<.-8>{Y}\only<9->{\alert{\beta}}) | |
447 | \to \tau \in \{0, 1\}^t$. | |
448 | \item Verification: $V_y(X, \only<9->{\alert{\beta},} \tau) \to | |
449 | v \in \{0, 1\}$. | |
450 | \end{itemize} | |
451 | \end{block} | |
452 | \begin{block}<+->{} | |
453 | \centering | |
454 | \begin{tikzpicture} | |
455 | \node[mugshot] (adv) at (0, 0) {\mugshot{adv.png}}; | |
456 | \node[mugshot] (alice) at (-5, 1.5) {\mugshot{alice.png}}; | |
457 | \node[mugshot] (bob) at (+5, 1.5) {\mugshot{bob.png}}; | |
458 | \visible<5->{ | |
459 | \path[offset = {(0mm, -6mm)}] node[left = of adv] | |
460 | {$A$\only<9->{, \alert{$\alpha$}}, $B$\only<9->{, \alert{$\beta$}}} | |
461 | edge[->] (adv); | |
462 | } | |
463 | \visible<6->{ | |
464 | \draw[->, offset = {(0mm, 5mm)}] | |
465 | (adv) to node[above, sloped] | |
466 | {$\only<-8>{Z}\only<9->{\alert{\gamma}}$} (alice); | |
467 | \draw[->, offset = {(0mm, 3mm)}] | |
468 | (alice) to node[below, sloped] | |
469 | {$T_a(\only<-8>{Z}\only<9->{\alert{\gamma}})$} | |
470 | (adv); | |
471 | } | |
472 | \visible<7->{ | |
473 | \draw[->, offset = {(0mm, 5mm)}] | |
474 | (adv) to node[above, sloped] {$Z$, $\tau$} (bob); | |
475 | \draw[->, offset = {(0mm, 3mm)}] | |
476 | (bob) to node[below, sloped] | |
477 | {$V_b(Z \only<9->{,\alert{\beta}}, \tau)$} (adv); | |
478 | } | |
479 | \visible<8->{ | |
480 | \path[offset = {(0mm, -6mm)}] node[right = of adv, text width = 40mm] | |
481 | {New $\tau^*$ with \\ | |
482 | $V_b(A\only<9->{, \alert{\beta}}, \tau^*) = 1$} | |
483 | edge[<-] (adv); | |
484 | } | |
485 | \end{tikzpicture} | |
486 | \end{block} | |
487 | \end{frame} | |
488 | ||
489 | \begin{frame}{Authentication tokens}{Deniably authenticated encryption} | |
490 | \begin{columns} | |
491 | \column{0.45\textwidth} | |
492 | \begin{block}{} | |
493 | \centering | |
494 | \begin{tikzpicture}[node distance = 5mm] | |
495 | \visible<+->{ | |
496 | \node[box = yellow!20, minimum width = 30mm] (m) {$m$}; | |
497 | } | |
498 | \visible<+->{ | |
499 | \node[box = green!20, left = -0.6pt of m] (tau) {$\tau$}; | |
500 | \node[op = green!20, above = of tau] (token) {$T$} edge[->] (tau); | |
501 | \node[left = of token] {$x_\textsc{tok}$} edge[->] (token); | |
502 | \node[above = of token] {$\beta$} edge[->] (token); | |
503 | } | |
504 | \visible<+->{ | |
505 | \draw[decorate, decoration = brace] | |
506 | (m.south east) -- (tau.south west) | |
507 | coordinate [pos = 0.5, below = 2.5pt] (p); | |
508 | \node[op = red!20, below = of p] (e) {$E$} edge[<-] (p); | |
509 | \node[left = of e] {$Y_\textsc{ae}$} edge[->] (e); | |
510 | \node[box = red!20, minimum width = 30mm + 15.6pt, below = of e] | |
511 | {$c$} edge[<-] (e); | |
512 | } | |
513 | \end{tikzpicture} | |
514 | \end{block} | |
515 | \column{0.50\textwidth} | |
516 | \begin{block}<+->{} | |
517 | \begin{description}[<+->] | |
518 | \item[Secrecy] Direct from encryption IND-CCA. | |
519 | \item[Authenticity] From encryption IND-CCA, token unpredictability, | |
520 | and key binding. | |
521 | \item[Deniability] Unconditionally weakly deniable. Strongly deniable | |
522 | if recipient can simulate tokens. | |
523 | \end{description} | |
524 | \end{block} | |
525 | \end{columns} | |
526 | \end{frame} | |
527 | ||
528 | \begin{frame}{Authentication tokens}{Instantiations} | |
529 | \kern-2ex | |
530 | \begin{block}<+->{Simple tokens from signatures} | |
531 | \begin{itemize}[<+->] | |
532 | \item Token key is just a signature key. | |
533 | \item Binding value is simply (hash of) rest of public key. | |
534 | \item Token is signature on recipient's binding value. | |
535 | \item Need constant-length signatures. | |
536 | \item Security directly from signature unforgeability. | |
537 | \end{itemize} | |
538 | \end{block} | |
539 | \begin{block}<+->{Deniable tokens from Diffie--Hellman} | |
540 | \begin{itemize}[<+->] | |
541 | \item Group $(G, +)$, generated by $P$; $\#G = p$ prime. | |
542 | \item Token private key $a \in \gf{p}$; public key $A = a P$. | |
543 | \item Binding: non-malleable NIZK proof-of-knowledge of $a$ and signature | |
544 | key. | |
545 | \item Security from NIZK and computational Diffie--Hellman in $G$. | |
546 | \end{itemize} | |
547 | \end{block} | |
548 | \end{frame} | |
549 | ||
550 | \subsection{Signing tags} | |
551 | ||
552 | \begin{frame}{Signing tags}{Background on key-encapsulation mechanisms} | |
553 | \kern-2ex | |
554 | \begin{block}<+->{Basic idea} | |
555 | \begin{itemize}[<+->] | |
556 | \item Asymmetric primitives often used to transport symmetric keys. | |
557 | \item Sender doesn't usually care about the key's specific value. | |
558 | \item Can improve efficiency and security by taking advantage of this. | |
559 | \end{itemize} | |
560 | \end{block} | |
561 | \kern-4ex | |
562 | \begin{columns} | |
563 | \column{0.41\textwidth} | |
564 | \begin{block}<+->{} | |
565 | \begin{itemize}[<+->] | |
566 | \item Key gen: $G() \to (x, X)$ | |
567 | \item Encap: $\mathcal{E}_X() \to (K, u)$ | |
568 | \item Decap: $\mathcal{D}_x(u) \to K'$ | |
569 | \end{itemize} | |
570 | \end{block} | |
571 | \column{0.55\textwidth} | |
572 | \begin{block}<+->{} | |
573 | \centering | |
574 | \begin{tikzpicture}[ | |
575 | node distance = 15mm, | |
576 | every to/.style = {font = \footnotesize}] | |
577 | \node[mugshot] (adv) {\mugshot{adv.png}}; | |
578 | \visible<+->{ | |
579 | \path[offset = {(0mm, 8mm)}] | |
580 | node[right = of adv] {$X$, $u^*$} | |
581 | edge [->] (adv); | |
582 | } | |
583 | \visible<+->{ | |
584 | \node[below left = 4mm and -10mm of adv, text depth = 2pt] | |
585 | {$K_0 \inr \{0, 1\}^k$} | |
586 | edge [->] (adv); | |
587 | \node[below right = 4mm and -10mm of adv, text depth = 2pt] | |
588 | {$K_1 = D_x(u^*)$} | |
589 | edge [->] (adv); | |
590 | \draw[dashed] (adv.south) -- +(0, -1); | |
591 | } | |
592 | \visible<+->{ | |
593 | \path[offset = {(0mm, 0mm)}] | |
594 | node[draw, fill = blue!20, right = of adv] (oracle) | |
595 | {$\mathcal{D}_x(\cdot)$}; | |
596 | \draw[offset = {(0mm, 1.5mm)}, ->] | |
597 | (adv) to node[above] {$u$} (oracle); | |
598 | \draw[offset = {(0mm, -1.5mm)}, <-] | |
599 | (adv) to node[below] {$\mathcal{D}_x(u)$} (oracle); | |
600 | } | |
601 | \visible<+->{ | |
602 | \path[offset = {(0mm, -10mm)}] | |
603 | node[right = of adv] {\textbf{?}} | |
604 | edge[<-] (adv); | |
605 | } | |
606 | \end{tikzpicture} | |
607 | \end{block} | |
608 | \end{columns} | |
609 | \end{frame} | |
610 | ||
611 | \begin{frame}<1-9>[label = kem]{Signing tags}{Weakly deniably authenticated | |
612 | asymmetric encryption} | |
613 | \begin{columns} | |
614 | \column{0.5\textwidth} | |
615 | \begin{block}{} | |
616 | \centering | |
617 | \begin{tikzpicture}[node distance = 5mm] | |
618 | \visible<1->{ | |
619 | \node[box = yellow!20, minimum width = 30mm] (m) {$m$}; | |
620 | } | |
621 | \visible<3->{ | |
622 | \node[op = red!20, below = of m] (enc) {$E$} | |
623 | edge[<-] (m); | |
624 | \node[box = red!20, minimum width = 30mm + 15pt, below = of enc] | |
625 | (c) {$c$} | |
626 | edge[<-] (enc); | |
627 | } | |
628 | \visible<5->{ | |
629 | \node[box = green!20, right = -0.6pt of c] (sig) {$\sigma$}; | |
630 | \node[op = green!20, above = 10mm] at (sig |- m) (s) {$S$} | |
631 | edge[->] (sig); | |
632 | \node[above = of s] {$a'$} edge[->] (s); | |
633 | } | |
634 | \visible<6->{ | |
635 | \draw[->] (s |- enc) -- (enc); | |
636 | } | |
637 | \visible<4->{ | |
638 | \node[box = green!20, left = 25mm of s, below] (t2) {$\tau$}; | |
639 | \node[box = blue!20, above = -0.6pt of t2] (b2) {$B$}; | |
640 | \draw[decorate, decoration = brace] | |
641 | (b2.north east) -- (t2.south east) | |
642 | coordinate[pos = 0.5, right = 2.5pt] (sm); | |
643 | } | |
644 | \visible<5->{ | |
645 | \draw[->] (sm) -- (s); | |
646 | } | |
647 | \visible<2->{ | |
648 | \node[box = green!20, left = of t2] (tag) {$\tau$}; | |
649 | \node[box = red!20, left = -0.6pt of tag] (k) {$K$}; | |
650 | \draw[decorate, decoration = brace] | |
651 | (k.north west) -- (tag.north east) | |
652 | coordinate[pos = 0.5, above = 2.5pt] (z); | |
653 | \node[op = blue!20, above = 8mm of z] (kem) {$\mathcal{E}$} | |
654 | edge[->] (z); | |
655 | \node[box = blue!20, left = -0.6pt of c] (u) {$u$}; | |
656 | \draw[rounded, ->] (kem) -| +(-10mm, -8mm) |- (u); | |
657 | \node (b) at (kem -| b2) {$B$} edge[->] (kem); | |
658 | } | |
659 | \visible<4->{ | |
660 | \draw[->] (tag) -- (t2); | |
661 | } | |
662 | \visible<3->{ | |
663 | \draw[rounded, ->] (k) |- (enc); | |
664 | } | |
665 | \visible<4->{ | |
666 | \draw[->] (b) -- (b2); | |
667 | } | |
668 | \end{tikzpicture} | |
669 | \end{block} | |
670 | \column{0.45\textwidth} | |
671 | \setcounter{beamerpauses}{7} | |
672 | \begin{block}<+->{} | |
673 | \begin{description} | |
674 | \item<.(0)->[Secrecy] From KEM and symmetric IND-CCA. | |
675 | \item<.(2)->[Authenticity] \alt<-.(2)>{Fails!}{From KEM, symmetric | |
676 | INT-CTXT and KEM non-directability.} | |
677 | \item<.(1)->[Deniability] Weak deniability from message\slash signature | |
678 | separation. | |
679 | \end{description} | |
680 | \end{block} | |
681 | \end{columns} | |
682 | \end{frame} | |
683 | ||
684 | \begin{frame}{Signing tags}{Fixing authentication} | |
685 | \begin{block}{What causes the problem?} | |
686 | \begin{itemize}[<+->] | |
687 | \item Signatures don't have to hide the message signed. | |
688 | \item So adversary can discover the tag $\tau$. | |
689 | \item Might construct KEM clue with known $K$ and copied $\tau$ -- | |
690 | forgery! | |
691 | \end{itemize} | |
692 | \end{block} | |
693 | \begin{block}<+->{KEM non-directability} | |
694 | \begin{itemize}[<+->] | |
695 | \item Say KEM is $(t, n)$-\emph{non-directable} if, given $t$-bit strings | |
696 | $r_0$, $r_1$, \ldots, $r_{n-1}$, and a public key~$X$, it's hard to | |
697 | find a clue $u$ such that the last $t$ bits of $D_x(u)$ match any | |
698 | $r_i$. | |
699 | \item We prove non-directability for a large class of random-oracle KEMs. | |
700 | \item How hard is the Cramer--Shoup KEM to direct? | |
701 | \end{itemize} | |
702 | \end{block} | |
703 | \end{frame} | |
704 | ||
705 | \againframe<10>{kem} | |
706 | ||
707 | \subsection{NAIADs} | |
708 | ||
709 | \begin{frame}{NAIADs}{What's a NAIAD?} | |
710 | \alert{N}on-interactive \alert{A}symmetric \alert{I}ntegrity | |
711 | \alert{A}lgorithm with \alert{D}eniability. | |
712 | ||
713 | \begin{block}<+->{The basic idea} | |
714 | \begin{itemize}[<+->] | |
715 | \item Essentially the asymmetric analogue of a MAC. | |
716 | \item Given: private key, recipient's public key, and message, construct | |
717 | tag. | |
718 | \item Given: private key, sender's public key, message, and tag, verify | |
719 | that tag is correct. | |
720 | \item Simulator constructs convincing tags given \emph{recipient's} | |
721 | private key. | |
722 | \end{itemize} | |
723 | \end{block} | |
724 | \end{frame} | |
725 | ||
726 | \begin{frame}{NAIADs}{Definitions} | |
727 | \kern-2ex | |
728 | \begin{block}<+->{} | |
729 | \begin{itemize}[<+->] | |
730 | \item Key generation: $G() \to (x, X)$. | |
731 | \item Tagging: $T_x(Y, m) \to \tau$. | |
732 | \item Verification: $V_y(X, m, \tau) \to v \in \{0, 1\}$. | |
733 | \item Simulation: $R_y(X, m) \to \tau'$. | |
734 | \end{itemize} | |
735 | \end{block} | |
736 | \kern-1ex | |
737 | \begin{block}<only@+-+(4)>{Authenticity} | |
738 | \centering | |
739 | \begin{tikzpicture} | |
740 | \node[mugshot] (adv) {\mugshot{adv.png}}; | |
741 | \visible<+->{ | |
742 | \node[mugshot] (alice) at (-5, 1.5) {\mugshot{alice.png}}; | |
743 | \node[mugshot] (bob) at (+5, 1.5) {\mugshot{bob.png}}; | |
744 | \draw[offset = {(0mm, -4mm)}] | |
745 | node[left = of adv] {$A$, $B$} edge[->] (adv); | |
746 | } | |
747 | \visible<+->{ | |
748 | \path[offset = {(0mm, -4mm)}] node[right = of adv, text width = 40mm] | |
749 | {New $m^*$, $\tau^*$ with \\ $V_b(A, m^*, \tau^*) = 1$} | |
750 | edge[<-] (adv); | |
751 | } | |
752 | \visible<+->{ | |
753 | \draw[offset = {(0mm, +5.5mm)}, ->] | |
754 | (adv) to node[above, sloped]{$Z, m$} (alice); | |
755 | \draw[offset = {(0mm, +3.5mm)}, ->] | |
756 | (alice) to node[below, sloped]{$T_a(Z, m)$} (adv); | |
757 | } | |
758 | \visible<+->{ | |
759 | \draw[offset = {(0mm, +5.5mm)}, ->] | |
760 | (adv) to node[above, sloped]{$Z, m, \tau$} (bob); | |
761 | \draw[offset = {(0mm, +3.5mm)}, ->] | |
762 | (bob) to node[below, sloped]{$V_b(Z, m, \tau)$} (adv); | |
763 | } | |
764 | \end{tikzpicture} | |
765 | \end{block} | |
766 | \begin{block}<only@+->{Deniability} | |
767 | \centering | |
768 | \begin{tikzpicture} | |
769 | \node[mugshot] (justin) {\mugshot{judge.png}}; | |
770 | \visible<+->{ | |
771 | \node[mugshot] (bob) at (+5, 1.5) {\mugshot{bob.png}}; | |
772 | \draw[->, offset = {(0mm, +4mm)}, sloped] (bob) to | |
773 | node[above] {$m$} node[below] {$\tau = T_a(B, m)$} | |
774 | (justin); | |
775 | } | |
776 | \visible<+->{ | |
777 | \node[mugshot] (robot-bob) at (-5, 1.5) {\mugshot{robot-bob.png}}; | |
778 | \draw[<->, offset = {(0mm, 5.5mm)}, sloped] (robot-bob) to | |
779 | node[above] {$m'$} | |
780 | (justin); | |
781 | \draw[->, offset = {(0mm, 2.5mm)}, sloped] (robot-bob) to | |
782 | node[below] {$\tau' = R_b(A, m')$} | |
783 | (justin); | |
784 | } | |
785 | \visible<+->{ | |
786 | \draw[offset = {(0mm, -4mm)}] | |
787 | node[left = of justin] | |
788 | {$a$, $b$} edge[->] (justin); | |
789 | } | |
790 | \visible<+->{ | |
791 | \node[thought = justin.north] at ($(justin.north) + (1/3, 1/2)$) | |
792 | {\large\bfseries ?}; | |
793 | } | |
794 | \end{tikzpicture} | |
795 | \end{block} | |
796 | \end{frame} | |
797 | ||
798 | \begin{frame}{NAIADs}{Strongly deniably authenticated asymmetric encryption} | |
799 | \kern-5ex | |
800 | \begin{columns} | |
801 | \column{0.45\textwidth} | |
802 | \begin{block}{} | |
803 | \centering | |
804 | \begin{tikzpicture}[node distance = 5mm] | |
805 | \visible<+->{ | |
806 | \node[box = yellow!20, minimum width = 30mm] (m) {$m$}; | |
807 | } | |
808 | \visible<+->{ | |
809 | \node[box = green!20, right = -0.6pt of m] (tau) {$\tau$}; | |
810 | \node[op = green!20, above = of tau] (t) {$T$} edge[->] (tau); | |
811 | \node[above = of t] {$a'$} edge[->] (t); | |
812 | \node[right = of t] {$B'$} edge[->] (t); | |
813 | \draw[->, rounded] (m) |- (t); | |
814 | } | |
815 | \visible<+->{ | |
816 | \draw[decorate, decoration = brace] | |
817 | (tau.south east) -- (m.south west) | |
818 | coordinate[pos = 0.5, below = 2.5pt] (p); | |
819 | \node[op = red!20, below = of p] (enc) {$E$} edge[<-] (p); | |
820 | \node[left = of enc] {$B$} edge[->] (enc); | |
821 | \node[box = red!20, minimum width = 30mm + 15pt, below = of enc] | |
822 | (c) {$c$} edge[<-] (enc); | |
823 | } | |
824 | \end{tikzpicture} | |
825 | \end{block} | |
826 | \column{0.50\textwidth} | |
827 | \begin{block}<+->{} | |
828 | \begin{description}[<+->] | |
829 | \item[Secrecy] Direct from encryption IND-CCA. | |
830 | \item[Authenticity] From encryption IND-CCA and NAIAD authenticity. | |
831 | \item[Deniability] From NAIAD deniability. | |
832 | \end{description} | |
833 | \end{block} | |
834 | \end{columns} | |
835 | \begin{block}<+->{Other constructions} | |
836 | \begin{itemize}[<+->] | |
837 | \item Use $T_a(B, A')$ as a deniable authentication token | |
838 | \item Use NAIAD in place of signature in `signed tag' construction. | |
839 | \end{itemize} | |
840 | \end{block} | |
841 | \end{frame} | |
842 | ||
843 | \begin{frame}{NAIADs}{Instantiations} | |
844 | \begin{block}<+->{Existing techniques} | |
845 | \begin{itemize}[<+->] | |
846 | \item Ring signature, with sender and recipient as the signers. | |
847 | \item Some non-disavowable designated-verifier signatures, e.g., [Lipmaa, | |
848 | Wang, Bao~2005]. | |
849 | \end{itemize} | |
850 | \end{block} | |
851 | \begin{block}<+->{New technique} | |
852 | Paper describes a new NAIAD, secure in the random oracle model assuming | |
853 | the difficulty of the computational Diffie--Hellman problem. | |
854 | \end{block} | |
855 | \end{frame} | |
856 | ||
857 | \begin{frame}{The end} | |
858 | \centering | |
859 | \hbox{} | |
860 | \vfill | |
861 | \Large Thanks for listening. | |
862 | \vskip 20mm | |
863 | \Huge \sffamily Questions? | |
864 | \vfill \vfill | |
865 | \end{frame} | |
866 | ||
867 | \end{document} | |
868 | ||
869 | %%% Local variables: | |
870 | %%% mode: LaTeX | |
871 | %%% TeX-PDF-mode: t | |
872 | %%% End: |