initial

[doc/deny] / deny.tex

%%% 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<q} f(x_i, y) = 1\biggr] \le q \epsilon \]
\end{lemma}
\begin{proof}
  Another calculation:
  \begin{eqnarray*}[rl]
    \Pr\biggl[\bigvee_{0\le i<q} f(x_i, y) = 1\biggr]
    & \le \sum_{0\le i<q} \Pr[f(x_i, y) = 1] \\
    &   = \sum_{0\le i<q} \sum_{x\in X} \Pr[f(x_i, y) = 1 \land x_i = x] \\
    &   = \sum_{0\le i<q} \sum_{x\in X}
                \Pr[f(x_i, y) = 1 \mid x_i = x] \Pr[x_i = x] \\
    &   = \sum_{0\le i<q} \sum_{x\in X} \Pr[f(x, y) = 1] \Pr[x_i = x] \\
    & \le \sum_{0\le i<q} \sum_{x\in X} \epsilon \cdot \Pr[x_i = x] \\
    &   = q \epsilon \eqnumber[\qed]
  \end{eqnarray*}
\end{proof}

%%%--------------------------------------------------------------------------
\section{Definitions}
\label{sec:defs}
\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 $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' = r 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' = C] =
  \Pr[r P = C - s X] = 1/p$ for any constant~$C$, 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}

The syntax of symmetric encryption 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 $\proto{se} = (\kappa, E,
  D)$, where $\kappa \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^\kappa$
    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^\kappa$
    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 = (\kappa, 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^\kappa$; \\
      $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^\kappa$; \\
      $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:deny.intuition}).  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{Authenticated encryption with additional data}
\label{sec:aead}

