%%% Deniably authenticated asymmetric encryption
%%%
%%% Copyright (c) 2010 Mark Wooding
%%% Licence: CC-BY

\documentclass[t]{beamer}
\usetheme{Madrid}
\usefonttheme{professionalfonts}
\usefonttheme[stillsansseriflarge, stillsansserifsmall]{serif}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[palatino, helvetica, courier, maths = cmr]{mdwfonts}
\usepackage{tikz}
\usepackage{crypto, mdwmath}
\usetikzlibrary{%
  shapes.symbols,shapes.callouts,%
  decorations.pathreplacing,positioning,calc}

\title{Deniably authenticated asymmetric encryption}
\author[Mark Wooding]{Mark Wooding \\ \texttt{mdw@distorted.org.uk}}
\institute{}

\def\Xid#1#2{\textsc{$#1$}-#2}
\def\proto#1{\Pi_\textsc{#1}}
\def\mugshot{\includegraphics[width = 2cm, height = 2.5cm, keepaspectratio]}
\def\random{\$}

\tikzset{
  mugshot/.style = {draw, fill = white, inner sep = 0, outer sep = \jot},
  thought/.style = {
    shape = cloud callout, cloud ignores aspect, draw, fill = white,
    cloud puffs = 20, cloud puff arc = 110,
    callout absolute pointer = (#1)
  },
  box/.style = {draw, minimum size = 16pt, fill = #1},
  op/.style = {box = #1, shape = circle},
  rounded/.style = {rounded corners = 2mm},
  offset/.style = {transform canvas = {shift = {#1}}},
  > = stealth
}

\newcount\f

\begin{document}
\frame{\titlepage}
\frame{\frametitle{Outline}\tableofcontents}
\AtBeginSubsection{\frame{%
    \frametitle{Outline}%
    \tableofcontents[%
      sectionstyle = show/shaded,%
      subsectionstyle = show/shaded/shaded]%
}}

%%%--------------------------------------------------------------------------
\section{Introduction}

\subsection{Motivation: sign-then-encrypt failures}

\begin{frame}{Sign-then-encrypt}
  \animate<10-14>
  \begin{block}{}
    \begin{tikzpicture}
      \node[mugshot] (bob)   at (0, 0) {
        \only<1-18>{\mugshot{bob.png}}%
        \only<19->{\mugshot{bob-unthrilled.png}}
      };
      \visible<2->{
        \node[thought = bob.north] at ($(bob) + (2, 3)$)
          {\begin{tabular}{l}
              Private key $b$ \\
              \visible<5->{Alice's public key $A$} \\
            \end{tabular}};
      }
      \visible<3->{
        \node[mugshot] (alice) at (10, 0){
          \only<3-16>{\mugshot{alice.png}}%
          \only<17->{\mugshot{alice-fallen.png}}
        };
      }
      \visible<18->{
        \node[mugshot] (julian) at ($(bob)!1/2!(alice)$)
          {\mugshot{wl.png}};
      }
      \visible<4->{
        \node[thought = alice.north] at ($(alice) + (-2, 3)$)
          {\begin{tabular}{l}
              Private key $a$ \\
              \visible<5->{Bob's public key $B$} \\
            \end{tabular}};
      }
      \animatevalue<9-15>{\f}{2}{8}
      \only<1-8>{\tikzset{message/.style = {}}}
      \only<9->{\tikzset{message/.style = {draw, fill = white}}}
      \visible<6->{
        \node[message] at ($(bob.east)!\f/10!(alice.west)$)
          { $\visible<8-15>{E_A(}
            m \visible<7->{, S_b(m)} \visible<8-15>{)} $};
      }
    \end{tikzpicture}
  \end{block}
  \begin{block}{}
    \begin{overprint}
    \onslide<+-+(1)> Meet Bob.  \visible<+>{Bob has a private key.}
    \onslide<+-+(1)> Bob meets Alice online.  \visible<+>{Alice has a
      private key too.}
    \onslide<+> Magically, they know each other's public keys.
    \onslide<+> Bob knows a secret.  He wants to send it to Alice.
    \onslide<+> Bob signs his message so that Alice knows it's from him.
    \onslide<+> He encrypts so nobody else knows what he's telling her.
    \onslide<+-+(6)> And then he sends the whole lot to Alice.
      \addtocounter{beamerpauses}{6}
    \onslide<+> Alice decrypts and verifies.
    \onslide<+> Alice isn't exactly a night in shining armour.
    \onslide<+> She publishes Bob's message and his signature.
    \onslide<+> Bob is not completely thrilled.
    \end{overprint}
  \end{block}
\end{frame}

\begin{frame}{Signatures and public-key encryption}
  \begin{itemize}[<+->]
  \item Lots of other problematic scenarios [Davis~2001].
  \item Encrypt-then-sign doesn't help much: recipient can publish NIZK proof
    of correct decryption.
  \item Signatures are universally verifiable.  Non-repudiation is
    undesirable when you're up to no good.
  \item Authenticated encryption is still valuable.  \visible<+>{Especially
      when you're up to no good.}
  \end{itemize}
\end{frame}

\subsection{Our contributions}

\begin{frame}{Deniably authenticated asymmetric encryption}
  \begin{block}{The basic idea}
    \begin{itemize}[<+->]
    \item Bob sends a message to Alice.
    \item Nobody else can read it (\emph{secrecy}).
    \item Alice knows that Bob sent it (\emph{authenticity}).
    \item Neither Alice nor Bob can prove that Bob sent it to anyone else
      (\emph{deniability}).
    \end{itemize}
  \end{block}
  \begin{block}<+->{We provide}
    \begin{itemize}[<+->]
    \item Formal definitions of security and deniability.
    \item Three constructions with various properties.
    \end{itemize}
  \end{block}
\end{frame}

\subsection{Previous work}

\begin{frame}{Previous and related work}
  \begin{itemize}[<+->]
  \item Deniable authentication since [Dolev, Dwork, Naor~1991]; also [Dwork,
    Naor, Sahai~19991], [Di~Raimondo, Gennaro~2005].  Intrinsically
    \emph{interactive}.
  \item Deniably authenticated key exchange [Di~Raimondo, Gennaro,
    Krawczyk~2006], e.g., SKEME [Krawczyk~1996], \emph{Off the Record}
    [Borisov, Goldberg, Brewer~2004], Wrestlers [Wooding~2006].  Also
    interactive.
  \item Chameleon signatures [Krawczyk, Rabin~1998].
  \item Ring signatures [Rivest, Shamir, Tauman~2001].
  \end{itemize}
\end{frame}

%%%--------------------------------------------------------------------------
\section{Definitions}

\subsection{Secrecy and authenticity}

\begin{frame}{Formal definitions}{Secrecy and authenticity}
  Multiparty outsider \alert<5-7>{secrecy} and \alert<8>{authenticity} [An,
  Dodis, Rabin~2002].
  \begin{block}{}
    \centering
    \begin{tikzpicture}
      \node[mugshot] (adv) at (0, 0) {\mugshot{adv.png}};
      \visible<2->{
        \node[mugshot] (alice) at (-5, 2) {\mugshot{alice.png}};
      }
      \visible<3->{
        \node[mugshot] (bob) at (+5, 2) {\mugshot{bob.png}};
      }
      \visible<2->{
        \path node[above = of adv]
          {{$A$\visible<3->{, $B$}}} edge[->] (adv);
      }
      \visible<4->{
        \draw[->, offset = {(0mm, 5mm)}]
          (adv) to node[above, sloped] {$m$, $Z$} (alice);
        \draw[->, offset = {(0mm, 2mm)}]
          (alice) to node[below, sloped] {$E_a(Z, m)$} (adv);
        \draw[->, offset = {(0mm, 5mm)}]
          (adv) to node[above, sloped] {$c$, $Z$} (bob);
        \draw[->, offset = {(0mm, 2mm)}]
          (bob) to node[below, sloped] {$D_b(Z, c)$} (adv);
      }
      \visible<5-7>{
        \path[offset = {(0mm, -2mm)}] node[right = of adv]
          {$m_0$, $m_1$} edge[<-] (adv);
      }
      \visible<6-7>{
        \path[offset = {(0mm, -6mm)}] node[right = of adv]
          {$c^* = E_a(B, m_\sigma)$}
          edge[->] (adv);
      }
      \visible<7>{
        \path[offset = {(0mm, -10mm)}] node[right = of adv]
          {Guess $\sigma = \textbf?$}
          edge[<-] (adv);
      }
      \visible<8>{
        \path[offset = {(0mm, -6mm)}] node[right = of adv, text width = 40mm]
          {New $c^*$ with \\ $D_b(A, c^*) \ne \bot$}
          edge[<-] (adv);
      }
    \end{tikzpicture}
  \end{block}
  \begin{block}{}
    \begin{overprint}
    \onslide<+> There is always an adversary.
    \onslide<+> We add a sender, Alice: private key $a$, public key $A$.
    \onslide<+> And a recipient, Bob: private key $b$, public key $B$.
    \onslide<+> Makes encryption and decryption queries with arbitrary public
      keys $Z$.
    \onslide<+> Adversary chooses two messages of equal length.
    \onslide<+> We encrypt one of them.
    \onslide<+> Adversary tries to guess which.
    \onslide<+> Adversary tries to construct forgery.
    \end{overprint}
  \end{block}
\end{frame}

\subsection{Strong deniability}

\begin{frame}<1-8>[label = deny]{Formal definitions}{Deniability}
  \kern-2ex
  \begin{block}{}
    \centering
    \begin{tikzpicture}[every to/.style = {sloped, font = \footnotesize}]
      \node[mugshot] (alice)         at (-5, -1.5) {\mugshot{alice.png}};
      \node[mugshot] (bob)           at (+5, +1.5) {\mugshot{bob.png}};
      \visible<2->{
        \node[mugshot] (justin)      at ( 0,  0)   {\mugshot{judge.png}};
      }
      \visible<4-8,10->{
        \node[mugshot] (robot-bob)   at (+5, -1.5) {\mugshot{robot-bob.png}};
      }
      \visible<12->{
        \node[mugshot] (robot-alice) at (-5, +1.5)
        {\mugshot{robot-alice.png}};
      }

      \visible<3-8>{
        \draw[->, offset = {(0mm, +4mm)}] (bob) to
          node[above] {$m$} node[below] {$c = E_a(B, m)$}
          (justin);
      }
      \visible<4->{
        \draw[dashed]
          ($(bob.east |- justin) - (3\jot, 0pt)$) -- (justin.east);
      }
      \visible<4-8>{
        \draw[<->, offset = {(0mm, -2.5mm)}] (robot-bob) to
          node[above] {$m'$}
          (justin);
        \draw[->, offset = {(0mm, -5.5mm)}] (robot-bob) to
          node[below] {$c' = R_b(A, \only<7->{\alert<7>{c},} m')$}
          (justin);
      }
      \visible<5-8,13>{
        \node[below = of justin] {$a$, $b$} edge[->] (justin);
      }
      \visible<6,13>{
        \node[thought = justin.north] at ($(justin.north) + (1/3, 1/2)$)
          {\large\bfseries ?};
      }

      \visible<9->{
        \draw[dashed]
          ($(alice.west |- justin) + (3\jot, 0pt)$) -- (justin.west);
      }
      \visible<10->{
        \draw[->, offset = {(0mm, -4mm)}] (alice) to
          node[above] {$m_0$} node[below] {$c_0 = E_a(B, m_0)$}
          (justin);
        \draw[<->, offset = {(0mm, -2.5mm)}] (robot-bob) to
          node[above] {$m_1$}
          (justin);
        \draw[->, offset = {(0mm, -5.5mm)}] (robot-bob) to
          node[below] {$c_1 = R_b(A, c_0, m_1)$}
          (justin);
      }
      \visible<11->{
        \draw[->, offset = {(0mm, +4mm)}] (bob) to
          node[above] {$m_1$} node[below] {$c'_1 = E_a(B, m_1)$}
          (justin);
      }
      \visible<12->{
        \draw[<->, offset = {(0mm, +5.5mm)}] (robot-alice) to
          node[above] {$m_0$}
          (justin);
        \draw[->, offset = {(0mm, +2.5mm)}] (robot-alice) to
          node[below] {$c'_0 = S_a(A, c'_1, m_0)$}
          (justin);
      }
    \end{tikzpicture}
  \end{block}
  \begin{block}{}
    \begin{overprint}
    \onslide<+> Start with a sender (Alice) and recipient (Bob).
    \onslide<+> Bob will try to convince a \emph{judge} (Justin) that Alice
      created a message.
    \onslide<+> Bob gives Justin the ciphertext $c$ and message $m$.
    \onslide<+> Simulator constructs ciphertext $c'$ for another message
      $m'$.
    \onslide<+> We give Alice and Bob's private keys to Justin.
    \onslide<+> \emph{Strong deniability} if Justin can't distinguish.
    \onslide<+> Useful relaxation: allow simulator a sample ciphertext.
    \onslide<+> Unfortunately, this definition is now too simplistic.
    \onslide<+> We need a richer model.
    \onslide<+> Scenario $A$: Bob's ciphertext is simulated; Alice has the
      genuine one.
    \onslide<+> Scenario $B$: Bob's ciphertext is genuine.
    \onslide<+> Alice must construct her own simulated ciphertext.
    \onslide<+> \emph{Weak deniability} if Justin can't distinguish.
    \end{overprint}
  \end{block}
\end{frame}

\subsection{Weak deniability}

\begin{frame}{Weak deniability}{What goes wrong?}
  \kern-2ex
  \begin{block}{}
    \begin{itemize}[<+->]
    \item Simulator accepts sample ciphertext as input.
    \item If the simulator was used, there must be two related ciphertexts.
    \item If no simulator was used, \dots
    \end{itemize}
  \end{block}
  \begin{block}<+->{Example: chameleon signatures [Krawczyk, Rabin 1998]}
    \begin{itemize}[<+->]
    \item Trapdoor commitments: public key $T$, private key $t$.
      \begin{itemize}[<+->]
      \item Commitment: choose random $\rho$, commitment is $c = C_T(m;
        \rho)$.
      \item Binding property: hard to find $(m', \rho') \ne (m, \rho)$ with
        $c = C_T(m'; \rho')$.
      \item Trapdoor opening: given $t$ and any $m'$, it's easy to find
        $\rho'$ with $c = C_T(m'; \rho')$.
      \end{itemize}
    \item Signatures: recipient (Bob) has trapdoor $t$.
      \begin{itemize}[<+->]
      \item To sign $m$ for Bob: $c \gets C_T(m; \rho)$; $\sigma \gets S_a(c,
        B)$: signature is $(c, \rho, \sigma)$.
      \item Bob can forge using his trapdoor.  Alice repudiates forgeries by
        revealing collision in $C_T$.
      \item But Alice can't repudiate genuine signature: deniability failure.
      \end{itemize}
    \end{itemize}
  \end{block}
\end{frame}

\againframe<9-13>{deny}

\begin{frame}{Weak deniability}{Security and authenticity revisited}
  \kern-2ex
  \begin{block}{}
    \centering
    \begin{tikzpicture}
      \node[mugshot] (adv) at (0, 0) {\mugshot{adv.png}};
      \node[mugshot] (alice) at (-5, 1.5) {\mugshot{alice.png}};
      \node[mugshot] (bob) at (+5, 1.5) {\mugshot{bob.png}};
      \path node[above = of adv] {$A$, $B$} edge[->] (adv);
      \draw[->, offset = {(0mm, 5.5mm)}]
        (adv) to node[above, sloped] {$m$, $Z$} (alice);
      \draw[->, offset = {(0mm, 2.5mm)}]
        (alice) to node[below, sloped] {$E_a(Z, m)$} (adv);
      \draw[->, offset = {(0mm, 5.5mm)}]
        (adv) to node[above, sloped] {$c$, $Z$} (bob);
      \draw[->, offset = {(0mm, 2.5mm)}]
        (bob) to node[below, sloped] {$D_b(Z, c)$} (adv);
      \path[offset = {(0mm, -2mm)}] node[right = of adv] {} edge[<-] (adv);
      \path[offset = {(0mm, -6mm)}] node[right = of adv] {} edge[->] (adv);
      \path[offset = {(0mm, -10mm)}] node[right = of adv] {} edge[<-] (adv);
      \visible<2->{
        \node[mugshot] (robot-bob) at (-5, -1.5) {\mugshot{robot-bob.png}};
        \draw[->, offset = {(0mm, -2.5mm)}]
          (adv) to node[above, sloped] {$m$, $Z$, $c$} (robot-bob);
        \draw[<-, offset = {(0mm, -5.5mm)}]
          (adv) to node[below, sloped] {$R_b(Z, c, m)$} (robot-bob);
      }
    \end{tikzpicture}
  \end{block}
  \begin{block}{}
    \begin{overprint}
      \onslide<+> With weak deniability, simulator works on an input
        ciphertext.
      \onslide<+> Must therefore allow adversary access to the simulator.
    \end{overprint}
  \end{block}
\end{frame}

%%%--------------------------------------------------------------------------
\section{Constructions}

\subsection{Authentication tokens}

\begin{frame}{Authentication tokens}{The basic idea}
  \kern-2ex
  \begin{block}{}
    \centering
    \begin{tikzpicture}
      \node[mugshot] (alice) {\mugshot{alice.png}};
      \node[mugshot] (bob) at (10, 0) {\mugshot{bob.png}};
      \node[mugshot] (eve) at (5, -1.5) {\mugshot{adv.png}};
      \visible<2->{
        \draw[->] (alice) to
          node[above]
            {$E_B(\visible<3->{\textrm{`\texttt{Eve is nosey}'},} m)$}
          (bob);
      }
    \end{tikzpicture}
  \end{block}
  \setcounter{beamerpauses}{3}
  \begin{block}{}
    \begin{itemize}[<+->]
    \item Alice and Bob can agree a password to be included in their
      encrypted messages.
    \item If the encryption is any good, an adversary can't work out the
      password.
    \item So he can't impersonate them to each other.
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}{Authentication tokens}{Definition}
  \kern-2ex
  \begin{block}{}
    \begin{itemize}[<+->]
    \item Key generation: $G() \to (x, X)$.
    \item<9-> \alert{Binding:} $B_x(X') \to \beta$.
    \item Token construction: $T_x(\only<.-8>{Y}\only<9->{\alert{\beta}})
      \to \tau \in \{0, 1\}^t$.
    \item Verification: $V_y(X, \only<9->{\alert{\beta},} \tau) \to
      v \in \{0, 1\}$.
    \end{itemize}
  \end{block}
  \begin{block}<+->{}
    \centering
    \begin{tikzpicture}
      \node[mugshot] (adv) at (0, 0) {\mugshot{adv.png}};
      \node[mugshot] (alice) at (-5, 1.5) {\mugshot{alice.png}};
      \node[mugshot] (bob) at (+5, 1.5) {\mugshot{bob.png}};
      \visible<5->{
        \path[offset = {(0mm, -6mm)}] node[left = of adv]
          {$A$\only<9->{, \alert{$\alpha$}}, $B$\only<9->{, \alert{$\beta$}}}
          edge[->] (adv);
      }
      \visible<6->{
        \draw[->, offset = {(0mm, 5mm)}]
          (adv) to node[above, sloped]
          {$\only<-8>{Z}\only<9->{\alert{\gamma}}$} (alice);
        \draw[->, offset = {(0mm, 3mm)}]
          (alice) to node[below, sloped]
          {$T_a(\only<-8>{Z}\only<9->{\alert{\gamma}})$}
          (adv);
      }
      \visible<7->{
        \draw[->, offset = {(0mm, 5mm)}]
          (adv) to node[above, sloped] {$Z$, $\tau$} (bob);
        \draw[->, offset = {(0mm, 3mm)}]
          (bob) to node[below, sloped]
          {$V_b(Z \only<9->{,\alert{\beta}}, \tau)$} (adv);
      }
      \visible<8->{
        \path[offset = {(0mm, -6mm)}] node[right = of adv, text width = 40mm]
          {New $\tau^*$ with \\
            $V_b(A\only<9->{, \alert{\beta}}, \tau^*) = 1$}
          edge[<-] (adv);
      }
    \end{tikzpicture}
  \end{block}
\end{frame}

\begin{frame}{Authentication tokens}{Deniably authenticated encryption}
  \begin{columns}
    \column{0.45\textwidth}
    \begin{block}{}
      \centering
      \begin{tikzpicture}[node distance = 5mm]
        \visible<+->{
          \node[box = yellow!20, minimum width = 30mm] (m) {$m$};
        }
        \visible<+->{
          \node[box = green!20, left = -0.6pt of m] (tau) {$\tau$};
          \node[op = green!20, above = of tau] (token) {$T$} edge[->] (tau);
          \node[left = of token] {$x_\textsc{tok}$} edge[->] (token);
          \node[above = of token] {$\beta$} edge[->] (token);
        }
        \visible<+->{
          \draw[decorate, decoration = brace]
            (m.south east) -- (tau.south west)
            coordinate [pos = 0.5, below = 2.5pt] (p);
          \node[op = red!20, below = of p] (e) {$E$} edge[<-] (p);
          \node[left = of e] {$Y_\textsc{ae}$} edge[->] (e);
          \node[box = red!20, minimum width = 30mm + 15.6pt, below = of e]
            {$c$} edge[<-] (e);
        }
      \end{tikzpicture}
    \end{block}
    \column{0.50\textwidth}
    \begin{block}<+->{}
      \begin{description}[<+->]
      \item[Secrecy] Direct from encryption IND-CCA.
      \item[Authenticity] From encryption IND-CCA, token unpredictability,
        and key binding.
      \item[Deniability] Unconditionally weakly deniable.  Strongly deniable
        if recipient can simulate tokens.
      \end{description}
    \end{block}
  \end{columns}
\end{frame}

\begin{frame}{Authentication tokens}{Instantiations}
  \kern-2ex
  \begin{block}<+->{Simple tokens from signatures}
    \begin{itemize}[<+->]
    \item Token key is just a signature key.
    \item Binding value is simply (hash of) rest of public key.
    \item Token is signature on recipient's binding value.
    \item Need constant-length signatures.
    \item Security directly from signature unforgeability.
    \end{itemize}
  \end{block}
  \begin{block}<+->{Deniable tokens from Diffie--Hellman}
    \begin{itemize}[<+->]
    \item Group $(G, +)$, generated by $P$; $\#G = p$ prime.
    \item Token private key $a \in \gf{p}$; public key $A = a P$.
    \item Binding: non-malleable NIZK proof-of-knowledge of $a$ and signature
      key.
    \item Security from NIZK and computational Diffie--Hellman in $G$.
    \end{itemize}
  \end{block}
\end{frame}

\subsection{Signing tags}

\begin{frame}{Signing tags}{Background on key-encapsulation mechanisms}
  \kern-2ex
  \begin{block}<+->{Basic idea}
    \begin{itemize}[<+->]
    \item Asymmetric primitives often used to transport symmetric keys.
    \item Sender doesn't usually care about the key's specific value.
    \item Can improve efficiency and security by taking advantage of this.
    \end{itemize}
  \end{block}
  \kern-4ex
  \begin{columns}
    \column{0.41\textwidth}
    \begin{block}<+->{}
      \begin{itemize}[<+->]
      \item Key gen: $G() \to (x, X)$
      \item Encap: $\mathcal{E}_X() \to (K, u)$
      \item Decap: $\mathcal{D}_x(u) \to K'$
      \end{itemize}
    \end{block}
    \column{0.55\textwidth}
    \begin{block}<+->{}
      \centering
      \begin{tikzpicture}[
        node distance = 15mm,
        every to/.style = {font = \footnotesize}]
        \node[mugshot] (adv) {\mugshot{adv.png}};
        \visible<+->{
          \path[offset = {(0mm, 8mm)}]
            node[right = of adv] {$X$, $u^*$}
            edge [->] (adv);
        }
        \visible<+->{
          \node[below left = 4mm and -10mm of adv, text depth = 2pt]
            {$K_0 \inr \{0, 1\}^k$}
            edge [->] (adv);
          \node[below right = 4mm and -10mm of adv, text depth = 2pt]
            {$K_1 = D_x(u^*)$}
            edge [->] (adv);
          \draw[dashed] (adv.south) -- +(0, -1);
        }
        \visible<+->{
          \path[offset = {(0mm, 0mm)}]
            node[draw, fill = blue!20, right = of adv] (oracle)
            {$\mathcal{D}_x(\cdot)$};
          \draw[offset = {(0mm, 1.5mm)}, ->]
            (adv) to node[above] {$u$} (oracle);
          \draw[offset = {(0mm, -1.5mm)}, <-]
            (adv) to node[below] {$\mathcal{D}_x(u)$} (oracle);
        }
        \visible<+->{
          \path[offset = {(0mm, -10mm)}]
            node[right = of adv] {\textbf{?}}
            edge[<-] (adv);
        }
      \end{tikzpicture}
    \end{block}
  \end{columns}
\end{frame}

\begin{frame}<1-9>[label = kem]{Signing tags}{Weakly deniably authenticated
    asymmetric encryption}
  \begin{columns}
    \column{0.5\textwidth}
    \begin{block}{}
      \centering
      \begin{tikzpicture}[node distance = 5mm]
        \visible<1->{
          \node[box = yellow!20, minimum width = 30mm] (m) {$m$};
        }
        \visible<3->{
          \node[op = red!20, below = of m] (enc) {$E$}
            edge[<-] (m);
          \node[box = red!20, minimum width = 30mm + 15pt, below = of enc]
            (c) {$c$}
            edge[<-] (enc);
        }
        \visible<5->{
          \node[box = green!20, right = -0.6pt of c] (sig) {$\sigma$};
          \node[op = green!20, above = 10mm] at (sig |- m) (s) {$S$}
            edge[->] (sig);
          \node[above = of s] {$a'$} edge[->] (s);
        }
        \visible<6->{
          \draw[->] (s |- enc) -- (enc);
        }
        \visible<4->{
          \node[box = green!20, left = 25mm of s, below] (t2) {$\tau$};
          \node[box = blue!20, above = -0.6pt of t2] (b2) {$B$};
          \draw[decorate, decoration = brace]
            (b2.north east) -- (t2.south east)
            coordinate[pos = 0.5, right = 2.5pt] (sm);
        }
        \visible<5->{
          \draw[->] (sm) -- (s);
        }
        \visible<2->{
          \node[box = green!20, left = of t2] (tag) {$\tau$};
          \node[box = red!20, left = -0.6pt of tag] (k) {$K$};
          \draw[decorate, decoration = brace]
            (k.north west) -- (tag.north east)
            coordinate[pos = 0.5, above = 2.5pt] (z);
          \node[op = blue!20, above = 8mm of z] (kem) {$\mathcal{E}$}
            edge[->] (z);
          \node[box = blue!20, left = -0.6pt of c] (u) {$u$};
          \draw[rounded, ->] (kem) -| +(-10mm, -8mm) |- (u);
          \node (b) at (kem -| b2) {$B$} edge[->] (kem);
        }
        \visible<4->{
          \draw[->] (tag) -- (t2);
        }
        \visible<3->{
          \draw[rounded, ->] (k) |- (enc);
        }
        \visible<4->{
          \draw[->] (b) -- (b2);
        }
      \end{tikzpicture}
    \end{block}
    \column{0.45\textwidth}
    \setcounter{beamerpauses}{7}
    \begin{block}<+->{}
      \begin{description}
      \item<.(0)->[Secrecy] From KEM and symmetric IND-CCA.
      \item<.(2)->[Authenticity] \alt<-.(2)>{Fails!}{From KEM, symmetric
          INT-CTXT and KEM non-directability.}
      \item<.(1)->[Deniability] Weak deniability from message\slash signature
        separation.
      \end{description}
    \end{block}
  \end{columns}
\end{frame}

\begin{frame}{Signing tags}{Fixing authentication}
  \begin{block}{What causes the problem?}
    \begin{itemize}[<+->]
    \item Signatures don't have to hide the message signed.
    \item So adversary can discover the tag $\tau$.
    \item Might construct KEM clue with known $K$ and copied $\tau$ --
      forgery!
    \end{itemize}
  \end{block}
  \begin{block}<+->{KEM non-directability}
    \begin{itemize}[<+->]
    \item Say KEM is $(t, n)$-\emph{non-directable} if, given $t$-bit strings
      $r_0$, $r_1$, \ldots, $r_{n-1}$, and a public key~$X$, it's hard to
      find a clue $u$ such that the last $t$ bits of $D_x(u)$ match any
      $r_i$.
    \item We prove non-directability for a large class of random-oracle KEMs.
    \item How hard is the Cramer--Shoup KEM to direct?
    \end{itemize}
  \end{block}
\end{frame}

\againframe<10>{kem}

\subsection{NAIADs}

\begin{frame}{NAIADs}{What's a NAIAD?}
  \alert{N}on-interactive \alert{A}symmetric \alert{I}ntegrity
  \alert{A}lgorithm with \alert{D}eniability.

  \begin{block}<+->{The basic idea}
    \begin{itemize}[<+->]
    \item Essentially the asymmetric analogue of a MAC.
    \item Given: private key, recipient's public key, and message, construct
      tag.
    \item Given: private key, sender's public key, message, and tag, verify
      that tag is correct.
    \item Simulator constructs convincing tags given \emph{recipient's}
      private key.
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}{NAIADs}{Definitions}
  \kern-2ex
  \begin{block}<+->{}
    \begin{itemize}[<+->]
    \item Key generation: $G() \to (x, X)$.
    \item Tagging: $T_x(Y, m) \to \tau$.
    \item Verification: $V_y(X, m, \tau) \to v \in \{0, 1\}$.
    \item Simulation: $R_y(X, m) \to \tau'$.
    \end{itemize}
  \end{block}
  \kern-1ex
  \begin{block}<only@+-+(4)>{Authenticity}
    \centering
    \begin{tikzpicture}
      \node[mugshot] (adv) {\mugshot{adv.png}};
      \visible<+->{
        \node[mugshot] (alice) at (-5, 1.5) {\mugshot{alice.png}};
        \node[mugshot] (bob) at (+5, 1.5) {\mugshot{bob.png}};
        \draw[offset = {(0mm, -4mm)}]
          node[left = of adv] {$A$, $B$} edge[->] (adv);
      }
      \visible<+->{
        \path[offset = {(0mm, -4mm)}] node[right = of adv, text width = 40mm]
          {New $m^*$, $\tau^*$ with \\ $V_b(A, m^*, \tau^*) = 1$}
          edge[<-] (adv);
      }
      \visible<+->{
        \draw[offset = {(0mm, +5.5mm)}, ->]
          (adv) to node[above, sloped]{$Z, m$} (alice);
        \draw[offset = {(0mm, +3.5mm)}, ->]
          (alice) to node[below, sloped]{$T_a(Z, m)$} (adv);
      }
      \visible<+->{
        \draw[offset = {(0mm, +5.5mm)}, ->]
          (adv) to node[above, sloped]{$Z, m, \tau$} (bob);
        \draw[offset = {(0mm, +3.5mm)}, ->]
          (bob) to node[below, sloped]{$V_b(Z, m, \tau)$} (adv);
      }
    \end{tikzpicture}
  \end{block}
  \begin{block}<only@+->{Deniability}
    \centering
    \begin{tikzpicture}
      \node[mugshot] (justin) {\mugshot{judge.png}};
      \visible<+->{
        \node[mugshot] (bob) at (+5, 1.5) {\mugshot{bob.png}};
        \draw[->, offset = {(0mm, +4mm)}, sloped] (bob) to
          node[above] {$m$} node[below] {$\tau = T_a(B, m)$}
          (justin);
      }
      \visible<+->{
        \node[mugshot] (robot-bob) at (-5, 1.5) {\mugshot{robot-bob.png}};
        \draw[<->, offset = {(0mm, 5.5mm)}, sloped] (robot-bob) to
          node[above] {$m'$}
          (justin);
        \draw[->, offset = {(0mm, 2.5mm)}, sloped] (robot-bob) to
          node[below] {$\tau' = R_b(A, m')$}
          (justin);
      }
      \visible<+->{
        \draw[offset = {(0mm, -4mm)}]
          node[left = of justin]
          {$a$, $b$} edge[->] (justin);
      }
      \visible<+->{
        \node[thought = justin.north] at ($(justin.north) + (1/3, 1/2)$)
          {\large\bfseries ?};
      }
    \end{tikzpicture}
  \end{block}
\end{frame}

\begin{frame}{NAIADs}{Strongly deniably authenticated asymmetric encryption}
  \kern-5ex
  \begin{columns}
    \column{0.45\textwidth}
    \begin{block}{}
      \centering
      \begin{tikzpicture}[node distance = 5mm]
        \visible<+->{
          \node[box = yellow!20, minimum width = 30mm] (m) {$m$};
        }
        \visible<+->{
          \node[box = green!20, right = -0.6pt of m] (tau) {$\tau$};
          \node[op = green!20, above = of tau] (t) {$T$} edge[->] (tau);
          \node[above = of t] {$a'$} edge[->] (t);
          \node[right = of t] {$B'$} edge[->] (t);
          \draw[->, rounded] (m) |- (t);
        }
        \visible<+->{
          \draw[decorate, decoration = brace]
            (tau.south east) -- (m.south west)
            coordinate[pos = 0.5, below = 2.5pt] (p);
          \node[op = red!20, below = of p] (enc) {$E$} edge[<-] (p);
          \node[left = of enc] {$B$} edge[->] (enc);
          \node[box = red!20, minimum width = 30mm + 15pt, below = of enc]
            (c) {$c$} edge[<-] (enc);
        }
      \end{tikzpicture}
    \end{block}
    \column{0.50\textwidth}
    \begin{block}<+->{}
      \begin{description}[<+->]
      \item[Secrecy] Direct from encryption IND-CCA.
      \item[Authenticity] From encryption IND-CCA and NAIAD authenticity.
      \item[Deniability] From NAIAD deniability.
      \end{description}
    \end{block}
  \end{columns}
  \begin{block}<+->{Other constructions}
    \begin{itemize}[<+->]
    \item Use $T_a(B, A')$ as a deniable authentication token
    \item Use NAIAD in place of signature in `signed tag' construction.
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}{NAIADs}{Instantiations}
  \begin{block}<+->{Existing techniques}
    \begin{itemize}[<+->]
    \item Ring signature, with sender and recipient as the signers.
    \item Some non-disavowable designated-verifier signatures, e.g., [Lipmaa,
      Wang, Bao~2005].
    \end{itemize}
  \end{block}
  \begin{block}<+->{New technique}
    Paper describes a new NAIAD, secure in the random oracle model assuming
    the difficulty of the computational Diffie--Hellman problem.
  \end{block}
\end{frame}

\begin{frame}{The end}
  \centering
  \hbox{}
  \vfill
  \Large Thanks for listening.
  \vskip 20mm
  \Huge \sffamily Questions?
  \vfill \vfill
\end{frame}

\end{document}

%%% Local variables:
%%% mode: LaTeX
%%% TeX-PDF-mode: t
%%% End:
