~mdw / doc / deny / blame
| 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: |