From: Mark Wooding Date: Mon, 30 Jan 2012 23:44:22 +0000 (+0000) Subject: initial X-Git-Url: https://git.distorted.org.uk/~mdw/doc/deny/commitdiff_plain/refs/heads/master initial --- 888f8938c4b60ff5279ca85aba4c61da8ffce224 diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..69b3f77 --- /dev/null +++ b/.gitignore @@ -0,0 +1,10 @@ +*.aux +*.log +*.dvi +*.nav +*.out +*.pdf +*.snm +*.toc +*.bbl +*.blg diff --git a/adv.png b/adv.png new file mode 100644 index 0000000..f258d85 Binary files /dev/null and b/adv.png differ diff --git a/alice-fallen.png b/alice-fallen.png new file mode 100644 index 0000000..b1d23ed Binary files /dev/null and b/alice-fallen.png differ diff --git a/alice.png b/alice.png new file mode 100644 index 0000000..9dfade3 Binary files /dev/null and b/alice.png differ diff --git a/bob-unthrilled.png b/bob-unthrilled.png new file mode 100644 index 0000000..d35c18a Binary files /dev/null and b/bob-unthrilled.png differ diff --git a/bob.png b/bob.png new file mode 100644 index 0000000..6627926 Binary files /dev/null and b/bob.png differ diff --git a/deny-lncs.tex b/deny-lncs.tex new file mode 100644 index 0000000..49b8dc4 --- /dev/null +++ b/deny-lncs.tex @@ -0,0 +1,3 @@ +%%% -*- mode: latex; TeX-PDF-mode: t; TeX-master: t -*- +\let\iflncs\iftrue +\input deny.tex diff --git a/deny-slides.tex b/deny-slides.tex new file mode 100644 index 0000000..5dca8d9 --- /dev/null +++ b/deny-slides.tex @@ -0,0 +1,872 @@ +%%% 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}{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}{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: diff --git a/deny.tex b/deny.tex new file mode 100644 index 0000000..cab9413 --- /dev/null +++ b/deny.tex @@ -0,0 +1,4453 @@ +%%% Deniably authenticated asymmetric encryption +%%% +%%% Copyright (c) 2010 Mark Wooding +%%% Licence: CC-BY + +%% things that need sorting out +%% +%% * doing something about the sender-simulator oracle +%% * sorting out the standard-model auth token +%% * tag auth tokens, and non-directable KEMs. +%% +%% interesting remarks +%% +%% * deniable auth token using ring signatures! + +\ifx\iflncs\notexist +\expandafter\let\csname iflncs\expandafter\endcsname\csname iffalse\endcsname +\fi + +\iflncs +\documentclass[runningheads]{llncs} +\else +\documentclass{strayman} +\fi + +\usepackage[T1]{fontenc} +\usepackage[utf8]{inputenc} +\iflncs\else +\usepackage[palatino, helvetica, courier, maths = cmr]{mdwfonts} +\usepackage[mdwmargin]{mdwthm} +\fi +\usepackage{mdwtab, mathenv, mdwmath, crypto, mdwref, mdwlist} +\usepackage{tikz} + +\usetikzlibrary{% + fit,positioning,calc,% + decorations.markings,% + decorations.pathreplacing} + +%%\makeatletter\def\th@construction{\th@base\relax} +%%\theoremstyle{construction} +%%\newtheorem{construction}[theorem]{Construction} +%%\defxref{con}{construction} +\iflncs\else +\numberwithin{theorem}{subsection} +\numberwithin{equation}{subsection} +\numberwithin{figure}{subsection} +\fi + +\title{Deniably authenticated asymmetric encryption} +\author{Mark Wooding} + +\def\Bin{\Sigma} +\def\random{\$} +\def\bitsto{\mathop{..}} +\let\epsilon\varepsilon +\let\emptystring\epsilon +\let\emptyset\varnothing +\let\mdwPr\Pr \def\Pr{\mdwPr\nolimits} +\let\len\ell +\def\proto#1{\Pi_{\text{\/\normalfont\scshape#1\/}}} +\def\Thing#1#2#3{% + \text{\normalfont\bfseries#1}^{\text{\normalfont\scshape#2}}_{#3}} +\def\Xid#1#2{\textsc{$#1$-#2}} + +\newenvironment{notation}{% + \dimen8=\textwidth% + \advance\dimen8-4em% + \begin{tabular}[L]{@{\qquad}>{$}p{0.4\dimen8}<{$}p{0.6\dimen8}}% +}{% + \end{tabular}% +} + +\renewcommand\topfraction{.8} + +\tikzset{ + 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}}}, + node distance = 5mm, + > = stealth +} + +\def\fixme{\marginpar{FIXME}} +\def\cn{\fixme\textsuperscript{[\textcolor{blue}{citation needed}]}} + +\bibliographystyle{mdwalpha} + +\begin{document} + +\maketitle + +\begin{abstract} + We consider the notion of \emph{deniably authenticated asymmetric + encryption}: briefly, Bob can encrypt a message and send the ciphertext + to Alice; Alice (and nobody else other than maybe Bob) can decrypt the + message; Alice is convinced that Bob actually sent the message; and nobody + can prove this to anyone else. + + We present formal definitions of security for this new notion, and offer + two efficient instantiations. One is a generic construction, using any + key-encapsulation mechanism, signature scheme, and symmetric authenticated + encryption scheme, but it meets a relatively weak notion of deniability; + the other has security based on the computational Diffie--Hellman problem: + and provides strong deniability, but the security is only proven in the + random oracle model. +\end{abstract} + +\thispagestyle{empty} +\newpage +\tableofcontents +\newpage + +%%%-------------------------------------------------------------------------- +\section{Introduction} +\label{sec:intro} + +\subsection{Authenticated asymmetric encryption} +\label{sec:intro.aae} + +Secure email protocols, such as PGP +\cite{Zimmermann:1995:PSC,rfc1991,rfc2440,rfc4880} and S/MIME +\cite{rfc2311,rfc2633,rfc3851} attempt to provide both \emph{secrecy} for the +messages they handle, and \emph{authenticity}. The former property, +informally, means that Bob can send a message to Alice and be confident that +nobody else can read it. The latter means that Alice can be confident that +the message was really sent by Bob. + +This is commonly achieved by a generic sign-then-encrypt construction: the +message plaintext is signed using a standalone digital-signature algorithm +with the sender's private key, and then the message and its signature +together are encrypted with the recipient's public key +\[ y = E_A([m, S_b(m)]) \] +This construction, among others, is analysed by An, Dodis, and Rabin +\cite{An:2002:SJS,cryptoeprint:2002:046} and shown to provide formally +defined notions of secrecy and authenticity. + +As noticed by Davis \cite{Davis:2001:DSE}, the sign-then-encrypt approach has +some surprising failure modes. For example, Alice can re-encrypt the signed +message using, say, Carol's public key, and sent it on: +\[ y' = E_C([m, S_b(m)]) \] +this can obviously cause confusion if the message doesn't encode the identity +of the intended recipient. But there are worse possibilities. For example, +if Alice and Bob are having an affair, each signed-and-encrypted +\emph{billet-doux} becomes potential blackmail material: Alice might threaten +to publish the +\[ m, S_b(m) \] +if her demands aren't met. If Alice is a journalist and Bob is a source, +leaking secrets to her, then the signed leaks are incriminating evidence. + +The encrypt-then-sign construction makes this sort of `attack' less trivial, +but still possible. The signature is applied to a ciphertext encrypted using +Alice's public key, so an \emph{unaided} third party should be unable to +verify that the ciphertext matches any particular claimed plaintext. But +there will usually be some additional information that Alice can publish to +show the correlation. For hybrid schemes, where an asymmetric encryption +scheme is used to transfer a symmetric key, publishing the symmetric key is +usually sufficient. In the case of asymmetric schemes based on trapdoor +permutations (e.g., RSA \cite{Rivest:1978:MOD}) she can publish the preimage +of the ciphertext. In the case of schemes based on Diffie--Hellman key +agreement (e.g., ElGamal's scheme \cite{ElGamal:1985:PKCb} or DLIES +\cite{cryptoeprint:1999:007,Abdalla:2001:DHIES,IEEE:2000:1363}) even +verifying the shared secret may be hard for third parties (this is the +decisional Diffie--Hellman problem), but Alice can additionally publish a +noninteractive zero-knowledge proof that the shared secret is +correct.\footnote{% + We'll work in a group $(G, +)$ with $p = \#G$ prime and generated by $P$. + Let $a \inr \gf{p}$ be Alice's private key, with $A = a P$. For ElGamal, + Bob encodes his message as $M \in G$, chooses $r \inr \gf{p}$, computes $R + = r P$ and $Z = r A$, and sends $(R, Z + M)$ as his ciphertext. Alice can + publish $Z$, but must prove that $Z = a R$. We assume a random oracle + $H\colon G^2 \to \gf{p}$. She chooses $u \inr \gf{p}$, computes $c = H(u + P, u R)$ and $v = u - c a$, and publishes $(Z, c, v)$. To verify, check + that $H(v P + c A, v R + c Z) = c$. Completeness is immediate; soundness + holds by rewinding and mutating the random oracle -- one obtains a new $c'$ + and $v'$ for the same $u$, and can solve for $a$; and the simulator fixes + up the random oracle after choosing $v$ at random. The structure of this + proof follows \cite{Maurer:2009:UZK}.} % + +Similarly, `signcryption' schemes \cite{Zheng:1997:DSH} usually provide a +`non-repudiation' property. \fixme + +With this in mind, it seems a shame that most work on asymmetric +authentication concentrates on \emph{non-repudiation} -- ensuring that Bob's +signature (or equivalent) can be demonstrated to third parties, even without +Bob's later cooperation -- or even despite his opposition. + +\subsection{Related work} +\label{sec:intro.related} + +Dolev, Dwork, and Naor's work \cite{Dolev:1991:NC} on nonmalleable +cryptography defines a simple asymmetric authentication protocol. If $m$ is +some message that Bob wants Alice to authenticate, he chooses a random string +$\rho$, and sends her $(m, \rho)$ encrypted using a nonmalleable encryption +scheme under Alice's public key. To authenticate the message~$m$, Alice +replies with $\rho$. The authors prove their protocol's security, on the +assumption that the encryption is nonmalleable, and comment without proof on +the `plausible deniability' that it offers. + +Dwork, Naor, and Sahai \cite{cryptoeprint:1999:023} address deniability in +the context of concurrent zero-knowledge interactive proofs. They improve +the \cite{Dolev:1991:NC} protocol, showing that the new version is deniable +under \emph{sequential} composition. They also \fixme +%%% read this and finish description + +Di~Raimondo and Gennaro \cite{Raimondo:2005:NAD} \fixme +%%% ought to actually read this + +There is an active literature on the topic of deniably authenticated key +exchange, where the participants are confident that they are communicating +securely with each other, but are unable to prove this to a third party. +Di~Raimondo, Gennaro, and Krawczyk \cite{cryptoeprint:2006:280} define +deniably authenticated key exchange and prove deniability properties of some +IPSEC subprotocols. + +The \emph{Off the Record} protocol for instant-messaging systems +\cite{Borisov:2004:OTR,Alexander:2007:IUA} provides strong deniability for +users, for example by publishing authentication keys at the ends of +conversations. The Wrestlers key-exchange protocol +\cite{cryptoeprint:2006:386} provides strong deniability, and has been +implemented as part of a virtual private network system +\cite{Wooding:2001:TrIPE}. + +All of the deniable protocols described above are fundamentally +\emph{interactive}, and therefore unsuitable for use in an encryption scheme. +On the other hand, we have an advantage over the designers of plain deniable +authentication protocols, since we can assume that both the sender \emph{and} +the recipient have public keys. This can be seen to be essential in a +non-interactive scheme as follows. If an authentication scheme doesn't +somehow identify a specific recipient (or set of recipients) then either +everyone can verify authenticity or nobody can. In the latter case, the +scheme is useless; in the former, it is undeniable. An interactive protocol +can identify the recipient implicitly through the interaction. A +non-interactive scheme doesn't have this luxury; the only means remaining is +to assume that the recipient knows something -- i.e., a private key. + +Other related concepts include \emph{chameleon signatures} and \emph{ring + signatures}. A chameleon signature \cite{cryptoeprint:1998:010} allows a +designated recipient to satisfy himself as to the origin of a message, and to +create forgeries -- so the recipient is unable to convince third parties that +a message is authentic; however, the sender is able to prove a forgery, and a +failure to provide such proof may be considered an admission of authenticity. +(We shall discuss chameleon signatures further in \ref{sec:deny.weak}.) A +ring signature \cite{Rivest:2001:HLS} lets sender `hide' among a set of users +-- without their participation -- and sign a message in such a way as to +convince a recipient that some member of the set signed it, but with no way +to determine which. (This differs from the group signatures of +\cite{Chaum:1991:GS} in two respects: firstly, the participants in a group +signature scheme are explicitly enrolled into it; and secondly, a group +signature scheme includes an authority who can reveal the individual +participant who signed a particular message.) + +\fixme Naccache \cite{Naccache:2010:ITC} asked +\begin{quote} + Construct a non-interactive authenticated PKE scheme: + \begin{itemize} + \item Alice encrypts a message for Bob and mixes with it a secret. + \item Bob can ascertain that the message cam from Alice. + \item Bob cannot convey this conviction to anybody. + \end{itemize} +\end{quote} + +\subsection{Our contribution} +\label{sec:intro.contribution} + +We provide formal definitions for deniably authenticated asymmetric +encryption. We give a `strong' definition, which allows a sender to deny +convincingly ever having communicated with a recipient, and a `weak' +definition, where it may be possible to prove the fact of communication, but +not the contents. (This latter definition turns out to be rather +complicated.) + +We also describe simple and efficient schemes which meet these definitions of +security. Our weakly deniable scheme is generic: it uses an asymmetric key +encapsulation mechanism, a digital signature scheme, and an authenticated +symmetric encryption scheme: security is proven in the standard model. We +show that Diffie--Hellman key distribution \cite{Diffie:1976:NDC} is a basis +for a strongly deniable authenticated encryption scheme. We describe such a +scheme and prove security, assuming the difficulty of the computational +Diffie--Hellman problem, in the random oracle model. + +%%%-------------------------------------------------------------------------- +\section{Preliminaries} +\label{sec:pre} + +\subsection{Binary strings and encodings} +\label{sec:bin} + +We write $\Bin = \{ 0, 1 \}$ as the set of binary digits; $\Bin^t$ is the set +of $t$-bit strings, and $\Bin^* = \bigcup_{0\le i} \Bin^i$ is the set of all +binary strings. We write $\emptystring$ for the empty string. If $m$ is a +binary string then $\len(m)$ is the length of $m$; so $m \in \Bin^{\len(m)}$, +and $\len(\emptystring) = 0$. If $0 \le i < \len(m)$ then $m[i]$ is the +$i$th bit of $m$. If $m$ and $n$ are two strings then $m \cat n$ is their +concatenation; we have $\len(m \cat n) = \len(m) + \len(n)$; $m \cat +\emptystring = \emptystring \cat m = m$; and $(m \cat n)[i] = m[i]$ if $i < +\len(m)$ and $n[i - \len(m)]$ otherwise. If $0 \le i \le j \le \len(m)$ then +$m[i \bitsto j]$ is the substring starting with bit~$i$ and ending before +bit~$j$ -- so $\len(m[i \bitsto j]) = j - i$, $m[i \bitsto j][k] = m[i + k]$, +and $m = m[0 \bitsto i] \cat m[i \bitsto j] \cat m[j \bitsto \len(m)]$. + +We shall assume the existence of a deterministic, unambiguous encoding of +integers, group elements, and other such objects, as bit strings. Rather +than build a complicated formalism, we shall simply write $[a, b, c, \ldots]$ +as the encoding of items $a$, $b$, $c$, \dots If $n$ is an integer with $0 +\le n < 2^k$ then $[n]_k$ is a $k$-bit encoding of $n$. + +We assume the existence of a distinguished object~$\bot$ (pronounced +`bottom'), and a set of \emph{atomic symbols}, written in +\cookie{sans-serif}, whose purpose is simply to be distinct from all other +objects. + +\subsection{Algorithms, oracles, and resource bounds} +\label{sec:alg} + +We present algorithms using a fairly standard imperative notation. We write +$x \gets \tau$ to mean that variable~$x$ is to be assigned the value of the +term~$\tau$. If $S$ is a set, then $x \getsr S$ means that $x$ is to be +assigned an element of $S$ chosen uniformly and independently at random. +Variables are globally scoped. Indentation is used to indicate the extent of +iterated and conditional fragments. + +We make frequent use of implicit `destructuring' (or `pattern matching') in +algorithm descriptions: a tuple (in parentheses, as is conventional) or +encoded sequence (in square brackets) containing variables may appear on the +left of an assignment, or as a formal argument to a procedure, indicating +that the corresponding right-hand-side or actual argument is to be decoded +and split up according to the structure of the pattern + +Oracles provided to algorithms are written as superscripts; the inputs +supplied in an oracle query are written as `$\cdot$'. + +We work throughout in the tradition of concrete security, as initiated in +\cite{Bellare:1994:SCB}. We consider adversaries operating under explicit +resource bounds of time and numbers of oracle queries, and provide explicit +bounds on their success probabilities and advantages. We find that this +approach both simplifies presentation -- since we no longer have to deal with +families of objects indexed by security parameters or other artificial +features of the asymptotic approach -- and provides more practically useful +results. (As an aside, we remark that, \cite{Goldreich:1997:FMCa} +notwithstanding, it's much easier to derive asymptotic results from concrete +ones than \emph{vice versa}.) + +We make use of the random oracle model, as formalized in +\cite{Bellare:1993:ROP}. Rather than give separate definitions for security +with random oracles, we shall quietly include a bound $q_H$ on an adversary's +random oracle queries when attacking a scheme which uses random oracles. + +The model of computation used to measure running times is not specified -- or +especially important to our results. We do note, however, that running times +\emph{include} the time taken by the `game' infrastructure, including any +time needed for oracles to compute their results. In order to take into +account algorithms which make use of precomputed tables, we also include in +the running time a term proportional to the size of the algorithm's +description according to the (unspecified) computational model. + +\subsection{Useful results} +\label{sec:handy} + +The following simple lemmata will be used in our security proofs. The first +is by Shoup; the second seems to be folklore; and the third is an abstraction +of various results. + +\begin{lemma}[Difference lemma \cite{Shoup:2002:OR}] + \label{lem:shoup} + + Let $S$, $T$, and $F$ be events such that + \[ \Pr[S \mid \bar{F}] = \Pr[T \mid \bar{F}] \] + Then + \[ \Pr[S] - \Pr[T] \le \Pr[F] \] +\end{lemma} +\begin{proof} + A simple calculation: + \begin{eqnarray*}[rl] + \Pr[S] - \Pr[T] + & = (\Pr[S \land F] + \Pr[S \land \bar{F}]) - + (\Pr[T \land F] + \Pr[T \land \bar{F}]) \\ + & = (\Pr[S \land F] - \Pr[T \land F]) + + \Pr[\bar{F}] (\Pr[S \mid \bar{F}] - \Pr[T \mid \bar{F}]) \\ + & \le \Pr[F] \eqnumber[\qed] + \end{eqnarray*} +\end{proof} + +\begin{lemma}[Advantage lemma] + \label{lem:advantage} + + Suppose that $b \inr \{0, 1\}$ is uniformly distributed. Let $a \in \{0, + 1\}$ be a random bit, not necessarily uniform or independent of $b$. + \[ \Pr[a = 1 \mid b = 1] - \Pr[a = 1 \mid b = 0] = 2 \Pr[a = b] - 1 \] +\end{lemma} +\begin{proof} + Another calculation: + \begin{eqnarray*}[rl] + \Pr[a = 1 \mid b = 1] - \Pr[a = 1 \mid b = 0] + & = \Pr[a = 1 \mid b = 1] + \Pr[a = 0 \mid b = 0] - 1 \\ + & = \frac{\Pr[a = b \land b = 1]}{\Pr[b = 1]} + + \frac{\Pr[a = b \land b = 0]}{\Pr[b = 0]} - 1 \\ + & = 2(\Pr[a = b \land b = 1] + \Pr[a = b \land b = 0]) - 1 \\ + & = 2\Pr[a = b] - 1 \eqnumber[\qed] + \end{eqnarray*} +\end{proof} + +\begin{lemma}[Randomization lemma] + \label{lem:random} + + Let $X$ and $Y$ be countable sets, and let $f\colon X \times Y \to \{0, + 1\}$ be a function. Suppose $y$ is a random variable taking values in $Y$ + such that, for all $x \in X$, + \[ \Pr[f(x, y) = 1] \le \epsilon \] + for some $\epsilon$. Let $(x_0, x_1, \ldots, x_{q-1})$ be random variables + taking values from $X$, and independent of $y$. Then + \[ \Pr\biggl[\bigvee_{0\le i S,E,R/SS,S,E or E,R/E,S -> S,E,R/S',E,S + +Let us investigate the indistinguishability properties of weakly deniable +encryption schemes. For simplicity, we consider (for the moment) only +perfect deniability, and therefore which other kinds of simulated ciphertexts +are identically distributed. We shall show later how to extend the analysis +to the more general situation. + +Fix a perfectly weakly deniable AAE scheme $\Pi = (G, E, D, R, S)$. Let +$\mathcal{C}$ be the ciphertext space of $\Pi$, and $\mathcal{N}$ be the hint +space -- so $E$ outputs a result in $\mathcal{C} \times \mathcal{N}$. + +We define random variables $x$, $X$, $y$ and $Y$, corresponding to two key +pairs as generated by $G$. Let $\mathcal{R}$ be the space of random +variables taking values in $\mathcal{N} \times (\Bin^*)^2 \times +\mathcal{C}^2$. For any message~$m \in \Bin^2$, we let $I_m \in \mathcal{R}$ +be distributed according to the experiment +\[ (c, \eta) \gets E_x(Y, m) : (\eta, m, m, c, c) \] + +We define an equivalence relation $\sim$ on $\mathcal{R}$, writing $(\eta, m, +n, c, d) \sim (\eta', m', n', c', d')$ if and only if $(m, n) = (m', n')$ +and, for all judges~$J$, +\[ \Pr[J(x, X, y, Y, \eta, c, m, d, m) = 1] = + \Pr[J(x, X, y, Y, \eta', c', m', d', m') = 1] +\] +Next we define some operations on $\mathcal{R}$: +\begin{eqnarray*}[rl] + \pi(\eta, m, n, c, d) &= (\eta, n, m, d, c) \\ + \delta(\eta, m, n, c, d) &= (\eta, m, m, c, c) \\ + \epsilon_{m'}(\eta, m, n, c, d) &= (\eta, m', n, E_x(Y, m'), d) \\ + \rho_{m'}(\eta, m, n, c, d) &= (\eta, m', n, R_y(X, c, m'), d) \\ + \sigma_{m'}(\eta, m, n, c, d) &= (\eta, m', n, S_x(Y, \eta, c, m'), d) +\end{eqnarray*} +Let us denote by $M$ the monoid generated by these operations under +composition $\alpha \beta = \alpha \circ \beta$, and let $e \in M$ be the +identity operation on $\mathcal{R}$. A simple reduction shows that, if +$\alpha \in M$ and $C \sim D$ then $\alpha C \sim \alpha D$. Using this +notation, the requirement that $\Pi$ is perfectly deniable is that, for all +messages $m$, $m'$, +\[ \pi \sigma_{m'} I_m \sim \pi \rho_{m'} I_m \sim \sigma_m I_{m'} \] +Since $\pi^2 = e$, then, we have +\[ \rho_{m'} I_m \sim \sigma_{m'} I_m \sim \pi \rho_m I_{m'} \] + +\newpage +\subsubsection{[Musings]} +starting points: +\[ \rho \sim \sigma \sim \pi \rho \qquad \pi \sigma \sim \pi \rho \sim +\sigma \] +hmm. is there a chance we can get +\[ \alpha \sim \beta \land C \sim D \implies \alpha C \sim \beta D \] +doesn't look very likely + +\[ \sigma \sim \pi \rho \] + +Let $P_J(C) = \Pr[J(x, X, y, Y, \eta, c, m, d, n) = 1]$. + +From properties of $\sim$: +\[ P_J(\alpha_1 C) - P_J(\alpha_0 C) = P_J(\alpha_1 D) - P_J(\alpha_0 D) \] +so +\[ P_J(\alpha_0 D) - P_J(\alpha_0 C) = P_J(\alpha_1 D) - P_J(\alpha_1 C) \] + +generic construction of non-leaky wdaae? + +\subsubsection{Strong deniability implies weak deniability} +\label{sec:deny.strong-weak} +By now, it's probably not at all clear that strong deniability actually +implies weak deniability; but this is nonetheless true. The important +observation is that, since the recipient's simulator works without reference +to an existing ciphertext, the standard encryption algorithm works well as a +sender's simulator. This is expressed in the following theorem. + +\begin{theorem}[$\textrm{SDENY} \implies \textrm{WDENY}$] + \label{th:strong-weak} + + Let $\Pi = (G, E, D, R)$ be a strongly deniable AAE scheme. Define + \[ E'_x(Y, m) = (E_x(Y, m), \bot) \textrm, \quad + R'_x(Y, c, m) = R_x(Y, m) + \quad \textrm{and} \quad + S'_x(Y, c, \eta, m) = E'_x(Y, m) + \] + Then $\Pi' = (G, E', D, R', S')$ is a non-leaky weakly deniable AAE scheme + such that + \begin{eqnarray*}[rl] + \InSec{ind-occa}(\Pi'; t, q_E, q_D, q_R) + & \le \InSec{ind-occa}(\Pi; t, q_E + q_R, q_D) + + 2 q_R \InSec{sdeny}(\Pi; t + t_E) \\ + \InSec{uf-ocma}(\Pi'; t, q_E, q_D, q_R) + & \le \InSec{uf-ocma}(\Pi; t, q_E + q_R, q_D) + + q_R \InSec{sdeny}(\Pi; t + t_E) \\ + \InSec{wdeny}(\Pi'; t) + & \le \InSec{sdeny}(\Pi; t + t_E) + \end{eqnarray*} + where $t_E$ is the time required for a single encryption. +\end{theorem} +\begin{proof} + For the IND-OCCA inequality, we use a hybrid argument. Let $A$ be an + adversary; we define $\G0$ be the game in which $b \inr \{0,1\}$ is chosen + at randomly, followed by $\Game{ind-occa-$b$}{\Pi'}(A)$ of + \xref{def:wdaae-security}. + + Now we define $\G{i}$, for $0 \le i \le q_R$. (This definition will + coincide with the definition we already gave for $\G0$.) In each case, the + first $i$ recipient-simulator queries are answered by invoking the + encryption oracle instead; the remaining $q_R - i$ queries use the + recipient simulator as before. In $\G{q_R}$, the recipient simulator isn't + used at all, so this game is exactly $\Game{ind-occa-$b$}{\Pi}(A)$ of + \xref{def:sdaae-security}. Let $S_i$ be the event that, in $\G{i}$, the + output $b'$ of $A$ is equal to $b$. We claim: + \begin{eqnarray}[rl] + \Adv{ind-occa}{\Pi'}(A) & = 2 \Pr[S_0] - 1 \\ + \Adv{ind-occa}{\Pi}(A) & = 2 \Pr[S_{q_R}] - 1 \\ + \Pr[S_i] - \Pr[S_{i+1}] & \le \InSec{sdeny}(\Pi; t) + \qquad \textrm{for $0 \le i < q_R$} + \end{eqnarray} + The first two equations are clear. The last inequality requires a + reduction. We construct a judge~$J$ which + simulates the above game (recall that the judge is given all of the + necessary private keys!), except that it uses its input ciphertext to + respond to the $i$th recipient-simulator query. If $A$ wins the simulated + game by guessing correctly, then $J$ outputs $1$, declaring its ciphertext + to be simulated; otherwise $J$ outputs $0$. Then, conditioning on any + particular message~$m$ being the value of the random variable corresponding + to the $i$th recipient-simulator query, we have + \begin{eqnarray*}[rl] + \Pr[S_i] - \Pr[S_{i+1}] + & = \sum_{m \in \Bin^*} + \Pr[M = m] (\Pr[S_i \mid M = m] - \Pr[S_{i+1} \mid M = m]) \\ + & \begin{subsplit} \displaystyle {} + = \sum_{m \in \Bin^*} + \Pr[M = m] (\Pr[\Game{sdeny-$1$}{\Pi}(J, m, m) = 1] - {} \\[-3\jot] + \Pr[\Game{sdeny-$0$}{\Pi}(J, m, m) = 1]) + \end{subsplit} \\ + & \le \sum_{m \in \Bin^*} + \Pr[M = m] \InSec{sdeny}(\Pi; t + t') \\ + & = \InSec{sdeny}(\Pi; t + t') \sum_{m \in \Bin^*} \Pr[M = m] \\ + & = \InSec{sdeny}(\Pi; t + t') + \end{eqnarray*} + which proves the claim. + + The proof of the UF-OCMA inequality is very similar; we omit the details. + + Finally, we prove the deniability inequality. Let $J$ be a judge in the + weak deniability game. Note that our `sender simulator' is precisely the + official encryption algorithm, so its output is obviously `genuine'. The + notation is uncomfortably heavyweight; let us write $\G{b} = + \Game{wdeny-$b$}{\Pi'}(J)$. In $\G0$ both ciphertexts are `genuine' -- + they were generated by the proper encryption algorithm, using the proper + private key. In $\G1$, on the other hand, the left-hand ciphertext is + genuine but the right-hand ciphertext is simulated by~$R$. However, $R$ is + meant to be a good simulator of genuine ciphertexts. Indeed, if $J$ can + tell a pair of good, independently generated ciphertexts from a good + ciphertext and a (still independent) $R$-simulated one, then we can use it + to distinguish $R$'s simulations.\footnote{% + This independence, which follows from the fact that the strong + deniability simulator is required to work \emph{ab initio} without + reference to an existing ciphertext, is essential to the proof. Without + it, we'd `prove' that one needs only a single simulator to achieve weak + deniability -- but the previous discussion of chameleon signatures shows + that this is false.} % + + Choose some message~$m^*$. We construct an explicit~$J'$ as follows. + \begin{program} + $J'(x, X, y, Y, c, m)$: \+ \\ + $c^* \gets E_y(X, m^*)$; \\ + $b \gets J'(x, X, y, Y, c^*, m^*, c, m)$; \\ + \RETURN $b$; + \end{program} + This $J'$ is given either a genuine or an $S$-simulated ciphertext and + message, allegedly for message~$m$. It generates a genuine ciphertext + independently for~$m'$. It now has either two independent genuine + ciphertexts or a genuine ciphertext and a simulation, and therefore + distinguishes the two cases exactly as well as $J$. We conclude that + \[ \Adv{wdeny}{\Pi'}(J') \le \InSec{sdeny}(\Pi; t + t') \] + as required. +\end{proof} + +Unsurprisingly, weak deniability doesn't imply strong deniability (unless +one-way functions don't exist). This will follow immediately from +\xref{th:gwd-not-sdeny}. + +\subsubsection{Insider authenticity} +\label{sec:deny.insider} +There is a kind of attack considered in the study of key-exchange protocols +(see, for example, \cite{Blake-Wilson:1997:KAP}) called \emph{key-compromise + impersonation}. The adversary is assumed to know the long-term secret +information of one of the participants -- Alice, say. Clearly, he can now +impersonate Alice to Bob. If the protocol is vulnerable to key-compromise +impersonation attacks, however, he can also impersonate Bob -- or anybody +else of his choosing -- to Alice.\footnote{% + It is apparently considered unsatisfactory for a key-exchange protocol to + admit key-compromise impersonation, though it's unclear to us why we might + expect Alice to retain any useful security properties after having been + corrupted.} % +The analogue of key-compromise-impersonation resistance in the context of +noninteractive asymmetric encryption is \emph{insider authenticity}. + +Deniably authenticated asymmetric encryption schemes do not provide insider +authenticity: the two are fundamentally incompatible. Indeed, the existence +of the recipient simulator~$S$ in definitions~\xref{def:sdaae-deny} +and~\ref{def:wdaae-deny} constitutes an insider-authenticity attack. + +Insider authenticity can be defined fairly easily by modifying the UF-OCMA +games of definitions~\ref{def:sdaae-security} or~\ref{def:wdaae-security} to +give the adversary the recipient's private key~$y$; we shall omit the tedious +formalities, but we shall end up with a security measure +$\InSec{uf-icma}(\Pi; t, q_E)$ (for `unforgeability under insider +chosen-message attack'). The attack is simple: retrieve a single message~$m$ +from the sender (if the scheme is only weakly deniable -- even this is +unnecessary if we have strong deniability), pass it to the simulator~$S$, +along with the private key~$y$ and a different message~$m' \ne m$. Let $y'$ +be the simulator's output. We know that the decryption algorithm will always +succeed on real ciphertexts; so if $p$ is the probability that decryption +fails, then +\[ \InSec{uf-icma}(\Pi; t_E + t_S, 1) \ge + p \ge 1 - \InSec{wdeny}(\Pi, S; t_D) \] +where $t_E$, $t_S$ and $t_D$ are the respective times required to encrypt a +message, run the recipient simulator, and decrypt a message. + +\subsection{Generic non-leaky weakly deniably authenticated asymmetric + encryption} +\label{sec:nleak} + +Let $\proto{wdaae} = (\mathcal{G}, \mathcal{E}, \mathcal{D}, \mathcal{R}, +\mathcal{S})$ be a weakly deniably authenticated asymmetric encryption +scheme. We shall assume that the hints output by the encryption algorithm +are bit strings of some constant length $n$. (All of the weakly deniable +schemes in this paper have this property.) + +Let $\proto{se} = (\kappa, E, D)$ be a symmetric encryption scheme, and let +$\proto{h} = (\nu, \lambda, H)$ be a universal one-way hash function. We +construct a \emph{non-leaky} weakly deniably authenticated asymmetric +encryption scheme +\begin{spliteqn*} + \Xid{\Pi}{wdaae-nleak}(\proto{wdaae}, \proto{se}, \proto{h}) = + (\Xid{G}{wdaae-nleak}, \Xid{E}{wdaae-nleak}, \\ + \Xid{D}{wdaae-nleak}, \Xid{R}{wdaae-nleak}, \Xid{S}{wdaae-nleak}) +\end{spliteqn*} +where the component algorithms are as follows. +\begin{program} + $\Xid{G}{wdaae-nleak}()$: \+ \\ + $(x, X) \gets \mathcal{G}()$; \\ + $K \getsr \Bin^\kappa$; \\ + \RETURN $\bigl( (x, K), X \bigr)$; \- +\next + $\Xid{E}{wdaae-nleak}_{x, K}(Y, m)$: \+ \\ + $N \getsr \Bin^\nu$; \\ + $(c, \eta) \gets \mathcal{E}_x(Y, \emptystring)$; \\ + $z \gets E_K(\eta)$; + $h \gets H_N(z)$; \\ + $c' \gets \mathcal{S}_x(Y, \eta, c, N \cat h \cat m)$; \\ + \RETURN $\bigl( (c', z), \bot \bigr)$; \- +\next + $\Xid{D}{wdaae-nleak}_{x, K}\bigl( Y, (c, z) \bigr)$: \+ \\ + $m \gets \mathcal{D}_x(Y, c)$; \\ + \IF $m = \bot$ \THEN \RETURN $\bot$; \\ + $N \gets m[0 \bitsto \nu]$; + $h \gets m[\nu \bitsto \nu + \lambda]$; \\ + \IF $H_N(z) \ne h$ \THEN \RETURN $\bot$; \\ + \RETURN $m[\nu + \lambda \bitsto \len(m)]$; \- +\newline + $\Xid{R}{wdaae-nleak}_{x, K}\bigl( Y, (c, z), m \bigr)$: \+ \\ + $N \getsr \Bin^\nu$; + $h \gets H_N(z)$; \\ + \RETURN $\mathcal{R}_x(Y, c, N \cat h \cat m)$; \- +\next + $\Xid{S}{wdaae-nleak}_{x, K}\bigl( Y, \eta', (c, z), m \bigr)$: \+ \\ + $\eta \gets D_K(z)$; \\ + $N \getsr \Bin^\nu$; + $h \gets H_N(z)$; \\ + \RETURN $\mathcal{S}_x(Y, \eta, c, N \cat h \cat m)$; \- +\end{program} + +It is clear that the constructed scheme is non-leaky. The following theorems +relate secrecy, authenticity and deniability to that of the original scheme. + +\begin{theorem}[Non-leaky secrecy] + \label{th:wdaae-nleak.sec} + + \fixme + Let $\proto{wdaae}$ be a weakly deniably authenticated asymmetric + encryption scheme with $n$-bit hints; let $\proto{se}$ be a symmetric + encryption scheme and let $\proto{h}$ be a universal one-way hash. Then + \[ \InSec{ind-occa}(\Xid{\Pi}{wdaae-nleak}(\proto{wdaae}, \proto{se}, + \proto{h}); t, q_E, q_D, q_R) \ldots + \] +\end{theorem} +\begin{proof} + Let $A$ be any adversary attacking $\Pi = + \Xid{\Pi}{wdaae-nleak}(\proto{wdaae}, \proto{se}, \proto{h})$ within the + stated resource bounds. We use a sequence of games. Game~$\G0$ is the + standard IND-OCCA attack game, with the bit $b$ chosen uniformly at + random. In each game $\G{i}$, let $S_i$ be the event that $A$'s output is + equal to $b$. It then suffices to bound $\Pr[S_0]$. + + Game~$\G1$ is like $\G0$, except that we change the way the challenge + message $m_b$ is encrypted. Specifically, we set $z = E_K(0^n)$. A simple + reduction, which we omit, shows that + \begin{equation} \label{eq:wdaae-nleak.sec.s0} + \Pr[S_0] - \Pr[S_1] \le \InSec{ind-cca}(\proto{se}; t, q_E, 0) + \end{equation} + + Game~$\G2$ is like $\G1$, except that we again change the way the challenge + message $m_b$ is encrypted. The new algorithm is as follows. + \begin{program} + $N \getsr \Bin^\nu$; \\ + $z \gets E_K(0^n)$; + $h \gets H_N(z)$; \\ + $(c, \eta) \gets \mathcal{E}_x(Y, N \cat h \cat m_b)$; \\ + \RETURN $(c, z)$; + \end{program} + We claim that + \begin{equation} \label{eq:wdaae-nleak.sec.s1} + \Pr[S_1] - \Pr[S_2] \le \InSec{wdeny}(\proto{wdaae}; t) + \end{equation} + To prove the claim, we describe a reduction from the weak deniability of + $\proto{wdaae}$, conditioning on the value of $m_b$, and using + \xref{lem:random}. + \fixme +\end{proof} + +%%%-------------------------------------------------------------------------- +\section{Authentication tokens} +\label{sec:tokens} + +An obvious way for Bob to authenticate an encrypted message sent to Alice is +for him to include in it a secret known only to himself and her, which is +independent of his actual message. We call such secrets \emph{authentication + tokens}. + +Authentication tokens may, on their own, either be deniable or not. A +deniable token is one that can be computed by either the sender or the +recipient; nondeniable tokens can be computed only by the sender, but the +recipient can still verify the token's validity. The corresponding +encryption scheme is weakly deniable regardless of whether the tokens are +deniable: since the token is independent of the message, it can be +transferred into another encrypted message without detection. However, if +the recipient can't compute a token independently, we achieve only weak +deniability: the token's existence proves that the sender created it. If the +tokens are deniable then the overall encryption scheme achieves strong +deniability. + +We first define formally what we demand of authentication tokens. Secondly, +we describe and prove the security of a simple deniably authenticated +asymmetric encryption scheme using an authentication token. Next, we +describe an obvious instantiation of nondeniable authentication tokens in +terms of a digital signature scheme. Finally, we sketch a deniable +authentication token based on the computational Diffie--Hellman problem. + +\subsection{Definitions for authentication tokens} +\label{sec:tokens.definition} + +Before we start on the formal definitions, there's a couple of details we +need to address. The intuition we gave above will lead us to a +three-algorithm definition: key-generation, token creation, and verification. +This will give us a perfectly serviceable authentication token which will +entirely fail to compose usefully to give us higher-level protocols. The +problem is that, as we've defined it, an authentication token depends only on +the sender's private key and the recipient's public key -- for the +authentication token scheme itself only. When we compose it with other +cryptographic schemes, our overall protocol is going to end up with a bunch +of keys and unless we bind them together somehow, an adversary in a +multiparty game will be able to make a public key consisting of (say) a +legitimate recipient's authentication-token public key, and a freshly +generated encryption scheme public key. + +We fix this problem by introducing a fourth `binding' algorithm into the +definition: given a collection of public keys for a higher-level protocol, +compute some binding value to represent them. The binding value and other +keys will be additional inputs into the authentication-token construction +algorithm. We could instead provide the other keys as inputs to the +key-generation algorithm, effectively making the binding value part of the +authentication token's public key; the downside with this approach is that +two schemes which both use this trick won't compose properly with each other. +Splitting binding from key generation solves the dependency problem. + +There are two other details. Firstly, because we'll be encrypting the +tokens, we'll need to be able to encode tokens as constant-length bit +strings. To simplify the exposition, we'll treat this encoding as the +primary form of the token. And, secondly, we'll introduce a notion of +deniability for tokens which will require a simulation algorithm. Rather +than introduce a syntactic difference between deniable and nondeniable +tokens, we shall require all tokens to have a simulation algorithm, though +nondeniable algorithms can use a trivial `simulator'. + +\begin{definition}[Authentication token syntax] + \label{def:at.syntax} + + An authentication token scheme is a sextuple $\proto{tok} = (\kappa, G, B, + T, V, R)$, where $\kappa$ is a positive integer, and $G$, $B$, $T$, $V$, + and $R$ are (maybe randomized) algorithms as follows. + \begin{itemize} + \item The \emph{key-generation algorithm} $G$ accepts no parameters and + outputs a pair~$(x, X) \gets G()$. We call $x$ the \emph{private key} + and $X$ the \emph{public key}. + \item The \emph{binding algorithm} $B$ accepts a private key~$x$, and a + string $s \in \Bin^*$, and outputs a \emph{binding value} $\beta \gets + B_x(s)$. + \item The \emph{token construction algorithm} $T$ accepts a private + key~$x$, a public key~$Y$, a string~$s \in \Bin^*$, and a binding + value~$\beta$, and outputs a token $\tau \gets C_x(Y, s, \beta)$, which + is either a $\kappa$-bit string $\tau \in \Bin^\kappa$, or the + distinguished value~$\bot$. + \item The \emph{token verification algorithm} $V$ accepts a private + key~$x$, a public key~$Y$, a binding value~$\beta$, a string~$s \in + \Bin^*$, and a token~$\tau \in \Bin^\kappa$; it outputs a bit $b \gets + V_x(Y, s, \beta, \tau)$. The verification algorithm must be such that, + if $(x, X)$ and $(y, Y)$ are any two pairs of keys generated by $G$, $s + \in \Bin^*$ is any string, $\beta$ is any binding value output by + $B_y(s)$, and $\tau$ is any token constructed by $T_x(Y, s, \beta)$, then + $V_y(X, s, \beta, \tau)$ outputs $1$. + \item The \emph{recipient simulator} $R$ accepts a private key~$x$, a + public key~$Y$, and a binding value~$\beta$, and outputs a token~$\tau + \in \Bin^\kappa$. \qed + \end{itemize} +\end{definition} + +The security definition is fairly straightforward. We play a game in which +the adversary's goal is to determine the authentication token shared between +two users: a `sender' and a `recipient'. We grant the adversary access to +an oracle which constructs tokens using to the sender's private key, and +another which verifies tokens using the recipient's key. So that the game is +nontrivial, we forbid the adversary from making a token-construction query +using the recipient's public key and binding value. + +Which raises the question of where the binding value comes from. For maximum +generality, we allow the adversary to select the input string, possibly +dependent on the recipient's public key, in a preliminary stage of the game. + +\begin{definition}[Authentication token security] + \label{def:at.security} + + Let $\Pi = (\kappa, G, B, T, V, R)$ be an authentication token scheme. We + measure an adversary $A$'s ability to attack $\Pi$ using the following + game. + \begin{program} + $\Game{token}{\Pi}(A)$: \+ \\ + $(x, X) \gets G()$; + $(y, Y) \gets G()$; \\ + $(s, t, \sigma) \gets A(\cookie{bind}, X, Y)$; \\ + $\alpha \gets B_x(s)$; + $\beta \gets B_y(t)$; \\ + $w \gets 0$; \\ + $A^{T_x(\cdot, \cdot, \cdot), \id{vrf}(\cdot, \cdot)} + (\cookie{guess}, \sigma, \alpha, \beta)$; \\ + \RETURN $w$; \- + \next + $\id{vrf}(Q, \tau)$: \+ \\ + $b \gets V_y(Q, t, \beta, \tau)$; \\ + \IF $Q = X \land b = 1$ \THEN $w \gets 1$; \\ + \RETURN $b$; \- + \end{program} + The adversary is forbidden from querying its token-construction oracle at + $(Y, t, \beta)$. + + The adversary's \emph{advantage} attacking $\Pi$ is measured by + \[ \Adv{token}{\Pi}(A) = \Pr[\Game{token}{\Pi}(A) = 1] \] + Finally, the \emph{insecurity function} of~$\Pi$ is defined by + \[ \InSec{token}(\Pi; t, q_T, q_V) = \max_A \Adv{token}{\Pi}(A) \] + where the maximum is taken over all adversaries $A$ completing the game in + time~$t$ and making at most $q_T$ token-construction and $q_V$ verification + queries. +\end{definition} + +Our notion of deniability for authentication tokens makes use of an +\emph{auxiliary input}~$a \in \Bin^*$ to the judge. In higher-level +protocols, this auxiliary input will be additional private keys corresponding +to the public keys input to the binding algorithm. From a technical point of +view, this complication is necessary in order to prove reductions to token +deniability. This isn't especially satisfying intuitively, though, so it's +worth considering what goes wrong if we don't allow auxiliary inputs. \fixme + +\begin{definition}[Authentication token deniability] + \label{def:at.deny} + + Let $\Pi = (\kappa, G, B, T, V, R)$ be an authentication token scheme. The + judge~$J$'s ability to distinguish simulated tokens is defined using the + following game. + \begin{program} + $\Game{deny}{\Pi}(J, s, a, b)$: \+ \\ + $(x, X) \gets G()$; + $(y, Y) \gets G()$; \\ + $\beta \gets B_y(s)$; \\ + $\tau_1 \gets T_x(Y, s, \beta)$; \\ + $\tau_0 \gets R_y(X, \beta)$; \\ + $b' \gets J(x, y, X, Y, s, a, \beta, \tau_b)$; \\ + \RETURN $b'$; \- + \end{program} + The judge's \emph{advantage} in distinguishing simulated tokens is measured + by + \[ \Adv{deny}{\Pi}(J) = \max_{s, a \in \Bin^*} \bigl( + \Pr[\Game{deny}{\Pi}(J, s, a, 1) = 1] - + \Pr[\Game{deny}{\Pi}(J, s, a, 0) = 1] \bigr) + \] + and the \emph{insecurity function} for the deniability of $\Pi$ is defined + as + \[ \InSec{deny}(\Pi; t) = \max_J \Adv{deny}{\Pi}(J) \] + where the maximum is take over all judges~$J$ completing in time~$t$. We + say that $\Pi$ is \emph{statistically deniable} if $\InSec{deny}(\Pi; t)$ + is constant; if it is identically zero then say that $\Pi$ is + \emph{perfectly deniable}. +\end{definition} + +\subsection{Deniably authenticated asymmetric encryption from authentication + tokens} +\label{sec:tokens.construct} + +In this section, we construct and analyse two deniably authenticated +asymmetric encryption schemes using +\begin{itemize} +\item a universal one-way hash function $\proto{h} = (\nu, \lambda, H)$; +\item an asymmetric encryption scheme $\proto{ae} = (G, E, D)$; and +\item an authentication token scheme $\proto{tok} = (\kappa, G, B, T, V, R)$. +\end{itemize} +The component algorithms for the schemes are shown in +\xref{fig:tokens.construct}. The first is a weakly deniable scheme +\begin{eqnarray*}[Ll] + \Xid{\Pi}{wdaae-tok}(\proto{ae}, \proto{tok}) = \\ + & (\Xid{G}{daae-tok}, \Xid{E}{daae-tok}, \Xid{D}{daae-tok}, + \Xid{R}{daae-tok}, \Xid{S}{daae-tok}) +\end{eqnarray*} +and the second is a strongly deniable scheme +\[ \Xid{\Pi}{sdaae-tok}(\proto{ae}, \proto{tok}) = + (\Xid{G}{daae-tok}, \Xid{\hat E}{daae-tok}, \Xid{D}{daae-tok}, + \Xid{\hat R}{daae-tok}) +\] + +\begin{figure} + \begin{program} + \begin{tikzpicture} + \node[box = yellow!20, minimum width = 30mm] (m) {$m$}; + \node[box = cyan!20, left = -0.6pt of m] (h) {$h$}; + \node[box = cyan!20, left = -0.6pt of h] (n) {$N$}; + \node[box = green!20, left = -0.6pt of n] (tau) {$\tau$}; + \node[op = green!20, above = of tau] (token) {$T$} edge[->] (tau); + \node[op = cyan!20, above = of h] (hash) {$H$} edge[->] (h); + \node[right = of hash] {$X$, $X'$} edge[->] (hash); + \node[above = of hash] (nn) {$N$} edge[->] (hash); + \draw[rounded, ->] ($(nn)!1/3!(hash)$) -| (n); + \node[left = of token] {$x'$} edge[->] (token); + \node[above = of token] {$Y'$, $Y$, $\beta$} edge[->] (token); + \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$} edge[->] (e); + \node[box = red!20, minimum width = 30mm + 46.8pt, below = of e] + {$c$} edge[<-] (e); + \end{tikzpicture} + \\[\bigskipamount] + $\Xid{G}{daae-tok}()$: \+ \\ + $(x, X) \gets G()$; + $(x', X') \gets G'()$; \\ + $\alpha \gets B'_x([X])$; \\ + \RETURN $\bigl( (x, x', X, X', \alpha), (X, X', \alpha) \bigr)$; \- + \next + $\Xid{E}{daae-tok}_{(x, x', X, X', \alpha)} + \bigl( (Y, Y', \beta), m \bigr)$: \+ \\ + $\tau \gets T_{x'}(Y', [Y], \beta)$; + \IF $\tau = \bot$ \THEN \RETURN $\bot$; \\ + $N \getsr \Bin^\nu$; $h \gets H_N([X, X'])$; \\ + $c \gets E_Y(\tau \cat N \cat h \cat m)$; \\ + \RETURN $(c, \tau)$; \- + \\[\medskipamount] + $\id{decrypt}(x, x', Y, Y', X, \alpha, c)$: \+ \\ + $m' \gets D_x(c)$; \\ + \IF $m' = \bot \lor \len(m') < \kappa + \nu + \lambda$ + \THEN \RETURN $(\bot, \bot)$; \\ + $\tau \gets m'[0 \bitsto \kappa]$; + $h \gets m'[\kappa + \nu \bitsto \kappa + \nu + \lambda]$; \\ + $N \gets m'[\kappa \bitsto \kappa + \nu]$; + $m \gets m'\bigl[ \kappa + \nu + \lambda \bitsto \len(m') \bigr]$; \\ + \IF $V_{x'}(Y', [X], \alpha, \tau) = 0 \lor + H_N([Y, Y']) \ne h$ \\ + \THEN \RETURN $(\bot, \bot)$ + \ELSE \RETURN $(\tau, m)$; + \- + \\[\medskipamount] + $\Xid{D}{daae-tok}_{(x, x', X, X', \alpha)} + \bigl( (Y, Y', \beta), c \bigr)$: \+ \\ + $(m, \tau) \gets \id{decrypt}(x, x', Y, Y', X, \alpha, c)$; \\ + \RETURN $m$; + \newline + $\Xid{R}{daae-tok}_{(x, x', X, X', \alpha)} + \bigl( (Y, Y', \beta), c, m \bigr)$: \+ \\ + $(\tau, m') \gets \id{decrypt}(x, x', Y, Y', X, \alpha, c)$; \\ + \IF $\tau = \bot$ \THEN \RETURN $\bot$; \\ + $N \getsr \Bin^\nu$; $h \gets H_N([Y, Y'])$; \\ + $c \gets E_X(\tau \cat N \cat h \cat m)$; \\ + \RETURN $c$; \- + \\[\medskipamount] + $\Xid{S}{daae-tok}_{(x, x', X, X', \alpha)} + \bigl( (Y, Y', \beta), \tau, c, m \bigr)$: \+ \\ + $N \getsr \Bin^\nu$; $h \gets H_N([X, X'])$; \\ + $c \gets E_Y(\tau \cat [X, X'] \cat m)$; \\ + \RETURN $c$; \- + \next + $\Xid{\hat E}{daae-tok}_{(x, x', X, X', \alpha)} + \bigl( (Y, Y', \beta), m \bigr)$: \+ \\ + $(c, \tau) \gets {}$\\ + \qquad $\Xid{E}{daae-tok}_{(x, x', X, X', \alpha)} + \bigl( (Y, Y', \beta), m \bigr)$; \\ + \RETURN $c$; \- + \\[\medskipamount] + $\Xid{\hat R}{daae-tok}_{(x, x', X, X', \alpha)} + \bigl( (Y, Y', \beta), m \bigr)$: \+ \\ + $\tau \gets R_{x'}(Y', \alpha)$; \\ + $N \getsr \Bin^\nu$; $h \gets H_N([X, X'])$; \\ + $c \gets E_X(\tau \cat N \cat h \cat m)$; \\ + \RETURN $c$; \- + \end{program} + \caption{Deniably authenticated asymmetric encryption from authentication + tokens} + \label{fig:tokens.construct} +\end{figure} + +\begin{theorem}[Secrecy of the authentication-token DAAE] + \label{th:daae-tok.secrecy} + + Let $\proto{ae}$ and $\proto{tok}$ be an asymmetric encryption and + an authentication token scheme, respectively. Then + \begin{spliteqn*} + \InSec{ind-occa}(\Xid{\Pi}{sdaae-tok}(\proto{ae}, \proto{tok}); + t, q_E, q_D) \le \\ + 2 q_E \InSec{uow}(\proto{h}; t) + + \InSec{ind-cca}(\proto{ae}; t, q_D) + \end{spliteqn*} + and + \begin{spliteqn*} + \InSec{ind-occa}(\Xid{\Pi}{wdaae-tok}(\proto{ae}, \proto{tok}); + t, q_E, q_D, q_R) \le \\ + 2 (q_E + q_R) \InSec{uow}(\proto{h}; t) + + \InSec{ind-cca}(\proto{ae}; t, q_D + q_R) + \end{spliteqn*} +\end{theorem} +\begin{proof} + We prove the latter inequality; the former is follows by a rather simpler + version of the same argument, since the encryption algorithms are (by + construction) almost the same, and there is no recipient simulator in the + strong-deniability game. + + So let $A$ be any adversary breaking the secrecy of $\Pi = + \Xid{\Pi}{wdaae-tok}$ within the given resource bounds. It will suffice to + bound the advantage of $A$. We use a sequence of games. Let $\G0$ be the + standard IND-CCA game, with $b$ chosen uniformly at random. In + game~$\G{i}$, let $S_i$ be the event that $A$'s output is equal to $b$. By + \xref{lem:advantage} it suffices to bound $\Pr[S_0]$. + + Let $\mathcal{H}$ be the set of pairs $(N, h) = (N, H_N([X, X'])$ computed + by the encryption and recipient-simulator oracles. Game~$\G1$ is the same + as $\G0$ except that we abort the game if $A$ makes a decryption or + recipient-simulation query with public key $(Z, Z', \gamma)$ and ciphertext + $c$, with following conditions: + \begin{itemize} + \item the ciphertext decrypts successfully, yielding a message $\tau \cat N + \cat h \cat m$, with $\len(\tau) = \kappa$, $\len(N) = \nu$ and $\len(h) + = \lambda$; + \item the pair $(N, h) \in \mathcal{H}$; and + \item the hash $h = H_N([Z, Z'])$; but + \item the public key $(Z, Z') \ne (X, X')$. + \end{itemize} + Let $F_1$ be the event that the game aborts for this reason. By + \xref{lem:shoup}, we have + \begin{equation} \label{eq:daae-tok.sec.s0} + \Pr[S_0] - \Pr[S_1] \le \Pr[F_1] + \end{equation} + We claim that + \begin{equation} \label{eq:daae-tok.sec.f1} + \Pr[F_1] \le (q_E + q_R) \InSec{uow}(\proto{h}; t) + \end{equation} + For $0 \le i < q_E + q_R$, let $M_i$ be the event that we abort the game + because a hash in an input ciphertext matches the hash output by the $i$th + encryption or recipient-simulator query; then $\Pr[F_1] \le \sum_{0\le + i] node {$\pi$} + ($(dd.west) + (0, 2pt)$); + \draw ($(dd.west) - (0, 2pt)$) + to[->, below] node {$\pi$} + ($(d.east) - (0, 2pt)$); + \node[left = of d] (t) {$\Bin^\kappa$} + edge [<-, below] node {$H_m$} (d) + edge [<-, above left] node {$T_m$} (xy); + \node[right = of dd] (v) {$\Bin^\kappa$} + edge [<-, below] node {$H_m$} (dd) + edge [<-, above right] node {$V_m$} (xy); + \end{tikzpicture} \] + + We can consequently rewrite + \[ T_{x, x'}((R, R'), m) = T_m(x P, x' P, R, R') \] + and + \[ V_{y, y'}((Q, Q'), m, \tau) = \begin{cases} + 1 & if $\tau = V_m(y P, y' P, Q, Q')$ \\ + 0 & otherwise + \end{cases} + \] + + Now, $H$ -- and hence its restriction $H_m$ -- is a random function, + assigning a uniformly distributed and independent $\kappa$-bit string to + each point in its domain. Since $D$ and $D'$ are injective, the functions + $T_m$ and $V_m$ also have this property. (Obviously the outputs of $H_m$, + $T_m$ and $V_m$ are not independent of \emph{each other}, merely of other + outputs of the same function.) It's also clear that the action of $H_m$ on + $D(G^4)$ is determined by $T_m$, and similarly for $D'(G^4)$ and $V_m$. + This observation motivates the definition of the next game~$\G1$. + + Game~$\G1$ redefines the three oracles provided to the adversary in terms + of three new functions $T$, $V$ and $H$ shown in \xref{fig:dh-naiad-g1}. + We use the `lazy sampling' technique; we implement $T$ directly as a lazily + sampled random function; $V$ consults $T$ where applicable, and otherwise + uses a separate lazily sampled random function; and $H$ consults $T$ or $V$ + where applicable. + + \begin{figure} + \begin{program} + Initialization: \+ \\ + $\mathcal{H} \gets \emptyset$; \\ + $\mathcal{T} \gets \emptyset$; \\ + $\mathcal{V} \gets \emptyset$; \- + \\[\medskipamount] + $T(R, R', m)$: \+ \\ + \IF $(R, R', m) \in \dom \mathcal{T}$ \THEN \\ + \quad $\tau \gets \mathcal{T}(R, R', m)$; \\ + \ELSE \\ \ind + $\tau \getsr \Bin^\kappa$; \\ + $\mathcal{T} \gets \mathcal{T} \cup \{ (R, R', m) \mapsto \tau \}$; + \- \\ + \RETURN $\tau$; \- + \next + $V'(Q, Q', m)$: \+ \\ + \IF $(Q, Q', m) \in \dom \mathcal{V}$ \THEN \\ + \quad $\tau' \gets \mathcal{V}(Q, Q', m)$; \\ + \ELSE \\ \ind + \IF $Q = X \land Q' = X'$ \THEN + $\tau' \gets T(Y, Y', m)$; \\ + \ELSE + $\tau' \getsr \Bin^\kappa$; \\ + $\mathcal{V} \gets \mathcal{V} \cup + \{ (Q, Q', m) \mapsto \tau' \}$; + \- \\ + \RETURN $\tau'$; \- + \\[\medskipamount] + $V(Q, Q', m, \tau)$: \+ \\ + $\tau' \gets V'(Q, Q', m)$; \\ + \IF $\tau = \tau'$ \THEN \RETURN $1$ \ELSE \RETURN $0$; \- + \newline + $H(s)$: \+ \\ + \IF $s \in \dom \mathcal{H}$ \THEN + $h \gets \mathcal{H}(s)$; \\ + \ELSE \\ \ind + \IF $s = [m, Q, Q', R, R', Z, Z', W, W']$ for some \\ + \hspace{4em} + $(m, Q, Q', R, R', Z, Z', W, W') \in \Bin^* \times G^8$ + \THEN \\ \ind + \IF $(Q, Q') = (X, X') \land + (Z, Z', W, W') = (x R, x R', x' R, x' R')$ \THEN + $h \gets T(R, R', m)$; \\ + \ELSE \IF $(R, R') = (Y, Y') \land + (Z, Z', W, W') = (y Q, y' Q, y Q', y' R')$ \THEN + $h \gets V'(Q, Q', m)$; \\ + \ELSE + $h \getsr \Bin^\kappa$; \- \\ + \ELSE + $h \getsr \Bin^\kappa$; \\ + $\mathcal{H} \gets \mathcal{H} \cup \{ s \mapsto h \}$; \- \\ + \RETURN $h$; + \end{program} + + \caption{Tagging, verification and hashing functions for $\G1$} + \label{fig:dh-naiad-g1} + \end{figure} + + The adversary's oracles map onto these functions in a simple way: $H$ is + precisely the hashing oracle, and + \[ T_{x, x'}((R, R'), m) = T(R, R', m) \qquad \textrm{and} \qquad + V_{y, y'}((Q, Q'), m, \tau) = V(Q, Q', m) \] + Given the foregoing discussion, we see that, despite the rather radical + restructuring of the game, all of the quantities that the adversary sees + are distributed identically, and therefore + \begin{equation} + \label{eq:dh-naiad-s0} + \Pr[S_0] = \Pr[S_1] + \end{equation} + + Game~$\G2$ is the same as $\G1$, except that we no longer credit the + adversary with a win if it makes a verification query $V_{y, y'}((X, X'), + m, \tau)$ without previously making a hashing query $H([m, X, X', Y, Y', y + X, y' X, y X', y' X'])$. If this happens, either there has been a previous + query to $T_{x, x'}((Y, Y'), m)$, in which case the verification query + can't count as a win in any case, or there was no such query, in which case + the true tag $\tau'$ will be freshly generated uniformly at random. + Evidently, then, + \begin{equation} + \label{eq:dh-naiad-s1} + \Pr[S_1] - \Pr[S_2] \le \frac{q_V}{2^\kappa} + \end{equation} + + Game~$\G3$ is similar to $\G2$, except that we change the way that the keys + are set up. Rather than choosing $x'$ and $y'$ at random and setting $(X', + Y') = (x' P, y' P)$, we choose $(u, u', v, v') \inr \gf{p}$ and set + \[ X' = u P + u' X \qquad \textrm{and} \qquad Y' = v P + v' Y \] + It's clear that (a) $X'$ and $Y'$ are still uniformly distributed on $G$, + and (b) they are independent of $u'$ and $v'$. Since this change doesn't + affect the distribution of $X'$ and $Y'$, we conclude that + \begin{equation} + \label{eq:dh-naiad-s2} + \Pr[S_2] = \Pr[S_3] + \end{equation} + + Finally, we bound $\Pr[S_3]$ by a reduction from the computational + Diffie--Hellman problem in~$G$. The reduction receives points $X^* = x P$ + and $Y^* = y P$ and must compute $Z^* = x y P$. It sets $X = X^*$ and $Y = + Y^*$. It chooses $u$, $u'$, $v$, and $v'$, determines $X'$ and $Y'$ as in + $\G4$, and runs $A$ with simulated oracles: the tagging and verification + oracles work exactly as in $\G3$; however, it cannot implement the hashing + function as described, so we must change it: + \begin{itemize} + \item rather than checking whether $(Z, Z', W, W') = (x R, x R', x' R, x' + R')$, we check whether $(W, W') = (u R + u' Z, u R' + u' Z')$; and + \item rather than checking whether $(Z, Z', W, W') = (y Q, y' Q, y Q', y' + R')$, we check whether $(Z', W') = (v R + v' Z, v R' + v' W)$. + \end{itemize} + Let $F$ be the event that this change causes the reduction's hashing + function to make a decision that the proper $\G3$ wouldn't make. + + Let $U$ be the event that the adversary (apparently, using the reduction's + modified hashing function) makes a successful forgery. In this case, we + must have seen a hashing query $H([m, X, X', Y, Y', Z, v R + v' Z, W, v R' + + v' W])$. If $F$ doesn't occur, then we in fact have $Z = x y P = Z^*$; + the work we must do in the reduction over and above $\G1$ is to choose $u$ + etc., to compute $X'$ and $Y'$, perform the dictionary maintenance, and + use the twin-Diffie--Hellman detector, so + \[ \Pr[U \mid \bar{F}] \le \InSec{cdh}(G; t + t') \] + Furthermore, the reduction and $\G4$ proceed identically unless $F$ occurs, + so \xref{lem:shoup} gives + \[ \Pr[S_4] - \Pr[U] \le \Pr[F] \] + A simple calculation bounds $\Pr[U]$: + \begin{eqnarray*}[rl] + \Pr[U] & = \Pr[U \land F] + \Pr[U \land \bar{F}] \\ + & = \Pr[U \land F] + \Pr[U \mid \bar{F}] \Pr[\bar{F}] \\ + & \le \Pr[F] + \Pr[U \mid \bar{F}] \\ + & \le \InSec{cdh}(G; t + t') + \Pr[F] + \eqnumber \label{eq:dh-naiad-t} + \end{eqnarray*} + Finally, we bound $\Pr[F]$ using \xref{lem:2dh-detect}: + \begin{equation} + \label{eq:dh-naiad-f} + \Pr[F] \le \frac{2 q_H}{\#G} + \end{equation} + Piecing together equations~\ref{eq:dh-naiad-s0}--\ref{eq:dh-naiad-f} + completes the proof. +\end{proof} + +\section{Tag signing and nondirectable key encapsulation} +\label{sec:tag} + +\subsection{Construction and general authenticity failure} +\label{sec:tag.construct} + +This section describes a rather different approach to constructing a deniably +authenticated asymmetric encryption scheme. The approach could be summed up +in the phrase `sign something irrelevant'. + +More concretely, we make use of the following ingredients: +\begin{itemize} +\item a key-encapsulation mechanism $\proto{kem} = (\lambda, \mathcal{G}, + \mathcal{E}, \mathcal{D})$; +\item an authenticated encryption with additional data (AEAD) scheme + $\proto{aead} = (\kappa, E, D)$, with $\kappa < \lambda$; and +\item a digital signature scheme $\proto{sig} = (G, S, V)$. +\end{itemize} +Given these, we define a weakly deniably authenticated asymmetric encryption +scheme +\begin{spliteqn*} + \Xid{\Pi}{wdaae-tag}(\proto{kem}, \proto{aead}, \proto{sig}) = + (\Xid{G}{wdaae-tag}, \Xid{E}{wdaae-tag}, \\ + \Xid{D}{wdaae-tag}, \Xid{R}{wdaae-tag}, \Xid{S}{wdaae-tag}) +\end{spliteqn*} +where the component algorithms are as shown in \xref{fig:tag.construct}. + +\begin{figure} + \begin{program} + \begin{tikzpicture}[node distance = 5mm] + \node[box = yellow!20, minimum width = 30mm] (m) {$m$}; + \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); + \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); + \draw[->] (s |- enc) -- (enc); + \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); + \draw[->] (sm) -- (s); + \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); + \draw[->] (tag) -- (t2); + \draw[rounded, ->] (k) |- (enc); + \draw[->] (b) -- (b2); + \end{tikzpicture} + \next + $\Xid{G}{wdaae-tag}()$: \+ \\ + $(x, X) \gets \mathcal{G}()$; + $(x', X') \gets G()$; \\ + \RETURN $\bigl( (x, x', X), (X, X') \bigr)$; \- + \\[\medskipamount] + $\Xid{E}{wdaae-tag}_{(x, x', X)}\bigl( (Y, Y'), m \bigr)$: \+ \\ + $(Z, u) \gets \mathcal{E}_Y()$; \\ + $K \gets Z[0 \bitsto \kappa]$; + $\tau \gets Z[\kappa \bitsto \lambda]$; \\ + $\sigma \gets S_{x'}([\tau, Y])$; \\ + $c \gets E_K(m, [\sigma])$; \\ + \RETURN $\bigl( K, (u, \sigma, c) \bigr)$; \- + \\[\medskipamount] + $\Xid{D}{wdaae-tag}_{(x, x', X)}\bigl( (Y, Y'), (u, \sigma, c) \bigr)$: + \+ \\ + $Z \gets \mathcal{D}_x(u)$; \IF $Z = \bot$ \THEN \RETURN $\bot$; \\ + $K \gets Z[0 \bitsto \kappa]$; + $\tau \gets Z[\kappa \bitsto \lambda]$; \\ + $v \gets V_{Y'}([\tau, X], \sigma)$; + \IF $v \ne 1$ \THEN \RETURN $\bot$; \\ + $m \gets D_K(c, [\sigma])$; \\ + \RETURN $m$; \- + \newline + $\Xid{R}{wdaae-tag}_{(x, x', X)} + \bigl( (Y, Y'), (u, \sigma, y), m' \bigr)$: \+ \\ + $Z \gets \mathcal{D}_x(u)$; \IF $Z = \bot$ \THEN \RETURN $\bot$; \\ + $K \gets Z[0 \bitsto \kappa]$; + $c' \gets E_K(m', [\sigma])$; \\ + \RETURN $(u, \sigma, c')$; \- + \next + $\Xid{S}{wdaae-tag}_{(x, x', X)} + \bigl( (Y, Y'), K, (u, \sigma, c), m' \bigr)$: \+ \\ + $c' \gets E_K(m', [\sigma])$; \\ + \RETURN $(u, \sigma, c')$; \- + \end{program} + \caption{Weakly deniably authenticated asymmetric encryption by signing + tags} + \label{fig:tag.construct} +\end{figure} + +When we analyse this construction, we find that we have good secrecy +(\xref{th:wdaae-tag.sec}) and deniability (\xref{th:wdaae-tag.deny}). +However, we are unable to prove authenticity. Indeed, it's quite easy to see +that authenticity fails, in general. + +Let $\proto{ae} = (G, E, D)$ be an asymmetric encryption scheme; we can +construct from it a simple KEM $\Xid{\Pi}{ae-kem}(\proto{ae}, \kappa) = +(\kappa, G, E', D)$ where $E'$ is simply +\begin{program} + $E'_X()$: $K \getsr \Bin^\kappa$; $u \gets E_X(K)$; \RETURN $(u, K)$; +\end{program} +We immediately have +\[ \InSec{ind-cca}(\Xid{\Pi}{ae-kem}(\proto{ae}, \kappa); t, q_D) \le + \InSec{ind-cca}(\proto{ae}; t, q_D) +\] +by a trivial reduction. + +Let $\proto{sig} = (G, S, V)$ be a digital signature scheme. We construct +another digital signature scheme $\proto{sig}' = (G, S', V')$ as follows. +\begin{program} + $S'_x(m)$: $\sigma \gets S_x(m)$; \RETURN $(\sigma, m)$; \\ + $V'_X(m, (m', \sigma))$: $v \gets V_X(m, \sigma)$; \IF $v = 1 \land m' = m$ + \THEN \RETURN $1$ \ELSE \RETURN $0$; +\end{program} +We immediately have +\[ \InSec{euf-cma}(\proto{sig}'; t, q_S) = + \InSec{euf-cma}(\proto{sig}; t, q_S) +\] + +We have the following proposition. + +\begin{proposition}[General authenticity failure of tag-signing] + \label{prop:daae-tag.auth-fail} + + Let $\proto{ae}$, $\proto{aead}$, and $\proto{sig}$ be an asymmetric + encryption scheme, a scheme for authenticated encryption with additional + data, and a digital signature scheme, respectively. Then + \[ \InSec{uf-ocma}(\Xid{\Pi}{wdaae-tag} + (\Xid{\Pi}{ae-kem}(\proto{ae}, \lambda), + \proto{aead}, \proto{sig}'); t, 1, 1, 0) = 1 + \] + for a small constant $t$. +\end{proposition} +\begin{proof} + Suppose that $\proto{ae} = (\mathcal{G}, \mathcal{E}, \mathcal{D})$, and + $\proto{aead} = (\kappa, E, D)$. We describe a simple adversary breaking + authenticity. + \begin{enumerate} + \item The adversary is invoked with public keys $(X, X')$ for the sender + and $(Y, Y')$ for the recipient. + \item It requests the encryption for public key $(Y, Y')$ and message $m = + 0$. Let the ciphertext returned be $(u, c, (\sigma, \tau))$. + \item It chooses a key $K \inr \Bin^\kappa$. + \item It computes $u' \gets \mathcal{E}_Y(K \cat \tau)$. + \item It computes $c' \gets E_K(1, [(\sigma, \tau)])$. + \item It submits the ciphertext $(u', c', (\sigma, \tau))$ to the + decryption oracle, with public key $(X, X')$. + \end{enumerate} + Inspection of the decryption algorithm shows that this is a valid + ciphertext, so the adversary wins with probability $1$. +\end{proof} + +What has gone wrong? The problem is that, while an honest KEM user allows it +to select its output key at random, the adversary might be able to +\emph{direct} it so as to give the output key that it wants. In the next +sections: +\begin{itemize} +\item we define what it means for a KEM to be \emph{nondirectable}: + essentially, that it is hard to arrange for the output key to be anything + in particular; +\item we show that a class of existing KEMs, using the random oracle model, + are already nondirectable; and +\item we prove the security of our construction assuming nondirectability of + the KEM. +\end{itemize} + +\subsection{Definition of nondirectability} +\label{sec:ndir.def} + +Informally, we say that a KEM $\Pi = (\kappa, G, E, D)$ is $(t, +n)$-nondirectable if, given a public key $X$ (with corresponding private key +$x$) and a set $\mathcal{T}$ of $n$ independent and uniformly distributed +$t$-bit strings, it's infeasible to find a clue $u$ for which $D_x(u)[\kappa +- t \bitsto \kappa] \in \mathcal{T}$. Formally, we have the following +definition. +\begin{definition}[$(t, n)$-nondirectability of a KEM] + \label{def:kem-nondir} + + Let $\Pi = (\kappa, G, E, D)$ be a key-encapsulation mechanism, let $t$ be + an integer such that $0 < t \le \kappa$, and let $n$ be a positive integer. + We measure an adversary $A$'s ability to attack the $t$-nondirectability of + $\Pi$ with the following game. + \begin{program} + $\Game{ndir}{\Pi, t, n}(A)$: \+ \\ + $(x, X) \gets G()$; \\ + \FOR $0 \le i < n$: \\ \ind + $\tau_i \getsr \Bin^t$; \- \\ + $\mathbf{t} \gets (\tau_0, \tau_1, \ldots, \tau_{n-1})$; \\ + $\mathcal{T} \gets \{\tau_0, \tau_1, \ldots, \tau_{n-1}\}$; \\ + $w \gets 0$; \\ + $A^{\id{try}(\cdot)}(X, \mathbf{t})$; \\ + \RETURN $w$; \- + \next + $\id{try}(u)$: \+ \\ + $K \gets D_x(u)$; \\ + \IF $K \ne \bot \land K[\kappa - t \bitsto \kappa] \in \mathcal{T}$ + \THEN $w \gets 1$; \\ + \RETURN $K$; + \end{program} + The \emph{advantage} of $A$ against the $(t, n)$-nondirectability of $\Pi$ + is given by + \[ \Adv{ndir}{\Pi, t, n}(A) = \Pr[\Game{ndir}{\Pi, t, n}(A) = 1] \] + Finally, the $t$-nondirectability insecurity function of $\Pi$ is defined + by + \[ \InSec{ndir}(\Pi, t, n; t', q_D) = \max_A \Adv{ndir}{\Pi, t, n}(A) \] + where the maximum is taken over all adversaries $A$ completing the game in + time~$t'$ and making at most $q_D$ oracle queries. +\end{definition} + +The general definition above is useful when proving security for +constructions which use KEMs as components; but the following theorem will be +handy when proving nondirectability of specific KEMs. + +\begin{theorem}[Multi-target nondirectability] + \label{th:kem-nondir-multi} + + For any key-encapsulation mechanism $\Pi$, + \[ \InSec{ndir}(\Pi, t, n; t', q) \le + n \, \InSec{ndir}(\Pi, t, 1; t', q) \] +\end{theorem} +\begin{proof} + We describe a reduction from attacking $(t, 1)$-nondirectability to + attacking $(t, n)$-nondirectability. Suppose, then, that we're given a + public key~$X$, a singleton vector $\mathbf{t} = (\tau_0)$, and an + arbitrary adversary~$A$ running within the given resource bounds. We + choose $\tau_i \inr \Bin^\kappa$ at random, for $1 \le i < n$, choose a + random permutation $\pi$ on $\{0, 1, \ldots, n - 1\}$, and set $\mathbf{t}' + = (\tau_{\pi(0)}, \tau_{\pi(1)}, \ldots, \tau_{\pi(n-1)})$. We run $A$ on + $X$ and $\mathbf{t}'$. Let $\epsilon = \Adv{ndir}{\Pi, t, n}(A)$; then we + claim that our reduction succeeds with probability at least $\epsilon/n$. + The theorem then follows immediately from the claim. + + To prove the claim, then, note that $\mathbf{t}$ is uniformly distributed + on $(\Bin^*)^n$, and $\pi$ is independent of $\mathbf{t}$ -- in particular, + $\pi^{-1}(0)$ is uniform and independent of $\mathbf{t}$. Hence, for any + algorithm selecting a coordinate of $\mathbf{t}$, the probability that it + chooses $\tau_0$ is at least $1/n$ (with equality if the coordinates are + distinct). Now consider the algorithm that runs $A$ on $\mathbf{t}'$ and + $X$, and selects the first element for which $A$ submits a matching KEM + clue: conditioning on $A$ winning the game, it matches $\tau_0$ with + probability at least $1/n$, and the claim follows. +\end{proof} + +\subsection{Random oracle key-encapsulation mechanisms} +\label{sec:ndir.ro} + +A number of key-encapsulation mechanisms in the random oracle model follow +a similar pattern: the sender constructs somehow a clue~$u$ and an answer~$z$ +such that $z$ is unpredictable given only $u$ and the recipient's public key, +but the recipient can easily determine $z$ given her private key. To move +from unpredictability to indistinguishable from random, both sender and +recipient hash $z$ to obtain a key~$K$. If we model the hash function as a +random oracle, then $K$ is indistinguishable from random if the adversary +can't determine~$z$ exactly. + +This pattern captures both Diffie--Hellman KEMs, such as are found in DHIES +\cite{Abdalla:2001:DHIES} or Twin ElGamal \cite{cryptoeprint:2008:067}, and +KEMs based on trapdoor one-way functions, such as RSA-KEM +\cite{cryptoeprint:2001:112}. + +A bit more formally, we make the following definitions. + +\begin{definition}[Pre-KEM syntax] + \label{def:pre-kem.syntax} + + A \emph{pre-KEM} is a triple $\proto{pkem} = (G, E, D)$ of (maybe + randomized) algorithms, as follows. + \begin{itemize} + \item The \emph{key-generation algorithm} $G$ accepts no parameters and + outputs a pair $(x, X) \gets G()$. We call $x$ the \emph{private key} + and $X$ the \emph{public key}. + \item The \emph{encapsulation algorithm} $E$ accepts a public key $X$ and + outputs a pair $(z, u) \gets E_X()$. We call $z$ the \emph{answer} and + $u$ the \emph{clue}. + \item The \emph{decapsulation algorithm} $D$ accepts a private key $x$ and + a clue $u$, and outputs $z \gets D_x(u)$ which is either an answer or the + distinguished symbol $\bot$. The decapsulation algorithm must be such + that if $(x, X)$ is any pair of keys produced by $G$, and $(z, u)$ is any + answer/clue pair output by $E_X()$, then $D_x(u)$ outputs $z$. \qed + \end{itemize} +\end{definition} + +The basic notion of security for a pre-KEM is \emph{one-wayness under + chosen-ciphertext attack}: given a public key and a clue, the adversary +should be unable to guess the correct answer. We grant the adversary access +to an oracle which verifies guessed answers to clues. + +\begin{definition}[Pre-KEM security] + \label{def:pre-kem.security} + + Let $\Pi = (G, E, D)$ be a pre-KEM. We measure an adversary~$A$'s ability + to attack $\Pi$ using the following game. + \begin{program} + $\Game{ow-cca}{\Pi}(A)$: \+ \\ + $(x, X) \gets G()$; \\ + $(z^*, u^*) \gets E_X()$; \\ + $w \gets 0$; + $A^{\id{vrf}(\cdot, \cdot)}(X, u^*)$; \\ + \RETURN $w$; \- + \next + $\id{vrf}(u, z)$: \+ \\ + $z' \gets D_x(u)$; \\ + \IF $z \ne z'$ \THEN \RETURN $0$; \\ + \IF $u = u^*$ \THEN $w \gets 1$; \\ + \RETURN $1$; \- + \end{program} + + The adversary's OW-CCA \emph{advantage} is measured by + \[ \Adv{ind-cca}{\Pi}(A) = + \Pr[\Game{ind-cca-$1$}{\Pi}(A) = 1] - + \Pr[\Game{ind-cca-$0$}{\Pi}(A) = 1] + \] + Finally, the IND-CCA insecurity function of $\Pi$ is defined by + \[ \InSec{ind-cca}(\Pi; t_D, q_V) = \max_A \Adv{ind-cca}{\Pi}(A) \] + where the maximum is taken over all adversaries~$A$ completing the game in + time~$t$ and making at most and $q_V$ queries to their verification + oracles. +\end{definition} + +\begin{example} + [Pre-KEM from Twin Diffie--Hellman \cite{cryptoeprint:2008:067}] + Let $G = \langle P \rangle$ be a group with prime order $p$. Private keys + are $(x, y) \inr \gf{p}^2$; the corresponding public key is $(X, Y) = (x P, + y P)$. To encapsulate, choose $r \inr \gf{p}$; the clue is $R = r P$, and + the answer is $z = (r X, r Y)$; to decapsulate, compute $z = (x R, y R)$. + Security is proven using \xref{lem:2dh-detect} to implement the + verification oracle. +\end{example} + +\begin{example}[Pre-KEM from a trapdoor one-way permutation] + A trapdoor one-way permutation generator is (informally, at least) a family + of permutations $f_K$ and an algorithm $G$ which generates pairs $(k, K)$, + such that $y = f_K(x)$ can be computed easily given only $K$, but computing + the preimage of a point is hard; given the `trapdoor' $k$, however, + computing inverses $x = f^{-1}_k(y)$ is also easy. Private keys are + trapdoors $k$; the corresponding public key is $K$. To encapsulate, choose + a random point $z$ in the domain of $f$: $z$ is itself the answer and $u = + f_K(z)$ is the clue. To decapsulate, calculate $z = f^{-1}_k(u)$. + Security follows immediately by a reduction from inverting $f_K$, since + guesses are readily confirmed using the permutation in the forward + direction. +\end{example} + +We are now ready to describe the `hash-KEM' construction of a full KEM from a +pre-KEM. Given a pre-KEM $\Pi = (G, E, D)$, and a hash function $H\colon +\Bin^* \to \Bin^\kappa$, we construct $\Xid{\Pi}{hkem}(\Pi, H) = (\kappa, G, +\Xid{E}{hkem}, \Xid{D}{hkem})$ as follows. +\begin{program} + $\Xid{E}{hkem}_X()$: \+ \\ + $(z, u) \gets E_X()$; \\ + $K \gets H([u, z])$; \\ + \RETURN $(K, u)$; \- +\next + $\Xid{D}{hkem}_x(u)$: \+ \\ + $z \gets D_x(u)$; \\ + $K \gets H([u, z])$; \\ + \RETURN $K$; \- +\end{program} + +\begin{theorem}[Hash-KEM security] + \label{th:hkem.sec} + + Let $\Pi$ be a pre-KEM, and let $H\colon \Bin^* \to \Bin^\kappa$ be a + random oracle; then + \[ \InSec{ind-cca}(\Xid{\Pi}{hkem}(\Pi, H); t, q_H) \le + 2 \InSec{ow-cca}(\Pi; t + q_H t_D + O(q_H + q_D), q_H) \] + where $t_D$ is the time required for $\Pi$'s decapsulation algorithm, and + the $O(\cdot)$ hides a small constant factor representing the time required + to generate a random $\kappa$-bit string and insert it into a hash table. +\end{theorem} +\begin{proof} + Let $A$ be any adversary attacking $\Xid{\Pi}{hkem}(\Pi, H)$ within the + stated resource bounds. We use a sequence of games. Game $\G0$ chooses a + uniform random bit $b \inr \{0, 1\}$, and then proceeds as in the IND-CCA + game. Let $X$ be the public key and $u^*$ and $K^*$ be the clue and key + provided to the adversary. Let $x$ be the corresponding private key, and + let $z^* = D_x(u^*)$. + + In each game $\G{i}$, let $S_i$ be the event that the adversary's output + $b' = b$. By \xref{lem:advantage}, it will suffice to show that + \[ \Pr[S_0] \le \frac{1}{2} + \InSec{ow-cca}(\Pi; t, q_H) \] + + In game~$\G1$, we change the behaviour of the random oracle and the + decapsulation oracle. Rather than decapsulating the given clue, the oracle + maintains a hash table: if a clue has not been queried before, it chooses a + $\kappa$-bit string uniformly at random, associates the string with the + clue in the hash table, and returns it; if the clue has been queried + before, it finds the associated random string, and returns it. If an input + to the random oracle has the form of a clue/answer pair $[u, z]$, where $z + = D_x(u)$, then it replies as if $u$ had been queried to the decapsulation + oracle; other random-oracle queries are handled by maintaining a second + hash table mapping query inputs to random $\kappa$-bit strings. While this + changes the underlying machinery substantially, everything appears + identically from the point of view of the adversary, so + \begin{equation} \label{eq:hkem.sec.s0} + \Pr[S_0] = \Pr[S_1] + \end{equation} + + In game~$\G2$, we always choose $K^*$ at random, regardless of the value of + $b$. If $b = 1$, we should have computed it as $H([u^*, z^*])$; but since + the random oracle associates uniformly distributed independent strings with + it inputs, the adversary cannot discover our deception unless it queries + $H$ at $[u^*, z^*]$. Let $F_1$ be the event that the adversary makes such + a query; then (\xref{lem:shoup}): + \begin{equation} \label{eq:hkem.sec.s1} + \Pr[S_1] - \Pr[S_2] \le \Pr[F_1] + \end{equation} + Since $b$ is uniform and not used anywhere in the game except to compare + with the adversary's output, we have + \begin{equation} \label{eq:hkem.sec.s2} + \Pr[S_2] = \frac{1}{2} + \end{equation} + Finally, we claim that + \begin{equation} \label{eq:hkem.sec.f1} + \Pr[F_1] \le \InSec{ow-cca}(\Pi; t + q_H t_D + O(q_D + q_H), q_H) + \end{equation} + We prove this by reduction, attacking $\Pi$. Our reduction simulates $\G2$ + as described, providing the public key $X$ and clue $u^*$ to $A$; it + answers decapsulation queries randomly, as for $\G1$, and uses its + verification oracle to identify random-oracle inputs of the necessary form. + Clearly if $A$ makes a query $H([u^*, z^*])$ then the reduction wins its + game. + + The theorem follows by combining + equations~\ref{eq:hkem.sec.s0}--\ref{eq:hkem.sec.f1}. +\end{proof} + +\begin{theorem}[Pre-KEM nondirectability] + If $H\colon \Bin^* \to \Bin^\kappa$ is a random oracle then + \[ \InSec{ndir}(\proto{hkem}, t, n; t', q_D, q_H) \le + \frac{(q_D + q_H) n}{2^t} \] +\end{theorem} +\begin{proof} + Let $A$ be an adversary in the nondirectability game. $A$ is given a set + $\mathcal{T}$ of uniformly distributed $t$-bit target strings with + $\#\mathcal{T} \le n$. The processing of each verification query involves + computing an answer $z$ from the input clue $u$, and querying the random + oracle at $[u, z]$. If the clues are distinct, the random oracle inputs + will be also distinct. Additionally, the adversary may make random oracle + queries of its own. In all, there may therefore be at most $q_D + q_H$ + such distinct queries. In response to each distinct query, the random + oracle chooses an independent uniformly distributed $\kappa$-bit string. + The probability that any such random oracle output has a $t$-bit suffix in + $\mathcal{T}$ is therefore at most $\#\mathcal{T}/2^t \le n/2^t$, and the + theorem follows immediately. +\end{proof} + +\subsection{Weakly deniable AAE from a nondirectable KEM} +\label{sec:tag.theorems} + +Having established the theory of nondirectable KEMs, we apply it to the +construction of \xref{sec:tag.construct}. + +\begin{theorem}[Tag-signing secrecy] + \label{th:wdaae-tag.sec} + + Let $\proto{kem}$, $\proto{aead}$, and $\proto{sig}$ be a key-encapsulation + mechanism, AEAD scheme and signature scheme, respectively. Then + \begin{spliteqn*} + \InSec{ind-occa}(\Xid{\Pi}{wdaae-tag} + (\proto{kem}, \proto{aead}, \proto{sig}); t, q_E, q_D, q_R) \le \\ + 2 \InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + + \InSec{ind-cca}(\proto{aead}; t, 1 + q_R, q_D) + \end{spliteqn*} +\end{theorem} +\begin{proof} + Let $A$ be any adversary attacking $\Pi = \Xid{\Pi}{wdaae-tag}(\proto{kem}, + \proto{aead}, \proto{sig})$ within the stated resource bounds. It will + suffice to bound $A$'s advantage. + + We use a sequence of games. Game~$\G0$ is the standard IND-OCCA game, with + $b$ chosen uniformly at random. In each game~$\G{i}$, let $S_i$ be the + event that $A$'s output is equal to $b$. + + In game~$\G1$, we change the way that we compute the challenge ciphertext. + Specifically, rather than using the key and tag output by the KEM, we + simply choose them at random. We record the KEM clue for later use, so + that the decryption and recipient-simulator oracles can notice it and use + the correct key and tag. We claim that + \begin{equation} \label{eq:wdaae-tag.sec.s0} + \Pr[S_0] - \Pr[S_1] \le \InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + \end{equation} + The claim follows by a simple reduction from KEM secrecy. The reduction is + given a KEM public key $Y$, a KEM clue $u^*$ and a string $Z^* \in + \Bin^\lambda$. It chooses a bit $b^*$, generates a KEM key pair $(x, X)$ + for the sender, and signature key pairs $(x', X')$ for the sender and $(y', + Y')$ for the recipient. It then runs $A$'s \cookie{find} stage, providing + it with the various public keys and encryption, decryption and + recipient-simulator oracles described below, eventually receiving two + messages $m_0$ and $m_1$ of equal length. It splits $Z^*$ into $K^*$ and + $\tau^*$, computes signature $\sigma^* \gets S_{x'}([\tau^*, Y])$, and + ciphertext $c^* \gets E_{K^*}(m_{b^*})$. It runs $A$'s \cookie{guess} + stage on $(u^*, c^*, \sigma^*)$, again providing the various oracles, until + $A$ outputs a bit. If $A$'s output equals $b^*$ then the reduction outputs + $1$; otherwise it outputs $0$. + + We now describe the oracles provided by the reduction. The encryption + oracle provided by the reduction simply uses the encryption algorithm, + using the known private key~$x'$ to make the necessary signatures. The + decryption oracle, given a ciphertext triple $(u, c, \sigma)$, checks + whether $u = u^*$. If so, it decrypts the ciphertext using the known value + of $Z^*$; otherwise, it queries the decapsulation oracle at $u$ to obtain + $Z$. The recipient-simulator oracle behaves similarly. + + We see that, if $Z^*$ is a real KEM output then the reduction simulates + $\G0$; otherwise it simulates $\G1$, both within the claimed resource + limits. It therefore obtains advantage $\Pr[S_0] - \Pr[S_1]$, which is by + definition bounded above as claimed. + + Finally, we bound $\Pr[S_1]$; we claim: + \begin{equation} \label{eq:wdaae-tag.sec.s1} + \Pr[S_1] \le + \frac12 \InSec{ind-cca}(\proto{aead}; t, 1 + q_R, q_D) + \frac12 + \end{equation} + Again, we use a reduction, this time from secrecy of the AEAD scheme. The + reduction encrypts the challenge ciphertext by running the + key-encapsulation algorithm to choose a clue $u^*$, but generating $\tau^*$ + at random and using the AEAD encryption oracle to encrypt one or other of + $A$'s chosen messages. It simulates the decryption oracle by detecting + ciphertexts with clue $u^*$ and using the AEAD decryption oracle. (We note + that the $A$ is forbidden from querying its decryption oracle at precisely + the challenge ciphertext, so the reduction will not itself make forbidden + queries.) The recipient-simulator oracle similarly detects ciphertexts + with clue $u^*$, and uses the AEAD encryption oracle (using the input + message as both message inputs) to construct its output. The claim follows + from an application of \xref{lem:advantage}. + + Finally, the theorem follows by combining + equations~\ref{eq:wdaae-tag.sec.s0} and~\ref{eq:wdaae-tag.sec.s1}, and + again applying \xref{lem:advantage}. +\end{proof} + +\begin{theorem}[Tag-signing authenticity] + \label{th:wdaae-tag.auth} + + Let $\proto{kem}$, $\proto{aead}$, and $\proto{sig}$ be a key-encapsulation + mechanism, AEAD scheme and signature scheme, respectively. Then + \begin{eqnarray*}[Lcl] + \InSec{uf-ocma}(\Xid{\Pi}{wdaae-tag} + (\proto{kem}, \proto{aead}, \proto{sig}); t, q_E, q_D, q_R) \le \\ + & & q_E \InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + + q_E \InSec{int-ctxt}(\proto{aead}; t, 1 + q_R, q_D) \\ + & + & \InSec{ndir}(\proto{kem}, \lambda - \kappa, q_E; t, q_D) + + \InSec{euf-cma}(\proto{sig}; t, q_E) + \end{eqnarray*} +\end{theorem} +\begin{proof} + Let $A$ be any adversary attacking $\Pi = \Xid{\Pi}{wdaae-tag}(\proto{kem}, + \proto{aead}, \proto{sig})$ within the stated resource bounds. It will + suffice to bound $A$'s advantage. + + We introduce the following notation. For $0 \le i < q_E$, let $(Q_i, Q'_i, + m_i)$ be the adversary's $i$th query to its encryption oracle. Let $(u_i, + Z_i) \gets \mathcal{E}_{Q_i}()$ be the KEM clue and output key generated + while answering the query, and $K_i = Z_i[0 \bitsto \kappa]$ and $\tau_i = + Z_i[\kappa \bitsto \lambda]$. Let $\sigma_i \gets S_{x'}([\tau_i, Q_i])$ + be the signature generated, and let $c_i \gets E_{K_i}(m_i, [\sigma_i])$ be + the AEAD ciphertext; the triple returned to the adversary is $(u_i, c_i, + \sigma_i)$. + + We use a sequence of games. Game~$\G0$ is the standard UF-OCMA game. In + each game~$\G{i}$, let $S_i$ be the event that $A$ queries its decryption + oracle on a valid forgery $(u, c, \sigma)$. + + In game~$\G1$, we alter the encryption oracle, so that, when answering a + query with $Q_i = Y$, it generates $Z_i$ uniformly at random, rather than + using the output of the KEM. We also alter the decryption and + recipient-simulator oracles: if the input clue is equal to $u_i$ for some + $0 \le i < q_E$ such that $Q_i = Y$, then they use the corresponding $Z_i$ + rather than applying the decapsulation algorithm. We claim that + \begin{equation} \label{eq:wdaae-tag.auth.s0} + \Pr[S_0] - \Pr[S_1] \le + q_E \InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + \end{equation} + The claim is proven using a hybrid argument. For $0 \le i \le q_E$, we + define the hybrid game $\G[H]i$ like $\G0$, except that the first $i$ + encryption oracle queries are answered by generating $Z_i$ at random, + rather than using the KEM, as in $\G1$; the remaining $q_E - i$ queries are + answered using the KEM, as in $\G0$. Let $T_i$ be the event in + game~$\G[H]i$ that the adversary correctly guesses~$b$. Notice that + $\G[H]0 \equiv \G0$ and $\G[H]{q_E} = \G1$. A reduction argument, similar + to that in the previous proof shows that, for $0 \le i < q_E$, + \[ \Pr[T_i] - \Pr[T_{i+1}] \le + \InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + \] + The claim then follows because + \[ \Pr[S_0] - \Pr[S_1] = \Pr[T_0] - \Pr[T_{q_E}] + = \sum_{0\le i] (kem) + edge [->] (B); + \draw[->] (tau) -- (tau2); + \node[op = green!20, below = of tau2.south east] (sig) {$S$}; + \draw[decorate, decoration = brace] + (B.south east) -- (tau2.south west) + coordinate [pos = 0.5, below = 2.5pt] edge [->] (sig); + \node[left = of sig] {$a'$} edge [->] (sig); + \node[box = green!20, below = of sig] (sigma) {$\sigma$} + edge [<-] (sig); + \node[box = yellow!20, right = -0.6pt of sigma, minimum width = 30mm] + (m) {$m$}; + \node at (m |- kem) {$m$} edge [->] (m); + \node[op = red!20, below = of m.south west] (enc) {$E$}; + \draw[decorate, decoration = brace] + (m.south east) -- (sigma.south west) + coordinate [pos = 0.5, below = 2.5pt] (p); + \draw[->, rounded] (p) |- (enc); + \draw[->, rounded] (K) |- (enc); + \node[box = red!20, below = of enc, minimum width = 35mm] (y) {$y$}; + \node[box = blue!20, left = -0.6pt of y] (u) {$u$}; + \draw[->] (enc) -- (y); + \draw[->, rounded] (kem) -- +(-1, 0) |- (u); + \end{tikzpicture} + \caption{Generic weakly-deniable asymmetric encryption} + \label{fig:gwd} +\end{figure} + +More formally, we define our generic weakly-deniable scheme +$\proto{aae-gwd}(\proto{kem}, \proto{sig}, \proto{se})$ +to be the collection of algorithms $(\Xid{G}{aae-gwd}, \Xid{E}{aae-gwd}, +\Xid{D}{aae-gwd}, \Xid{R}{aae-gwd}, \Xid{S}{aae-gwd})$ as follows. +\begin{program} + $\Xid{G}{aae-gwd}()$: \+ \\ + $(x, X) \gets \mathcal{G}()$; \\ + $(x', X') \gets G()$; \\ + \RETURN $\bigl( (x, x'), (X, X') \bigr)$; \- +\newline + $\Xid{E}{aae-gwd}_{x, x'}\bigl((Y, Y'), m\bigr)$: \+ \\ + $(Z, u) \gets \mathcal{E}_Y()$; \\ + $K \gets Z[0 \bitsto \kappa]$; + $\tau \gets Z[\kappa \bitsto \lambda]$; \\ + $\sigma \gets S_{x'}([\tau, Y])$; \\ + $y \gets E_K([\sigma] \cat m)$; \\ + \RETURN $\bigl((u, y), K\bigr)$; \- +\next + $\Xid{D}{aae-gwd}_{x, x'}\bigl((Y, Y'), (u, y)\bigr)$: \+ \\ + $Z \gets \mathcal{D}_x(u)$; + \IF $Z = \bot$ \THEN \RETURN $\bot$; \\ + $K \gets Z[0 \bitsto \kappa]$; + $\tau \gets Z[\kappa \bitsto \lambda]$; \\ + $\hat{m} \gets D_K(y)$; + \IF $\hat{m} = \bot$ \THEN \RETURN $\bot$; \\ + $[\sigma] \cat m \gets \hat{m}$; + \IF $V_{Y'}([\tau, X], \sigma) = 0$ \THEN \RETURN $\bot$; \\ + \RETURN $m$; +\newline + $\Xid{R}{aae-gwd}((x, x'), (Y, Y'), (u, y), m')$: \+ \\ + $Z \gets \mathcal{D}_x(u)$; + \IF $Z = \bot$ \THEN \RETURN $\bot$; \\ + $K \gets Z[0 \bitsto \kappa]$; \\ + $\hat{m} \gets D_K(y)$; + \IF $\hat{m} = \bot$ \THEN \RETURN $\bot$; \\ + $[\sigma] \cat m \gets \hat{m}$; \\ + $y' \gets E_K(\sigma \cat m')$; \\ + \RETURN $(u, y')$; \- +\next + $\Xid{S}{aae-gwd}((Y, Y'), (x, x'), (u, y), K, m')$: \+ \\ + \\ + \\ + $\hat{m} \gets D_K(y)$; + \IF $\hat{m} = \bot$ \THEN \RETURN $\bot$; \\ + $[\sigma] \cat m \gets \hat{m}$; \\ + $y' \gets E_K(\sigma \cat m')$; \\ + \RETURN $(u, y')$; \- +\end{program} + +\subsection{Deniability} +\label{sec:gwd.deny} + +Examining the encryption algorithm for our scheme reveals that the +authentication and secrecy parts are almost independent. Most importantly, +the signature~$\sigma$ is the only part of the ciphertext dependent on the +sender's private key is used, and $\sigma$ is independent of the message~$m$. +As we've seen, encrypting the signature prevents outsiders from detaching and +reusing it in forgeries, but the recipient can extract the signature and +replace the message. + +This is the source of the scheme's deniability: anyone who knows the +symmetric key~$K$ can extract the signature and replace the encrypted message +with a different one. + +More formally, we have the following theorem. + +\begin{theorem} + \label{th:gwd-wdeny} + + The scheme $\Pi = \proto{aae-gwd}(\proto{kem}, \proto{sig}, + \proto{se})$ has perfect deniability: i.e., + \[ \InSec{wdeny}(\Pi; t) = 0 \] +\end{theorem} +\begin{proof} + Simply observe that the clue encrypted signature are simply copied from the + input original ciphertext in each case, and the symmetric ciphertext in + each case is constructed using the proper symmetric encryption algorithm + using the proper symmetric key. +\end{proof} + +However, our scheme is not strongly deniable unless signatures are easily +forged. To formalize this claim, we must deal with the syntactic difference +between strongly and weakly deniable encryption schemes. + +\begin{theorem} + \label{th:gwd-not-sdeny} + + Let $\Pi = \proto{aae-gwd}(\proto{kem}, \proto{sig}, + \proto{se}) = (G, E, D, R, S)$ as defined above. Define $\pi_0(c, + \eta) = c$ and $\bar{E}_x(Y, m) = \pi_0(E_x(Y, m))$ to discard the hint + $\eta$. For any recipient simulator~$R'$, let $\Pi'(R') = (G, \bar{E}, D, + R')$; then $\Pi'(R')$ is syntactically a strongly deniable AAE scheme; but + \[ \InSec{sdeny}(\Pi'(R'); t) \ge + 1 - \InSec{euf-cma}(\proto{sig}; t_{R'} + t', 0) \] + where $t_{R'}$ is the running time of $R'$ and $t'$ is the time taken to + decrypt a ciphertext of $\Pi$. +\end{theorem} +\begin{proof} + It is plain that $\Pi'(R')$ is syntactically correct. + + Recall that a strong-deniability simulator does not require a sample + ciphertext to work from. Now, consider the judge~$J$ which, given a + ciphertext and the appropriate keys, recovers the symmetric key using the + recipient's private key, decrypts the symmetric ciphertext to extract the + signature, and verifies it against the tag using the sender's public key; + if the signature verifies OK, it outputs~$1$, otherwise~$0$. If given a + genuine ciphertext, the judge always outputs $1$. Let $\epsilon$ be the + probability that the judge outputs $1$ given a simulated ciphertext; then + $J$'s advantage is $1 - \epsilon$ by definition. The theorem will follow + from the claim that + \[ \epsilon \le \InSec{euf-cma}(\proto{sig}; t_{R'} + t', 0) \] + We prove this by a simple reduction: given a public verification key for + the signature scheme, generate a KEM key pair, and run $S$ on the KEM + private key, the verification key, and the empty message. Decrypt the + resulting ciphertext using the KEM private key, recovering the signature + and tag, and return both as the forgery. The reduction runs in the stated + time, proving the claim. +\end{proof} + +\subsection{Conventional security} +\label{sec:gwd.aae} + +Before we embark on the formal security proof, it's worth reflecting on the +intuitive reason that the generic scheme is secure -- in the sense of +providing (outsider) secrecy and authenticity. + +Secrecy is fairly straightforward: it follows directly from the security of +the KEM and the symmetric encryption scheme. + +Firstly we consider secrecy, and initially restrict our attention to secrecy +under chosen-plaintext attack only. If the KEM is any good then the key~$Z$ +appears to be random and particularly the first $\kappa$ bits -- i.e., the +symmetric key~$K$ -- are unknown to the adversary. Since~$K$ is good, and we +assume that the symmetric scheme is good, then the ciphertext~$y$ hides~$m$, +and since~$y$ is the only part of the overall ciphertext that depends on~$m$ +this is sufficient. + +For secrecy under chosen-ciphertext attack we must show that a decryption +oracle doesn't help. A decryption query may share a KEM clue with a given +target ciphertext. If it does then we appeal to symmetric security; if not, +then the KEM security suffices. + +Finally we deal with authenticity. For a forgery to be successful, it must +contain a signature which can be verified using the purported sender's public +key; if the signature scheme is good, then this must be a signature actually +made by the purported sender. If the KEM clue on the forgery doesn't match +the clue from the message from which the signature was extracted, then the +tag taken from the forgery will fail to match with high probability. If the +KEM clue does match then the symmetric key must also match, and so the +symmetric scheme's authentication will ensure that the signature and message +are both unaltered -- so the forgery is trivial. + +We now present the formal security theorems. + +\begin{theorem}[AAE-GWD secrecy] + \label{th:gwd-secrecy} + Let $\Pi = \proto{aae-gwd}(\proto{kem}, \proto{sig}, + \proto{se})$ be as defined above. Then + \[ \InSec{ind-occa}(\Pi; t, q_E, q_D) \le \\ + 2\,\InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + + \InSec{ind-cca}(\proto{se}; t, 1 + q_R, q_D + q_R) + \] +\end{theorem} +\begin{theorem}[AAE-GWD authenticity] + \label{th:gwd-authenticity} + Let $\Pi = \proto{aae-gwd}(\proto{kem}, \proto{sig}, + \proto{se})$ be as defined above. Then + \begin{spliteqn*} + \InSec{uf-ocma}(\Pi; t, q_E, q_D, q_R) \le + q_E \InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + {} \\ + q_E \InSec{int-ctxt}(\proto{se}; t, 1 + q_R, q_D + q_R) + + q_E \InSec{ind-cca}(\proto{se}; t, 1 + q_R, 0) + {} \\ + \InSec{euf-cma}(\proto{sig}; t, q_E) + \end{spliteqn*} +\end{theorem} + +\begin{proof}[Proof of \xref{th:gwd-secrecy}] + We use sequences of games over the same underlying probability space, as + described in \cite{Shoup:2002:OR,cryptoeprint:2004:332}. + + Let $A$ be any adversary attacking the outsider secrecy of $\Pi$ which runs + within the stated resource bounds. It will therefore suffice to bound + $A$'s advantage. + + In game~$\G0$, we toss a coin~$b \inr \{0, 1\}$, and play + $\Game{ind-occa-$b$}{\Pi}(A)$. The adversary's output is $b'$. Let $S_0$ + be the event that $b = b'$. We have, by \xref{lem:advantage}, that + \begin{equation} + \label{eq:gwd-sec-s0} + \Adv{ind-occa}{\Pi}(A) = 2\Pr[S_0] - 1 + \end{equation} + Hence bounding $\Pr[S_0]$ will be sufficient to complete the proof. In + each game~$\G{i}$ that we define, $S_i$ will be the event that $b' = b$ in + that game. As we define new games, we shall bound $\Pr[S_i]$ in terms of + $\Pr[S_{i+1}]$ until eventually we shall be able to determine this + probability explicitly. + + Before we start modifying the game, we shall pause to establish some + notation. The \emph{challenge ciphertext} passed to the \cookie{guess} + stage of the adversary is a clue/signature/ciphertext triple $c^* = (u^*, + y^*)$, where $(Z^*, u^*) \gets \mathcal{E}_Y()$, $K^* = Z^*[0 \bitsto + \kappa]$, $\tau^* = Z^*[\kappa \bitsto \lambda]$, $\sigma^* \gets + S_x([\tau^*, Y])$, and $y^* \gets E_{K^*}([\sigma^*] \cat m_b)$. + + Game~$\G1$ works in almost the same way as $\G0$. The difference is that + rather than computing~$Z^*$ using the key-encapsulation algorithm + $\mathcal{E}_Y$, we simply choose it uniformly at random from + $\Bin^\lambda$. Furthermore, the decryption and recipient-simulator + oracles compensate for this by inspecting the input ciphertext $c = (u, + y)$: if and only if $u = u^*$ then decryption proceeds using $Z = Z^*$ + rather than using the key-decapsulation algorithm~$\mathcal{D}$. + + We claim that + \begin{equation} + \label{eq:gwd-sec-g1} + \Pr[S_0] - \Pr[S_1] \le + \InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + \end{equation} + The proof of the claim is by a simple reduction argument: we define an + adversary~$\hat{A}$ which attacks the KEM. We describe the + adversary~$\hat{A}$ in detail by way of example; future reduction arguments + will be rather briefer. + + The adversary receives as input a public key~$Y$ for the KEM, an + $\lambda$-bit string $Z^*$ and a clue~$u^*$. It generates signature key + pairs ~$(x', X')$ and $(y', Y')$, and a KEM key pair~$(x, X)$, using the + key-generation algorithms; it also chooses $b \in \{0, 1\}$ uniformly at + random. It runs the \cookie{find} stage of adversary~$A$, giving it $(X, + X')$ and $(Y, Y')$ as input. Eventually, the \cookie{find} stage completes + and outputs $m_0$ and $m_1$ and a state~$s$. Our KEM adversary computes + $\sigma^*$ and $y^*$ in terms of the $Z^*$ it was given and the + message~$m_b$, and runs the \cookie{guess} stage of adversary~$A$, + providing it with the ciphertext~$(u^*, y^*)$ and the state~$s$. + Eventually, $A$ completes, outputting its guess~$b'$. If $b' = b$ then our + KEM adversary outputs~$1$; otherwise it outputs~$0$. + + During all of this, we must simulate $A$'s various oracles. The encryption + oracle poses no special difficulty, since we have the signing key~$x'$. On + input $\bigl((Q, Q'), (u, \sigma, y)\bigr)$, the simulated decryption + oracle works as follows. If $u = u^*$ then set $Z= Z^*$; otherwise + retrieve $Z$ by querying the decapsulation oracle at~$u$, since this is + permitted by the KEM IND-CCA game rules. Except for this slightly fiddly + way of discovering~$Z$, the simulated decryption oracle uses the `proper' + decryption algorithm, verifying the signature $\sigma$ on the tag~$\tau = + Z[\kappa \bitsto \lambda]$ using the public key~$Q'$. The + recipient-simulator oracle works in a similar fashion. + + If the KEM adversary is playing the `real' + $\Game{ind-cca-$1$}{\proto{kem}}$ then our KEM adversary simulates + $\G0$ perfectly; hence, the probability that it outputs $1$ is precisely + $\Pr[S_0]$. On the other hand, if it is playing + $\Game{ind-cca-$0$}{\proto{kem}}$ then it simulates~$\G1$, and the + probability that it outputs $1$ is $\Pr[S_1]$. Hence + \[ \Pr[S_0] - \Pr[S_1] = \Adv{ind-cca}{\proto{kem}}(\hat{A}) + \le \InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + \] + as claimed. + + Finally, we can bound $S_1$ explicitly in $\G1$: + \begin{equation} + \label{eq:gwd-sec-s1} + \Pr[S_1] \le + \frac{1}{2} \InSec{ind-cca}(\proto{se}; t, 1 + q_R, q_D + q_R) + + \frac{1}{2} + \end{equation} + This follows by a simple reduction to the chosen-ciphertext secrecy of + $\proto{se}$: $K^*$ will be known to the IND-CCA game, but not + directly to our adversary. It will generate all of the long-term + asymmetric keys, and run $A$'s \cookie{find} stage, collects the two + plaintext messages, encrypts them (making use of the left-or-right + $\proto{se}$ encryption oracle to find $y^* = E_{K^*}([\sigma^*] \cat + \id{lr}(m_0, m_1))$. The challenge ciphertext is passed to $A$'s + \cookie{guess} stage, which will eventually output a guess~$b'$; our + adversary outputs this guess. + + The decryption oracle is simulated as follows. Let $(u, y)$ be the + chosen-ciphertext query. If $u \ne u^*$ then we decrypt $y$ by recovering + $K \cat \tau = \mathcal{D}_y(u)$ as usual; otherwise we must have $y \ne + y^*$ so $y$ is a legitimate query to the symmetric decryption oracle, so we + recover $\hat{m} = D_{K^*}(y)$ and continue from there. + + The recipient-simulation oracle is simulated as follows. Let $(Z, c, m)$ + be the simulation query. If $u \ne u^*$ then we use the KEM as usual. If + $y \ne y^*$ then we can recover the signature using our symmetric + decryption oracle; otherwise, we already know that the signature is + $\sigma^*$. In either case, we construct the new plaintext and invoke the + symmetric encryption oracle to do the encryption, using the same message as + both the left and right inputs to the oracle. + + This is a valid adversary, and runs in the stated resource bounds; we apply + \xref{lem:advantage} and the claim follows. + + We can bound the advantage of adversary~$A$ by combining + equations~\ref{eq:gwd-sec-s0}--\ref{eq:gwd-sec-s1}: + \begin{eqnarray*}[rl] + \Adv{ind-occa}{\Pi}(A) + & = 2\Pr[S_0] - 1 \\ + & \le 2 \, \InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + + \InSec{ind-cca}(\proto{se}; t, 1 + q_R, q_D + q_R) + \end{eqnarray*} + completing the proof. +\end{proof} + +\begin{proof}[Proof of \xref{th:gwd-authenticity}] + We use a sequence of games again. + + Let $A$ be any adversary attacking the outsider authenticity of $\Pi$ and + running within the specified resource bounds. It will suffice to bound + $A$'s advantage. + + Game~$\G0$ is precisely $\Game{uf-ocma}{\Pi}(A)$. We let $S_0$ be the + event that $A$ outputs a valid forgery, i.e., + \begin{equation} + \label{eq:gwd-auth-s0} + \Adv{uf-ocma}{\Pi}(A) = \Pr[S_0] + \end{equation} + As before, in each subsequent game~$\G{i}$ we let $S_i$ be the + corresponding event. The two key pairs will be $((x, x'), (X, X'))$ and + $((y, y'), (Y, Y'))$. For each $0 \le i < q_E$, we define $m_i$ to be the + message in $A$'s $i$th encryption-oracle query and $(P, P_i)$ as the + corresponding public key; and we set $(Z_i, u_i) \gets \mathcal{E}_{P_i}()$ + to be the KEM output while responding to that query, with $K_i \cat \tau_i + = Z_i$, $\sigma_i = S_{x'}([\tau_i, Q_i])$, and $y_i \gets E_{K_i}(m_i)$. + For each $0 \le j < q_D$, let $(Q^*_j, u^*_j, y^*_j)$ be the adversary's + $j$th decryption query, and define $Z^*_j = \mathcal{D}_y(u^*_j)$, $K^*_j = + Z^*_i[0 \bitsto \kappa]$, $\tau^*_j = Z^*_j[\kappa \bitsto \lambda]$, and + $[\sigma^*_j] \cat m^*_j = \hat{m}^*_j = D_{K^*_j}(y^*_j)$, insofar as such + quantities are well-defined. For each $0 \le j < q_R$, let $(\hat{Q}_j, + \hat{u}_j, \hat{y}_j, \hat{m}_j)$ be the adversary's $j$th + recipient-simulation query, and define $\hat{Z}_j$, etc.\@ accordingly; let + $\hat{y}'_j = E_{\hat{K}_j}([\hat{\sigma}_j] \cat \hat{m}_j)$ be the + symmetric ciphertext in the simulator oracle's output. + + Game~$\G1$ is the same as~$\G0$, except that the encryption oracle + generates random keys $Z_i \inr \Bin^\lambda$ if $Q_i = Y$ rather than + using the keys output by the key encapsulation algorithm. The clue~$u_i$ + returned is valid; but the key $K_i$ used for the symmetric encryption, and + the tag~$\tau_i$ signed by the signature algorithm, are random and + independent of the clue. We also modify the decryption oracle: if $Q^*_j = + X$, and $u^*_j = u_i$ matches a clue returned by the encryption oracle with + $Q_i = Y$, then the decryption oracle sets $Z^*_j = Z_i$ rather than using + the decapsulation algorithm. We claim that + \begin{equation} + \label{eq:gwd-auth-g1} + \Pr[S_0] - \Pr[S_1] \le + q_E \InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + \end{equation} + For this we use a hybrid argument: for $0 \le i \le q_E$ we define + game~$\G[H]{i}$ to use random keys to generate $Z_\kappa$ for $0 \le \kappa + < i$ and to use the `proper' encapsulation algorithm for the remaining $q_E + - i$ queries; let $T_i$ be the event that the adversary returns a valid + forgery in~$\G[H]{i}$. Then + \[ \G[H]{0} \equiv \G0 \qquad \textrm{and} \qquad \G[H]{q_E} \equiv \G1 \] + but a simple reduction argument shows that, for $0 \le i < q_E$, + \[ \Pr[T_i] - \Pr[T_{i+1}] \le + \InSec{ind-cca}(\proto{kem}; t, q_D + q_R) + \] + We construct an adversary~$\hat{A}$ attacking the KEM's secrecy by + simulating one of a pair of hybrid games. Let $\hat{A}$'s input be + $\hat{Z}, \hat{u}$. The KEM adversary proceeds by answering the first~$i$ + encryption queries using random keys, using $Z_i = \hat{Z}$ for query $i$, + and the key encapsulation algorithm for the remaining $q_E - i - 1$ + queries. A decryption query can be answered by using the key decapsulation + oracle if $u^*_j \ne u_\kappa$ for all $u_\kappa$ queried so far, or by + setting $Z^*_j = Z_\kappa$ directly otherwise; clearly if $\kappa = i$ then + $Z^*_j = Z_i = \hat{Z}$; a recipient-simulator query is answered similarly. + If $\hat{Z}$ is a real KEM output then we have simulated $\G[H]{i}$; + otherwise we have simulated~$\G[H]{i+1}$. The claim follows since + \begin{eqnarray*}[rl] + \Pr[S_0] - \Pr[S_1] + & = \Pr[T_0] - \Pr[T_{q_E}] \\ + & = \sum_{0\le i = stealth +} + +\begin{document} + + \begin{tikzpicture}[node distance = 5mm] + \node[box = yellow!20, minimum width = 30mm] (m) {$m$}; + \node[op = red!20, below = of m] (enc) {$E$} + edge[<-] (m); + \coordinate[below = of enc] (p); + \node[box = red!20, minimum width = 30mm + 15pt, below = of enc] + (c) {$c$} + edge[<-] (enc); + \node[box = green!20, right = -0.6pt of c] (sig) {$\sigma$}; + \node[box = blue!20, left = -0.6pt of c] (u) {$u$}; + \node[op = green!20, above = 10mm] at (sig |- m) (s) {$S$} + edge[->] (sig); + \node[above = of s] {$a'$} edge[->] (s); + \draw[->] (s |- enc) -- (enc); + \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) edge[->] (s); + \node[box = green!20, left = of t2] (tag) {$\tau$} edge[->] (t2); + \node[box = red!20, left = -0.6pt of tag] (k) {$K$}; + \draw[rounded, ->] (k) |- (enc); + \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); + \draw[rounded, ->] (kem) -| +(-10mm, -8mm) |- (u); + \node at (kem -| b2) {$B$} edge[->] (kem) edge[->] (b2); + \end{tikzpicture} + +\end{document} diff --git a/judge.png b/judge.png new file mode 100644 index 0000000..7b03e38 Binary files /dev/null and b/judge.png differ diff --git a/pre-complication.tex b/pre-complication.tex new file mode 100644 index 0000000..57edb57 --- /dev/null +++ b/pre-complication.tex @@ -0,0 +1,2548 @@ +%%% Deniably authenticated asymmetric encryption +%%% +%%% Copyright (c) 2010 Mark Wooding +%%% Licence: CC-BY + +\documentclass{strayman} + +\usepackage[T1]{fontenc} +\usepackage[utf8]{inputenc} +\usepackage[palatino, helvetica, courier, maths = cmr]{mdwfonts} +\usepackage{mdwtab, mathenv, mdwmath, crypto, mdwref, mdwlist} +\usepackage[mdwmargin]{mdwthm} +\usepackage{tikz} + +\usetikzlibrary{fit,positioning,calc} + +\numberwithin{theorem}{subsection} +\numberwithin{equation}{subsection} +\numberwithin{figure}{subsection} + +\title{Deniably authenticated public-key encryption} +\author{Mark Wooding} + +\def\Bin{\Sigma} +\def\random{\$} +\def\bitsto{\mathop{..}} +\let\emptystring\varepsilon +\let\emptyset\varnothing +\def\textnm#1{\text{\/\normalfont#1\/}} + +\def\fixme{\marginpar{FIXME}} +\def\cn{\fixme\textsuperscript{[\textcolor{blue}{citation needed}]}} + +\bibliographystyle{mdwalpha} + +\begin{document} + +\maketitle + +\begin{abstract} + We consider the notion of \emph{deniably authenticated asymmetric + encryption}: briefly, Bob can encrypt a message and send the ciphertext + to Alice; Alice (and nobody else other than maybe Bob) can decrypt the + message; Alice is convinced that Bob actually sent the message; and nobody + can prove this to anyone else. + + We present formal definitions of security for this new notion, and offer + two efficient instantiations. One is a generic construction, using any + key-encapsulation mechanism, signature scheme, and symmetric authenticated + encryption scheme, but it meets a relatively weak notion of deniability; + the other has security based on the computational Diffie--Hellman problem + and provides strong deniability, but the security is only proven in the + random oracle model. +\end{abstract} + +\newpage +\tableofcontents +\newpage + +%%%-------------------------------------------------------------------------- +\section{Introduction} +\label{sec:intro} + +\subsection{Authenticated asymmetric encryption} +\label{sec:intro.aae} + +Secure email protocols, such as PGP +\cite{Zimmermann:1995:PSC,rfc1991,rfc2440,rfc4880} and S/MIME +\cite{rfc2311,rfc2633,rfc3851} attempt to provide both \emph{secrecy} for the +messages they handle, and \emph{authenticity}. The former property, +informally, means that Bob can send a message to Alice and be confident that +nobody else can read it. The latter means that Alice can be confident that +the message was really sent by Bob. + +This is commonly achieved by a generic sign-then-encrypt construction: the +message plaintext is signed using a standalone digital-signature algorithm +with the sender's private key, and then the message and its signature +together are encrypted with the recipient's public key +\[ y = E_A([m, S_b(m)]) \] +This construction, among others, is analysed by An, Dodis, and Rabin +\cite{An:2002:SJS,cryptoeprint:2002:046} and shown to provide formally +defined notions of secrecy and authenticity. + +As noticed by Davis \cite{Davis:2001:DSE}, the sign-then-encrypt approach has +some surprising failure modes. For example, Alice can re-encrypt the signed +message using, say, Carol's public key, and sent it on: +\[ y' = E_C([m, S_b(m)]) \] +this can obviously cause confusion if the message doesn't encode the identity +of the intended recipient. But there are worse possibilities. For example, +if Alice and Bob are having an affair, each signed-and-encrypted +\emph{billet-doux} becomes potential blackmail material: Alice might threaten +to publish the +\[ m, S_b(m) \] +if her demands aren't met. If Alice is a journalist and Bob is a source, +leaking secrets to her, then the signed leaks are incriminating evidence. + +The encrypt-then-sign construction makes this sort of `attack' less trivial, +but still possible. The signature is applied to a ciphertext encrypted using +Alice's public key, so an \emph{unaided} third party should be unable to +verify that the ciphertext matches any particular claimed plaintext. But +there will usually be some additional information that Alice can publish to +show the correlation. For hybrid schemes, where an asymmetric encryption +scheme is used to transfer a symmetric key, publishing the symmetric key is +usually sufficient. In the case of asymmetric schemes based on trapdoor +permutations (e.g., RSA \cite{Rivest:1978:MOD}) she can publish the preimage +of the ciphertext. In the case of schemes based on Diffie--Hellman key +agreement (e.g., ElGamal's scheme \cite{ElGamal:1985:PKCb} or DLIES +\cite{cryptoeprint:1999:007,Abdalla:2001:DHIES,IEEE:2000:1363}) even +verifying the shared secret may be hard for third parties (this is the +decisional Diffie--Hellman problem), but Alice can additionally publish a +noninteractive zero-knowledge proof that the shared secret is +correct.\footnote{% + We'll work in a group $(G, +)$ with $p = \#G$ prime and generated by $P$. + Let $a \inr \gf{p}$ be Alice's private key, with $A = a P$. For ElGamal, + Bob encodes his message as $M \in G$, chooses $r \inr \gf{p}$, computes $R + = r P$ and $Z = r A$, and sends $(R, Z + M)$ as his ciphertext. Alice can + publish $Z$, but must prove that $Z = a R$. We assume a random oracle + $H\colon G^2 \to \gf{p}$. She chooses $u \inr \gf{p}$, computes $c = H(u + P, u R)$ and $v = u - c a$, and publishes $(Z, c, v)$. To verify, check + that $H(v P + c A, v R + c Z) = c$. Completeness is immediate; soundness + holds by rewinding and mutating the random oracle -- one obtains a new $c'$ + and $v'$ for the same $u$, and can solve for $a$; and the simulator fixes + up the random oracle after choosing $v$ at random. The structure of this + proof follows \cite{Maurer:2009:UZK}.} % + +Similarly, `signcryption' schemes \cite{Zheng:1997:DSH} usually provide a +`non-repudiation' property. \fixme + +With this in mind, it seems a shame that most work on asymmetric +authentication concentrates on \emph{non-repudiation} -- ensuring that Bob's +signature (or equivalent) can be demonstrated to third parties, even without +Bob's later cooperation -- or even despite his opposition. + +\subsection{Related work} +\label{sec:intro.related} + +Dolev, Dwork, and Naor's work \cite{Dolev:1991:NC} on nonmalleable +cryptography defines a simple asymmetric authentication protocol. If $m$ is +some message that Bob wants Alice to authenticate, he chooses a random string +$\rho$, and sends her $(m, \rho)$ encrypted using a nonmalleable encryption +scheme under Alice's public key. To authenticate the message~$m$, Alice +replies with $\rho$. The authors prove their protocol's security, on the +assumption that the encryption is nonmalleable, and comment without proof on +the `plausible deniability' that it offers. + +Dwork, Naor, and Sahai \cite{cryptoeprint:1999:023} address deniability in +the context of concurrent zero-knowledge interactive proofs. They improve +the \cite{Dolev:1991:NC} protocol, showing that the new version is deniable +under \emph{sequential} composition. They also \fixme +%%% read this and finish description + +Di~Raimondo and Gennaro \cite{Raimondo:2005:NAD} \fixme +%%% ought to actually read this + +There is an active literature on the topic of deniably authenticated key +exchange, where the participants are confident that they are communicating +securely with each other, but are unable to prove this to a third party. +Di~Raimondo, Gennaro, and Krawczyk \cite{cryptoeprint:2006:280} define +deniably authenticated key exchange and prove deniability properties of some +IPSEC subprotocols. + +The \emph{Off the Record} protocol for instant-messaging systems +\cite{Borisov:2004:OTR,Alexander:2007:IUA} provides strong deniability for +users, for example by publishing authentication keys at the ends of +conversations. The Wrestlers key-exchange protocol +\cite{cryptoeprint:2006:386} provides strong deniability, and has been +implemented as part of a virtual private network system +\cite{Wooding:2001:TrIPE}. + +Other related concepts include \emph{chameleon signatures} and \emph{ring + signatures}. A chameleon signature \cite{cryptoeprint:1998:010} allows a +designated recipient to satisfy himself as to the origin of a message, and to +create forgeries -- so the recipient is unable to convince third parties that +a message is authentic; however, the sender is able to prove a forgery, and a +failure to provide such proof may be considered an admission of authenticity. +(We shall discuss chameleon signatures further in \ref{sec:deny.weak}.) A +ring signature\cn\ allows a sender to `hide' among a set of users -- without +their participation -- and sign a message in such a way as to convince a +recipient that some member of the set signed it, but with no way to determine +which. (This differs from the group signatures of \cite{Chaum:1991:GS} in +two respects: firstly, the participants in a group signature scheme are +explicitly enrolled into it; and secondly, a group signature scheme includes +an authority who can reveal the individual participant who signed a +particular message.) + +All of the deniable protocols described above are fundamentally +\emph{interactive}, and therefore unsuitable for use in an encryption scheme. +On the other hand, we have an advantage over the designers of plain deniable +authentication protocols, since we can assume that both the sender \emph{and} +the recipient have public keys. This can be seen to be essential in a +non-interactive scheme as follows. If an authentication scheme doesn't +somehow identify a specific recipient (or set of recipients) then either +everyone can verify authenticity or nobody can. In the latter case, the +scheme is useless; in the former, it is undeniable. An interactive protocol +can identify the recipient implicitly through the interaction. A +non-interactive scheme doesn't have this luxury; the only means remaining is +to assume that the recipient knows something -- i.e., a private key. + +\fixme Naccache \cite{Naccache:2010:ITC} asked +\begin{quote} + Construct a non-interactive authenticated PKE scheme: + \begin{itemize} + \item Alice encrypts a message for Bob and mixes with it a secret. + \item Bob can ascertain that the message cam from Alice. + \item Bob cannot convey this conviction to anybody. + \end{itemize} +\end{quote} + +\subsection{Our contribution} +\label{sec:intro.contribution} + +We provide formal definitions for deniably authenticated asymmetric +encryption. We give a `strong' definition, which allows a sender to deny +convincingly ever having communicated with a recipient, and a `weak' +definition, where it may be possible to prove the fact of communication, but +not the contents. (This latter definition turns out to be rather +complicated.) + +We also describe simple and efficient schemes which meet these definitions of +security. Our weakly deniable scheme is generic: it uses an asymmetric key +encapsulation mechanism, a digital signature scheme, and an authenticated +symmetric encryption scheme: security is proven in the standard model. We +show that Diffie--Hellman key distribution \cite{Diffie:1976:NDC} is a basis +for a strongly deniable authenticated encryption scheme. We describe such a +scheme and prove security, assuming the difficulty of the computational +Diffie--Hellman problem, in the random oracle model. + +%%%-------------------------------------------------------------------------- +\section{Preliminaries} +\label{sec:pre} + +%% Key encapsulation ROR-CCA +%% IND-CCA for symmetric encryption +%% Asymmetric authenticated encryption -- outsider IND and UF +%% Timing of adversaries includes oracles and loading +%% Pseudorandom generator? (Could just assume bigger KEM output) +%% Digital signatures EUF-CMA. + +\subsection{Binary strings and encodings} +\label{sec:bin} + +We write $\Bin = \{ 0, 1 \}$ as the set of binary digits; $\Bin^t$ is the set +of $t$-bit strings, and $\Bin^* = \bigcup_{0\le i} \Bin^i$ is the set of all +binary strings. We write $\emptystring$ for the empty string. If $m$ is a +binary string then $|m|$ is the length of $m$; so $m \in \Bin^{|m|}$, and +$|\emptystring| = 0$. If $0 \le i < |m|$ then $m[i]$ is the $i$th bit of +$m$. If $m$ and $n$ are two strings then $m \cat n$ is their concatenation; +we have $|m \cat n| = |m| + |n|$; $m \cat \emptystring = \emptystring \cat m += m$; and $(m \cat n)[i] = m[i]$ if $i < |m|$ and $n[i - |m|]$ otherwise. If +$0 \le i \le j \le |m|$ then $m[i \bitsto j]$ is the substring starting with +bit~$i$ and ending before bit~$j$ -- so $|m[i \bitsto j]| = j - i$, $m[i +\bitsto j][k] = m[i + k]$, and $m = m[0 \bitsto i] \cat m[i \bitsto j] \cat +m[j \bitsto |m|]$. + +We shall assume the existence of a deterministic, unambiguous encoding of +integers, group elements, and other such objects, as bit strings. Rather +than build a complicated formalism, we shall simply write $[a, b, c, \ldots]$ +as the encoding of items $a$, $b$, $c$, \dots If $n$ is an integer with $0 +\le n < 2^k$ then $[n]_k$ is a $k$-bit encoding of $n$. + +We assume the existence of a distinguished object~$\bot$ (pronounced +`bottom'), and a set of \emph{atomic symbols}, written in +\cookie{sans-serif}, whose purpose is simply to be distinct from all other +objects. + +\subsection{Algorithms, oracles, and resource bounds} +\label{sec:alg} + +We present algorithms using a fairly standard imperative notation. We write +$x \gets \tau$ to mean that variable~$x$ is to be assigned the value of the +term~$\tau$. If $S$ is a set, then $x \getsr S$ means that $x$ is to be +assigned an element of $S$ chosen uniformly and independently at random. +Variables are globally scoped. Indentation is used to indicate the extent of +iterated and conditional fragments. + +We make frequent use of implicit `destructuring' (or `pattern matching') in +algorithm descriptions: a tuple (in parentheses, as is conventional) or +encoded sequence (in square brackets) containing variables may appear on the +left of an assignment, or as a formal argument to a procedure, indicating +that the corresponding right-hand-side or actual argument is to be decoded +and split up according to the structure of the pattern + +Oracles provided to algorithms are written as superscripts; the inputs +supplied in an oracle query are written as `$\cdot$'. + +We work throughout in the tradition of concrete security, as initiated in +\cite{Bellare:1994:SCB}. We consider adversaries operating under explicit +resource bounds of time and numbers of oracle queries, and provide explicit +bounds on their success probabilities and advantages. We find that this +approach both simplifies presentation -- since we no longer have to deal with +families of objects indexed by security parameters or other artificial +features of the asymptotic approach -- and provides more practically useful +results. (As an aside, we remark that, \cite{Goldreich:1997:FMCa} +notwithstanding, it's much easier to derive asymptotic results from concrete +ones than \emph{vice versa}.) + +We make use of the random oracle model, as formalized in +\cite{Bellare:1993:ROP}. Rather than give separate definitions for security +with random oracles, we shall quietly include a bound $q_H$ on an adversary's +random oracle queries when attacking a scheme which uses random oracles. + +The model of computation used to measure running times is not specified -- or +especially important to our results. We do note, however, that running times +\emph{include} the time taken by the `game' infrastructure, including any +time needed for oracles to compute their results. In order to take into +account algorithms which make use of precomputed tables, we also include in +the running time a term proportional to the size of the algorithm's +description according to the (unspecified) computational model. + +\subsection{Useful results} +\label{sec:handy} + +The following lemma will be used in our security proofs. + +\begin{lemma}[Difference lemma \cite{Shoup:2002:OR}] + \label{lem:shoup} + Let $S$, $T$, and $F$ be events such that + \[ \Pr[S \mid \bar{F}] = \Pr[T \mid \bar{F}] \] + Then + \[ \Pr[S] - \Pr[T] \le \Pr[F] \] +\end{lemma} +\begin{proof} + A simple calculation: + \begin{eqnarray*}[rl] + \Pr[S] - \Pr[T] + & = (\Pr[S \land F] + \Pr[S \land \bar{F}]) - + (\Pr[T \land F] + \Pr[T \land \bar{F}]) \\ + & = (\Pr[S \land F] - \Pr[T \land F]) + + \Pr[\bar{F}] (\Pr[S \mid \bar{F}] - \Pr[T \mid \bar{F}]) \\ + & \le \Pr[F] \eqnumber[\qed] + \end{eqnarray*} +\end{proof} + +%%%-------------------------------------------------------------------------- +\section{Definitions} +\label{sec:defs} + +This section presents our formal definitions for the structure and security +properties of the cryptographic objects we'll be dealing with in the paper. +Most of the definitions are fairly standard; the only slightly unusual aspect +is that we deal with \emph{concrete} security, with explicit resource and +probability bounds, rather than asymptotic notions. Therefore we don't need +to mention an explicit security parameter or deal with ensembles of +probability distributions. + +We strongly prefer the concrete security treatment. Asymptotic results +follow as trivial corollaries of our main results; but deriving concrete +security definitions and results from asymptotic statements is decidedly +nontrivial. + +\subsection{Diffie--Hellman problems} +\label{sec:dh} + +Throughout this section, let $(G, +)$ be a (necessarily cyclic) group of +prime order, written additively; let $p = \#G$ be its order, and let $P$ be a +generator of $G$. In order to simplify notation, we shall think of $G$ as +being a $\gf{p}$-vector space; group elements (vectors) will be given +uppercase letters, while elements of $\gf{p}$ (scalars) will be given +lowercase letters. + +The computational Diffie--Hellman problem in $G$ is to determine $x y P$ +given only $x P$ and $y P$. The problem is named after the authors of +\cite{Diffie:1976:NDC}, whose key distribution scheme relies on the +difficulty of this problem in the group $\gf{p}^*$ of units in a prime finite +field. + +More formally, we use the following definition. + +\begin{definition}[Computational Diffie--Hellman] + \label{def:cdh} + + If $A$ is any algorithm, then its \emph{advantage} in solving the + computational Diffie--Hellman problem (CDH) in $G$ is given by + \[ \Adv{cdh}{G}(A) = + \Pr[\textrm{$x \getsr \gf{p}$; $y \getsr \gf{p}$} : + A(x P, y P) = x y P] + \] + The CDH insecurity function of $G$ is then + \[ \InSec{cdh}(G; t) = \max_A \Adv{cdh}{G}(A) \] + where the maximum is taken over all algorithms~$A$ completing the game in + time~$t$. +\end{definition} + +We shall also make use of the \emph{twin Diffie--Hellman} problem +\cite{cryptoeprint:2008:067}: given $x P$, $x' P$ and $y P$, to find $x y P$ +and $x' y P$, given an oracle which can decide, given $(U, V, V')$, whether +$V = x U$ and $V' = x' U$. + +\begin{definition}[Twin Diffie--Hellman] + \label{def:2dh} + + An algorithm $A$'s ability to solve the twin Diffie--Hellman problem in a + group~$G$ is measured using the following game. + \begin{program} + $\Game{2dh}{G}(A)$: \+ \\ + $x \getsr \gf{p}$; + $x' \getsr \gf{p}$; + $y \getsr \gf{p}$; \\ + $(Z, Z') \gets A^{\id{2dhp}(\cdot, \cdot, \cdot)}(x P, x' P, y P)$; \\ + \IF $Z = x y P \land Z' = x' y P$ \THEN \RETURN $1$ \ELSE \RETURN $0$; + \- \\[\medskipamount] + $\id{2dhp}(U, V, V')$: \+ \\ + \IF $V = x U \land V' = x' U$ \THEN \RETURN $1$ \ELSE \RETURN $0$; + \end{program} + If $A$ is any algorithm, then its \emph{advantage} in solving the twin + Diffie--Hellman problem (2DH) in $G$ is given by + \[ \Adv{2dh}{G}(A) = \Pr[\Game{2dh}{G}(A) = 1] \] + Finally, the 2DH insecurity function of ~$H$ is given by + \[ \InSec{2dh}(G; t, q) = \max_A \Adv{2dh}{G}(A) \] + where the maximum is taken over all algorithms~$A$ completing the game in + time~$t$ and making at most~$q$ queries to the \id{2dhp} oracle. +\end{definition} + +This all seems rather artificial; but \cite{cryptoeprint:2008:067} relates +2DH security tightly to plain CDH security. The main trick is as follows. +\begin{lemma}[Detecting 2DH triples] + \label{lem:2dh-detect} + + Let $G$ be a cyclic group generated by~$P$, with prime order $p = \#G$. + Let $X \in G$ be any group element; let $r$ and $s$ be any elements of + $\gf{p}$, and set $X' = r P + s X$. If $Y = y P$ for some $y \in \gf{p}$, + and $Z$, $Z'$ are two further group elements, then + \begin{enumerate} + \item if $Z = y X$, then and $Z' = y X'$ if and only if $Z' = r Y + s Z$; + and, conversely, + \item if $Z \ne y X$ then there is precisely one possible value of $s$ for + which $Z' = y Y + s Z$. + \end{enumerate} +\end{lemma} +\begin{proof} + For the first statement, suppose that $Z = y X$; then $y X' = y (r P + s X) + = r (y P) + s (y X) = r Y + s Z$. For the second, suppose now that $Z \ne + y X$, but + \[ Z' = r Y + s Z \] + holds anyway. We already have $X' = r P + s X$, so + \[ y X' = r Y + s y X \] + Subtracting the latter equation from the former gives + \[ Z' - y X' = s (Z - y X) \] + Since $Z - y X \ne 0$, it generates $G$; hence there is a single satisfying + $s \in \gf{p}$ as claimed. +\end{proof} + +\begin{theorem}[$\textrm{CDH} \Leftrightarrow \textrm{2DH}$] + \label{th:cdh-2dh} + + Let $G$ be a cyclic group with prime order; then + \[ \InSec{cdh}(G; t) \le + \InSec{2dh}(G; t, q) \le + \InSec{cdh}(G; t + t') + \frac{q}{\#G} \] + where $t'$ is the time taken to perform two scalar multiplications and an + addition in $G$. +\end{theorem} +\begin{proof} + The first inequality is obvious. For the second, suppose that $A$ is any + algorithm for solving 2DH in~$G$. Let $p = \#G$. We define algorithm~$B$ + as follows. + \begin{program} + $B(X, Y)$: \+ \\ + $r \getsr \gf{p}$; + $s \getsr \gf{p}$; + $X' \gets r P + s X$; \\ + $(Z, Z') \gets A^{\id{2dhp}'(\cdot, \cdot, \cdot)}(X, X', Y)$; \\ + \IF $\id{2dhp}'(Y, Z, Z') = 1$ \THEN \RETURN $Z$ \ELSE \RETURN $\bot$; + \- \\[\medskipamount] + $\id{2dhp}'(U, V, V')$: \+ \\ + \IF $V' = r U + s V$ \THEN \RETURN $1$ \ELSE \RETURN $0$; + \end{program} + If $A$ runs in time $t$, then $B$ runs in time~$t + t'$ as stated: while + $\id{2dhp}'$ works differently from $\id{2dhp}$, the simultaneous + multiplication in the former can be done more efficiently than the two + separate multiplications in the latter; so the only overhead is in the + additional setup. + + We have $r$ uniform on $\gf{p}$ and independent of $s$, so $\Pr[X' = A] = + \Pr[r P = A - s X] = 1/p$ for any constant~$A$, so $X'$ is uniform on $G$ + and independent of~$s$. By \xref{lem:2dh-detect}, there are at most $q$ + values of $s$ which would cause $\id{2dhp}'$ to give an incorrect answer. + The theorem follows. +\end{proof} + +\subsection{Symmetric encryption} +\label{sec:se} + +We shall require a symmetric encryption scheme; the syntax of such schemes is +straightforward. The only slightly unusual feature of our definition is that +we require the key space to be a set of binary strings of a given length: +this will be important in what follows. + +\begin{definition}[Symmetric encryption syntax] + \label{def:se-syntax} + + A \emph{symmetric encryption scheme} is a triple $\Pi_\textnm{se} = (k, E, + D)$, where $k \ge 0$ is a nonnegative integer, and $E$ and $D$ are (maybe + randomized) algorithms, as follows. + \begin{itemize} + \item The \emph{encryption algorithm}~$E$ accepts a key $K \in \Bin^k$ and + a message $m \in \Bin^*$, and outputs a ciphertext $c \gets E_K(m)$. + \item The \emph{decryption algorithm}~$D$ accepts a key $K \in \Bin^k$ and + a ciphertext $c$, and outputs $m = D_K(c)$ which is either a message $m + \in \Bin^*$ or the distinguished symbol~$\bot$. This decryption + algorithm must be such that, for all $K \in \Bin^*$, and all messages $m + \in \Bin^*$, if $c$ is any output of $E_K(m)$ then $D_K(c)$ outputs + $m$. \qed + \end{itemize} +\end{definition} + +We define two security notions for symmetric encryption. + +Our notion of secrecy is \emph{indistinguishability under chosen-ciphertext + attack} (IND-CCA). We choose a random key~$K$ for the symmetric encryption +scheme and provide the adversary with two oracles: an encryption oracle which +accepts two messages $m_0$ and $m_1$ of the same length, consistently chooses +either $m_0$ or $m_1$, encrypts it using the key~$K$, and returns the +resulting ciphertext $y = E_K(m_b)$; and a decryption oracle which accepts a +ciphertext and returns the corresponding plaintext or an indication that the +ciphertext was malformed. The scheme is considered secure if no adversary +playing this game can determine whether the encryption oracle is encrypting +$m_0$ or $m_1$. Since the game would be trivial if the adversary could ask +for decryption of ciphertexts returned by the encryption oracle, we forbid +(only) this. + +Our notion of authenticity is \emph{integrity of ciphertexts} (INT-CTXT). +We choose a random key~$K$, and provide the adversary with two oracles: an +encryption oracle which encrypts a message provided as input and returns the +resulting ciphertext; and a decryption oracle which decrypts the ciphertext +provided as input and returns the plaintext or an indication that the +ciphertext was invalid. The scheme is considered security if no adversary +playing this game can query its decryption oracle on a valid ciphertext which +wasn't returned by the encryption oracle. + +These notions are standard; we take them from +\cite{Bellare:2000:AER,cryptoeprint:2000:025}. Rogaway +\cite{cryptoeprint:2006:221} presents a rather more convenient definition +which combines both secrecy and authenticity into a single notion; this +definition is stronger than we need because it requires that ciphertexts be +indistinguishable from random data, rather than merely other ciphertexts. + +\begin{definition}[Symmetric encryption security] + \label{def:se-security} + + Let $\Pi = (k, E, D)$ be a symmetric encryption scheme. An adversary~$A$'s + ability to attack the security of $\Pi$ is measured using the following + games. + + \begin{program} + $\Game{ind-cca-$b$}{\Pi}(A)$: \+ \\ + $K \getsr \Bin^k$; \\ + $b' \gets A^{E_K(\id{lr}(\cdot, \cdot)), D_K(\cdot)}$; \\ + \RETURN $b'$; + \next + $\id{lr}(m_0, m_1)$: \+ \\ + \RETURN $m_b$; + \newline + $\Game{int-ctxt}{\Pi}(A)$: \+ \\ + $K \getsr \Bin^k$; \\ + $Y \gets \emptyset$; $w \gets 0$; \\ + $A^{\id{encrypt}(\cdot), \id{decrypt}(\cdot)}$; \\ + \RETURN $w$; \- + \next + $\id{encrypt}(m)$: \+ \\ + $y \gets E_K(m)$; \\ + $Y \gets Y \cup \{ y \}$; \\ + \RETURN $y$; \- + \next + $\id{decrypt}(y)$: \+ \\ + $m \gets D_K(y)$; \\ + \IF $m \ne \bot \land y \notin Y$ \THEN $w \gets 1$; \\ + \RETURN $m$; \- + \end{program} + + In the IND-CCA games, we require that the two messages $m_0$ and $m_1$ + passed to the encryption oracle have the same length, and that the + adversary not query its decryption oracle on any ciphertext produced by the + encryption oracle. + + The adversary's \emph{advantage} in these games is defined as follows. + \begin{eqnarray*}[c] + \Adv{ind-cca}{\Pi}(A) = + \Pr[\Game{ind-cca-$1$}{\Pi}(A) = 1] - + \Pr[\Game{ind-cca-$0$}{\Pi}(A) = 1] + \\[\medskipamount] + \Adv{int-ctxt}{\Pi}(A) = + \Pr[\Game{int-ctxt}{\Pi}(A) = 1] + \end{eqnarray*} + + Finally, the IND-CCA and INT-CTXT insecurity functions of $\Pi$ are given + by + \begin{eqnarray*}[c] + \InSec{ind-cca}(\Pi; t, q_E, q_D) = \max_A \Adv{ind-cca}{\Pi}(A) + \\[\medskipamount] + \InSec{int-ctxt}(\Pi; t, q_E, q_D) = \max_A \Adv{int-ctxt}{\Pi}(A) + \end{eqnarray*} + where the maxima are taken over all adversaries~$A$ completing the game in + time~$t$ and making at most $q_E$ and $q_D$ queries to their encryption and + decryption oracles, respectively. +\end{definition} + +In fact, our constructions only require security against a single +chosen-plaintext query in order to achieve the usual notions of +indistinguishability and authenticity (\xref{sec:aae}). However, in order to +prove deniability we shall have need to encrypt additional messages under the +same key, and it would be a shame to lose secrecy or authenticity as a +consequence. + +Symmetric encryption schemes according to this definition can easily be +constructed using a generic `encrypt-then-authenticate' approach using a +symmetric encryption scheme secure against chosen-plaintext attack and a +message authentication code (MAC) secure against `strong' forgery under +chosen-message attack.\footnote{% + Such schemes may fail to meet Rogaway's stronger definition because MAC + tags need not be indistinguishable from random data.} % +Alternatively, there are dedicated schemes based on block ciphers, such as +OCB~\cite{Rogaway:2002:AEA,Rogaway:2001:OCB,cryptoeprint:2001:026}, +CCM~\cite{rfc3610,Dworkin:2003:DRB} (but note \cite{cryptoeprint:2003:070}) +and GCM~\cite{McGrew:2004:SPG}. + +\subsection{Key encapsulation mechanisms} +\label{sec:kem} + +A \emph{key encapsulation mechanism}, or KEM, is an asymmetric cryptographic +scheme for transferring a short random secret (e.g., a symmetric key) to a +recipient. It differs from asymmetric encryption in that the KEM is +responsible for choosing the random string as part of its operation, rather +than having it be an input. This makes efficient constructions simpler and +more efficient, and makes security reductions more efficient (and hence more +meaningful). + +ElGamal's encryption scheme \cite{ElGamal:1985:PKCb} be seen, with copious +hindsight, as consisting of a KEM based on the Diffie--Hellman problem +combined with a symmetric encryption using the same group operation as a +one-time pad. Zheng and Seberry \cite{Zheng:1993:PAA}, inspired by +Damg\aa{}rd's `modified ElGamal' scheme \cite{Damgaard:1991:TPP}, present a +number of constructions (without proofs) of asymmetric encryption schemes +secure against adaptive chosen-ciphertext attacks. The DHIES scheme of +Abdalla, Bellare, and Rogaway +\cite{cryptoeprint:1999:007,Abdalla:2001:DHIES}, standardized in +\cite{IEEE:2000:1363}), uses a hash function to derive a symmetric key from +the Diffie--Hellman shared secret; they prove security against +chosen-ciphertext attack. Finally, Shoup \cite{cryptoeprint:2001:112} +formalizes the notion of a key-encapsulation, and describes one (RSA-KEM, +formerly `Simple RSA') based on the RSA primitive \cite{Rivest:1978:MOD}. + +\begin{definition}[Key encapsulation mechanism syntax] + \label{def:kem-syntax} + + A \emph{key encapsulation mechanism} is a quadruple $\Pi_\textnm{kem} = + (\ell, G, E, D)$ where $\ell \ge 0$ is a non-negative integer, and $G$, $E$ + and $D$ are (maybe randomized) algorithms, as follows. + \begin{itemize} + \item The \emph{key-generation algorithm} $G$ accepts no parameters and + outputs a pair $(x, X) \gets G()$. We call $x$ the \emph{private key} + and $X$ the \emph{public key}. + \item The \emph{encapsulation algorithm} $E$ accepts a public key $X$ and + outputs a pair $(K, u) \gets E_X()$ where $K \in \Bin^\ell$ is a bit + string, and $u$ is a `clue'. + \item The \emph{decapsulation algorithm} $D$ accepts a private key $x$ and + a clue $u$, and outputs $K \gets D_x(u)$ which is either a string $K \in + \Bin^\ell$ or the distinguished symbol $\bot$. The decapsulation + algorithm must be such that if $(x, X)$ is any pair of keys produced by + $G$, and $(K, u)$ is any key/clue pair output by $E_X()$, then $D_x(u)$ + outputs $K$. \qed + \end{itemize} +\end{definition} + +Our notion of security is indistinguishability from random under +chosen-ciphertext attack (IND-CCA). We generate a key pair, and invoke the +encapsulation algorithm on the public key. The adversary is provided with +the resulting KEM clue and an $\ell$-bit string. It may query an oracle +which accepts a clue as input and returns the result of applying the +decapsulation algorithm to it using the private key. The scheme is +considered secure if the adversary cannot determine whether its input string +was the output of the key encapsulation algorithm, or generated uniformly at +random and independently. Since this game can be won easily if the adversary +is permitted query its decapsulation oracle on its input clue, we forbid +(only) this. + +\begin{definition}[Key encapsulation mechanism security] + \label{def:kem-security} + + Let $\Pi = (\ell, G, E, D)$ be a key encapsulation mechanism. We measure + an adversary~$A$'s ability to attack $\Pi$ using the following games. + \begin{program} + $\Game{ind-cca-$b$}{\Pi}(A)$: \+ \\ + $(x, X) \gets G()$; \\ + $K_0 \getsr \Bin^\ell$; \\ + $(K_1, u) \gets E_X()$; \\ + $b' \gets A^{D_x(\cdot)}(K_b, u)$; \\ + \RETURN $b'$; + \end{program} + In these games, the adversary is forbidden from querying its decapsulation + oracle at the challenge clue $u$. + + The adversary's IND-CCA \emph{advantage} is measured by + \[ \Adv{ind-cca}{\Pi}(A) = + \Pr[\Game{ind-cca-$1$}{\Pi}(A) = 1] - + \Pr[\Game{ind-cca-$0$}{\Pi}(A) = 1] + \] + Finally, the IND-CCA insecurity function of $\Pi$ is defined by + \[ \InSec{ind-cca}(\Pi; t, q_D) = \max_A \Adv{ind-cca}{\Pi}(A) \] + where the maximum is taken over all adversaries~$A$ completing the game in + time~$t$ and making at most $q_D$ queries to their decapsulation oracles. +\end{definition} + +\subsection{Digital signatures} +\label{sec:sig} + +Our definition for digital signatures is, more specifically, for signature +schemes with appendix: the signing algorithm produces a signature, +and the verification algorithm requires both the signature and the original +message in order to function. + +\begin{definition}[Digital signature syntax] + \label{def:sig-syntax} + + A \emph{digital signature scheme} is a triple $\Pi_\textnm{sig} = (G, S, + V)$ of (maybe randomized) algorithms, as follows. + \begin{itemize} + \item The \emph{key-generation algorithm} $G$ accepts no parameters and + outputs a pair $(x, X) \gets G()$. We call $x$ the \emph{private key} + and $X$ the \emph{public key}. + \item The \emph{signature algorithm} $S$ accepts a private key~$x$ and a + message~$m \in \Bin^*$, and outputs a signature~$\sigma \gets S_x(m)$. + \item The \emph{verification algorithm} $V$ accepts a public key~$X$, a + message~$m \in \Bin^*$, and a signature~$\sigma$, and outputs a bit $b + \gets V_X(m, \sigma)$ subject to the condition that, if $(x, X)$ is any + key pair output by $G$, $m \in \Bin^*$ is any message, and $\sigma$ is + any signature output by $S_x(m)$, then $V_X(m, \sigma)$ outputs $1$. + \qed + \end{itemize} +\end{definition} + +Our notion of security for digital signatures is \emph{existential + unforgeability under chosen-message attack} (EUF-CMA). It is essentially +that of \cite{Goldwasser:1988:DSS}, modified to measure concrete security. +We provide the adversary with a public key and a signing oracle which signs +input messages using the corresponding private key. The scheme is considered +secure if no adversary can output a valid message/signature pair for a +message distinct from the adversary's signing queries. + +\begin{definition}[Digital signature security] + \label{def:sig-security} + + Let $\Pi = (G, S, V)$ be a digital signature scheme. The \emph{advantage} + of an adversary~$A$'s ability to attack $\Pi$ is given by + \[ \Adv{euf-cma}{\Pi}(A) = \Pr[\textrm{ + $(x, X) \gets G()$; + $(m, \sigma) \gets A^{S_x(\cdot)}$ + } : V_X(m, \sigma) = 1] + \] + where the adversary is forbidden from returning a message~$m$ if it queried + its signing oracle~$S_x(\cdot)$ at $m$. + + The EUF-CMA \emph{insecurity function} of $\Pi$ is given by + \[ \InSec{euf-cma}(\Pi; t, q) = \max_A \Adv{euf-cma}{\Pi}(A) \] + where the maximum is taken over all adversaries~$A$ completing the game in + time~$t$ and issuing at most $q$ signing-oracle queries. +\end{definition} + +This notion is weaker than it might be. A possible strengthening would be to +allow the adversary to return a pair~$(m, \sigma')$ even if it made a signing +query for $m$, as long as the signing oracle didn't return the +signature~$\sigma'$. We shall not require this stronger definition. + +\subsection{Authenticated asymmetric encryption} +\label{sec:aae} + +Our definitions for authenticated asymmetric encryption are based on those of +\cite{Baek:2007:FPS}. + +\begin{definition}[Authenticated asymmetric encryption syntax] + \label{def:aae-syntax} + + An \emph{authenticated asymmetric encryption scheme} is a triple + $\Pi_\textnm{aae} = (G, E, D)$ of (maybe randomized) algorithms, as + follows. + \begin{itemize} + \item The \emph{key-generation algorithm} $G$ accepts no parameters and + outputs a pair $(x, X) \gets G()$. We call $x$ the \emph{private key} + and $X$ the \emph{public key}. + \item The \emph{encryption algorithm} $E$ accepts a private key~$x$, a + public key~$Y$, and a message $m \in \Bin^*$, and outputs a ciphertext $c + \gets E_x(Y, m)$. + \item The \emph{decryption algorithm} $D$ accepts a private key~$x$, a + public key~$Y$ and a ciphertext~$c$, and outputs a result~$m \gets D_x(Y, + c)$ which is either a message $m \in \Bin^*$ or the distinguished + symbol~$\bot$. The decryption algorithm must be such that if $(x, X)$ + and $(y, Y)$ are any two pairs of keys produced by $G$, $m$ is any + message, and $c$ is any output of $E_x(Y, m)$, then $D_y(X, m)$ outputs + $m$. \qed + \end{itemize} +\end{definition} + +Our security notion for secrecy is \emph{indistinguishability under outsider + chosen-ciphertext attack} (IND-OCCA). We generate a key pair each for two +participants, a `sender' and a `recipient'. The adversary is given the two +public keys and provided with two oracles: an encryption oracle, which +accepts a message and a public key, and encrypts the message using the public +key and the sender's private key, returning the resulting ciphertext; and a +decryption oracle, which accepts a ciphertext and a public key, and decrypts +the ciphertext using the recipient's private key and checks it against the +given public key, returning either the resulting plaintext or an indication +that the decryption failed. The adversary runs in two stages: in the first +`find' stage, it chooses two messages $m_0$ and $m_1$ of equal lengths and +returns them; one of these messages is encrypted by the sender using the +recipient's public key. The adversary's second stage is given the resulting +`challenge' ciphertext. The scheme is considered secure if no adversary can +determine which of its messages was encrypted. Since this is trivial if the +adversary queries its decryption oracle with the challenge ciphertext and the +sender's public key, (only) this is forbidden. The resulting game is +precisely \cite{Baek:2007:FPS}'s `FSO/FUO-IND-CCA2', which corresponds to +\cite{An:2002:SJS}'s notion of `multi-user outsider privacy'. A similar +`insider security' notion would provide the adversary with the sender's +private key. We prefer outsider security: the idea that we must prevent +Alice from decrypting the message she just encrypted to send to Bob seems +unnecessary. + +Our security notion for authenticity is \emph{unforgeability under outsider + chosen-message attack} (UF-OCMA). Again, we generate sender and recipient +keys, and the adversary is given the same two oracles. This time, the +adversary's task is to submit to the decryption oracle a ciphertext which it +accepts as being constructed by the sender, but is not equal to any +ciphertext returned by the encryption oracle. This notion is strictly weaker +than \cite{Baek:2007:FPS}'s FSO-UF-CMA, since it corresponds to +\cite{An:2002:SJS,cryptoeprint:2002:046}'s `multi-user outsider +authenticity', whereas FSO-UF-CMA corresponds to `multi-user \emph{insider} +authenticity'. This weakening of security is a necessary consequence of our +deniability requirements: we \emph{want} Alice to be able to forge messages +that appear to be sent to her by Bob: see \xref{sec:deny.insider}. On the +other hand, we allow the adversary to make multiple decryption queries; this +makes a difference to our quantitative results. + +\begin{definition}[Authenticated asymmetric encryption scheme security] + \label{def:aae-security} + + Let $\Pi = (G, E, D)$ be an asymmetric authenticated encryption scheme. An + adversary $A$'s ability to attack the security of $\Pi$ is measured by the + following games. + + \begin{program} + $\Game{ind-occa-$b$}{\Pi}(A)$: \+ \\ + $(x, X) \gets G()$; + $(y, Y) \gets G()$; \\ + $(m_0, m_1, s) \gets + A^{E_x(\cdot, \cdot), D_y(\cdot, \cdot)}(\cookie{find}, X, Y)$; \\ + $c^* \gets E_x(Y, m_b)$; \\ + $b' \gets + A^{E_x(\cdot, \cdot), D_y(\cdot, \cdot)}(\cookie{guess}, c^*, s)$; \\ + \RETURN $b'$; \- + \\[\medskipamount] + $\Game{uf-ocma}{\Pi}(A)$: \+ \\ + $w \gets 0$; + $\mathcal{C} \gets \emptyset$; \\ + $(x, X) \gets G()$; + $(y, Y) \gets G()$; \\ + $A^{\id{enc}(\cdot, \cdot), \id{dec}}(X, Y)$; \\ + \RETURN $w$; \- + \next + $\id{enc}(Z, m)$: \+ \\ + $c \gets E_x(Z, m)$; \\ + \IF $Z = Y$ \THEN $\mathcal{C} \gets \mathcal{C} \cup \{ c \}$; \\ + \RETURN $c$; \- + \\[\medskipamount] + $\id{dec}(Z, c)$: \+ \\ + $m \gets D_y(Z, c)$; \\ + \IF $Z = X \land m \ne \bot \land c \notin \mathcal{C}$ \THEN + $w \gets 1$; \\ + \RETURN $m$; \- + \end{program} + + In the IND-OCCA games $\Game{ind-occa-$b$}{\Pi}$, the adversary is + forbidden from querying its decryption oracle $D_y(\cdot, \cdot)$ on the + pair $(X, c^*)$; in the UF-OCMA game $\Game{uf-ocma}{\Pi}$, the adversary + is forbidden from returning any ciphertext $c$ that it obtained by querying + its encryption oracle~$E_x(\cdot, \cdot)$. + + The adversary's \emph{advantage} in these games is measured as follows. + \begin{eqnarray*}[c] + \Adv{ind-occa}{\Pi}(A) = + \Pr[\Game{ind-occa-$1$}{\Pi}(A) = 1] - + \Pr[\Game{ind-occa-$0$}{\Pi}(A) = 1] + \\[\medskipamount] + \Adv{uf-ocma}{\Pi}(A) = + \Pr[\Game{uf-ocma}{\Pi}(A) = 1] + \end{eqnarray*} + Finally, the IND-CCA and OUF-CMA insecurity functions of $\Pi$ are given by + \begin{eqnarray*}[c] + \InSec{ind-occa}(\Pi; t, q_E, q_D) = \max_A \Adv{ind-occa}{\Pi}(A) + \\[\medskipamount] + \InSec{uf-ocma}(\Pi; t, q_E, q_D) = \max_A \Adv{uf-ocma}{\Pi}(A) + \end{eqnarray*} + where the maxima are taken over all adversaries~$A$ completing the game in + time~$t$ and making at most $q_E$ and $q_D$ queries to their encryption and + decryption oracles, respectively. +\end{definition} + +%%%-------------------------------------------------------------------------- +\section{Defining deniably authenticated encryption} +\label{sec:deny} + +The basic intuition behind deniably authenticated encryption is fairly clear. +If Bob sends a message Alice, then she shouldn't later be able to convince a +third party -- Justin, say -- that Bob actually sent it. Of course, we're +considering encrypted messages, so Alice will have to send something other +than just the message to Justin if he's to be convinced of anything. +(Otherwise Justin is able to compromise the indistinguishability of the +encryption scheme.) + +This intuition seems fairly clear; but, as we shall see, the notion of +deniably authenticated encryption is somewhat slippery to formalize. + +\subsection{An attempt at a formal definition} +\label{sec:deny.first} + +Following our intuition above, we model Justin as an algorithm~$J$ which +receives as input a message~$m$ and ciphertext~$c$, and some other +information, and outputs either~$1$ or $0$ depending on whether it is +convinced that $c$ represents an authentic encryption of $m$ sent from Bob to +Alice. For deniability, we shall require the existence of a \emph{simulator} +which forges ciphertexts sufficiently well that Justin can't distinguish them +from ones that Bob made. The difficult questions concern which inputs we +should give Justin on the one hand, and the simulator on the other. + +The simulator is easier. We must provide at least Bob's public key, in order +to identify him as the `sender'. We must also provide Alice's \emph{private} +key. This initially seems excessive; but a simulator which can forge +messages without Alice's private key exhibits an outsider-authenticity +failure. (We could get around this by providing Bob's private key and +Alice's public key instead, but we already know that Bob can construct +plausible ciphertexts, so this seems uninteresting -- for now.) We should +also give the simulator the `target' message for which it is supposed to +concoct a ciphertext: allowing the simulator to make up the target message +yields a very poor notion of deniability. Finally, we might give the +simulator a \emph{valid} ciphertext from Bob to Alice. Doing this weakens +our deniability, because Bob may no longer be able to deny engaging in any +form of communication with Alice; but this seems a relatively minor +complaint. We therefore end up with two different notions: \emph{strong + deniability}, where the simulator is given only the keys and the target +message; and \emph{weak deniability}, where the simulator is also provided +with a valid ciphertext. + +Now we turn to Justin's inputs. It's clear that if he can say whether a +ciphertext is an encryption of some specified message given only Alice's and +Bob's public keys then he exhibits an outsider-secrecy failure. If Alice is +to prove anything useful about the ciphertext to Justin, then, she must +provide additional information, possibly in the form of a zero-knowledge +proof. We don't need to model this, though: it's clearly \emph{sufficient} +to hand Alice's private key to Justin. On the other hand, this is also +\emph{necessary}, since \emph{in extremis} Alice could do precisely this. +Similarly, it might be the case that Justin demands that Bob engage in some +protocol in an attempt to demonstrate his innocence. We can therefore also +give Bob's private key to Justin. + +This gives us enough to define our notion of \emph{strong deniability}. As +we shall see, however, weak deniability is somewhat trickier to capture. + +\begin{definition}[Strongly deniable authenticated asymmetric encryption] + \label{def:aae-sdeny} + + Let $\Pi = (G, E, D)$ be an asymmetric authenticated encryption scheme, and + let $S$ (the `simulator') and $J$ (the `judge') be algorithms. The + simulator's ability to deceive the judge is measured by the following + games. + \begin{program} + $\Game{sdeny-$b$}{\Pi, S}(J, m_0, m_1)$: \+ \\ + $(x, X) \gets G()$; + $(y, Y) \gets G()$; \\ + $c_0 \gets E_y(X, m_0)$; \\ + $c_1 \gets S(x, Y, m_1)$; \\ + $b' \gets J(x, X, y, Y, c_b, m_b)$; \\ + \RETURN $b'$; + \end{program} + + We measure $J$'s \emph{advantage} in distinguishing simulated ciphertexts + from genuine ones by + \[ \Adv{sdeny}{\Pi, S}(J) = \max_{m_0, m_1 \in \Bin^*} \bigl( + \Pr[\Game{sdeny-$1$}{\Pi, S}(J, m_0, m_1) = 1] - + \Pr[\Game{sdeny-$0$}{\Pi, S}(J, m_0, m_1) = 1] \bigr) \] + Finally, we define the \emph{insecurity function} of $S$ as a simulator for + the deniability of $\Pi$ by + \[ \InSec{sdeny}(\Pi, S; t) = \max_J \Adv{sdeny}{\Pi, S}(J) \] + where the maximum is taken over all algorithms~$J$ completing the game in + time~$t$. +\end{definition} + +\subsection{Chameleon signatures and weak deniability} +\label{sec:deny.weak} + +Unfortunately, this still isn't quite enough. Chameleon signatures +\cite{cryptoeprint:1998:010} achieve weak deniability as we've outlined above +but still provide a kind of nonrepudiation property. Briefly, a chameleon +signature uses trapdoor commitments: Alice generates a trapdoor and a public +key for the commitment scheme; Bob signs a message $m$ by creating a +commitment for $m$ using Alice's public key, signs the commitment (and +Alice's public commitment key) with an ordinary EUF-CMA signature scheme, and +presents the pair of this signature and an opening of the commitment as his +chameleon signature on~$m$. This achieves a limited form of deniability +(called `non-transferability' in \cite{cryptoeprint:1998:010}): Alice can +forge signatures using her trapdoor, so she can't convince others of the +signature's validity -- but she can only do this for commitments that Bob has +already signed, or she'd break the unforgeability of the underlying signature +scheme. In theory, then, a dispute can be settled by demanding that Bob +provide an opening to the commitment different from Alice's: if he can, then +Alice must have used her trapdoor; otherwise he is deemed to accept the +validity of the signature. This looks like a deniability failure. + +(Di~Raimondo and Gennaro \cite{Raimondo:2005:NAD} frame the same problem in +terms of a deniability failure for the receiver, and describe a notion of +`forward deniability' which excludes this failure. The difference in point +of view is mainly whether we consider the sender acting voluntarily or under +compulsion.) + +None of this affects strong deniability. If Alice can make up plausible +messages from nothing but Bob's public key then Bob has nothing to prove. +(We prove a formal version of this statement in \xref{th:strong-weak}.) But +it means that our weak deniability is still too weak. + +The fundamental problem is that, if the recipient's simulator needs a valid +ciphertext to work on, then there must be at least one valid ciphertext for +any simulated one, and Bob should be able to produce it; if he can't, then we +conclude that the ciphertext we have is the valid original. To avoid this, +then, we must demand a \emph{second} simulator: given a genuine +ciphertext~$c$ corresponding to a message~$m$, Alice's public key, Bob's +private key, and a target message~$m'$, the simulator must construct a new +ciphertext~$c'$. To test the efficacy of this simulator, we ask that Justin +attempt to distinguish between, on the one hand, a legitimate +message/ciphertext pair and an `Alice-forgery' created by the first +simulator, and on the other hand, a `Bob-forgery' created by the second +simulator and a legitimate message/ciphertext pair: the simulator is good if +Justin can't distinguish these two cases. The intuition here is Justin is +being asked to adjudicate between Alice and Bob: each of them claims to have +the `legitimate' ciphertext, but one of them has secretly used the +simulator. Justin shouldn't be able to work out which is telling the truth. + +A scheme based on chameleon signatures fails to meet this stricter +definition. Justin looks at the two chameleon signatures: if they have the +same underlying signature, it's an Alice forgery; if the signatures differ +then it's a Bob forgery. If the second simulator, which isn't given Alice's +trapdoor key, can make a second ciphertext using the same underlying +signature then either it can find a new commitment with the same signature, +which is an non-repudiation failure for the signature,\footnote{% + Well, almost. In fact, signature schemes as we've defined them don't have + to be unforgeable in this case. In the EUF-CMA game + (\xref{def:sig-security}) the adversary is given only oracle access to the + signing algorithm, while the legitimate signer has access to the signing + algorithm's internal state which may help in the construction of forgeries. + We conclude that EUF-CMA is insufficient for non-repudiation.}% +or it can find a second opening of the commitment, which is a binding failure +for the commitment scheme. + +Again, we can distinguish two variant definitions, according to whether Bob's +simulator has to work only on the given ciphertext, or whether it's also +provided with a `hint' produced by the encryption algorithm but not made +available to the adversary in the IND-OCCA and UF-OCMA games. We prefer this +latter formulation;\footnote{% + As described in \cite{cryptoeprint:1998:010}, we could instead attach this + hint to the ciphertext, encrypted under a symmetric key. We shall describe + how this can be done with our proposed scheme.} % +we must therefore define formally our `leaky' encryption schemes which +provide such hints. As one would expect, the security notions carry over +directly because the adversary never gets to see the hints. + +\begin{definition}[Leaky authenticated asymmetric encryption] + \label{def:aae-leaky} + + A \emph{leaky authentic asymmetric encryption scheme} $\Pi_\textnm{laae} = + (G, E', D)$ is a triple of (maybe randomized) algorithms as follows. + \begin{itemize} + \item The \emph{leaky encryption algorithm} $E'$ accepts as input a private + key~$x$, a public key~$Y$, a message~$m$, and outputs a pair $(c, s) + \gets E'_x(Y, m)$ consisting of a ciphertext~$c$ and a \emph{hint}~$\nu$. + \item If we define $\bar E_x(Y, m)$ to perform $E$ and discard the hint + \begin{program} + $\bar E_x(Y, m)$: \+ \\ + $(c, \nu) \gets E_x(Y, m)$; \\ + \RETURN $c$ + \end{program} + then $\bar\Pi_\textnm{laae} = (G, \bar E, D)$ is an authenticated + asymmetric encryption scheme.\footnote{% + Think of the bar as `plugging the leak'.} % + \end{itemize} + For any adversary~$A$, time bound~$t$ and query bounds~$q_E$ and $q_D$, we + define + \begin{eqnarray*}[x] + \Adv{ind-occa}{\Pi_\textnm{laae}}(A) = + \Adv{ind-occa}{\bar\Pi_\textnm{laae}}(A) \qquad + \Adv{uf-ocma}{\Pi_\textnm{laae}}(A) = + \Adv{uf-ocma}{\bar\Pi_\textnm{laae}}(A) \\ + \InSec{ind-occa}(\Pi_\textnm{laae}; t, q_D) = + \InSec{ind-occa}(\bar\Pi_\textnm{laae}; t, q_D) \\ + \InSec{uf-ocma}(\Pi_\textnm{laae}; t, q_E) = + \InSec{uf-ocma}(\bar\Pi_\textnm{laae}; t, q_E) + \end{eqnarray*} + inheriting security definitions from the non-leaky version. +\end{definition} + +Obviously, any non-leaky scheme can easily be transformed into a leaky scheme +with a trivial `leak'. We shall make use of this below. + +We are now finally in a position to define \emph{weak deniability}. + +\begin{definition}[Weakly deniable authenticated asymmetric encryption] + \label{def:aae-wdeny} + + Let $\Pi = (G, E, D)$ be a leaky asymmetric authenticated encryption + scheme, and let $S$ and $S'$ (the `simulators'), and $J$ and $J'$ (the + `judges') be algorithms. The simulators' ability to deceive the judges is + measured using the following games. + \begin{program} + $\Game{wdeny-$b$}{\Pi, S}(J, m_0, m_1)$: \+ \\ + $(x, X) \gets G()$; + $(y, Y) \gets G()$; \\ + $(c_0, \nu) \gets E_y(X, m_0)$; \\ + $c_1 \gets S(x, Y, c_0, m_1)$; \\ + $b' \gets J(x, X, y, Y, c_b, m_b)$; \\ + \RETURN $b'$; + \next + $\Game{wdeny$'$-$0$}{\Pi, S, S'}(J', m_0, m_1)$: \+ \\ + $(x, X) \gets G()$; + $(y, Y) \gets G()$; \\ + $(c_0, \nu) \gets E_y(X, m_0)$; \\ + $c_1 \gets S'(X, y, c_0, \nu, m_1)$; \\ + $b' \gets J'(x, X, y, Y, c_0, m_0, c_1, m_1)$; \\ + \RETURN $b'$; + \- \\[\medskipamount] + $\Game{wdeny$'$-$1$}{\Pi, S, S'}(J', m_0, m_1)$: \+ \\ + $(x, X) \gets G()$; + $(y, Y) \gets G()$; \\ + $(c_1, \nu) \gets E_y(X, m_1)$; \\ + $c_0 \gets S(x, Y, c_1, m_0)$; \\ + $b' \gets J'(x, X, y, Y, c_0, m_0, c_1, m_1)$; \\ + \RETURN $b'$; + \end{program} + + We define the judges' \emph{advantage} at distinguishing the simulators' + output as follows. + \begin{eqnarray*}[x] + \begin{subsplit} \displaystyle + \Adv{wdeny}{\Pi, S}(J) = \max_{m_0, m_1 \in \Bin^*} \bigl( + \Pr[\Game{wdeny-$1$}{\Pi, S}(J, m_0, m_1) = 1] - {} \\ + \Pr[\Game{wdeny-$0$}{\Pi, S}(J, m_0, m_1) = 1] \bigr) + \end{subsplit} \\[\bigskipamount] + \begin{subsplit} \displaystyle + \Adv{wdeny$'$}{\Pi, S, S'}(J') = \max_{m_0, m_1 \in \Bin^*} \bigl( + \Pr[\Game{wdeny$'$-$1$}{\Pi, S, S'}(J', m_0, m_1) = 1] - {} \\ + \Pr[\Game{wdeny$'$-$0$}{\Pi, S, S'}(J', m_0, m_1) = 1] \bigr) + \end{subsplit} + \end{eqnarray*} + Finally, the insecurity function of the simulators is defined by + \[ \InSec{wdeny}(\Pi, S, S'; t) = \max\bigl( + \max_J \Adv{wdeny}{\Pi, S}(J), + \max_{J'} \Adv{wdeny$'$}{\Pi, S, S'}(J') + \bigr) + \] + where the maxima are taken over all judges~$J$ and~$J'$ completing their + respective games in time~$t$. +\end{definition} + +\subsection{Remarks} +\label{sec:deny.discuss} + +\subsubsection{Strong deniability implies weak deniability} +By now, it's probably not at all clear that strong deniability actually +implies weak deniability; but this is nonetheless true. The important +observation is that, since the recipient's simulator works without reference +to an existing ciphertext, the standard encryption algorithm works well as a +sender's simulator. This is expressed in the following theorem. + +\begin{theorem}[$\textrm{SDENY} \implies \textrm{WDENY}$] + \label{th:strong-weak} + + Let $\Pi = (G, E, D)$ be an authenticated asymmetric encryption scheme, and + let~$S$ be a simulator. Let $\Pi' = (G, E', D)$ where $E'_x(Y, m) = + (E_x(Y, m), \bot)$, so $\Pi'$ is a (trivially) `leaky' AAE scheme. Then + there exists a simulator~$S'$ such that + \[ \InSec{wdeny}(\Pi', S, S'; t) \le \InSec{sdeny}(\Pi, S; t') \] + where $t' - t$ is the time required for a single encryption. +\end{theorem} +\begin{proof} + The only difference between the SDENY and WDENY games is that the WDENY + simulator is given an additional argument; the simulator's output is the + same in both cases, as is the input to the judge. It follows, then, that + the strong-deniability simulator~$S$ is sufficient to show that, for + any judge~$J$ + \[ \Adv{wdeny}{\Pi', S}(J, m_0, m_1) \le \InSec{sdeny}(\Pi, S; t) \] + where $t$ is the running time of~$J$. + + The simulator~$S'$ simply uses the `proper' encryption algorithm: + \begin{program} + $S'(X, y, c, \nu, m)$: \+ \\ + $c' \gets E_y(X, m)$; \\ + \RETURN $c'$; + \end{program} + We must now show that this simulator is sufficient to convince any~$J'$ in + the WDENY$'$ game. + + The notation is uncomfortably heavyweight; let us write $\G{b} = + \Game{wdeny$'$-$b$}{\Pi', S, S'}$. In $\G1$ both ciphertexts are `genuine' + -- they were generated by the proper encryption algorithm, using the proper + private key. In $\G0$, on the other hand, the right-hand ciphertext is + genuine but the left-hand ciphertext is simulated by~$S$. However, $S$ is + meant to be a good simulator of genuine ciphertexts. Indeed, if $J'$ can + tell a pair of good, independently generated ciphertexts from a good + ciphertext and a (still independent) $S$-simulated one, then we can use it + to distinguish $S$'s simulations.\footnote{% + This independence, which follows from the fact that the strong + deniability simulator is required to work \emph{ab initio} without + reference to an existing ciphertext, is essential to the proof. Without + it, we'd `prove' that one needs only a single simulator to achieve weak + deniability -- but the previous discussion of chameleon signatures shows + that this is false.} % + + Choose some message~$m^*$. We construct an explicit~$J$ as follows. + \begin{program} + $J(x, X, y, Y, c, m)$: \+ \\ + $c^* \gets E_y(X, m^*)$; \\ + $b \gets J'(x, X, y, Y, c, m, c^*, m^*)$; \\ + \RETURN $b$; + \end{program} + This $J$ is given either a genuine or an $S$-simulated ciphertext and + message, allegedly for message~$m$. It generates a genuine ciphertext + independently for~$m'$. It now has either two independent genuine + ciphertexts or a genuine ciphertext and a simulation, and therefore + distinguishes the two cases exactly as well as $J'$. We conclude that + \[ \Adv{wdeny$'$}{\Pi', S, S'}(J') \le \InSec{sdeny}(\Pi S; t') \] + as required. +\end{proof} + +\subsubsection{Insider authenticity} +\label{sec:deny.insider} +There is a kind of attack considered in the study of key-exchange protocols +(see, for example, \cite{Blake-Wilson:1997:KAP}) called \emph{key-compromise + impersonation}. The adversary is assumed to know the long-term secret +information of one of the participants -- Alice, say. Clearly, he can now +impersonate Alice to Bob. If the protocol is vulnerable to key-compromise +impersonation attacks, however, he can also impersonate Bob -- or anybody +else of his choosing -- to Alice.\footnote{% + It is apparently considered unsatisfactory for a key-exchange protocol to + admit key-compromise impersonation, though it's unclear to us why we might + expect Alice to retain any useful security properties after having been + corrupted.} % +The analogue of key-compromise-impersonation resistance in the context of +noninteractive asymmetric encryption is \emph{insider authenticity}. + +Deniably authenticated asymmetric encryption schemes do not provide insider +authenticity: the two are fundamentally incompatible. Indeed, the existence +of the receiver simulator~$S$ in \xref{def:aae-sdeny} or \xref{def:aae-wdeny} +constitutes an insider-authenticity attack. + +Insider authenticity can be defined fairly easily by modifying the UF-OCMA +game of \xref{def:aae-security} to give the adversary the receiver's private +key~$y$; we shall omit the tedious formalities, but we shall end up with a +security measure $\InSec{uf-icma}(\Pi; t, q_E)$ (for `unforgeability under +insider chosen-message attack'). The attack is simple: retrieve a single +message~$m$ from the sender (if the scheme is only weakly deniable -- even +this is unnecessary if we have strong deniability), pass it to the +simulator~$S$, along with the private key~$y$ and a different message~$m' \ne +m$. Let $y'$ be the simulator's output. We know that the decryption +algorithm will always succeed on real ciphertexts; so if $p$ is the +probability that decryption fails, then +\[ \InSec{uf-icma}(\Pi; t_E + t_S, 1) \ge + p \ge 1 - \InSec{wdeny}(\Pi, S; t_D) \] +where $t_E$, $t_S$ and $t_D$ are the respective times required to encrypt a +message, run the receiver simulator, and decrypt a message. + +%%%-------------------------------------------------------------------------- +\section{Generic weakly deniable construction} +\label{sec:gwd} + +In this section we describe a generic construction meeting the definition of +`weak deniability' (\xref{def:aae-wdeny}), and prove its security. + +\subsection{Description of the construction} +\label{sec:gwd.description} + +Firstly, we give an informal description; then we present the formal version +as pseudocode. We need the following ingredients. +\begin{itemize} +\item A key encapsulation mechanism (KEM; + \xref{def:kem-syntax})~$\Pi_\textnm{kem} = (\ell, \mathcal{G}, \mathcal{E}, + \mathcal{D})$, secure against chosen-ciphertext attack (IND-CCA; + \xref{def:kem-security}). +\item A symmetric encryption scheme (\xref{def:se-syntax}) + scheme~$\Pi_\textnm{se} = (k, E, D)$, secure against chosen-ciphertext + attack and with integrity of ciphertexts (IND-CCA and INT-CTXT; + \xref{def:se-security}), where $k < \ell$. +\item A digital signature (\xref{def:sig-syntax}) scheme~$\Pi_\textnm{sig} = + (G, S, V)$, secure against existential forgery under chosen-message attack + (EUF-CMA; \xref{def:sig-security}) and satisfying the additional property + that the encoding $[\sigma]$ of any signature $\sigma$ has the same + length.\footnote{% + Most practical signature schemes, e.g., based on RSA + \cite{Rivest:1978:MOD,Bellare:1996:ESD,RSA:2002:PVR,rfc3447} or DSA + \cite{FIPS:2000:DSS}, have this property for arbitrary messages. + Regardless, we investigate how to weaken this requirement in + \xref{sec:gwd.variant}.} % +\end{itemize} + +Alice's private key consists of a private key~$a$ for the KEM and a private +key~$a'$ for the signature scheme; her public key consists of the two +corresponding public keys $A$ and~$A'$. Similarly, Bob's private key +consists of $b$ and $b'$ for the KEM and signature scheme, and his public key +is $B$ and $B'$. A diagram of the scheme is shown in \xref{fig:gwd}. + +To send a message~$m$ to Bob, Alice performs the following steps. +\begin{enumerate} +\item She runs the KEM on Bob's public key~$B$; it returns a `clue'~$u$ and + an $\ell$-bit `key'~$Z$. +\item She splits $Z$ into a $k$-bit key~$K$ for the symmetric encryption + scheme, and a $t$-bit `tag'~$\tau$. +\item She signs $[\tau, B]$ using the signature scheme and her private + key~$a'$, producing a signature~$\sigma$. +\item She encrypts the signature and her message using the symmetric + encryption scheme, with key~$K$, producing a ciphertext $y$. +\item The final ciphertext consists of two elements: the KEM clue~$u$ and the + symmetric ciphertext~$y$. +\end{enumerate} +To decrypt the message represented by $(u, y)$, Bob performs these steps. +\begin{enumerate} +\item He applies the KEM to the clue~$u$ and his private key~$b$, obtaining + an $\ell$-bit `key'~$Z$. +\item He splits $Z$ into a $k$-bit key~$K$ for the symmetric encryption + scheme and a $t$-bit tag~$\tau$. +\item He decrypts the ciphertext~$y$ using the symmetric encryption scheme + with key~$K$, obtaining a signature~$\sigma$ and a message~$m$. +\item He verifies the signature $\sigma$ on the pair~$[\tau, B]$, using + Alice's public key~$A'$. +\end{enumerate} + +\begin{figure} + \centering + \begin{tikzpicture} + \tikzset{ + box/.style = {draw, minimum size = 14pt, fill = #1}, + around/.style = {inner sep = 0pt, fit = #1}, + node distance = 5mm, + rounded/.style = {rounded corners = 2mm} + } + \node[box = blue!20] (kem) {$\mathcal{E}$}; + \node[box = red!20, left = -0.3pt] at (0, -1) (K) {$K$}; + \node[box = green!20, right = -0.3pt] at (0, -1) (tau) {$\tau$}; + \node[around = (K) (tau)] (Z) {}; + \draw[->] (kem) -- (Z); + \node[box = green!20, right = of tau] (tau2) {$\tau$}; + \node[box = blue!20, right = -0.6pt of tau2] (B) {$B$}; + \node[around = (tau2) (B)] (sign-input) {}; + \node at (B |- kem) {$B$} edge [->] (kem) + edge [->] (B); + \draw[->] (tau) -- (tau2); + \node[box = green!20, below = of sign-input] (sig) {$S$} + edge [<-] (sign-input); + \node[left = of sig] {$a'$} edge [->] (sig); + \node[box = green!20, below = of sig] (sigma) {$\sigma$} + edge [<-] (sig); + \node[box = yellow!20, right = -0.6pt of sigma, minimum width = 30mm] + (m) {$m$}; + \node at (m |- kem) {$m$} edge [->] (m); + \node[around = (sigma) (m)] (enc-input) {}; + \node[box = red!20, below = of m.south west] (enc) {$E$}; + \draw[->, rounded] (enc-input) |- (enc); + \draw[->, rounded] (K) |- (enc); + \node[box = red!20, below = of enc, minimum width = 35mm] (y) {$y$}; + \node[box = blue!20, left = -0.6pt of y] (u) {$u$}; + \draw[->] (enc) -- (y); + \draw[->, rounded] (kem) -- +(-1, 0) |- (u); + \end{tikzpicture} + \caption{Generic weakly-deniable asymmetric encryption} + \label{fig:gwd} +\end{figure} + +More formally, we define our generic weakly-deniable scheme +$\Pi_\textnm{aae-gwd}(\Pi_\textnm{kem}, \Pi_\textnm{sig}, \Pi_\textnm{se})$ +to be the triple of algorithms $(\Xid{G}{aae-gwd}, \Xid{E'}{aae-gwd}, +\Xid{D}{aae-gwd})$ as follows. +\begin{program} + $\Xid{G}{aae-gwd}()$: \+ \\ + $(x, X) \gets \mathcal{G}()$; \\ + $(x', X') \gets G()$; \\ + \RETURN $\bigl( (x, x'), (X, X') \bigr)$; \- +\newline + $\Xid{E'}{aae-gwd}_{x, x'}\bigl((Y, Y'), m\bigr)$: \+ \\ + $(Z, u) \gets \mathcal{E}_Y()$; \\ + $K \gets Z[0 \bitsto k]$; + $\tau \gets Z[k \bitsto \ell]$; \\ + $\sigma \gets S_{x'}([\tau, Y])$; \\ + $y \gets E_K([\sigma] \cat m)$; \\ + \RETURN $\bigl((u, y), K\bigr)$; \- +\next + $\Xid{D}{aae-gwd}_{x, x'}\bigl((Y, Y'), (u, y)\bigr)$: \+ \\ + $Z \gets \mathcal{D}_x(u)$; + \IF $Z = \bot$ \THEN \RETURN $\bot$; \\ + $K \gets Z[0 \bitsto k]$; + $\tau \gets Z[k \bitsto \ell]$; \\ + $\hat{m} \gets D_K(y)$; + \IF $\hat{m} = \bot$ \THEN \RETURN $\bot$; \\ + $[\sigma] \cat m \gets \hat{m}$; + \IF $V_{Y'}([\tau, X], \sigma) = 0$ \THEN \RETURN $\bot$; \\ + \RETURN $m$; +\end{program} + +\subsection{Conventional security} +\label{sec:gwd.aae} + +Before we embark on the formal security proof, it's worth reflecting on the +intuitive reason that the generic scheme is secure -- in the sense of +providing (outsider) secrecy and authenticity. + +Secrecy is fairly straightforward: it follows directly from the security of +the KEM and the symmetric encryption scheme. + + +Firstly we consider secrecy, and initially restrict our attention to secrecy +under chosen-plaintext attack only. If the KEM is any good then the key~$Z$ +appears to be random and particularly the first $k$ bits -- i.e., the +symmetric key~$K$ -- are unknown to the adversary. Since~$K$ is good, and we +assume that the symmetric scheme is good, then the ciphertext~$y$ hides~$m$, +and since~$y$ is the only part of the overall ciphertext that depends on~$m$ +this is sufficient. + +For secrecy under chosen-ciphertext attack we must show that a decryption +oracle doesn't help. A decryption query may share a KEM clue with a given +target ciphertext. If it does then we appeal to symmetric security; if not, +then the KEM security suffices. + +Finally we deal with authenticity. For a forgery to be successful, it must +contain a signature which can be verified using the purported sender's public +key; if the signature scheme is good, then this must be a signature actually +made by the purported sender. If the KEM clue on the forgery doesn't match +the clue from the message from which the signature was extracted, then the +tag taken from the forgery will fail to match with high probability. If the +KEM clue does match then the symmetric key must also match, and so the +symmetric scheme's authentication will ensure that the signature and message +are both unaltered -- so the forgery is trivial. + +We now present the formal security theorems. + +\begin{theorem}[AAE-GWD secrecy] + \label{th:gwd-secrecy} + Let $\Pi = \Pi_\textnm{aae-gwd}(\Pi_\textnm{kem}, \Pi_\textnm{sig}, + \Pi_\textnm{se})$ be as defined above. Then + \[ \InSec{ind-occa}(\Pi; t, q_E, q_D) \le \\ + 2\,\InSec{ind-cca}(\Pi_\textnm{kem}; t, q_D) + + \InSec{ind-cca}(\Pi_\textnm{se}; t, 1, q_D) + \] +\end{theorem} +\begin{theorem}[AAE-GWD authenticity] + \label{th:gwd-authenticity} + Let $\Pi = \Pi_\textnm{aae-gwd}(\Pi_\textnm{kem}, \Pi_\textnm{sig}, + \Pi_\textnm{se})$ be as defined above. Then + \begin{spliteqn*} + \InSec{uf-ocma}(\Pi; t, q_E, q_D) \le + q_E \InSec{ind-cca}(\Pi_\textnm{kem}; t, 0) + + q_E \InSec{int-ctxt}(\Pi_\textnm{se}; t, 1, q_D) + {} \\ + q_E \InSec{ind-cca}(\Pi_\textnm{se}; t, 1, 0) + + \InSec{euf-cma}(\Pi_\textnm{sig}; t, q_E) + \end{spliteqn*} +\end{theorem} +\begin{proof}[Proof of \xref{th:gwd-secrecy}] + We use sequences of games over the same underlying probability space, as + described in \cite{Shoup:2002:OR,cryptoeprint:2004:332}. + + Let $A$ be any adversary attacking the outsider secrecy of $\Pi$ which runs + within the stated resource bounds. It will therefore suffice to bound + $A$'s advantage. + + In game~$\G0$, we toss a coin~$b \inr \{0, 1\}$, and play + $\Game{ind-occa-$b$}{\Pi}(A)$. The adversary's output is $b'$. Let $S_0$ + be the event that $b = b'$. We have, as a standard result, that + \begin{eqnarray*}[rl] + \Adv{ind-occa}{\Pi}(A) + & = \Pr[S_0 \mid b = 1] - \Pr[\bar S_0 \mid b = 0] \\ + & = \Pr[S_0 \mid b = 1] + \Pr[S_0 \mid b = 0] - 1 \\ + & = \frac{\Pr[S_0 \land b = 1]}{\Pr[b = 1]} + + \frac{\Pr[S_0 \land b = 0]}{\Pr[b = 0]} - 1 \\ + & = 2(\Pr[S_0 \land b = 1] + \Pr[S_0 \land b = 0]) - 1 \\ + & = 2\Pr[S_0] - 1 \eqnumber \label{eq:gwd-sec-s0} + \end{eqnarray*} + Hence bounding $\Pr[S_0]$ will be sufficient to complete the proof. In + each game~$\G{i}$ that we define, $S_i$ will be the event that $b' = b$ in + that game. As we define new games, we shall bound $\Pr[S_i]$ in terms of + $\Pr[S_{i+1}]$ until eventually we shall be able to determine this + probability explicitly. + + Before we start modifying the game, we shall pause to establish some + notation. The \emph{challenge ciphertext} passed to the \cookie{guess} + stage of the adversary is a clue/signature/ciphertext triple $c^* = (u^*, + y^*)$, where $(Z^*, u^*) \gets \mathcal{E}_Y()$, $K^* = Z^*[0 \bitsto k]$, + $\tau^* = Z^*[k \bitsto \ell]$, $\sigma^* \gets S_x([\tau^*, Y])$, and $y^* + \gets E_{K^*}([\sigma^*] \cat m_b)$. + + Game~$\G1$ works in almost the same way as $\G0$. The difference is that + rather than computing~$Z^*$ using the key-encapsulation algorithm + $\mathcal{E}_Y$, we simply choose it uniformly at random from $\Bin^\ell$. + Furthermore, the decryption oracle compensates for this by inspecting the + input ciphertext $c = (u, y)$: if and only if $u = u^*$ then decryption + proceeds using $Z = Z^*$ rather than using the key-decapsulation + algorithm~$\mathcal{D}$. + + We claim that + \begin{equation} + \label{eq:gwd-sec-g1} + \Pr[S_0] - \Pr[S_1] \le + \InSec{ind-cca}(\Pi_\textnm{kem}; t, q_D) + \end{equation} + The proof of the claim is by a simple reduction argument: we define an + adversary~$\hat{A}$ which attacks the KEM. We describe the + adversary~$\hat{A}$ in detail by way of example; future reduction arguments + will be rather briefer. + + The adversary receives as input a public key~$Y$ for the KEM, an $\ell$-bit + string $Z^*$ and a clue~$u^*$. It generates signature key pairs ~$(x', + X')$ and $(y', Y')$, and a KEM key pair~$(x, X)$, using the key-generation + algorithms; it also chooses $b \in \{0, 1\}$ uniformly at random. It runs + the \cookie{find} stage of adversary~$A$, giving it $(X, X')$ and $(Y, Y')$ + as input. Eventually, the \cookie{find} stage completes and outputs $m_0$ + and $m_1$ and a state~$s$. Our KEM adversary computes $\sigma^*$ and $y^*$ + in terms of the $Z^*$ it was given and the message~$m_b$, and runs the + \cookie{guess} stage of adversary~$A$, providing it with the + ciphertext~$(u^*, \sigma^*, y^*)$ and the state~$s$. Eventually, $A$ + completes, outputting its guess~$b'$. If $b' = b$ then our KEM adversary + outputs~$1$; otherwise it outputs~$0$. + + During all of this, we must simulate $A$'s encryption and decryption + oracles. The encryption oracle poses no special difficulty, since we have + the signing key~$x'$. On input $\bigl((Q, Q'), (u, \sigma, y)\bigr)$, the + simulated decryption oracle works as follows. If $u = u^*$ then set $Z = + Z^*$; otherwise retrieve $Z$ by querying the decapsulation oracle at~$u$, + since this is permitted by the KEM IND-CCA game rules. Except for this + slightly fiddly way of discovering~$Z$, the simulated decryption oracle + uses the `proper' decryption algorithm, verifying the signature $\sigma$ on + the tag~$\tau = Z[k \bitsto \ell]$ using the public key~$Q'$. + + If the KEM adversary is playing the `real' + $\Game{ind-cca-$1$}{\Pi_\textnm{kem}}$ then our KEM adversary simulates + $\G0$ perfectly; hence, the probability that it outputs $1$ is precisely + $\Pr[S_0]$. On the other hand, if it is playing + $\Game{ind-cca-$0$}{\Pi_\textnm{kem}}$ then it simulates~$\G1$, and the + probability that it outputs $1$ is $\Pr[S_1]$. Hence + \[ \Pr[S_0] - \Pr[S_1] = \Adv{ind-cca}{\Pi_\textnm{kem}}(\hat{A}) + \le \InSec{ind-cca}(\Pi_\textnm{kem}; t, q_D) + \] + as claimed. + + Finally, we can bound $S_1$ explicitly in $\G1$: + \begin{equation} + \label{eq:gwd-sec-s1} + \Pr[S_1] \le \frac{1}{2} \InSec{ind-cca}(\Pi_\textnm{se}; t, 1, q_D) + + \frac{1}{2} + \end{equation} + This follows by a simple reduction to the chosen-ciphertext secrecy of + $\Pi_\textnm{se}$: $K^*$ will be known to the IND-CCA game, but not + directly to our adversary. It will generate all of the long-term + asymmetric keys, and run $A$'s \cookie{find} stage, collects the two + plaintext messages, encrypts them (making use of the left-or-right + $\Pi_\textnm{se}$ encryption oracle to find $y^* = E_{K^*}([\sigma] \cat + \id{lr}(m_0, m_1))$. The challenge ciphertext is passed to $A$'s + \cookie{guess} stage, which will eventually output a guess~$b'$; our + adversary outputs this guess. + + The decryption oracle is simulated as follows. Let $(u, y)$ be the + chosen-ciphertext query. If $u \ne u^*$ then we decrypt $y$ by recovering + $K \cat \tau = \mathcal{D}_y(u)$ as usual; otherwise we must have $y \ne + y^*$ so $y$ is a legitimate query to the symmetric decryption oracle, so we + recover $\hat{m} = D_{K^*}(y)$ and continue from there. + + This is a valid adversary, and runs in the stated resource bounds, so the + claim follows. + + We can bound the advantage of adversary~$A$ by combining + equations~\ref{eq:gwd-sec-s0}--\ref{eq:gwd-sec-s1}: + \begin{eqnarray*}[rl] + \Adv{ind-occa}{\Pi}(A) + & = 2\Pr[S_0] - 1 \\ + & \le 2 \, \InSec{ind-cca}(\Pi_\textnm{kem}; t, q_D) + + \InSec{ind-cca}(\Pi_\textnm{se}; t, 1, q_D) + \end{eqnarray*} + completing the proof. +\end{proof} + +\begin{proof}[Proof of \xref{th:gwd-authenticity}] + We use a sequence of games again. + + Let $A$ be any adversary attacking the outsider authenticity of $\Pi$ and + running within the specified resource bounds. It will suffice to bound + $A$'s advantage. + + Game~$\G0$ is precisely $\Game{uf-ocma}{\Pi}(A)$. We let $S_0$ be the + event that $A$ outputs a valid forgery, i.e., + \begin{equation} + \label{eq:gwd-auth-s0} + \Adv{uf-ocma}{\Pi}(A) = \Pr[S_0] + \end{equation} + As before, in each subsequent game~$\G{i}$ we let $S_i$ be the + corresponding event. The two key pairs will be $((x, x'), (X, X'))$ and + $((y, y'), (Y, Y'))$. For each $0 \le j < q_D$, let $(Q^*_j, u^*_j, + y^*_j)$ be the adversary's $j$th decryption query, and define $Z^*_j = + \mathcal{D}_y(u^*_j)$, $K^*_j = Z^*_i[0 \bitsto k]$, $\tau^*_j = Z^*_j[k + \bitsto \ell]$, and $[\sigma^*_j] \cat m^*_j = \hat{m}^*_j = + D_{K^*_j}(y^*_j)$, insofar as such quantities are well-defined. For each + $0 \le i < q_E$, we define $m_i$ to be the message in $A$'s $i$th + encryption-oracle query and $(P, P_i)$ as the corresponding public key; and + we set $(Z_i, u_i) \gets \mathcal{E}_{P_i}()$ to be the KEM output while + responding to that query, with $K_i \cat \tau_i = Z_i$, $\sigma_i = + S_{x'}([\tau_i, Q_i])$, and $y_i \gets E_{K_i}(m_i)$. + + Game~$\G1$ is the same as~$\G0$, except that the encryption oracle + generates random keys $Z_i \inr \Bin^\ell$ if $Q_i = Y$ rather than using + the keys output by the key encapsulation algorithm. The clue~$u_i$ + returned is valid; but the key $K_i$ used for the symmetric encryption, and + the tag~$\tau_i$ signed by the signature algorithm, are random and + independent of the clue. We also modify the decryption oracle: if $Q^*_j = + X$, and $u^*_j = u_i$ matches a clue returned by the encryption oracle with + $Q_i = Y$, then the decryption oracle sets $Z^*_j = Z_i$ rather than using + the decapsulation algorithm. + + We claim that + \begin{equation} + \label{eq:gwd-auth-g1} + \Pr[S_0] - \Pr[S_1] \le q_E \InSec{ind-cca}(\Pi_\textnm{kem}; t, 0) + \end{equation} + For this we use a hybrid argument: for $0 \le i \le q_E$ we define + game~$\G[H]{i}$ to use random keys to generate $Z_k$ for $0 \le k < i$ and + to use the `proper' encapsulation algorithm for the remaining $q_E - i$ + queries; let $T_i$ be the event that the adversary returns a valid forgery + in~$\G[H]{i}$. Then + \[ \G[H]{0} \equiv \G0 \qquad \textrm{and} \qquad \G[H]{q_E} \equiv \G1 \] + but a simple reduction argument shows that, for $0 \le i < q_E$, + \[ \Pr[T_i] - \Pr[T_{i+1}] \le \InSec{ind-cca}(\Pi_\textnm{kem}; t, q_D) \] + We construct an adversary~$\hat{A}$ attacking the KEM's secrecy by + simulating one of a pair of hybrid games. Let $\hat{A}$'s input be + $\hat{Z}, \hat{u}$. The KEM adversary proceeds by answering the first~$i$ + encryption queries using random keys, using $Z_i = \hat{Z}$ for query $i$, + and the key encapsulation algorithm for the remaining $q_E - i - 1$ + queries. A decryption query with $Q^*_j$ can be answered by using the key + decapsulation if $u^*_j \ne u_k$, or by setting $Z^*_j = Z_k$ directly + otherwise; clearly if $k = i$ then $Z^*_j = Z_i = \hat{Z}$. If $\hat{Z}$ + is a real KEM output then we have simulated $\G[H]{i}$; otherwise we have + simulated~$\G[H]{i+1}$. The claim follows since + \begin{eqnarray*}[rl] + \Pr[S_0] - \Pr[S_1] + & = \Pr[T_0] - \Pr[T_{q_E}] \\ + & = \sum_{0\le i] node {$\pi$} + ($(dd.west) + (0, 2pt)$); + \draw ($(dd.west) - (0, 2pt)$) + to[->, below] node {$\pi$} + ($(d.east) - (0, 2pt)$); + \node[left = of d] (t) {$\Bin^k$} + edge [<-, below] node {$H_m$} (d) + edge [<-, above left] node {$T_m$} (xy); + \node[right = of dd] (v) {$\Bin^k$} + edge [<-, below] node {$H_m$} (dd) + edge [<-, above right] node {$V_m$} (xy); + \end{tikzpicture} \] + + We can consequently rewrite + \[ T_{x, x'}((R, R'), m) = T_m(x P, x' P, R, R') \] + and + \[ V_{y, y'}((Q, Q'), m, \tau) = \begin{cases} + 1 & if $\tau = V_m(y P, y' P, Q, Q')$ \\ + 0 & otherwise + \end{cases} + \] + + Now, $H$ -- and hence its restriction $H_m$ -- is a random function, + assigning a uniformly distributed and independent $k$-bit string to each + point in its domain. Since $D$ and $D'$ are injective, the functions $T_m$ + and $V_m$ also have this property. (Obviously the outputs of $H_m$, $T_m$ + and $V_m$ are not independent of \emph{each other}, merely of other outputs + of the same function.) It's also clear that the action of $H_m$ on + $D(G^4)$ is determined by $T_m$, and similarly for $D'(G^4)$ and $V_m$. + This observation motivates the definition of the next game~$\G2$. + + Game~$\G2$ redefines the three oracles provided to the adversary in terms + of three new functions $T$, $V$ and $H$ shown in \xref{fig:dh-nidaa-g2}. + We use the `lazy sampling' technique; we implement $T$ directly as a lazily + sampled random function; $V$ consults $T$ where applicable, and otherwise + uses a separate lazily sampled random function; and $H$ consults $T$ or $V$ + where applicable. + + \begin{figure} + \begin{program} + Initialization: \+ \\ + $\mathcal{H} \gets \emptyset$; \\ + $\mathcal{T} \gets \emptyset$; \\ + $\mathcal{V} \gets \emptyset$; \- + \\[\medskipamount] + $T(R, R', m)$: \+ \\ + \IF $(R, R', m) \in \dom \mathcal{T}$ \THEN \\ + \quad $\tau \gets \mathcal{T}(R, R', m)$; \\ + \ELSE \\ \ind + $\tau \getsr \Bin^k$; \\ + $\mathcal{T} \gets \mathcal{T} \cup \{ (R, R', m) \mapsto \tau \}$; + \- \\ + \RETURN $\tau$; \- + \next + $V'(Q, Q', m)$: \+ \\ + \IF $(Q, Q', m) \in \dom \mathcal{V}$ \THEN \\ + \quad $\tau' \gets \mathcal{V}(Q, Q', m)$; \\ + \ELSE \\ \ind + \IF $Q = X \land Q' = X'$ \THEN + $\tau' \gets T(Y, Y', m)$; \\ + \ELSE + $\tau' \getsr \Bin^k$; \\ + $\mathcal{V} \gets \mathcal{V} \cup + \{ (Q, Q', m) \mapsto \tau' \}$; + \- \\ + \RETURN $\tau'$; \- + \\[\medskipamount] + $V(Q, Q', m, \tau)$: \+ \\ + $\tau' \gets V'(Q, Q', m)$; \\ + \IF $\tau = \tau'$ \THEN \RETURN $1$ \ELSE \RETURN $0$; \- + \newline + $H(s)$: \+ \\ + \IF $s \in \dom \mathcal{H}$ \THEN + $h \gets \mathcal{H}(s)$; \\ + \ELSE \\ \ind + \IF $s = [m, Q, Q', R, R', Z, Z', W, W']$ for some \\ + \hspace{4em} + $(m, Q, Q', R, R', Z, Z', W, W') \in \Bin^* \times G^8$ + \THEN \\ \ind + \IF $(Q, Q') = (X, X') \land + (Z, Z', W, W') = (x R, x R', x' R, x' R')$ \THEN + $h \gets T(R, R', m)$; \\ + \ELSE \IF $(R, R') = (Y, Y') \land + (Z, Z', W, W') = (y Q, y' Q, y Q', y' R')$ \THEN + $h \gets V'(Q, Q', m)$; \\ + \ELSE + $h \getsr \Bin^k$; \- \\ + \ELSE + $h \getsr \Bin^k$; \\ + $\mathcal{H} \gets \mathcal{H} \cup \{ s \mapsto h \}$; \- \\ + \RETURN $h$; + \end{program} + + \caption{Tagging, verification and hashing functions for $\G2$} + \label{fig:dh-nidaa-g2} + \end{figure} + + The adversary's oracles map onto these functions in a simple way: $H$ is + precisely the hashing oracle, and + \[ T_{x, x'}((R, R'), m) = T(R, R', m) \qquad \textrm{and} \qquad + V_{y, y'}((Q, Q'), m, \tau) = V(Q, Q', m) \] + Given the foregoing discussion, we see that, despite the rather radical + restructuring of the game, all of the quantities that the adversary sees + are distributed identically, and therefore + \begin{equation} + \label{eq:dh-nidaa-s1} + \Pr[S_2] = \Pr[S_1] + \end{equation} + + Game~$\G3$ is the same as $\G2$, except that we no longer credit the + adversary with a win if it makes a verification query $V_{y, y'}((X, X'), + m, \tau)$ without previously making a hashing query $H([m, X, X', Y, Y', y + X, y' X, y X', y' X'])$. If this happens, either there has been a previous + query to $T_{x, x'}((Y, Y'), m)$, in which case the verification query + can't count as a win in any case, or there was no such query, in which case + the true tag $\tau'$ will be freshly generated uniformly at random. + Evidently, then, + \begin{equation} + \label{eq:dh-nidaa-s2} + \Pr[S_2] - \Pr[S_3] \le \frac{q_V}{2^k} + \end{equation} + + Game~$\G4$ is similar to $\G3$, except that we change the way that the keys + are set up. Rather than choosing $x'$ and $y'$ at random and setting $(X', + Y') = (x' P, y' P)$, we choose $(u, u', v, v') \inr \gf{p}$ and set + \[ X' = u P + u' X \qquad \textrm{and} \qquad Y' = v P + v' Y \] + It's clear that (a) $X'$ and $Y'$ are still uniformly distributed on $G$, + and (b) they are independent of $u'$ and $v'$. Since this change doesn't + affect the distribution of $X'$ and $Y'$, we conclude that + \begin{equation} + \label{eq:dh-nidaa-s3} + \Pr[S_4] = \Pr[S_3] + \end{equation} + + Finally, we bound $\Pr[S_4]$ by a reduction from the computational + Diffie--Hellman problem in~$G$. The reduction receives points $X^* = x P$ + and $Y^* = y P$ and must compute $Z^* = x y P$. It sets $X = X^*$ and $Y = + Y^*$. It chooses $u$, $u'$, $v$, and $v'$, determines $X'$ and $Y'$ as in + $\G4$, and runs $A$ with simulated oracles: the tagging and verification + oracles work exactly as in $\G4$; however, it cannot implement the hashing + function as described, so we must change it: + \begin{itemize} + \item rather than checking whether $(Z, Z', W, W') = (x R, x R', x' R, x' + R')$, we check whether $(W, W') = (u R + u' Z, u R' + u' Z')$; and + \item rather than checking whether $(Z, Z', W, W') = (y Q, y' Q, y Q', y' + R')$, we check whether $(Z', W') = (v R + v' Z, v R' + v' W)$. + \end{itemize} + Let $F$ be the event that this change causes the reduction's hashing + function to make a decision that the proper $\G4$ wouldn't make. + + Let $T$ be the event that the adversary (apparently, using the reduction's + modified hashing function) makes a successful forgery. In this case, we + must have seen a hashing query $H([m, X, X', Y, Y', Z, v R + v' Z, W, v R' + + v' W])$. If $F$ doesn't occur, then we in fact have $Z = x y P = Z^*$; + the work we must do in the reduction over and above $\G1$ is to choose $u$ + etc., to compute $X'$ and $Y'$, perform the dictionary maintenance, and + use the twin-Diffie--Hellman detector, so + \[ \Pr[T \mid \bar{F}] \le \InSec{cdh}(G; t + t') \] + Furthermore, the reduction and $\G4$ proceed identically unless $F$ occurs, + so \xref{lem:shoup} gives + \[ \Pr[S_4] - \Pr[T] \le \Pr[F] \] + A simple calculation bounds $\Pr[T]$: + \begin{eqnarray*}[rl] + \Pr[T] & = \Pr[T \land F] + \Pr[T \land \bar{F}] \\ + & = \Pr[T \land F] + \Pr[T \mid \bar{F}] \Pr[\bar{F}] \\ + & \le \Pr[F] + \Pr[T \mid \bar{F}] \\ + & \le \InSec{cdh}(G; t + t') + \Pr[F] + \eqnumber \label{eq:dh-nidaa-t} + \end{eqnarray*} + Finally, we bound $\Pr[F]$ using \xref{lem:2dh-detect}: + \begin{equation} + \label{eq:dh-nidaa-f} + \Pr[F] \le \frac{2 q_H}{\#G} + \end{equation} + Piecing together equations~\ref{eq:dh-nidaa-s1}--\ref{eq:dh-nidaa-f} + completes the proof. +\end{proof} + +\subsection{Magic tokens: an alternative to NIDAA} +\label{sec:magic} + +For readers who dislike random oracles, we briefly sketch an alternative to +NIDAA schemes. If we're willing to encrypt the NIDAA tag then we don't +actually have to reveal to the adversary any tag intended for the target +recipient: we can replace them all with nonsense strings of the same length, +as we did with the signatures in the proof of \xref{th:gwd-authenticity}. +And if we don't have to reveal them, they don't have to be message-dependent! +We call these \emph{magic tokens}. + +The only requirements on a magic token are that the sender and recipient +should both be able to compute it, but the adversary shouldn't -- even if he +shares many other tokens with the sender. So how do we make a token? Well, +a Diffie--Hellman shared secret seems like a plausible choice. + +Again we work in a cyclic group~$G = \langle P \rangle$ with $p = \#G$ prime +If Alice's and Bob's private keys are $a$ and $b$ respectively, and their +public keys are $A = a P$ and $B = b P$, then their token is simply $Z = a b +P$. + +This doesn't quite work. Suppose the adversary chooses $X = A - r P$ as his +public key, for some $r \inr \gf{p}$. If Bob sends the adversary a token $Y += b X = b A - b r P = Z - r B$, then the adversary computes $Z = Y + r B$ +which is the token shared by Alice and Bob. + +We can fix this. Along with the shared group, we select a random common +reference string, and include in each user's public key a non-malleable +non-interactive zero-knowledge proof of knowledge \cite{DeSantis:2001:RNI} of +the corresponding private key. Now before handing over a token, Bob will +check the NIZK. For maliciously formed public keys like $Y$ above, the +adversary doesn't know the private key, and so Bob will fail to verify the +NIZK. + +Slightly more formally, we sketch a reduction from the computational +Diffie--Hellman problem to forging Alice and Bob's token. The reduction +passes $A$ and $B$ to the forger, along with a freshly generated common +reference string and simulated NIZKs for $A$ and $B$. The forger runs and +outputs its guess as to the token, which (if the token is correct) is +precisely the solution to the CDH problem. All that remains is to implement +a token-issuing oracle: given $(Y, N)$, we must compute $b Y$, where $B = b +P$ and $N$ is a NIZK proof of knowledge for $y$ such that $Y = y P$. To do +this, we use the NIZK extractor to recover $y$ from the adversary and return +$y B = b Y$; this will work despite the adversary having seen the simulated +proofs for $A$ and $B$ because the NIZK is non-malleable. + +\part{trailing cruft} +%%%-------------------------------------------------------------------------- +\section{Diffie--Hellman-based strongly deniable construction} + +This section describes an authenticated asymmetric encryption scheme which +achieves a stronger definition of deniability: a simulator can construct a +convincing ciphertext without having to see a genuine one. + +The scheme's security depends on a number of ingredients: +\begin{itemize} +\item a cyclic group~$G = \langle P \rangle$, with prime order~$p$, in which + the computational Diffie--Hellman problem is hard; +\item a symmetric encryption scheme~$\Pi_\textnm{se} = (k, E, D)$ which + provides secrecy under chosen-plaintext attack; and +\item a cryptographic hash function~$H\colon \Bin^* \to \Bin^k$, which we + shall model as a random oracle. +\end{itemize} + +\subsection{Prologue: asymmetric deniable authentication} + +Rather than present the entire scheme in one go, we first present the +important central part, which provides deniable authentication using +asymmetric keys. + +\begin{definition}[$\Pi_\textnm{auth}^{G, H}$] + \label{def:pi-auth} + + Let $G$ be a cyclic group, of prime order~$p$, generated by $P$; and let + $H\colon \Bin^* \to \Bin^k$ be a hash function. + + The asymmetric authentication scheme $\Pi_\textnm{auth}^{G, H} = + (\Xid{G}{auth}^{G, H}, \Xid{T}{auth}^{G, H}, \Xid{V}{auth}^{G, H})$ is + defined as follows. + \begin{program} + $\Xid{G}{auth}^{G, H}()$: \+ \\ + $x \getsr \gf{p}$; $x' \getsr \gf{p}$; + $X \gets x P$; $X' \gets x' P$; \\ + $y \getsr \gf{p}$; + $Y \gets y' P$; \\ + \RETURN $\bigl( (x, x', y), (X, X', Y) \bigr)$; + \- \\[\medskipamount] + $\Xid{T}{auth}^{G, H}_{x, x', y}(m)$: \+ \\ + $h \gets H_p([\cookie{msg}, m]) + p \Z$; \\ + $Z \gets x y h P$; + $Z' \gets x' y h P$; \\ + $\tau \gets H([\cookie{tag}, Z, Z'])$; \\ + \RETURN $\tau$; + \- \\[\medskipamount] + $\Xid{V}{auth}^{G, H}_{x, x', y}(m, \tau)$: \+ \\ + \IF $\tau = \Xid{T}{auth}^{G, H}_{x, x', y}(m)$ + \THEN \RETURN $1$ \\ \ELSE \RETURN $0$; + \next + $H_n(x)$: \+ \\ + $i \gets 0$; \\ + $\ell \gets \lfloor \log_2 n \rfloor + 1$; \\ + \REPEAT \\ \ind + $h \gets \emptystring$; \\ + \WHILE $|h| < \ell$ \DO \\ \ind + $h \gets h \cat H([i, n, x])$; \\ + $i \gets i + 1$; \- \\ + $[y]_\ell \gets h[0 \bitsto \ell]$; \- \\ + \UNTIL $y < n$; \\ + \RETURN $y$; + \end{program} +\end{definition} + +Observe that $Z = x h Y = y h X$ and $Z' = z' h Y = y h X'$, so either $(x, +x')$ or $y$, together with the public keys $(X, X', Y)$, are sufficient to +compute or verify tags. + +The function~$H_n\colon \Bin^* \to \{0, 1, \ldots, n - 1\}$ is a random +mapping + +\subsubsection{System parameters} +Let $(G, +)$ be a finite, prime-order (necessarily cyclic) group in which the +computational Diffie--Hellman problem is difficult; let $p = \#G$ be the +order of $G$, and let $P \in G - \{ 0 \}$ be a generator of $G$. Let +$H\colon \Bin^* \to \Bin^k$ be a hash function (to be modelled as a random +oracle) and $\Pi_{se} = (k, E, D)$ be a symmetric encryption scheme. + +\subsubsection{Keys} +Each user chooses two indices $x, x' \getsr \gf{p}$. The pair $(x, x')$ is +the user's private key, and the pair $(X, X') = (x P, x' P)$ is the +corresponding public key. + +\begin{program} + Algorithm $\Xid{G}{dh}^{G, \Pi_\textnm{se}, H}()$: \+ \\ + $x \getsr \gf{p}$; $X \gets x P$; \\ + $x' \getsr \gf{p}$; $X' \gets x' P$; \\ + \RETURN $\bigl( (x, x'), (X, X') \bigr)$; \- +\newline + Algorithm $\Xid{E}{dh}^{G, \Pi_\textnm{se}, H}_{x, x'}(Y, Y', m)$: \+ \\ + $r \getsr \gf{p}$; $R \gets r P$; \\ + $K \gets H(\cookie{key}, R, r Y, r Y')$; \\ + $c \gets E_K(\empty, m)$; \\ + $h \gets H(\cookie{msg}, c)$; \\ + $\sigma \gets H(\cookie{sig}, R, x h Y, x h Y')$; \\ + \RETURN $(R, \sigma, c)$; \- +\next + Algorithm $\Xid{D}{dh}^{G, \Pi_\textnm{se}, H}_{x, x'} + (Y, Y', R, \sigma, c)$: \+ \\ + $h \gets H(\cookie{msg}, c)$; \\ + \IF $\sigma \ne H(\cookie{sig}, R, x h Y, x' h Y)$ \THEN + \RETURN $\bot$; \\ + $K \gets H(\cookie{msg}, R, x R, x' R)$; \\ + $m \gets D_K(c)$; \\ + \RETURN $m$; +\end{program} + +Deniable authentication is somewhat slippery to define. + +Here, then, is a first stab at a definition. We'll capture Alice's attempt +at presenting evidence as an algorithm. It runs in two parts. The first +part is given Alice's private key~$a$ and Bob's public key~$B$; it runs for a +while, and eventually produces a message~$m$, and a state~$s$ for the second +part. We get Bob to encrypt this message, and then run the second part of +Alice's algorithm, giving it the state~$s$ from the first part and the +ciphertext $c = E_b(A, m)$; it too runs for a while, and eventually outputs +an evidence package~$v$. Finally, we run Justin's algorithm~$J$ on~$c$, $m$ +and $v$, and Justin outputs either 1 or~0 depending on whether he was +convinced. For deniability, then, we'd demand that, for any Alice +algorithm~$A$, there's a simulator $S(A)$ which accepts $a$, $m$, $c$ and~$s$ +from the first part of $A$, and some $m' \ne m$, and outputs $c'$ and $v'$ +such that $J$ can't distinguish simulated inputs $(c', m', v')$ from genuine +ones $(c, m, v)$. + +Unfortunately, it seems really hard to make this work. For example, $v$ +might contain a hash of $m$, which would make Justin's job really easy. We +can't simulate this kind of evidence in a black-box way: the first part of +Alice's algorithm can encode the hash in its state, so the simulator can't +substitute a different message without understanding the structure of either +the state or the evidence package. + +This isn't the only problem with the above definition. +\begin{itemize} +\item It only models Alice presenting her evidence noninteractively. We'd + like to be able to rule out interactive proofs between Alice and Justin. +\item It allows the simulator a choice of alternative message $m'$. While + the simulator might be able to raise a doubt that Alice's claimed + message~$m$ might not have been sent by Bob, she might still be able to + demonstrate that Bob's message was very \emph{similar} to~$m$. +\end{itemize} + +In fact, the definition is unnecessarily complicated. + + +%% What we /don't/ want to happen: Alice receives message from Bob, presents +%% judge with convincing evidence that Bob sent it. So we want a simulator +%% which makes equally convincing evidence. +%% +%% Judge can't decrypt message sent to Alice without help. Alice might just +%% turn over her private key, or maybe reveal some partial information +%% sufficient to decrypt the message. +%% +%% Oooh: Alice might try to prove stuff about the plaintext in +%% zero-knowledge. Do I really need to capture full interaction? This will +%% turn into a disaster. +%% +%% What inputs do I give Alice, the judge, and the simulator? Simulation +%% without Alice's private key (or something like it) isn't going to work +%% well: IND-CCA! We could consider partial information about Alice's key, +%% but it's going to have to come from somewhere, so we'll suppose that Alice +%% uses it directly. (Working with partial information seems really hard, so +%% I'll leave that one for someone cleverer.) +%% +%% What does Alice give the judge? Ciphertext, plaintext, supporting +%% evidence. The supporting evidence is tough: want to allow stuff like +%% proofs or session keys, but disallow things like hashes of plaintext. +%% +%% Game, initial stab +%% +%% 1. Alice chooses message $m$. +%% 2. Sends $m$ to Bob. Bob encrypts $m$, and returns ciphertext $y$. +%% 3. Alice examines $y$ and constructs evidence $v$. +%% 4. Alice sends $(m, y, v)$ to judge +%% +%% This is going to be hard. Provide input message to Alice and universally +%% quantify? Maximize? +%% +%% So, the real game, for a message $m$ is to run Alice with $m$ and $y$. + +%%%-------------------------------------------------------------------------- +\section{Open problems} +\label{sec:open} + +A number of problems remain outstanding. +\begin{itemize} +\item Construct a strongly deniably authenticated encryption scheme which is + secure in the standard model. +\end{itemize} + + +\section{Acknowledgements} +\label{sec:ack} + +I'm very grateful to Christine Swart for encouraging me to actually write +this up properly. + +\bibliography{mdw-crypto,cryptography,cryptography2000,eprint,jcryptology,lncs1991,lncs1997b,lncs2002b,rfc} + +\end{document} + +%%% Local variables: +%%% mode: LaTeX +%%% TeX-PDF-mode: t +%%% End: diff --git a/robot-alice.png b/robot-alice.png new file mode 100644 index 0000000..f057fca Binary files /dev/null and b/robot-alice.png differ diff --git a/robot-bob.png b/robot-bob.png new file mode 100644 index 0000000..68e067a Binary files /dev/null and b/robot-bob.png differ diff --git a/wl.png b/wl.png new file mode 100644 index 0000000..c35eaaa Binary files /dev/null and b/wl.png differ