\begin{definition}[AEAD syntax]
  \label{def:aead-syntax}

  An \emph{authenticated encryption with additional data (AEAD)} scheme is a
  triple $\proto{se} = (\kappa, E, D)$, where $\kappa \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^\kappa$, additional data~$h \in \Bin^*$, and a message $m \in
    \Bin^*$, and outputs a ciphertext $c \gets E_K(h, m)$.
  \item The \emph{decryption algorithm}~$D$ accepts a key $K \in
    \Bin^\kappa$, additional data~$h \in \Bin^*$, and a ciphertext $c$, and
    outputs $m = D_K(h, 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^*$, all additional data strings~$h \in \Bin^*$,
    and all messages $m \in \Bin^*$, if $c$ is any output of $E_K(h, m)$ then
    $D_K(h, c)$ outputs $m$. \qed
  \end{itemize}
\end{definition}

\begin{definition}[AEAD security]
  \label{def:aead-security}

  Let $\Pi = (\kappa, 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^\kappa$; \\
      $b' \gets A^{E_K(\cdot, \id{lr}(\cdot, \cdot)),
                        D_K(\cdot, \cdot)}()$; \\
      \RETURN $b'$;
    \next
    $\Game{int-ctxt}{\Pi}(A)$: \+ \\
      $K \getsr \Bin^\kappa$; \\
      $Y \gets \emptyset$; $w \gets 0$; \\
      $A^{\id{encrypt}(\cdot, \cdot), \id{decrypt}(\cdot, \cdot)}()$; \\
      \RETURN $w$; \-
  \newline
    $\id{lr}(m_0, m_1)$: \+ \\
      \RETURN $m_b$;
    \next
    $\id{encrypt}(h, m)$: \+ \\
      $y \gets E_K(h, m)$; \\
      $Y \gets Y \cup \{ (h, y) \}$; \\
      \RETURN $y$; \-
    \next
    $\id{decrypt}(h, y)$: \+ \\
      $m \gets D_K(h, y)$; \\
      \IF $m \ne \bot \land (h, 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 pair $(h, y)$ such that
  $y$ was output by the encryption oracle on a query with additional
  data~$h$.

  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}

\subsection{Asymmetric encryption}
\label{sec:ae}

An \emph{asymmetric encryption scheme} allows a sender, say Alice, to
transmit a message to a recipient, say Bob, whose public key she knows, and
be confident that the message's contents will remain secret from anyone who
doesn't know Bob's private key.

Our notion of security is the standard find-then-guess notion of
indistinguishability under chosen-ciphertext attack, as described in
\cite{Bellare:1998:RAN}, which also shows that this is sufficient to achieve
\emph{non-malleability} under chosen-ciphertext attack; see also
\cite{Bellare:1999:NME,cryptoeprint:1999:018,cryptoeprint:2006:228}.

\begin{definition}[Asymmetric encryption syntax]
  \label{def:ae-syntax}

  An \emph{asymmetric encryption scheme} is a triple $\proto{ae} = (G, E, D)$
  where $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{encryption algorithm} $E$ accepts a public key $X$ and a
    message $m \in \Bin^*$, and outputs a \emph{ciphertext} $c \gets E_X(m)$.
  \item The \emph{decryption algorithm} $D$ accepts a private key $x$ and a
    ciphertext $c$, and outputs $m \gets D_x(c)$ which is either a message $m
    \in \Bin^*$ or the distinguished symbol~$\bot$.  This decryption
    algorithm must be such that, for all messages $m \in \Bin^*$, if $(x, X)$
    is any key pair output by $G$, and $c$ is any ciphertext output by
    $E_X(m)$, then $D_x(c)$ outputs $m$. \qed
  \end{itemize}
\end{definition}

\begin{definition}[Asymmetric encryption security]
  \label{def:ae-security}

  Let $\Pi = (G, E, D)$ be an asymmetric encryption scheme.  An
  adversary~$A$'s ability to attack the security of $\Pi$ is measured using
  the following game.

  \begin{program}
    $\Game{ind-cca}{\Pi}(A, b)$: \+ \\
      $(x, X) \gets G()$; \\
      $(m_0, m_1, s) \gets A^{D_x(\cdot)}(\cookie{find}, X)$; \\
      $c^* \gets E_X(m_b)$; \\
      $b' \gets A^{D_x(\cdot)}(\cookie{guess}, s, c^*)$; \\
      \RETURN $b'$;
  \end{program}
  The adversary is required to produce two messages $m_0$ and $m_1$ of equal
  lengths at the end of its \cookie{find} stage, and is forbidden from
  querying its decryption oracle $D_x(\cdot, \cdot)$ on the challenge
  ciphertext $c^*$ during the \cookie{guess} stage.

  The adversary's \emph{advantage} in this game us measured as follows.
  \[ \Adv{ind-cca}{\Pi}(A) =
       \Pr[\Game{ind-cca}(A, 1) = 1] -
       \Pr[\Game{ind-cca}(A, 0) = 1]
  \]
  Finally, the IND-CCA insecurity function of $\Pi$ is given 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 decryption oracles.
\end{definition}

\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
(without proofs) a number of constructions 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 $\proto{kem} =
  (\lambda, G, E, D)$ where $\lambda \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^\lambda$ 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^\lambda$ 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 $\lambda$-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 = (\lambda, 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^\lambda$; \\
      $(K_1, u) \gets E_X()$; \\
      $b' \gets A^{D_x(\cdot)}(X, u, K_b)$; \\
      \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 $\proto{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$ attacking $\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{Universal one-way hashing}
\label{sec:defs.uowhf}

\begin{definition}[Universal one-way hash function syntax]
  \label{def:uowhf.syntax}

  A \emph{universal one-way hash function} is a triple $\proto{h} = (\nu,
  \lambda, H)$ consisting of two positive integers $\nu$ and $\lambda$, and
  an algorithm $H$:
  \begin{itemize}
  \item The \emph{hashing algorithm} $H$ accepts as input a \emph{nonce}~$N
    \in \Bin^\nu$ and a message~$m \in \Bin^*$, and outputs an $\lambda$-bit
    hash $h \gets H_N(m)$.  \qed
  \end{itemize}
\end{definition}

\begin{definition}[Universal one-way hash function security]
  \label{def:uowhf.security}

  let $\Pi = (\nu, \lambda, H)$ be a universal one-way hash function.  We
  measure the \emph{advantage} of $A$ in attacking $\Pi$ by
  \[ \Adv{uow}{\Pi}(A) =
       \Pr[\textrm{$(m, \sigma) \gets A(\cookie{find})$;
           $N \getsr \Bin^\nu$; $m' \gets A(\cookie{guess}, N, m, \sigma)$}
         : H_K(m) = H_K(m')]
  \]
  Finally, the \emph{insecurity function} of $\Pi$ is given by
  \[ \InSec{uow}(\Pi; t) = \max_A \Adv{uow}{\Pi}(A) \]
  where the maximum is taken over all adversaries $A$ completing the game in
  time~$t$.
\end{definition}

%%%--------------------------------------------------------------------------
\section{Defining deniably authenticated encryption}
\label{sec:deny}

\subsection{Capturing the intuition}
\label{sec:deny.intuition}

The basic intuition behind deniably authenticated encryption is fairly clear.
If Bob sends a message Alice, then
\begin{itemize}
\item (authenticated) she should be able to have confidence that the message
  was sent by Bob;
\item (encryption) both she and Bob should be able to have confidence that
  nobody else could read the message; and
\item (deniably) nobody should later be able to convince a third party --
  Justin, say -- that Bob actually sent it.
\end{itemize}
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.

\subsubsection{Authenticated encryption}
An, Dodis and Rabin \cite{An:2002:SJS} study asymmetric authenticated
encryption and provide good definitions.  They consider authenticated
encryption in a multiparty setting, and deal with both `insider' and
`outsider' security.

The basic idea of their definitions is standard.  For secrecy, an adversary
chooses two messages, is given an encryption of one of them, and attempts to
guess which message was encrypted.  For authenticity, the adversary attempts
to construct a forged ciphertext which is accepted as authentic.  In both
cases, the adversary is provided with oracles which simulate the other
parties in the protocol: specifically, an encryption oracle simulating a
sender, and a decryption oracle simulating a recipient.

To properly model security in the multiparty setting, the encryption oracle
accepts as input a public key identifying the proposed recipient of the
ciphertext; and the decryption oracle accepts a public key of the claimed
sender.  The adversary may pass any purported public keys of its choosing to
these oracles, whether or not it knows the corresponding private keys.

The notion of outsider security assumes that the sender and recipient are
trusted, and captures attacks by third parties.  Accordingly, in the outsider
security setting, the adversary is given only the public keys of the sender
and recipient.  By contrast, insider security assumes that only one of the
participants is honest: in the secrecy game, the adversary is given the
sender's private key; and in the authenticity game, the adversary is given
the recipient's private key.  The idea of insider-secure secrecy doesn't seem
especially useful, though it does capture a kind of forward security.  The
notion of insider-secure authenticity captures a kind of non-repudiation
property which is explicitly contrary to our goals.  We therefore deal only
with outsider security.

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.

\subsubsection{Deniability}
Following our intuition above, we might 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 sample 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.

We could simply measure the simulator's ability to deceive Justin separately
for each message; but this would only give us convincing deniability for
messages which are independent of the key.  Instead, we split the deniability
game into two parts: one where Justin gets to choose two messages of his
choice (they don't have to be the same length, like they do for secrecy), and
one where he has to decide whether the ciphertext he's given is genuine or
simulated.

There are ways we could make the definition stronger.  For example, we might
consider auxiliary inputs, or even allow Justin to choose the public and
private keys himself, subject to being (more-or-less) distributed
correctly.\footnote{%
  This does actually have some merit as an idea.  Consider an (admittedly
  pathological) example.  Suppose that the scheme's private key includes an
  otherwise useless random group element $Q$, and that genuine ciphertexts
  contain a Diffie--Hellman pair $(r P, r Q)$ for random $r$, while simulated
  ciphertexts (for no good reason) contain a pair $(r P, s P)$ with random
  $r$ and $s$.  Distinguishing genuine ciphertexts from simulations on the
  basis of this pair is precisely the decision Diffie--Hellman problem, so
  Justin may well find it difficult; but if he knows $q$ such that $Q = q P$
  -- which isn't part of the private key -- then he'd find it easy.} %
We take the view that our definition is already sufficiently complicated and
unwieldy.

\subsection{Definitions for strong deniability}
\label{sec:deny.strong}

This gives us enough to define strong deniability.  As we shall see, however,
weak deniability is somewhat trickier to capture.

Following the discussion above, we define the syntax of a strongly deniable
authentication encryption scheme.  (Weakly deniable schemes will turn out to
be \emph{syntactically} different, which will be somewhat annoying.)

\begin{definition}[Strongly deniable AAE syntax]
  \label{def:sdaee-synax}

  A \emph{strongly deniable asymmetric authenticated encryption scheme}
  (SD-AAE) is a quadruple of (maybe randomized) algorithms
  $\proto{sdaae} = (G, E, D, R)$ 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 corresponding \emph{public key}.
  \item The \emph{encryption algorithm}~$E$ accepts as input 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 as input a private
    key~$x$, a public key~$Y$, and a ciphertext~$c$, and outputs $m \gets
    D_y(Y, M)$ which is either a message~$m \in \Bin^*$ or the distinguished
    symbol~$\bot$.  The decryption algorithm must be such that, for all key
    pairs $(x, X)$ and $(y, Y)$ output by $G$, all messages $m \in \Bin^*$,
    if $c$ is any output of $E_x(Y, m)$, then $D_y(X, c)$ outputs $m$.
  \item The \emph{recipient simulator}~$R$ accepts as input a private
    key~$x$, a public key~$Y$, and a message~$m \in \Bin^*$, and outputs a
    ciphertext $c \gets R_x(Y, m)$. \qed
  \end{itemize}
\end{definition}
The recipient simulator is syntactically like the encryption algorithm, but
semantically different.  In particular, the encryption algorithm is given the
sender's private key and the recipient's public key, while the recipient
simulator is given the sender's public key and the recipient's private key.

We now proceed to define the security notions.

\begin{definition}[Strongly deniable AAE security]
  \label{def:sdaae-security}

  Let $\Pi = (G, E, D, R)$ be a strongly deniable asymmetric authenticated
  encryption scheme.  An adversary $A$'s ability to attack the secrecy and
  authenticity of $\Pi$ is measured using the following games.
  \begin{program}
    $\Game{ind-occa}{\Pi}(A, b)$: \+ \\
      $(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 required
  to produce two messages $m_0$ and $m_1$ of equal lengths at the end of the
  \cookie{find} stage, and is forbidden from querying its decryption oracle
  $D_y(\cdot, \cdot)$ on the pair $(X, c^*)$ during the \cookie{guess} stage;
  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}{\Pi}(A, 1) = 1] -
        \Pr[\Game{ind-occa}{\Pi}(A, 0) = 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}

\begin{definition}[Strongly deniable AAE deniability]
  \label{def:sdaae-deny}

  Let $\Pi = (G, E, D, R)$ be a strongly deniable asymmetric authenticated
  encryption scheme.  The judge~$J$'s ability to distinguish simulated
  ciphertexts is defined by the following games.
  \begin{program}
    $\Game{sdeny}{\Pi}(J, b)$: \+ \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $(m, \sigma) \gets J(\cookie{find}, x, X, y, Y)$;
      \IF $b = 1$ \THEN $c \gets E_x(Y, m)$; \\
      \ELSE $c \gets R_y(X, m)$; \\
      $b' \gets J(\cookie{guess}, \sigma, c)$; \\
      \RETURN $b'$;
  \end{program}
  We measure $J$'s \emph{advantage} in distinguishing simulated ciphertexts
  from genuine ones by
  \[ \Adv{sdeny}{\Pi}(J) =
        \Pr[\Game{sdeny}{\Pi}(J, 1) = 1] -
        \Pr[\Game{sdeny}{\Pi}(J, 0) = 1] \]
  Finally, we define the \emph{insecurity function} for the (strong)
  deniability of $\Pi$ by
  \[ \InSec{sdeny}(\Pi; t) = \max_J \Adv{sdeny}{\Pi}(J) \]
  where the maximum is taken over all algorithms~$J$ completing the game in
  time~$t$.  We say that $\Pi$ is \emph{statistically deniable} if
  $\InSec{sdeny}(\Pi; t)$ is constant; if it is identically zero then we say
  that $\Pi$ is \emph{perfectly deniable}.
\end{definition}

\subsection{Intuition for weak deniability}
\label{sec:deny.weak-intuition}

If we followed our intuition, we'd define weak deniability by taking the
definition for strongly deniable AAE above, and simply giving the simulator a
sample ciphertext -- say $c_0$ in \xref{def:sdaae-deny}.

\subsubsection{Chameleon signatures}
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.

Chameleon signatures make use of 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 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 recipient, 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.

\subsubsection{A second simulator}
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} `sender' 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 commitment but different openings, then it's an Alice forgery; if the
commitments differ, then it's a Bob forgery.  If the sender simulator, which
isn't given Alice's trapdoor key, can make a second ciphertext using the same
commitment, then it has found a second opening of the commitment, which is a
binding failure.

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
  a general construction of a non-leaky scheme from a leaky one.} %
we must therefore define formally our weakly deniable schemes as `leaky'
encryption schemes which provide such hints.

\subsubsection{The secrecy and authenticity games}
The fact that the recipient simulator is given a sample ciphertext can affect
the secrecy and authenticity of the encryption scheme in surprising ways.
The generic weakly-deniable scheme described in \xref{sec:gwd.description}
provides an example of the problem.  We sketch the scheme very briefly here:
to encrypt a message, the sender uses a KEM to generate a pseudorandom
string, splits the string in half, signs one half, and encrypts the signature
and his message using a symmetric encryption scheme with the other half of
the string as a key; the ciphertext is the KEM clue and the symmetric
ciphertext.

It's a standard result that a scheme like this provides secrecy against
chosen-ciphertext attack if the KEM is secure and the symmetric encryption
scheme is secure against an adversary making only one encryption query --
i.e., a \emph{one-time} encryption scheme is sufficient for secrecy.  This is
very convenient: many symmetric encryption schemes, such as GCM
\cite{McGrew:2004:SPG}, require a nonce or IV input, which must (at least) be
distinct for each encryption.  A one-time encryption scheme can be
deterministic and stateless, perhaps using the same nonce all the time.  GCM
fails catastrophically if a nonce is reused: authentication fails completely,
and applying XOR-linear differences becomes easy.

Unfortunately, the way to construct simulated ciphertexts is to recover the
symmetric key from the sample ciphertext and encrypt the replacement message
with it, including the signature from the sample, and copying the sample KEM
clue.  We've therefore reused the symmetric key, so a one-time symmetric
encryption scheme is no longer suitable.  Indeed, if one used GCM with a
fixed nonce here, authenticity for the entire scheme would be lost.  It would
certainly be unfortunate if our security model failed to identify such a
defect!  From a practical point of view, users are unlikely to simulate
ciphertexts if simulation has a security cost, which argues in favour of
ciphertexts being genuine, and therefore compromises deniability.

The problem is that the simulator can poke about inside ciphertexts in ways
that the adversary cannot in the usual attack game.  To capture the effects
of simulators, then, we must allow adversaries to make use of them.  We shall
therefore provide an oracle for the recipient-simulator.

It's worth considering why we didn't need to provide an oracle for the
simulator in the strong deniability definition.  The intuitive reason is that
the simulator can't provide information about ciphertexts, because it doesn't
accept one as input.  The formal reason, as shown in the proof of
\xref{th:strong-weak}, is that we can replace simulations by real
encryptions using the deniability test.

It would be convenient if we could similarly show that access to the sender
simulator doesn't help an adversary attack weakly deniable schemes.  Alas,
this doesn't seem to be the case: certainly, it's not true that we can
necessarily simulate a sender-simulation oracle using the recipient
simulator.  To see this, consider the following contrived example: suppose
that legitimate ciphertexts contain a field $x$ which is uniformly
distributed on $\{0, 1, 2\}$, while a recipient-simulated ciphertext contains
$x_R = (x + 1) \bmod 3$ where $x$ is the value in the sample ciphertext; in
order to achieve weak deniability, the sender simulator must include $x_S =
(x - 1) \bmod 3$ due to the ordering of inputs to the judge -- but now, if
one is given a genuine ciphertext and a simulation constructed from it, one
can tell immediately whether the simulation was generated by the sender or
the receiver.

This kind of distinguishability doesn't immediately appear to be a
deniability failure \emph{per se} (but see \xref{sec:deny.sufficient}), but
it does suggest that the simulators exhibit undesirable artifacts.  Also,
correctly modelling the sender simulator in the attack games is very
complicated, because one must somehow account for the hints without simply
handing them to the adversary.  We therefore prefer to require
indistinguishability of genuine/recipient-simulated ciphertext pairs from
genuine/sender-simulated pairs for deniability, in \emph{addition} to the
existing requirement that genuine/recipient-simulated pairs be
indistinguishable from sender-simulated/genuine pairs.

The result of this chicanery is that, if we allowed adversaries to make $q_S$
sender-simulator oracle queries, then we'd get insecurity results up to $2
q_S \epsilon$ higher for secrecy and $q_S \epsilon$ for authenticity than the
apparent results neglecting sender-simulator queries, where $\epsilon$ is the
deniability insecurity to be defined later.  While this seems disconcerting,
\begin{itemize}
\item we expect, as a matter of course, that $\epsilon = 0$ -- as it is in
  our example constructions -- or at most very small, and certainly
  `negligible' should one take an asymptotic view, so this doesn't affect
  asymptotic results;
\item one would, presumably, be interested in using the simulators in
  practice only if $\epsilon$ were indeed small or zero; and
\item we may salve our consciences with the knowledge that, were we to
  provide adversarial access to the sender simulator, the secrecy and
  authenticity games would become fiendishly complicated.
\end{itemize}

\subsection{Definitions for weak deniability}
\label{sec:deny.weak}

\begin{definition}[Weakly deniable AAE syntax]
  \label{def:wdaae-syntax}

  A \emph{strongly deniable asymmetric authenticated encryption scheme}
  (SD-AAE) is a quintuple of (maybe randomized) algorithms
  $\proto{sdaae} = (G, E, D, R, S)$ 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 corresponding \emph{public key}.
  \item The \emph{encryption algorithm}~$E$ accepts as input a private
    key~$x$, a public key~$Y$, and a message~$m \in \Bin^*$, and outputs a
    pair $(c, \eta) \gets E_x(Y, m)$ consisting of a ciphertext~$c$ and a
    \emph{hint}~$\eta$.  If the hint is always $\bot$ then we say that the
    AAE scheme is \emph{non-leaky}; otherwise we say that it is \emph{leaky}.
  \item The \emph{decryption algorithm}~$D$ accepts as input a private
    key~$x$, a public key~$Y$, and a ciphertext~$c$, and outputs $m \gets
    D_y(Y, M)$ which is either a message~$m \in \Bin^*$ or the distinguished
    symbol~$\bot$.  The decryption algorithm must be such that, for all key
    pairs $(x, X)$ and $(y, Y)$ output by $G$, all messages $m \in \Bin^*$,
    if $(c, \eta)$ is any output of $E_x(Y, m)$, then $D_y(X, c)$ outputs
    $m$.
  \item The \emph{recipient simulator}~$R$ accepts as input a private
    key~$x$, a public key~$Y$, a ciphertext~$c$, and a message~$m \in
    \Bin^*$, and outputs a ciphertext $c' \gets R_x(Y, c, m)$.
  \item The \emph{sender simulator}~$S$ accepts as input a private key~$x$, a
    public key~$Y$, a ciphertext~$c$, a hint $\eta$, and a message~$m \in
    \Bin^*$, and outputs a ciphertext $c \gets S_x(Y, \eta, c, m)$.  \qed
  \end{itemize}
\end{definition}

\begin{definition}[Weakly deniable AAE security]
  \label{def:wdaae-security}

  Let $\Pi = (G, E, D, R, S)$ be a weakly deniable asymmetric authenticated
  encryption scheme.  An adversary $A$'s ability to attack the secrecy and
  authenticity of $\Pi$ is measured using the following games.
  \begin{program}
    $\Game{ind-occa}{\Pi}(A, b)$: \+ \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $(m_0, m_1, s) \gets
        A^{\bar{E}_x(\cdot, \cdot), D_y(\cdot, \cdot),
          R_y(\cdot, \cdot, \cdot)}
                (\cookie{find}, X, Y)$; \\
      $(c^*, \eta^*) \gets E_x(Y, m_b)$; \\
      $b' \gets
        A^{\bar{E}_x(\cdot, \cdot), D_y(\cdot, \cdot),
          R_y(\cdot, \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}(\cdot, \cdot),
        \id{rsim}(\cdot, \cdot, \cdot)}(X, Y)$; \\
      \RETURN $w$; \-
  \next
    $\bar{E}_x(Z, m)$: \+ \\
      $(c, \eta) \gets E_x(Z, m)$; \\
      \RETURN $c$; \-
    \\[\medskipamount]
    $\id{enc}(Z, m)$: \+ \\
      $(c, \eta) \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$; \-
    \\[\medskipamount]
    $\id{rsim}(Z, c, m')$: \+ \\
      $c' \gets R_y(Z, c, m')$; \\
      \IF $c' \ne \bot$ \THEN
        $\mathcal{C} \gets \mathcal{C} \cup \{ c' \}$; \\
      \RETURN $c'$; \-
  \end{program}

  In $\Game{ind-occa}{\Pi}$, the adversary is forbidden from querying its
  decryption oracle $D_y(\cdot, \cdot)$ on the pair $(X, c^*)$.  (It's fine
  to pass simulated ciphertexts from $R_y(\cdot, \cdot, \cdot)$ to the
  decryption oracle.)

  The adversary's \emph{advantage} in these games is measured as follows.
  \begin{eqnarray*}[c]
    \Adv{ind-occa}{\Pi}(A) =
        \Pr[\Game{ind-occa}{\Pi}(A, 1) = 1] -
        \Pr[\Game{ind-occa}{\Pi}(A, 0) = 1]
  \\[\medskipamount]
    \Adv{uf-ocma}{\Pi}(A) =
        \Pr[\Game{uf-ocma}{\Pi}(A) = 1]
  \end{eqnarray*}
  Finally, the IND-OCCA and UF-OCMA insecurity functions of $\Pi$ are given
  by
  \begin{eqnarray*}[c]
    \InSec{ind-occa}(\Pi; t, q_E, q_D, q_R) = \max_A \Adv{ind-occa}{\Pi}(A)
  \\[\medskipamount]
    \InSec{uf-ocma}(\Pi; t, q_E, q_D, q_R) = \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$, $q_D$, and $q_R$ queries to their
  encryption, decryption and recipient-simulator oracles, respectively.
\end{definition}

As we mentioned above, there are three kinds of pairs of ciphertexts which
ought to be hard to distinguish.  We describe three distinct subgames, $0$,
$1$, and $2$, and ask the adversary to output a guess as to which one it
played.  If we write $p_{ij}$ as the probability that the adversary outputs
$j$ when it was playing subgame~$i$, then we define its advantage as
$\max_{i, j \in \{0, 1, 2\}} p_{ii} - p_{ji}$.  Obviously the cases $i = j$
aren't very interesting, but it's simpler to leave them in anyway.

The reason that we structure the definition like this is that it gives us
very strong results to use in reductions.  Stepping from a game which works
like subgame~$i$ to one that works like subgame~$j$ \fixme

\begin{definition}[Weakly deniable AAE deniability]
  \label{def:wdaae-deny}

  Let $\Pi = (G, E, D, R, S)$ be a weakly deniable asymmetric authenticated
  encryption scheme.  The judge~$J$'s ability to distinguish simulated
  ciphertexts is defined by the following game.
  \begin{program}
    $\Game{wdeny}{\Pi}(J, i)$: \+ \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $(m_0, m_1, \sigma) \gets J(\cookie{find}, x, X, y, Y)$; \\
      \IF $i = 2$ \THEN \\ \ind
        $(c_0, \eta) \gets E_x(Y, m_0)$; \\
        $c_1 \gets R_y(X, c_0, m_1)$; \- \\
      \ELSE \IF $i = 1$ \THEN \\ \ind
        $(c_1, \eta) \gets E_x(Y, m_1)$; \\
        $c_0 \gets S_x(Y, \eta, c_1, m_0)$; \- \\
      \ELSE \IF $i = 0$ \THEN \\ \ind
        $(c_0, \eta) \gets E_x(Y, m_0)$; \\
        $c_1 \gets S_x(Y, \eta, c_0, m_1)$; \- \\
      $j \gets J(\cookie{guess}, \sigma, c_0, c_1)$; \\
      \RETURN $j$;
  \end{program}
  We measure $J$'s \emph{advantage} in distinguishing simulated ciphertexts
  from genuine ones by
  \[ \Adv{wdeny}{\Pi}(J) = \max_{i, j \in \{0, 1, 2\}}
        (\Pr[\Game{wdeny}{\Pi}(A, i) = i] -
         \Pr[\Game{wdeny}{\Pi}(A, j) = i])
  \]
  Finally, we define the \emph{insecurity function} for the (weak)
  deniability of $\Pi$ by
  \[ \InSec{wdeny}(\Pi; t) = \max_J \Adv{wdeny}{\Pi}(J) \]
  where the maximum is taken over all algorithms~$J$ completing the game in
  time~$t$.  We say that $\Pi$ is \emph{statistically deniable} if
  $\InSec{wdeny}(\Pi; t)$ is constant; if it is identically zero then we say
  that $\Pi$ is \emph{perfectly deniable}.
\end{definition}

\subsection{Discussion}
\label{sec:deny.discuss}

\subsubsection{Sufficiency of the simulators}
\label{sec:deny.sufficient}
As we've defined them, the various simulators expect to receive only
`genuine' ciphertexts, as generated by the encryption algorithm $E_x(Y, m)$.
Especially in the case of the weak-deniability sender simulator, the reader
may be wondering whether this indicates a lapse in the definition.

With a practical point of view, we may imagine that Alice, a user of a weakly
deniable AAE scheme, is confronted with a ciphertext forged by Bob.  If Alice
has the original ciphertext which Bob used as his sample, then she could
reveal it directly.  If the original contents were not to her liking, she
could also construct a sender-simulation from it.  That this will be
satisfactory is a direct consequence of weak deniability.  But \fixme

%% E,R/S,E and E,R/E,S are indistinguishable pairs
%% hence E,S/E,R/S,E and so R,E/E,S/E,R
%% want S,R/S,E, say

%% history is important!  want S(R),R(E)/S(E),E/E,R(E)  -- no, i've got lost
%% somewhere

%% want S(E),R(E)/E,R(E) or so

%% given E,R/S,E -> 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<q_E+q_R} \Pr[M_i]$.  It will suffice to show that
  \[ \Pr[M_i] \le \InSec{uow}(\proto{h}; t) \]
  But this follows immediately by a simple reduction: the \cookie{find} stage
  generates $X$ and $X'$ and outputs $[X, X']$; the \cookie{guess} stage
  receives a key $N^*$ to be used in responding to the $i$th oracle query,
  and simulates $\G0$.  The event $M_i$ is easy to detect: if it occurs, the
  reduction stops simulating the game and outputs the colliding key.

  We now bound $\Pr[S_1]$ by a reduction from IND-CCA security of
  $\proto{ae}$.  The reduction's \cookie{find} stage starts by generating
  authentication-token keys for the sender and recipient, and
  asymmetric-encryption keys for the sender.  It generates binding values for
  the sender and recipient.  Finally, it runs the \cookie{find} stage of $A$,
  providing simulated encryption, decryption and recipient-simulator oracles
  to be described later.  Eventually, $A$'s \cookie{find} stage completes,
  returning two messages $m_0$ and~$m_1$ of equal length.  The reduction
  computes a token $\tau^*$, chooses a key $N^* \inr \Bin^\nu$, computes
  $h^* = H_{N^*}([X, X'])$, and outputs $m^*_0 = \tau^* \cat N^* \cat h^*
  \cat m_0$ and $m^*_1 = \tau^* \cat N^* \cat h^* \cat m_1$, where $X$ and
  $X'$ are the public keys of the simulated sender.  These two strings
  clearly have the same length.

  The reduction's \cookie{guess} stage is then invoked with a challenge
  ciphertext~$c^*$.  It runs $A$'s \cookie{guess} stage on $c^*$, simulating
  the oracles in the way.  Finally, when $A$ outputs a guess $b'$, the
  reduction outputs the same guess.

  We now describe the simulated oracles provided by the reduction.  The only
  secret required by $\Pi$'s encryption algorithm is the authentication-token
  key, which the reduction chose at the beginning of the game, so the
  simulated encryption oracle can use the encryption algorithm directly.  The
  reduction simulates $A$'s decryption oracle using its own decryption
  oracle, thereby using one decryption query for each of $A$'s decryption
  queries; it verifies the token using the private key it chose earlier.
  Note that $A$ is forbidden from querying its decryption oracle at $c^*$
  using the sender's public key, though it may use a different public key.
  However, a different sender public key will either fail to match the public
  key hash embedded in $c^*$ or the game will abort, so such a query must
  output $\bot$.

  Finally, the reduction also uses its decryption oracle to implement its
  recipient-simulator oracle, using one decryption query for each of $A$'s
  recipient-simulator queries.  Again, there's a special case if the sample
  ciphertext is equal to $c^*$: in this case, the reduction performs the
  simulation by prepending $\tau^* \cat N \cat H_N([X, X'])$ to the query
  message for some fresh $N \inr \Bin^\nu$, and encrypting the result.

  Plainly, the reduction provides an accurate simulation for $A$, and
  achieves the same advantage; also, the reduction completes its game in the
  same time.  Therefore, by \xref{lem:advantage},
  \begin{equation} \label{eq:daae-tok.sec.s1}
    \Pr[S_1] \le \frac12 \InSec{ind-cca}(\proto{ae}; t, q_D + q_R) + \frac12
  \end{equation}
  The theorem follows by combining
  equations~\ref{eq:daae-tok.sec.s0}--\ref{eq:daae-tok.sec.s1}.
\end{proof}

\begin{theorem}[Authenticity of the authentication-token DAAE]
  \label{th:daae-tok.auth}

  Let $\proto{ae}$ and $\proto{tok}$ be an asymmetric encryption and
  an authentication token scheme, respectively.  Then
  \[ \InSec{uf-ocma}(\Xid{\Pi}{sdaae-tok}(\proto{ae}, \proto{tok});
        t, q_E, q_D) \le
       q_E \InSec{ind-cca}(\proto{ae}; t, q_D)
  \]
  and
  \begin{spliteqn*}
    \InSec{uf-ocma}(\Xid{\Pi}{wdaae-tok}(\proto{ae}, \proto{tok});
        t, q_E, q_D, q_R) \le \\
      (q_E + q_R) \InSec{ind-cca}(\proto{ae}; t, q_D + q_R) +
      \InSec{token}(\proto{tok}; t, q_E, q_D + q_R)
  \end{spliteqn*}
\end{theorem}
\begin{proof}
  Again, we give the proof in the weak deniability case: the strong
  deniability case is similar but easier.

  Let $A$ be any adversary attacking the authenticity of $\Pi =
  \Xid{\Pi}{wdaae-tok}$ and running within the stated resource bounds.  It
  suffices to bound $A$'s advantage, which we do using a sequence of games.
  Let $\G0 = \Game{uf-ocma}{\Pi}(A)$ be the original attack game.  In each
  game~$\G{i}$, let $S_i$ be the event that $A$ wins, i.e., that submits a
  valid forgery to its decryption oracle.  Our objective is then to bound
  $S_0$ from above.

  In game~$\G1$, we change the way that the encryption oracle works.
  Specifically, if the input public key is equal to the recipient public key,
  then rather than generating $\tau$ using the token-construction algorithm,
  it simply sets $\tau = 0^\kappa$.  We also change the decryption and
  recipient-simulator oracles so that they accept these modified ciphertext
  as being valid and, in the latter case, to propagate the fake token into
  the simulated ciphertext.

  We claim that
  \begin{equation} \label{eq:daae-tok.auth.s0}
    \Pr[S_0] - \Pr[S_1] \le
      (q_E + q_R) \InSec{ind-cca}(\proto{ae}; t, q_D + q_R)
  \end{equation}
  To prove the claim, we use a hybrid argument.  For $0 \le i \le q_E + q_R$,
  we define game~$\G[H]i$ to use fake tokens for the final $i$ encryption or
  simulator queries, but generate proper tokens for the first $q_E + q_R - i$
  queries.  If $T_i$ is the event that the adversary wins in $\G[H]i$, then
  the claim will follow if we can show that
  \[ \Pr[T_i] - \Pr[T_{i+1}] \le
       \InSec{ind-cca}(\proto{ae}; t, q_D + q_R)
  \]
  This we show by a reduction from the secrecy of $\proto{ae}$.  The
  reduction accepts a public key, which it uses for the recipient, and
  generates the other keys.  The \cookie{find} stage of the reduction runs
  $A$, using simulated oracles, until the $i$th encryption or simulation
  query; then, if $m$ is the input message, the reduction's \cookie{find}
  stage chooses $N \inr \Bin^\nu$, sets $h = H_N([X, X'])$, and outputs the
  two messages $\tau \cat N \cat h \cat m$ and $0^\kappa \cat N \cat h \cat
  m$, which are of equal lengths.  The \cookie{guess} stage of the reduction
  is given a challenge ciphertext $c^*$ corresponding to one of these
  plaintexts; it records $c^*$ and $m$, and resumes execution of $A$ until
  completion; finally, it outputs $1$ if $A$ submits a valid forgery and $0$
  otherwise.  The reduction's simulated decryption and simulator oracles
  detect the challenge ciphertext~$c^*$ and use the recorded message.
  Depending on which message was chosen by the IND-CCA game, the reduction
  simulates either $\G[H]i$ or $\G[H]{i+1}$; it outputs $1$ precisely when
  $T_i$ or $T_{i+1}$ occur in the respective cases, and the claim follows.

  Finally, we bound $\Pr[S_1]$, claiming
  \begin{equation} \label{eq:daae-tok.auth.s1}
    \Pr[S_1] \le \InSec{token}(\proto{tok}; t, q_E, q_D + q_R)
  \end{equation}
  Again, we prove this claim by a reduction, this time from the authenticity
  of $\proto{tok}$.  The \cookie{bind} stage of the reduction generates
  encryption keys for the sender and recipient and outputs encodings of them.
  The \cookie{guess} stage simulates $\G1$.  We handle an encryption query
  naming the recipient public key by using a `fake' token $0^\kappa$; for any
  other public key, we can use the token-construction oracle to generate a
  token.  For decryption and the recipient simulator, we must recognize
  ciphertexts from the encryption or recipient-simulator oracle and accept
  them as valid despite the invalid tokens; for other ciphertexts, we decrypt
  and use the token verification oracle.  If the decryption oracle receives a
  valid ciphertext with the sender public key, other than one constructed by
  the encryption or recipient-simulator oracles, then it must contain a valid
  authentication token between the sender and the recipient -- but $\G1$
  contains no mechanism for constructing such a token, so the token must have
  been forged.  The claim follows.

  Finally, the theorem follows from combining
  equations~\ref{eq:daae-tok.auth.s0} and~\ref{eq:daae-tok.auth.s1}.
\end{proof}

\begin{theorem}[Deniability of the authentication-token DAAE]
  \label{th:daae-tok.deny}

  Let $\proto{ae}$ and $\proto{tok}$ be an asymmetric encryption and
  an authentication token scheme, respectively.  Then
  \[ \InSec{sdeny}(\Xid{\Pi}{sdaae-tok}(\proto{ae}, \proto{tok}); t) =
        \InSec{deny}(\proto{tok}; t) \]
  and
  \[ \InSec{wdeny}(\Xid{\Pi}{wdaae-tok}(\proto{ae}, \proto{tok}); t) = 0 \]
\end{theorem}
\begin{proof}
  We prove the first statement by reduction.  Firstly, we show that
  \[ \InSec{sdeny}(\Xid{\Pi}{sdaae-tok}(\proto{ae}, \proto{tok}); t) \le
        \InSec{deny}(\proto{tok}; t)
  \]
  If $J$ is a judge distinguishing simulated ciphertexts in time~$t$ then we
  construct a judge~$J'$ distinguishing simulated tokens.  Recall the inputs
  to $J'$: the public and private keys $(x', X')$ of the sender and $(y',
  Y')$ of the recipient, a string~$s$, the recipient's binding value~$\beta$
  on $s$, an auxiliary input~$a$, and a (possibly simulated) token~$\tau$.
  If $s$ is the encoding of a public key $Y$ for $\proto{se}$, and $a = y$ is
  the corresponding private key, then $J'$ chooses a $\proto{se}$ key pair
  $(x, X)$ for the sender, computes $\alpha = B_{x'}([X])$, chooses a key~$N
  \in \Bin^\nu$, computes $h = H_N([X, X'])$, constructs a ciphertext $c =
  E_Y(\tau \cat N \cat h \cat m$ for some message~$m$, and runs $J$ giving it
  all of the keys and binding values, the message $m$ and the ciphertext $c$.
  Notice that $c$ is distributed exactly as a genuine ciphertext if $\tau$ is
  genuine, or as a simulated ciphertext if $\tau$ is simulated; hence we
  conclude that $J'$ distinguishes with advantage at most
  $\InSec{deny}(\proto{tok}; t)$.  Finally, we observe that the recipient's
  encryption key pair $(y, Y)$ is independent of the token key pair, so we
  can apply \xref{lem:random} to complete the proof of the inequality.

  Secondly, we show that
  \[ \InSec{sdeny}(\Xid{\Pi}{sdaae-tok}(\proto{ae}, \proto{tok}); t) \ge
        \InSec{deny}(\proto{tok}; t)
  \]
  We use a reduction in the other direction: given keys, a ciphertext and a
  judge~$J$ distinguishing tokens, we construct a judge~$J'$ distinguishing
  ciphertexts: simply decrypt the ciphertext using the recipient's decryption
  key, extract the token from the recovered plaintext, and pass it, together
  with the necessary keys, to $J$.

  The second statement is easier.  It suffices to observe that, in both the
  sender-simulator and recipient-simulator cases, both ciphertexts contain
  the same token, properly generated using the token-construction algorithm;
  they both contain hashes of the sender's public key using uniformly
  distributed keys, the appropriate messages, and are encrypted using the
  proper encryption algorithm.  Therefore all three distributions are
  identical and we have perfect weak deniability.
\end{proof}

\subsection{Authentication tokens using signatures}
\label{sec:tokens.sig}

In this section, we describe a simple, non-deniable, proof-of-concept
authentication token scheme using digital signatures.  Let $\proto{sig} = (G,
S, V)$ be a signature scheme with the property that all signatures are bit
strings of some constant length, i.e., there exists an integer $\kappa$ such
that, for all messages~$m$,
\[ \textrm{$(x, X) \gets G()$;
   $\sigma \gets S_x(m)$} : \sigma \in \Bin^\kappa
\]
This requirement is not especially onerous.  Most practical signature scheme
already this property already.  For those that do not, most will at least
produce signatures which can be encoded as a bounded-length string for
fixed-length messages, and this latter condition can be assured using a
universal one-way hash function.

If $\proto{sig} = (G, S, V)$ is a signature scheme producing $\kappa$-bit
signatures, then we define our token scheme
\[ \Xid{\Pi}{sig}(\proto{sig}) =
        (\kappa, \Xid{G}{sig}, \Xid{B}{sig}, \Xid{T}{sig},
                \Xid{V}{sig}, \Xid{R}{sig})
\]
where the component algorithms are as follows.
\begin{program}
  $\Xid{G}{sig}()$: \+ \\
    $(x, X) \gets G()$; \\
    \RETURN $(x, X)$; \-
\next
  $\Xid{B}{sig}_x(s)$: \+ \\
    \RETURN $\emptystring$; \-
  \\[\medskipamount]
  $\Xid{R}{sig}_x(Y, s, \alpha)$: \+ \\
    \RETURN $0^\kappa$; \-
\next
  $\Xid{T}{sig}_x(Y, s, \beta)$: \+ \\
    \IF $\beta \ne \epsilon$
    \THEN \RETURN $\bot$; \\
    $\tau \gets S_x(s)$; \\
    \RETURN $s$; \-
\next
  $\Xid{V}{sig}_x(Y, s, \alpha, \tau)$: \+ \\
    $v \gets V_Y(s, \tau)$; \\
    \RETURN $v$; \-
\end{program}

\begin{theorem}[Security of signature tokens]
  Let $\proto{sig}$ be a signature scheme producing $\kappa$-bit signatures.
  Then
  \[ \InSec{token}(\Xid{\Pi}{sig}(\proto{sig}; t, q_T, q_V) \le
        \InSec{euf-cma}(\proto{sig}; t, q_T)
  \]
\end{theorem}
\begin{proof}
  Immediate reduction.
\end{proof}

\begin{theorem}[Non-deniability of signature tokens]
  Let $\proto{sig}$ be a signature scheme producing $\kappa$-bit signatures.
  Let $R$ be any algorithm, and let $\Pi = (\kappa, \Xid{G}{sig},
  \Xid{B}{sig}, \Xid{T}{sig}, \Xid{V}{sig}, R)$, where $\Xid{G}{sig}$ etc.\
  are as defined above.  Then
  \[ \InSec{deny}(\Pi; t) \ge 1 - \InSec{euf-cma}(\Pi; t, 0) \]
\end{theorem}
\begin{proof}
  Let $J$ be the judge which applies the verification algorithm
  $\Xid{V}{sig}$ to its supplied public key and token, and outputs the
  result.  By correctness of $\proto{sig}$, $J$ will always output $1$ given
  a valid token.  Note that $R$ is not given the private signature key or any
  sample messages; therefore (immediate reduction) the probability that $R$
  outputs a valid signature is bounded above by $\InSec{euf-cma}(\Pi; t, 0)$.
\end{proof}

Toegether with the equality in \xref{th:daae-tok.deny}, this theorem shows a
separation between weak and strong deniability.

\subsection{Deniable authentication tokens from the Diffie--Hellman problem}
\label{sec:tokens.dh}

This section sketches a construction of a deniable authentication token whose
security is based on the difficulty of the computational Diffie--Hellman
problem.  A full analysis, alas, must wait for another time: the construction
makes use of non-interactive zero-knowledge proofs, and developing the
necessary definitions for a satisfactory concrete analysis would require too
much space.

We require the following ingredients:
\begin{itemize}
\item a group $G$ of prime order $p = \#G$, generated by an element $P$, such
  that elements of $G$ have fixed-length encodings;
\item a digital signature scheme $\proto{sig} = (G, S, V)$; and
\item a non-malleable non-interactive zero-knowledge (NIZK) proof of
  knowledge scheme.
\end{itemize}
The token scheme works as follows.
\begin{description}
\item[Key generation] A private key is a pair of scalars $x, \hat{x} \inr
  \gf{p}$; the corresponding public key is $(X, \hat{X}) = (x P, \hat{x} P)$.
\item[Binding] We are given a private key $x$ and a string $s$.  We generate
  a signature key pair $(x', X')$ and compute a signature $\sigma \gets
  S_{x'}(s)$.  The binding value a NIZK proof of knowledge of $x$, $X'$, and
  $\sigma$.
\item[Token construction] We are given a private key~$(x, \hat{x})$, a
  string~$s$, a binding value, and a public key $(Y, \hat{Y})$.  We verify
  the NIZK in the binding value.  If it is valid, the token is simply an
  encoding of $(x Y, x \hat{Y})$.
\item[Verification] Given a private key $(y, \hat{y})$, a public key~$(X,
  \hat{X})$, and a token $(Z, \hat{Z})$, we check that $(Z, \hat{Z}) = (y X,
  \hat{y} X)$.
\item[Simulation] Given a private key $(y, \hat{y})$ and a public key~$(X,
  \hat{X})$, we simulate the token as $(y X, \hat{y} X)$.
\end{description}
Perfect deniability is immediate.  Authenticity is somewhat trickier.  We
sketch a reduction from twin Diffie--Hellman, and use \xref{th:cdh-2dh}.

The reduction is given three group elements $X$, $Y$, and $\hat{Y}$ which
will serve as the two public keys: we can choose $\hat{x} \inr \gf{p}$
randomly and set $\hat{X} = \hat{x} P$.  The desired output is precisely the
corresponding authentication token.  The reduction runs the first stage of
the adversary, collecting strings to be bound to the keys.  The reduction
generates signing keys and simulates the NIZKs for the binding values (since
it doesn't know the corresponding private keys).  It then runs the second
stage of the adversary.

We now describe how the oracles are simulated.  The token-construction oracle
is given a public key $Q$, string $s$, and NIZK $\pi$; at least one of these
differs from the recipient's public keys and (simulated) NIZK.  If the NIZK
differs, we use the NIZK extractor to recover the signature, verification
key, and private key, verify the signature, and answer the query using the
extracted private key.  If the public key $Q$ differs from the recipient's
public key $Y$ but the NIZK matches then the proof of knowledge of the
private key must be invalid, so we reject.  Similarly, if $s$ is not equal to
the string bound to the recipient public key then the proof of knowledge of
the signature is probably invalid (reduction from forgery of $\proto{sig}$).
The verification oracle uses the twin-Diffie--Hellman verification oracle to
decide whether the token is correct.  This completes the sketch of the
reduction.

%%%--------------------------------------------------------------------------
\section{Non-interactive asymmetric integrity algorithms with deniability}
\label{sec:naiad}

In this section, we describe and define an important ingredient in our
strongly deniable scheme, which we term \emph{non-interactive asymmetric
  integrity algorithms with deniability}, or NAIAD for short.  The basic
setup is this.  Alice and Bob both have private keys, and know each others'
public keys.  (As mentioned in the introduction, the assumption that both
participants have keys is essential if we are to have non-interactive
deniable authentication.)  Alice has a message that she wants to send to Bob,
so that Bob knows that it came from Alice, but nobody can prove this to
anyone else.

This will be an essential ingredient in our quest for strongly deniable
authenticated encryption.  We could get away with using a signature
scheme for weak deniability, but a digital signature is clear evidence that a
communication occurred, and we should like to avoid leaving such traces.

\subsection{Definitions}
\label{sec:naiad.defs}

We have a fairly clear idea of what deniability and authentication should
mean now.  Since we have seen that signatures suffice for weakly deniable
encryption, we shall focus only on strong deniability.

\begin{definition}
  \label{def:naiad-syntax}

  A \emph{non-interactive asymmetric integrity algorithm with deniability}
  (NAIAD) is a quadruple $\proto{naiad} = (G, T, V, R)$ 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{tagging algorithm} $T$ accepts a private key~$x$, a public
    key~$Y$, and a message~$m \in \Bin^*$, and outputs a tag~$\tau \gets
    T_x(Y, m)$.
  \item The \emph{verification algorithm} $V$ accepts a private key~$x$, a
    public key~$Y$, a message~$m \in \Bin^*$, and a tag~$\tau$, and outputs a
    verdict $v \gets V_x(Y, m, \tau)$ which is a bit $v \in \{0, 1\}$.  The
    verification 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 $\tau$ is any
    tag produced by $T_x(Y, m)$, then $V_y(X, m, \tau)$ outputs~$1$.
  \item The \emph{recipient simulator} $R$ accepts a private key~$x$, a
    public key~$Y$, and a message~$m \in \Bin^*$, and outputs a tag~$\tau
    \gets S_x(Y, m)$. \qed
  \end{itemize}
\end{definition}

\begin{definition}
  \label{def:naiad-security}

  Let $\Pi = (G, T, V, R)$ be a NAIAD.  We measure an adversary~$A$'s ability
  to attack $\Pi$'s authenticity using the following game.
  \begin{program}
    $\Game{uf-ocma}{\Pi}(A)$: \+ \\
      $w \gets 0$;
      $\mathcal{T} \gets \emptyset$; \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $A^{\id{tag}(\cdot, \cdot), \id{vrf}(\cdot, \cdot)}(X, Y)$; \\
      \RETURN $v$; \-
  \newline
    $\id{tag}(Q, m)$: \+ \\
      $\tau \gets T_x(Q, m)$; \\
      \IF $Q = Y$ \THEN
        $\mathcal{T} \gets \mathcal{T} \cup \{ (m, \tau) \}$; \\
      \RETURN $\tau$; \-
    \next
    $\id{vrf}(Q, m, \tau)$: \+ \\
      $v \gets V_y(Q, m, \tau)$; \\
      \IF $v = 1 \land Q = X \land (m, \tau) \notin \mathcal{T}$ \THEN
        $w \gets 1$; \\
      \RETURN $v$;
  \end{program}

  The adversary's UF-OCMA \emph{advantage} is measured by
  \[ \Adv{uf-ocma}{\Pi}(A) = \Pr[\Game{uf-ocma}{\Pi}(A) = 1] \]
  Finally, the UF-OCMA insecurity function of $\Pi$ is defined by
  \[ \InSec{uf-ocma}(\Pi; t, q_T, q_V) = \max_A \Adv{uf-ocma}{\Pi}(A) \]
  where the maximum is taken over all adversaries~$A$ completing the game in
  time~$t$ and making at most $q_T$ tagging queries and at most $q_V$
  verification queries.
\end{definition}

\begin{definition}
  \label{def:naiad-deniability}

  Let $\Pi = (G, T, V, R)$ and $J$ (the `judge') be an algorithm.  The
  simulator's ability to deceive the judge is measured by the following
  games.
  \begin{program}
    $\Game{sdeny-$b$}{\Pi}(J, m_0, m_1)$: \+ \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $\tau_0 \gets T_y(X, m_0)$; \\
      $\tau_1 \gets R(x, Y, m_1)$; \\
      $b' \gets J(x, X, y, Y, \tau_b, m_b)$; \\
      \RETURN $b'$;
  \end{program}

  We measure $J$'s \emph{advantage} in distinguishing simulated tags from
  genuine ones by
  \[ \Adv{sdeny}{\Pi}(J) = \max_{m_0, m_1 \in \Bin^*} \bigl(
        \Pr[\Game{sdeny-$1$}{\Pi}(J, m_0, m_1) = 1] -
        \Pr[\Game{sdeny-$0$}{\Pi}(J, m_0, m_1) = 1] \bigr) \]
  Finally, we define the \emph{insecurity function} for the deniability of
  $\Pi$ by
  \[ \InSec{sdeny}(\Pi; t) = \max_J \Adv{sdeny}{\Pi}(J) \]
  where the maximum is taken over all algorithms~$J$ completing the game in
  time~$t$.
\end{definition}

\subsection{A NAIAD based on Diffie--Hellman}
\label{sec:naiad.dh}

We now present a simple NAIAD whose security in the random-oracle model is
based on the computational Diffie--Hellman problem.  We work in a cyclic
group $G$ with $p = \#G$ prime, generated by a point $P \in G$.  We assume a
hash function $H\colon \Bin^* \to \Bin^\kappa$, which we model as a random
oracle.  The scheme is
\[ \proto{dh}^H(G) =
        (\Xid{G}{dh}, \Xid{T}{dh}^H, \Xid{V}{dh}^H, \Xid{R}{dh}^H)
\]
where the algorithms are defined as follows.
\begin{program}
  $\Xid{G}{dh}()$: \+ \\
    $x \getsr \gf{p}$;
    $x' \getsr \gf{p}$; \\
    $X \gets x P$;
    $X' \gets x' P$; \\
    \RETURN $\bigl((x, x'), (X, X')\bigr)$; \-
\next
  $\Xid{T}{dh}^{H(\cdot)}_{x, x'}((Y, Y'), m)$: \+ \\
    $\tau \gets H([m, x P, x' P, Y, Y', x Y, x Y', x' Y, x' Y'])$; \\
    \RETURN $\tau$; \-
  \\[\medskipamount]
  $\Xid{V}{dh}^{H(\cdot)}_{x, x'}((Y, Y'), m, \tau)$: \+ \\
    $\tau' \gets H([m, Y, Y', x P, x' P, y X, y' X, y X', y' X'])$; \\
    \IF $\tau = \tau'$ \THEN \RETURN $1$
    \ELSE \RETURN $0$; \-
  \\[\medskipamount]
  $\Xid{R}{dh}^{H(\cdot)}_{x, x'}((Y, Y'), m, \tau)$: \+ \\
    $\tau' \gets H([m, Y, Y', x P, x' P, y X, y' X, y X', y' X'])$; \\
    \RETURN $\tau'$;
\end{program}

\begin{theorem}[Deniability of Diffie--Hellman NAIAD]
  Let $\Pi = \proto{dh}^H(G)$ be as described above.  Then $\Pi$ is
  perfectly deniable; i.e.,
  \[ \InSec{sdeny}(\Pi; t, q_H) = 0 \]
\end{theorem}
\begin{proof}
  There is precisely one correct tag for a given message from a given sender
  to a given recipient, and it can be computed either by the tagging
  algorithm or by the simulator.
\end{proof}

\begin{theorem}[Security of Diffie--Hellman NAIAD]
  \label{th:dh-security}

  Let $\Pi = \proto{dh}^H(G)$ be as described above.  Then
  \[ \InSec{uf-ocma}(\Pi; t, q_T, q_V, q_H) \le
        \InSec{cdh}(G; t + t') +
        \frac{2 q_H}{\#G} + \frac{q_V}{2^\kappa}
  \]
  where the $t'$ is the time taken to perform $4 q_H + 4$ multiplications and
  $2 q_H + 2$ additions in $G$, and $q_T + q_V + q_H$ hashtable probes and
  insertions.
\end{theorem}
\begin{proof}
  Let~$A$ be any adversary which attacks the authenticity of $\Pi$ and runs
  within the stated resource bounds.  It will suffice to bound $A$'s
  advantage.

  Game~$\G0 \equiv \Game{uf-ocma}{\Pi}(A)$ is the standard NAIAD attack game:
  $A$ receives $X = x P$, $X' = x' P$, $Y = y P$, and $Y' = y' P$ as input;
  its objective is to submit a forgery to its verification oracle.

  In order to simplify our presentation, we shall describe the tagging and
  verification functions in a different way.  Firstly, we define the function
  $D\colon G^4 \to G^8$ by
  \[ D(x P, x' P, Y, Y') = (x P, x' P, Y, Y', x Y, x Y', x' Y, x' Y') \]
  (This function is clearly not easily computable, though it becomes so if we
  know $x$ and $x'$.)  $D$ is evidently injective, because it includes its
  preimage in the image.

  Next, we define a simple permutation $\pi\colon G^8 \to G^8$ by
  \[ \pi(X, X', Y, Y', Z, Z', W, W') = (Y, Y', X, X', Z, W, Z', W') \]
  (It's not important, but $\pi = \pi^{-1}$.) If we define $D' = \pi \circ D$
  then
  \[ D(Y, Y', X, X') = D'(X, X', Y, Y') \]
  Finally, for any message~$m$, we define $H_m\colon G^8 \to \Bin^\kappa$ by
  \[ H_m(X, X', Y, Y', Z, Z', W, W') = H([m, X, X', Y, Y', Z, Z', W, W']) \]
  We can now define
  \[ T_m = H_m \circ D \qquad \textrm{and} \qquad
     V_m = H_m \circ D' = H_m \circ \pi \circ D \]
  i.e., the following diagram commutes.
  \[ \begin{tikzpicture}
    \tikzset{
      every to/.style = {above, draw, font = \footnotesize},
      every edge/.style = {every to},
      node distance = 20mm
    }
    \node (xy) {$G^4$};
    \node[coordinate, below = of xy] (x) {};
    \node[left = 5mm of x] (d) {$G^8$}
        edge [<-, left] node {$D$} (xy);
    \node[right = 5mm of x] (dd) {$G^8$}
        edge [<-, right] node {$D'$} (xy);
    \draw ($(d.east) + (0, 2pt)$)
        to[->] 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<q_E} (T_i - T_{i+1})
  \]

  In game~$\G2$, we no longer credit the adversary with a win for any forgery
  attempt $(u, c, \sigma)$ if $u = u_i$ for some $0 \le i < q_E$ such that
  $Q_i = Y$.  Let $F_2$ be the event that the adversary makes a decryption
  query that, in $\G1$, would be a valid forgery, but which is rejected in
  $\G2$; then (\xref{lem:shoup})
  \begin{equation} \label{eq:wdaae-tag.auth.s1}
    \Pr[S_1] - \Pr[S_2] \le \Pr[F_2]
  \end{equation}
  For each $0 \le i < q_E$, let $E_i$ be the event that the adversary makes a
  decryption query $(u_i, c, \sigma)$ which would have been a valid forgery
  in $\G1$ but is not in $\G2$.  Then $F_2 = \bigvee_{0\le i<q_E} E_i$ so
  \[ \Pr[F_2] \le \sum_{0\le i<q_E} \Pr[E_i] \]
  We claim that
  \[ \Pr[E_i] \le \InSec{int-ctxt}(\proto{aead}; t, 1 + q_R, q_D) \]
  and it will therefore follow that
  \begin{equation} \label{eq:wdaae-tag.auth.f2}
    \Pr[F_2] \le q_E \InSec{int-ctxt}(\proto{aead}; t, 1 + q_R, q_D)
  \end{equation}
  We prove the claim by a reduction from authenticity of the AEAD scheme.
  The reduction generates keys for the sender and recipient and simulates
  $\G1$, with the following exceptions.  If $Q_i = Y$ then the reduction
  generates $\tau_i$ at random, but doesn't bother choosing $K_i$: rather, it
  uses the AEAD encryption oracle to determine $c_i$.  Similarly, when
  responding to a decryption query with clue $u_i$, it uses its AEAD
  decryption oracle to verify and decrypt the AEAD ciphertext; and it uses
  the AEAD encryption oracle to answer recipient-simulator queries with clue
  equal to $u_i$.  If $E_i$ occurs, then there must be a decryption query
  $(Y, Y', u_i, c, \sigma)$ with $(c, \sigma)$ not equal to $(c_i, \sigma_i)$
  or any of the ciphertext/signature pairs output by the recipient-simulator
  oracle with clue $u_i$.  But if this happens then the reduction will have
  submitted a valid ciphertext/header pair $(c, [\sigma])$, not output by the
  AEAD encryption oracle, proving the claim.

  In game~$\G3$, we no longer credit the adversary with a win for any forgery
  attempt $(u, c, \sigma)$ when $\tau = \mathcal{D}_y(u)[\kappa \bitsto
  \lambda] = \tau_i$ for any $0 \le i < q_E$ with $Q_i = Y$.  Let $F_3$ be
  the event that the adversary makes a decryption query that, in $\G2$, would
  be a valid forgery, but which is rejected in $\G3$; then (\xref{lem:shoup})
  \begin{equation} \label{eq:wdaae-tag.auth.s2}
    \Pr[S_2] - \Pr[S_3] \le \Pr[F_3]
  \end{equation}
  Note that the $\tau_i$ are each uniformly distributed, so a simple
  reduction (which we omit) shows that
  \begin{equation} \label{eq:wdaae-tag.auth.f3}
    \Pr[F_3] \le \InSec{ndir}(\proto{kem}, \lambda - \kappa, q_E; t, q_D)
  \end{equation}

  Let us pause to examine the situation in $\G3$.  Let $(X, X', u, c,
  \sigma)$ be a decryption query, and let $Z \gets \mathcal{D}_y(u)$, and
  $\tau = Z[\kappa \bitsto \lambda]$, then we must have $\tau \ne \tau_i$ for
  any $0 \le i < q_E$ with $Q_i = Y$.  We must also have $V_X([\tau, Y],
  \sigma) \to 1$; but the only signatures produced by the encryption oracle
  are on messages $[\tau_i, Q_i] \ne [\tau, Y]$.  Therefore the only avenue
  remaining to the adversary is to forge a signature.  Another simple
  reduction, which again we omit, shows that
  \begin{equation} \label{eq:wdaae-tag.auth.s3}
    \Pr[S_3] \le \InSec{euf-cma}(\proto{sig}; t, q_E)
  \end{equation}

  Finally, piecing together
  equations~\ref{eq:wdaae-tag.auth.s0}--\ref{eq:wdaae-tag.auth.s3} completes
  the proof.
\end{proof}

\begin{theorem}[Tag-signing weak deniability]
  \label{th:wdaae-tag.deny}

  Let $\proto{kem}$, $\proto{aead}$, and $\proto{sig}$ be a key-encapsulation
  mechanism, AEAD scheme and signature scheme, respectively.  Then
  \[ \InSec{wdeny}(\Xid{\Pi}{wdaae-tag}
        (\proto{kem}, \proto{aead}, \proto{sig}); t, q_E, q_D, q_R) = 0
  \]
\end{theorem}
\begin{proof}
  Inspection of the simulators reveals that any pair of ciphertexts submitted
  to the judge have the following structure: both ciphertexts contain the
  same properly-generated KEM clue and signature, and potentially different,
  but properly-generated AEAD encryptions of the appropriate messages.  They
  are therefore identically distributed.
\end{proof}

%%%--------------------------------------------------------------------------
\section{Generic weakly deniable construction}
\label{sec:gwd}

In this section we describe a generic construction meeting the definition of
`weak deniability' (\xref{sec:deny.weak}), 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})~$\proto{kem} = (\lambda, \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~$\proto{se} = (\kappa, E, D)$, secure against chosen-ciphertext
  attack and with integrity of ciphertexts (IND-CCA and INT-CTXT;
  \xref{def:se-security}), where $\kappa < \lambda$.
\item A digital signature (\xref{def:sig-syntax}) scheme~$\proto{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 $\lambda$-bit `key'~$Z$.
\item She splits $Z$ into a $\kappa$-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 $\lambda$-bit `key'~$Z$.
\item He splits $Z$ into a $\kappa$-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}
    \node[op = 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$};
    \draw[decorate, decoration = brace]
        (K.north west) -- (tau.north east)
        coordinate [pos = 0.5, above = 2.5pt] edge [<-] (kem);
    \node[box = green!20, right = of tau] (tau2) {$\tau$};
    \node[box = blue!20, right = -0.6pt of tau2] (B) {$B$};
    \node at (B |- kem) {$B$} edge [->] (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<q_E} (\Pr[T_i] - \Pr[T_{i+1}]) \\
    & \le q_E \InSec{ind-cca}(\proto{kem}; t, q_D + q_R)
  \end{eqnarray*}

  For all $0 \le i < q_E$, let $\mathcal{Y}_i$ be the set of symmetric
  ciphertexts output by the encryption oracle or the recipient-simulator
  oracle with sender public key $X$ and clue $u_i$; i.e,,
  \[ \mathcal{Y}_i =
        \{ y_i \} \cup \{\, \hat{y}'_j \mid
                \hat{Q}_j = X \land \hat{u}_j = u_i \,\}
  \]
  Game~$\G2$ is the same as $\G1$, except that
  \begin{itemize}
  \item the decryption oracle returns $\bot$ whenever a query is made with
    $u^*_j = u_i$ and $y^*_j \notin \mathcal{Y}_i$, where $u_i$ is any clue
    returned by the encryption oracle so far; and
  \item the recipient-simulator oracle returns $\bot$ if $\hat{u}_j = u_i$
    and $\hat{y}_j \notin \mathcal{Y}_i$.
  \end{itemize}
  Let $F_2$ be the event that a query of this form is rejected in $\G2$,
  when it would be accepted in $\G1$.  By \xref{lem:shoup} we have
  \begin{equation}
    \label{eq:gwd-auth-s2}
    \Pr[S_1] - \Pr[S_2] \le \Pr[F_2]
  \end{equation}
  We claim that
  \begin{equation}
    \label{eq:gwd-auth-f2}
    \Pr[F_2] \le q_E \InSec{int-ctxt}(\proto{se}; t, 1 + q_R, q_D + q_R)
  \end{equation}
  Again the proof of this claim proceeds by a hybrid argument: we introduce
  hybrid games $\G[H]{i}'$ for $0 \le i \le q_E$ in which symmetric
  ciphertexts in $\mathcal{Y}_\kappa$ are rejected if $0 \le \kappa < i$; so
  \[ \G[H]0' \equiv \G1 \qquad \textrm{and} \qquad \G[H]{q_E}' \equiv \G2 \]
  Let $0 \le i < q_E$.  Let $T'_i$ be the event that a ciphertext is rejected
  in $\G[H]{i+i}'$ which was not in $\G[H]i'$.  If this occurs, then we must
  have
  \[ u^*_j = u_i \textrm{,} \qquad
     y^*_j \notin \mathcal{Y}_i \textrm{,} \qquad \textrm{and} \qquad
     D_{K_i}(y^*_j) \ne \bot
  \]
  or
  \[ \hat{u}_j = u_i \textrm{,} \qquad
     \hat{y}_j \notin \mathcal{Y}_i \textrm{,} \qquad \textrm{and} \qquad
     D_{K_i}(\hat{y}_j) \ne \bot
  \]
  $K_i$ is random in all of these games, so a simple reduction shows that
  \[ \Pr[T'_i] \le
        \InSec{int-ctxt}(\proto{se}; t, 1 + q_R, q_D + q_R)
  \]
  The reduction uses the INT-CTXT encryption oracle to perform the $i$th
  encryption query, and decryption oracle to respond to any decryption query
  with $u^*_j = u_i$, and both decryption and encryption oracles to respond
  to recipient-simulator queries with or with $\hat{u}_j = u_i$.

  If $F_2$ occurs then $y^*_j \notin \mathcal{Y}_i$ or $\hat{y}_j \notin
  \mathcal{Y}_i$ is an INT-CTXT forgery.  Since the $T'_i$ form a partition
  of $F_2$,
  \[ \Pr[F_2] = \sum_{0 \le i < q_E} T'_i \le
        q_E \InSec{int-ctxt}(\proto{se}; t, 1 + q_R, q_D + q_R) \]
  and the claim is proven.

  Game~$\G3$ is the same as~$\G2$, except that the encryption oracle no
  longer includes a valid signature in some ciphertexts, as follows.  Let $n
  = \len([\sigma])$ is the length of an encoded signature.  Then, if $Q_i =
  Y$, then we set $y_i = E_K(0^n \cat m_i)$ when encrypting message~$m_i$.
  Other encryption queries are not affected.  We claim that
  \begin{equation}
    \label{eq:gwd-auth-g3}
    \Pr[S_2] - \Pr[S_3] \le q_E \InSec{ind-cca}(\proto{se}; t, 1, 0)
  \end{equation}
  Again we use a hybrid argument: we introduce hybrid games $\G[H]{i}''$ for
  $0 \le i \le q_E$ in which the first $i$ encryption queries are performed
  as in $\G3$ and the remaining $q_E - i$ queries are performed as in $\G2$.
  Hence we have
  \[ \G[H]0'' \equiv \G2 \qquad \textrm{and} \qquad
        \G[H]{q_E}'' \equiv \G3
  \]
  Let $T''_i$ be the event that the adversary outputs a good forgery in
  $\G[H]{i}''$.  A reduction to symmetric IND-CCA security shows that
  \[ \Pr[T''_i] - \Pr[T''_{i+1}] \le
        \InSec{ind-cca}(\proto{se}; t, 1 + q_R, 0)
  \]
  The reduction works by querying the IND-CCA encryption oracle for the $i$th
  query, using the pair $0^n \cat m_i$ and $[\sigma_i] \cat m_i$; other
  queries are encrypted by generating $Z_i \inr \Bin^\lambda$ at random, as
  before.  We shall not require the decryption oracle: for decryption
  queries, if $u^*_j = u_i$ then either $y^*_j \in \mathcal{Y}_i$, in which
  case we set $m^*_j$ to the corresponding message (either $m_i$ or some
  $\hat{m}'_k$), or $y^*_j \ne y_i$ in which case we immediately return
  $\bot$; for recipient-simulator queries, if $\hat{u}_j = u_i$, we return
  $\bot$ if $\hat{y}_j \notin \mathcal{Y}$, and compute $\hat{y}'_j$ by
  encrypting $0^n \cat \hat{m}_j$ otherwise.  Other decryption and
  recipient-simulator queries are answered using the KEM private key as
  usual.  The claim follows because
  \begin{eqnarray*}[rl]
    \Pr[S_0] - \Pr[S_1]
    & = \Pr[T_0] - \Pr[T_{q_E}] \\
    & = \sum_{0\le i<q_E} (\Pr[T''_i] - \Pr[T''_{i+1}]) \\
    & \le q_E \InSec{ind-cca}(\proto{se}; t, 1 + q_R, 0)
  \end{eqnarray*}

  Observe that in $\G3$ we never generate a signature on a message of the
  form $[\tau, Y]$.  In order to generate a forgery in this game, though, the
  adversary must construct such a signature.  We can therefore bound
  $\Pr[S_2]$ using a reduction to the authenticity of $\proto{sig}$:
  \begin{equation}
    \label{eq:gwd-auth-s3}
    \Pr[S_2] \le \InSec{euf-cma}(\proto{sig}; t, q_E)
  \end{equation}
  The reduction uses the signing oracle in order to implement $A$'s
  encryption oracle.  Because no signing queries are on messages of the form
  $[\tau, Y]$, and a successful forgery for $\Pi$ must contain a signature
  $\sigma^*_j$ for which $V_{X'}([\tau^*_j, Y])$ returns $1$, our reduction
  succeeds whenever $A$ succeeds in $\G2$.  The claim follows.

  We can bound the advantage of adversary~$A$ by combining
  equations~\ref{eq:gwd-auth-s0}--\ref{eq:gwd-auth-s3}:
  \begin{eqnarray*}[rLl]
    \Adv{uf-ocma}{\Pi}(A)
    & =   \Pr[S_0] \\
    & \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{eqnarray*}
  and the theorem follows.
\end{proof}

\subsection{Variants}
\label{sec:gwd.variant}

\subsubsection{Exposing the signature}
The authenticity of our scheme requires that the signature~$\sigma$ be
encrypted.  Why is this?  What are the consequences if it isn't encrypted?

For secrecy, it's sufficient that the signature is covered by the symmetric
encryption's authenticity.  A scheme for authenticated encryption with
additional data (AEAD) \cite{Rogaway:2002:AEA} would suffice, placing the
signature in the AEAD scheme's header input.  (The reader may verify that the
proof of \ref{th:gwd-secrecy} still goes through with minimal changes.)

This is not the case for authenticity.\footnote{%
  We therefore find ourselves in the rather surprising position of requiring
  authenticity of the signature for secrecy, and secrecy of the signature for
  authenticity!} %
The problem is that it might be possible, through some backdoor in the
decapsulation function, to `direct' a KEM to produce a clue which
encapsulates a specified string.  The security definition can't help us: it
deals only with honest users of the public key.  Furthermore, some signature
schemes fail to hide the signed message -- indeed, signature schemes `with
message recovery' exist where this is an explicit feature.

Suppose, then, that we have such a `directable' KEM and a non-hiding
signature scheme: we'd attack our deniable AAE scheme as follows.  Request an
encryption of some arbitrary message~$m$ for the targetted recipient, extract
the tag from the signature, generate a random symmetric key, and construct a
KEM clue which encapsulates the symmetric key and tag.  Now we send the clue,
copy the signature from the legitimate ciphertext, and encrypt a different
message, using the hash as additional data.

We note that practical KEMs seem not to be `directable' in this manner.  KEMs
which apply a cryptographic hash function to some value are obviously hard to
`direct'.  KEMs based on Diffie--Hellman are likely to be undirectable anyway
assuming the difficulty of extracting discrete logarithms -- which is of
course at least as hard as computational Diffie--Hellman.

\subsubsection{Non-leaky encryption}
We briefly sketch a variant of our weakly deniable scheme which doesn't need
to leak the symmetric key -- and therefore the sender doesn't need to
remember the symmetric key for every message he sends.  We use Krawczyk and
Rabin's trick \cite{cryptoeprint:1998:010}.

We include, in each participant's private key, a key~$R$ for the symmetric
encryption scheme.  When encrypting a message, a sender computes an
additional ciphertext $d = E_R(K)$, and includes $d$ in the computation of
the signature $\sigma = S_{x'}([Y, \tau, d])$ and in the combined ciphertext.
This doesn't affect authenticity, but secrecy degrades by
$\InSec{euf-cma}(\proto{sig}; t, q_E)$, since we must appeal to
unforgeability of the signatures in order to demonstrate that a decryption
query with a reused clue will be rejected unless the rest of the ciphertext
is also reused.

%%%--------------------------------------------------------------------------
\section{Open problems}
\label{sec:open}

A number of problems remain outstanding.
\begin{itemize}
\item Can we formalize the requirement that a KEM be `non-directable' and
  construct efficient non-directable KEMs?  Is this sufficient to show that
  only authenticity of signatures are required in the generic scheme of
  \xref{sec:gwd}?  (This would obviate the constant-length requirement on the
  signature scheme.)
\item The NAIAD of \xref{sec:naiad.dh} requires four multiplications in the
  group.  These can be precomputed once per correspondent, but it still seems
  inefficient: can we construct a faster NAIAD?
\item Can we construct a NAIAD with security in the standard model?
\item It might be that the non-interactive proof systems of Groth and Sahai
  \cite{Groth:2008:ENP,cryptoeprint:2007:155} can be used to make efficient
  magic tokens.  Is this really the case?  Can we achieve a similarly (or
  more) efficient scheme without requiring a pairing and/or with weaker
  intractability assumptions?
\end{itemize}

%%%--------------------------------------------------------------------------
\section{Acknowledgements}
\label{sec:ack}

I'm very grateful to Christine Swart for encouraging me to actually write
this up properly.  Thanks also to Matthew Kreeger for his helpful comments.

\bibliography{mdw-fixes,mdw-crypto,cryptography,cryptography2000,eprint,jcryptology,lncs1991,lncs1997b,lncs2001d,lncs2002b,rfc}

\end{document}

%%% Local variables:
%%% mode: LaTeX
%%% TeX-PDF-mode: t
%%% hs-minor-mode: nil
%%% outline-minor-mode: t
%%% End: