| 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: |