initial

[doc/deny] / pre-complication.tex

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

\documentclass{strayman}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[palatino, helvetica, courier, maths = cmr]{mdwfonts}
\usepackage{mdwtab, mathenv, mdwmath, crypto, mdwref, mdwlist}
\usepackage[mdwmargin]{mdwthm}
\usepackage{tikz}

\usetikzlibrary{fit,positioning,calc}

\numberwithin{theorem}{subsection}
\numberwithin{equation}{subsection}
\numberwithin{figure}{subsection}

\title{Deniably authenticated public-key encryption}
\author{Mark Wooding}

\def\Bin{\Sigma}
\def\random{\$}
\def\bitsto{\mathop{..}}
\let\emptystring\varepsilon
\let\emptyset\varnothing
\def\textnm#1{\text{\/\normalfont#1\/}}

\def\fixme{\marginpar{FIXME}}
\def\cn{\fixme\textsuperscript{[\textcolor{blue}{citation needed}]}}

\bibliographystyle{mdwalpha}

\begin{document}

\maketitle

\begin{abstract}
  We consider the notion of \emph{deniably authenticated asymmetric
    encryption}: briefly, Bob can encrypt a message and send the ciphertext
  to Alice; Alice (and nobody else other than maybe Bob) can decrypt the
  message; Alice is convinced that Bob actually sent the message; and nobody
  can prove this to anyone else.

  We present formal definitions of security for this new notion, and offer
  two efficient instantiations.  One is a generic construction, using any
  key-encapsulation mechanism, signature scheme, and symmetric authenticated
  encryption scheme, but it meets a relatively weak notion of deniability;
  the other has security based on the computational Diffie--Hellman problem
  and provides strong deniability, but the security is only proven in the
  random oracle model.
\end{abstract}

\newpage
\tableofcontents
\newpage

%%%--------------------------------------------------------------------------
\section{Introduction}
\label{sec:intro}

\subsection{Authenticated asymmetric encryption}
\label{sec:intro.aae}

Secure email protocols, such as PGP
\cite{Zimmermann:1995:PSC,rfc1991,rfc2440,rfc4880} and S/MIME
\cite{rfc2311,rfc2633,rfc3851} attempt to provide both \emph{secrecy} for the
messages they handle, and \emph{authenticity}.  The former property,
informally, means that Bob can send a message to Alice and be confident that
nobody else can read it.  The latter means that Alice can be confident that
the message was really sent by Bob.

This is commonly achieved by a generic sign-then-encrypt construction: the
message plaintext is signed using a standalone digital-signature algorithm
with the sender's private key, and then the message and its signature
together are encrypted with the recipient's public key
\[ y = E_A([m, S_b(m)]) \]
This construction, among others, is analysed by An, Dodis, and Rabin
\cite{An:2002:SJS,cryptoeprint:2002:046} and shown to provide formally
defined notions of secrecy and authenticity.

As noticed by Davis \cite{Davis:2001:DSE}, the sign-then-encrypt approach has
some surprising failure modes.  For example, Alice can re-encrypt the signed
message using, say, Carol's public key, and sent it on:
\[ y' = E_C([m, S_b(m)]) \]
this can obviously cause confusion if the message doesn't encode the identity
of the intended recipient.  But there are worse possibilities.  For example,
if Alice and Bob are having an affair, each signed-and-encrypted
\emph{billet-doux} becomes potential blackmail material: Alice might threaten
to publish the
\[ m, S_b(m) \]
if her demands aren't met.  If Alice is a journalist and Bob is a source,
leaking secrets to her, then the signed leaks are incriminating evidence.

The encrypt-then-sign construction makes this sort of `attack' less trivial,
but still possible.  The signature is applied to a ciphertext encrypted using
Alice's public key, so an \emph{unaided} third party should be unable to
verify that the ciphertext matches any particular claimed plaintext.  But
there will usually be some additional information that Alice can publish to
show the correlation.  For hybrid schemes, where an asymmetric encryption
scheme is used to transfer a symmetric key, publishing the symmetric key is
usually sufficient.  In the case of asymmetric schemes based on trapdoor
permutations (e.g., RSA \cite{Rivest:1978:MOD}) she can publish the preimage
of the ciphertext.  In the case of schemes based on Diffie--Hellman key
agreement (e.g., ElGamal's scheme \cite{ElGamal:1985:PKCb} or DLIES
\cite{cryptoeprint:1999:007,Abdalla:2001:DHIES,IEEE:2000:1363}) even
verifying the shared secret may be hard for third parties (this is the
decisional Diffie--Hellman problem), but Alice can additionally publish a
noninteractive zero-knowledge proof that the shared secret is
correct.\footnote{%
  We'll work in a group $(G, +)$ with $p = \#G$ prime and generated by $P$.
  Let $a \inr \gf{p}$ be Alice's private key, with $A = a P$.  For ElGamal,
  Bob encodes his message as $M \in G$, chooses $r \inr \gf{p}$, computes $R
  = r P$ and $Z = r A$, and sends $(R, Z + M)$ as his ciphertext.  Alice can
  publish $Z$, but must prove that $Z = a R$.  We assume a random oracle
  $H\colon G^2 \to \gf{p}$.  She chooses $u \inr \gf{p}$, computes $c = H(u
  P, u R)$ and $v = u - c a$, and publishes $(Z, c, v)$.  To verify, check
  that $H(v P + c A, v R + c Z) = c$.  Completeness is immediate; soundness
  holds by rewinding and mutating the random oracle -- one obtains a new $c'$
  and $v'$ for the same $u$, and can solve for $a$; and the simulator fixes
  up the random oracle after choosing $v$ at random.  The structure of this
  proof follows \cite{Maurer:2009:UZK}.} %

Similarly, `signcryption' schemes \cite{Zheng:1997:DSH} usually provide a
`non-repudiation' property.  \fixme

With this in mind, it seems a shame that most work on asymmetric
authentication concentrates on \emph{non-repudiation} -- ensuring that Bob's
signature (or equivalent) can be demonstrated to third parties, even without
Bob's later cooperation -- or even despite his opposition.

\subsection{Related work}
\label{sec:intro.related}

Dolev, Dwork, and Naor's work \cite{Dolev:1991:NC} on nonmalleable
cryptography defines a simple asymmetric authentication protocol.  If $m$ is
some message that Bob wants Alice to authenticate, he chooses a random string
$\rho$, and sends her $(m, \rho)$ encrypted using a nonmalleable encryption
scheme under Alice's public key.  To authenticate the message~$m$, Alice
replies with $\rho$.  The authors prove their protocol's security, on the
assumption that the encryption is nonmalleable, and comment without proof on
the `plausible deniability' that it offers.

Dwork, Naor, and Sahai \cite{cryptoeprint:1999:023} address deniability in
the context of concurrent zero-knowledge interactive proofs.  They improve
the \cite{Dolev:1991:NC} protocol, showing that the new version is deniable
under \emph{sequential} composition.  They also \fixme
%%% read this and finish description

Di~Raimondo and Gennaro \cite{Raimondo:2005:NAD} \fixme
%%% ought to actually read this

There is an active literature on the topic of deniably authenticated key
exchange, where the participants are confident that they are communicating
securely with each other, but are unable to prove this to a third party.
Di~Raimondo, Gennaro, and Krawczyk \cite{cryptoeprint:2006:280} define
deniably authenticated key exchange and prove deniability properties of some
IPSEC subprotocols.

The \emph{Off the Record} protocol for instant-messaging systems
\cite{Borisov:2004:OTR,Alexander:2007:IUA} provides strong deniability for
users, for example by publishing authentication keys at the ends of
conversations.  The Wrestlers key-exchange protocol
\cite{cryptoeprint:2006:386} provides strong deniability, and has been
implemented as part of a virtual private network system
\cite{Wooding:2001:TrIPE}.

Other related concepts include \emph{chameleon signatures} and \emph{ring
  signatures}.  A chameleon signature \cite{cryptoeprint:1998:010} allows a
designated recipient to satisfy himself as to the origin of a message, and to
create forgeries -- so the recipient is unable to convince third parties that
a message is authentic; however, the sender is able to prove a forgery, and a
failure to provide such proof may be considered an admission of authenticity.
(We shall discuss chameleon signatures further in \ref{sec:deny.weak}.)  A
ring signature\cn\ allows a sender to `hide' among a set of users -- without
their participation -- and sign a message in such a way as to convince a
recipient that some member of the set signed it, but with no way to determine
which.  (This differs from the group signatures of \cite{Chaum:1991:GS} in
two respects: firstly, the participants in a group signature scheme are
explicitly enrolled into it; and secondly, a group signature scheme includes
an authority who can reveal the individual participant who signed a
particular message.)

All of the deniable protocols described above are fundamentally
\emph{interactive}, and therefore unsuitable for use in an encryption scheme.
On the other hand, we have an advantage over the designers of plain deniable
authentication protocols, since we can assume that both the sender \emph{and}
the recipient have public keys.  This can be seen to be essential in a
non-interactive scheme as follows.  If an authentication scheme doesn't
somehow identify a specific recipient (or set of recipients) then either
everyone can verify authenticity or nobody can.  In the latter case, the
scheme is useless; in the former, it is undeniable.  An interactive protocol
can identify the recipient implicitly through the interaction.  A
non-interactive scheme doesn't have this luxury; the only means remaining is
to assume that the recipient knows something -- i.e., a private key.

\fixme Naccache \cite{Naccache:2010:ITC} asked
\begin{quote}
  Construct a non-interactive authenticated PKE scheme:
  \begin{itemize}
  \item Alice encrypts a message for Bob and mixes with it a secret.
  \item Bob can ascertain that the message cam from Alice.
  \item Bob cannot convey this conviction to anybody.
  \end{itemize}
\end{quote}

\subsection{Our contribution}
\label{sec:intro.contribution}

We provide formal definitions for deniably authenticated asymmetric
encryption.  We give a `strong' definition, which allows a sender to deny
convincingly ever having communicated with a recipient, and a `weak'
definition, where it may be possible to prove the fact of communication, but
not the contents.  (This latter definition turns out to be rather
complicated.)

We also describe simple and efficient schemes which meet these definitions of
security.  Our weakly deniable scheme is generic: it uses an asymmetric key
encapsulation mechanism, a digital signature scheme, and an authenticated
symmetric encryption scheme: security is proven in the standard model.  We
show that Diffie--Hellman key distribution \cite{Diffie:1976:NDC} is a basis
for a strongly deniable authenticated encryption scheme.  We describe such a
scheme and prove security, assuming the difficulty of the computational
Diffie--Hellman problem, in the random oracle model.

%%%--------------------------------------------------------------------------
\section{Preliminaries}
\label{sec:pre}

%% Key encapsulation ROR-CCA
%% IND-CCA for symmetric encryption
%% Asymmetric authenticated encryption -- outsider IND and UF
%% Timing of adversaries includes oracles and loading
%% Pseudorandom generator?  (Could just assume bigger KEM output)
%% Digital signatures EUF-CMA.

\subsection{Binary strings and encodings}
\label{sec:bin}

We write $\Bin = \{ 0, 1 \}$ as the set of binary digits; $\Bin^t$ is the set
of $t$-bit strings, and $\Bin^* = \bigcup_{0\le i} \Bin^i$ is the set of all
binary strings.  We write $\emptystring$ for the empty string.  If $m$ is a
binary string then $|m|$ is the length of $m$; so $m \in \Bin^{|m|}$, and
$|\emptystring| = 0$.  If $0 \le i < |m|$ then $m[i]$ is the $i$th bit of
$m$.  If $m$ and $n$ are two strings then $m \cat n$ is their concatenation;
we have $|m \cat n| = |m| + |n|$; $m \cat \emptystring = \emptystring \cat m
= m$; and $(m \cat n)[i] = m[i]$ if $i < |m|$ and $n[i - |m|]$ otherwise.  If
$0 \le i \le j \le |m|$ then $m[i \bitsto j]$ is the substring starting with
bit~$i$ and ending before bit~$j$ -- so $|m[i \bitsto j]| = j - i$, $m[i
\bitsto j][k] = m[i + k]$, and $m = m[0 \bitsto i] \cat m[i \bitsto j] \cat
m[j \bitsto |m|]$.

We shall assume the existence of a deterministic, unambiguous encoding of
integers, group elements, and other such objects, as bit strings.  Rather
than build a complicated formalism, we shall simply write $[a, b, c, \ldots]$
as the encoding of items $a$, $b$, $c$, \dots  If $n$ is an integer with $0
\le n < 2^k$ then $[n]_k$ is a $k$-bit encoding of $n$.

We assume the existence of a distinguished object~$\bot$ (pronounced
`bottom'), and a set of \emph{atomic symbols}, written in
\cookie{sans-serif}, whose purpose is simply to be distinct from all other
objects.

\subsection{Algorithms, oracles, and resource bounds}
\label{sec:alg}

We present algorithms using a fairly standard imperative notation.  We write
$x \gets \tau$ to mean that variable~$x$ is to be assigned the value of the
term~$\tau$.  If $S$ is a set, then $x \getsr S$ means that $x$ is to be
assigned an element of $S$ chosen uniformly and independently at random.
Variables are globally scoped.  Indentation is used to indicate the extent of
iterated and conditional fragments.

We make frequent use of implicit `destructuring' (or `pattern matching') in
algorithm descriptions: a tuple (in parentheses, as is conventional) or
encoded sequence (in square brackets) containing variables may appear on the
left of an assignment, or as a formal argument to a procedure, indicating
that the corresponding right-hand-side or actual argument is to be decoded
and split up according to the structure of the pattern

Oracles provided to algorithms are written as superscripts; the inputs
supplied in an oracle query are written as `$\cdot$'.

We work throughout in the tradition of concrete security, as initiated in
\cite{Bellare:1994:SCB}.  We consider adversaries operating under explicit
resource bounds of time and numbers of oracle queries, and provide explicit
bounds on their success probabilities and advantages.  We find that this
approach both simplifies presentation -- since we no longer have to deal with
families of objects indexed by security parameters or other artificial
features of the asymptotic approach -- and provides more practically useful
results.  (As an aside, we remark that, \cite{Goldreich:1997:FMCa}
notwithstanding, it's much easier to derive asymptotic results from concrete
ones than \emph{vice versa}.)

We make use of the random oracle model, as formalized in
\cite{Bellare:1993:ROP}.  Rather than give separate definitions for security
with random oracles, we shall quietly include a bound $q_H$ on an adversary's
random oracle queries when attacking a scheme which uses random oracles.

The model of computation used to measure running times is not specified -- or
especially important to our results.  We do note, however, that running times
\emph{include} the time taken by the `game' infrastructure, including any
time needed for oracles to compute their results.  In order to take into
account algorithms which make use of precomputed tables, we also include in
the running time a term proportional to the size of the algorithm's
description according to the (unspecified) computational model.

\subsection{Useful results}
\label{sec:handy}

The following lemma will be used in our security proofs.

\begin{lemma}[Difference lemma \cite{Shoup:2002:OR}]
  \label{lem:shoup}
  Let $S$, $T$, and $F$ be events such that
  \[ \Pr[S \mid \bar{F}] = \Pr[T \mid \bar{F}] \]
  Then
  \[ \Pr[S] - \Pr[T] \le \Pr[F] \]
\end{lemma}
\begin{proof}
  A simple calculation:
  \begin{eqnarray*}[rl]
    \Pr[S] - \Pr[T]
    & = (\Pr[S \land F] + \Pr[S \land \bar{F}]) -
        (\Pr[T \land F] + \Pr[T \land \bar{F}]) \\
    & = (\Pr[S \land F] - \Pr[T \land F]) +
        \Pr[\bar{F}] (\Pr[S \mid \bar{F}] - \Pr[T \mid \bar{F}]) \\
    & \le \Pr[F] \eqnumber[\qed]
  \end{eqnarray*}
\end{proof}

%%%--------------------------------------------------------------------------
\section{Definitions}
\label{sec:defs}

This section presents our formal definitions for the structure and security
properties of the cryptographic objects we'll be dealing with in the paper.
Most of the definitions are fairly standard; the only slightly unusual aspect
is that we deal with \emph{concrete} security, with explicit resource and
probability bounds, rather than asymptotic notions.  Therefore we don't need
to mention an explicit security parameter or deal with ensembles of
probability distributions.

We strongly prefer the concrete security treatment.  Asymptotic results
follow as trivial corollaries of our main results; but deriving concrete
security definitions and results from asymptotic statements is decidedly
nontrivial.

\subsection{Diffie--Hellman problems}
\label{sec:dh}

Throughout this section, let $(G, +)$ be a (necessarily cyclic) group of
prime order, written additively; let $p = \#G$ be its order, and let $P$ be a
generator of $G$.  In order to simplify notation, we shall think of $G$ as
being a $\gf{p}$-vector space; group elements (vectors) will be given
uppercase letters, while elements of $\gf{p}$ (scalars) will be given
lowercase letters.

The computational Diffie--Hellman problem in $G$ is to determine $x y P$
given only $x P$ and $y P$.  The problem is named after the authors of
\cite{Diffie:1976:NDC}, whose key distribution scheme relies on the
difficulty of this problem in the group $\gf{p}^*$ of units in a prime finite
field.

More formally, we use the following definition.

\begin{definition}[Computational Diffie--Hellman]
  \label{def:cdh}

  If $A$ is any algorithm, then its \emph{advantage} in solving the
  computational Diffie--Hellman problem (CDH) in $G$ is given by
  \[ \Adv{cdh}{G}(A) =
        \Pr[\textrm{$x \getsr \gf{p}$; $y \getsr \gf{p}$} :
                A(x P, y P) = x y P]
  \]
  The CDH insecurity function of $G$ is then
  \[ \InSec{cdh}(G; t) = \max_A \Adv{cdh}{G}(A) \]
  where the maximum is taken over all algorithms~$A$ completing the game in
  time~$t$.
\end{definition}

We shall also make use of the \emph{twin Diffie--Hellman} problem
\cite{cryptoeprint:2008:067}: given $x P$, $x' P$ and $y P$, to find $x y P$
and $x' y P$, given an oracle which can decide, given $(U, V, V')$, whether
$V = x U$ and $V' = x' U$.

\begin{definition}[Twin Diffie--Hellman]
  \label{def:2dh}

  An algorithm $A$'s ability to solve the twin Diffie--Hellman problem in a
  group~$G$ is measured using the following game.
  \begin{program}
    $\Game{2dh}{G}(A)$: \+ \\
      $x \getsr \gf{p}$;
      $x' \getsr \gf{p}$;
      $y \getsr \gf{p}$; \\
      $(Z, Z') \gets A^{\id{2dhp}(\cdot, \cdot, \cdot)}(x P, x' P, y P)$; \\
      \IF $Z = x y P \land Z' = x' y P$ \THEN \RETURN $1$ \ELSE \RETURN $0$;
  \- \\[\medskipamount]
    $\id{2dhp}(U, V, V')$: \+ \\
      \IF $V = x U \land V' = x' U$ \THEN \RETURN $1$ \ELSE \RETURN $0$;
  \end{program}
  If $A$ is any algorithm, then its \emph{advantage} in solving the twin
  Diffie--Hellman problem (2DH) in $G$ is given by
  \[ \Adv{2dh}{G}(A) = \Pr[\Game{2dh}{G}(A) = 1] \]
  Finally, the 2DH insecurity function of ~$H$ is given by
  \[ \InSec{2dh}(G; t, q) = \max_A \Adv{2dh}{G}(A) \]
  where the maximum is taken over all algorithms~$A$ completing the game in
  time~$t$ and making at most~$q$ queries to the \id{2dhp} oracle.
\end{definition}

This all seems rather artificial; but \cite{cryptoeprint:2008:067} relates
2DH security tightly to plain CDH security.  The main trick is as follows.
\begin{lemma}[Detecting 2DH triples]
  \label{lem:2dh-detect}

  Let $G$ be a cyclic group generated by~$P$, with prime order $p = \#G$.
  Let $X \in G$ be any group element; let $r$ and $s$ be any elements of
  $\gf{p}$, and set $X' = r P + s X$.  If $Y = y P$ for some $y \in \gf{p}$,
  and $Z$, $Z'$ are two further group elements, then
  \begin{enumerate}
  \item if $Z = y X$, then and $Z' = y X'$ if and only if $Z' = r Y + s Z$;
    and, conversely,
  \item if $Z \ne y X$ then there is precisely one possible value of $s$ for
    which $Z' = y Y + s Z$.
  \end{enumerate}
\end{lemma}
\begin{proof}
  For the first statement, suppose that $Z = y X$; then $y X' = y (r P + s X)
  = r (y P) + s (y X) = r Y + s Z$.  For the second, suppose now that $Z \ne
  y X$, but
  \[ Z' = r Y + s Z \]
  holds anyway.  We already have $X' = r P + s X$, so
  \[ y X' = r Y + s y X \]
  Subtracting the latter equation from the former gives
  \[ Z' - y X' = s (Z - y X) \]
  Since $Z - y X \ne 0$, it generates $G$; hence there is a single satisfying
  $s \in \gf{p}$ as claimed.
\end{proof}

\begin{theorem}[$\textrm{CDH} \Leftrightarrow \textrm{2DH}$]
  \label{th:cdh-2dh}

  Let $G$ be a cyclic group with prime order; then
  \[ \InSec{cdh}(G; t) \le
        \InSec{2dh}(G; t, q) \le
        \InSec{cdh}(G; t + t') + \frac{q}{\#G} \]
  where $t'$ is the time taken to perform two scalar multiplications and an
  addition in $G$.
\end{theorem}
\begin{proof}
  The first inequality is obvious.  For the second, suppose that $A$ is any
  algorithm for solving 2DH in~$G$.  Let $p = \#G$.  We define algorithm~$B$
  as follows.
  \begin{program}
    $B(X, Y)$: \+ \\
      $r \getsr \gf{p}$;
      $s \getsr \gf{p}$;
      $X' \gets r P + s X$; \\
      $(Z, Z') \gets A^{\id{2dhp}'(\cdot, \cdot, \cdot)}(X, X', Y)$; \\
      \IF $\id{2dhp}'(Y, Z, Z') = 1$ \THEN \RETURN $Z$ \ELSE \RETURN $\bot$;
  \- \\[\medskipamount]
    $\id{2dhp}'(U, V, V')$: \+ \\
      \IF $V' = r U + s V$ \THEN \RETURN $1$ \ELSE \RETURN $0$;
  \end{program}
  If $A$ runs in time $t$, then $B$ runs in time~$t + t'$ as stated: while
  $\id{2dhp}'$ works differently from $\id{2dhp}$, the simultaneous
  multiplication in the former can be done more efficiently than the two
  separate multiplications in the latter; so the only overhead is in the
  additional setup.

  We have $r$ uniform on $\gf{p}$ and independent of $s$, so $\Pr[X' = A] =
  \Pr[r P = A - s X] = 1/p$ for any constant~$A$, so $X'$ is uniform on $G$
  and independent of~$s$.  By \xref{lem:2dh-detect}, there are at most $q$
  values of $s$ which would cause $\id{2dhp}'$ to give an incorrect answer.
  The theorem follows.
\end{proof}

\subsection{Symmetric encryption}
\label{sec:se}

We shall require a symmetric encryption scheme; the syntax of such schemes is
straightforward.  The only slightly unusual feature of our definition is that
we require the key space to be a set of binary strings of a given length:
this will be important in what follows.

\begin{definition}[Symmetric encryption syntax]
  \label{def:se-syntax}

  A \emph{symmetric encryption scheme} is a triple $\Pi_\textnm{se} = (k, E,
  D)$, where $k \ge 0$ is a nonnegative integer, and $E$ and $D$ are (maybe
  randomized) algorithms, as follows.
  \begin{itemize}
  \item The \emph{encryption algorithm}~$E$ accepts a key $K \in \Bin^k$ and
    a message $m \in \Bin^*$, and outputs a ciphertext $c \gets E_K(m)$.
  \item The \emph{decryption algorithm}~$D$ accepts a key $K \in \Bin^k$ and
    a ciphertext $c$, and outputs $m = D_K(c)$ which is either a message $m
    \in \Bin^*$ or the distinguished symbol~$\bot$.  This decryption
    algorithm must be such that, for all $K \in \Bin^*$, and all messages $m
    \in \Bin^*$, if $c$ is any output of $E_K(m)$ then $D_K(c)$ outputs
    $m$. \qed
  \end{itemize}
\end{definition}

We define two security notions for symmetric encryption.

Our notion of secrecy is \emph{indistinguishability under chosen-ciphertext
  attack} (IND-CCA).  We choose a random key~$K$ for the symmetric encryption
scheme and provide the adversary with two oracles: an encryption oracle which
accepts two messages $m_0$ and $m_1$ of the same length, consistently chooses
either $m_0$ or $m_1$, encrypts it using the key~$K$, and returns the
resulting ciphertext $y = E_K(m_b)$; and a decryption oracle which accepts a
ciphertext and returns the corresponding plaintext or an indication that the
ciphertext was malformed.  The scheme is considered secure if no adversary
playing this game can determine whether the encryption oracle is encrypting
$m_0$ or $m_1$.  Since the game would be trivial if the adversary could ask
for decryption of ciphertexts returned by the encryption oracle, we forbid
(only) this.

Our notion of authenticity is \emph{integrity of ciphertexts} (INT-CTXT).
We choose a random key~$K$, and provide the adversary with two oracles: an
encryption oracle which encrypts a message provided as input and returns the
resulting ciphertext; and a decryption oracle which decrypts the ciphertext
provided as input and returns the plaintext or an indication that the
ciphertext was invalid.  The scheme is considered security if no adversary
playing this game can query its decryption oracle on a valid ciphertext which
wasn't returned by the encryption oracle.

These notions are standard; we take them from
\cite{Bellare:2000:AER,cryptoeprint:2000:025}.  Rogaway
\cite{cryptoeprint:2006:221} presents a rather more convenient definition
which combines both secrecy and authenticity into a single notion; this
definition is stronger than we need because it requires that ciphertexts be
indistinguishable from random data, rather than merely other ciphertexts.

\begin{definition}[Symmetric encryption security]
  \label{def:se-security}

  Let $\Pi = (k, E, D)$ be a symmetric encryption scheme.  An adversary~$A$'s
  ability to attack the security of $\Pi$ is measured using the following
  games.

  \begin{program}
    $\Game{ind-cca-$b$}{\Pi}(A)$: \+ \\
      $K \getsr \Bin^k$; \\
      $b' \gets A^{E_K(\id{lr}(\cdot, \cdot)), D_K(\cdot)}$; \\
      \RETURN $b'$;
    \next
    $\id{lr}(m_0, m_1)$: \+ \\
      \RETURN $m_b$;
  \newline
    $\Game{int-ctxt}{\Pi}(A)$: \+ \\
      $K \getsr \Bin^k$; \\
      $Y \gets \emptyset$; $w \gets 0$; \\
      $A^{\id{encrypt}(\cdot), \id{decrypt}(\cdot)}$; \\
      \RETURN $w$; \-
    \next
    $\id{encrypt}(m)$: \+ \\
      $y \gets E_K(m)$; \\
      $Y \gets Y \cup \{ y \}$; \\
      \RETURN $y$; \-
    \next
    $\id{decrypt}(y)$: \+ \\
      $m \gets D_K(y)$; \\
      \IF $m \ne \bot \land y \notin Y$ \THEN $w \gets 1$; \\
      \RETURN $m$; \-
  \end{program}

  In the IND-CCA games, we require that the two messages $m_0$ and $m_1$
  passed to the encryption oracle have the same length, and that the
  adversary not query its decryption oracle on any ciphertext produced by the
  encryption oracle.

  The adversary's \emph{advantage} in these games is defined as follows.
  \begin{eqnarray*}[c]
    \Adv{ind-cca}{\Pi}(A) =
        \Pr[\Game{ind-cca-$1$}{\Pi}(A) = 1] -
        \Pr[\Game{ind-cca-$0$}{\Pi}(A) = 1]
    \\[\medskipamount]
    \Adv{int-ctxt}{\Pi}(A) =
        \Pr[\Game{int-ctxt}{\Pi}(A) = 1]
  \end{eqnarray*}

  Finally, the IND-CCA and INT-CTXT insecurity functions of $\Pi$ are given
  by
  \begin{eqnarray*}[c]
    \InSec{ind-cca}(\Pi; t, q_E, q_D) = \max_A \Adv{ind-cca}{\Pi}(A)
  \\[\medskipamount]
    \InSec{int-ctxt}(\Pi; t, q_E, q_D) = \max_A \Adv{int-ctxt}{\Pi}(A)
  \end{eqnarray*}
  where the maxima are taken over all adversaries~$A$ completing the game in
  time~$t$ and making at most $q_E$ and $q_D$ queries to their encryption and
  decryption oracles, respectively.
\end{definition}

In fact, our constructions only require security against a single
chosen-plaintext query in order to achieve the usual notions of
indistinguishability and authenticity (\xref{sec:aae}).  However, in order to
prove deniability we shall have need to encrypt additional messages under the
same key, and it would be a shame to lose secrecy or authenticity as a
consequence.

Symmetric encryption schemes according to this definition can easily be
constructed using a generic `encrypt-then-authenticate' approach using a
symmetric encryption scheme secure against chosen-plaintext attack and a
message authentication code (MAC) secure against `strong' forgery under
chosen-message attack.\footnote{%
  Such schemes may fail to meet Rogaway's stronger definition because MAC
  tags need not be indistinguishable from random data.} %
Alternatively, there are dedicated schemes based on block ciphers, such as
OCB~\cite{Rogaway:2002:AEA,Rogaway:2001:OCB,cryptoeprint:2001:026},
CCM~\cite{rfc3610,Dworkin:2003:DRB} (but note \cite{cryptoeprint:2003:070})
and GCM~\cite{McGrew:2004:SPG}.

\subsection{Key encapsulation mechanisms}
\label{sec:kem}

A \emph{key encapsulation mechanism}, or KEM, is an asymmetric cryptographic
scheme for transferring a short random secret (e.g., a symmetric key) to a
recipient.  It differs from asymmetric encryption in that the KEM is
responsible for choosing the random string as part of its operation, rather
than having it be an input.  This makes efficient constructions simpler and
more efficient, and makes security reductions more efficient (and hence more
meaningful).

ElGamal's encryption scheme \cite{ElGamal:1985:PKCb} be seen, with copious
hindsight, as consisting of a KEM based on the Diffie--Hellman problem
combined with a symmetric encryption using the same group operation as a
one-time pad.  Zheng and Seberry \cite{Zheng:1993:PAA}, inspired by
Damg\aa{}rd's `modified ElGamal' scheme \cite{Damgaard:1991:TPP}, present a
number of constructions (without proofs) of asymmetric encryption schemes
secure against adaptive chosen-ciphertext attacks.  The DHIES scheme of
Abdalla, Bellare, and Rogaway
\cite{cryptoeprint:1999:007,Abdalla:2001:DHIES}, standardized in
\cite{IEEE:2000:1363}), uses a hash function to derive a symmetric key from
the Diffie--Hellman shared secret; they prove security against
chosen-ciphertext attack.  Finally, Shoup \cite{cryptoeprint:2001:112}
formalizes the notion of a key-encapsulation, and describes one (RSA-KEM,
formerly `Simple RSA') based on the RSA primitive \cite{Rivest:1978:MOD}.

\begin{definition}[Key encapsulation mechanism syntax]
  \label{def:kem-syntax}

  A \emph{key encapsulation mechanism} is a quadruple $\Pi_\textnm{kem} =
  (\ell, G, E, D)$ where $\ell \ge 0$ is a non-negative integer, and $G$, $E$
  and $D$ are (maybe randomized) algorithms, as follows.
  \begin{itemize}
  \item The \emph{key-generation algorithm} $G$ accepts no parameters and
    outputs a pair $(x, X) \gets G()$.  We call $x$ the \emph{private key}
    and $X$ the \emph{public key}.
  \item The \emph{encapsulation algorithm} $E$ accepts a public key $X$ and
    outputs a pair $(K, u) \gets E_X()$ where $K \in \Bin^\ell$ is a bit
    string, and $u$ is a `clue'.
  \item The \emph{decapsulation algorithm} $D$ accepts a private key $x$ and
    a clue $u$, and outputs $K \gets D_x(u)$ which is either a string $K \in
    \Bin^\ell$ or the distinguished symbol $\bot$.  The decapsulation
    algorithm must be such that if $(x, X)$ is any pair of keys produced by
    $G$, and $(K, u)$ is any key/clue pair output by $E_X()$, then $D_x(u)$
    outputs $K$. \qed
  \end{itemize}
\end{definition}

Our notion of security is indistinguishability from random under
chosen-ciphertext attack (IND-CCA).  We generate a key pair, and invoke the
encapsulation algorithm on the public key.  The adversary is provided with
the resulting KEM clue and an $\ell$-bit string.  It may query an oracle
which accepts a clue as input and returns the result of applying the
decapsulation algorithm to it using the private key.  The scheme is
considered secure if the adversary cannot determine whether its input string
was the output of the key encapsulation algorithm, or generated uniformly at
random and independently.  Since this game can be won easily if the adversary
is permitted query its decapsulation oracle on its input clue, we forbid
(only) this.

\begin{definition}[Key encapsulation mechanism security]
  \label{def:kem-security}

  Let $\Pi = (\ell, G, E, D)$ be a key encapsulation mechanism.  We measure
  an adversary~$A$'s ability to attack $\Pi$ using the following games.
  \begin{program}
    $\Game{ind-cca-$b$}{\Pi}(A)$: \+ \\
      $(x, X) \gets G()$; \\
      $K_0 \getsr \Bin^\ell$; \\
      $(K_1, u) \gets E_X()$; \\
      $b' \gets A^{D_x(\cdot)}(K_b, u)$; \\
      \RETURN $b'$;
  \end{program}
  In these games, the adversary is forbidden from querying its decapsulation
  oracle at the challenge clue $u$.

  The adversary's IND-CCA \emph{advantage} is measured by
  \[ \Adv{ind-cca}{\Pi}(A) =
        \Pr[\Game{ind-cca-$1$}{\Pi}(A) = 1] -
        \Pr[\Game{ind-cca-$0$}{\Pi}(A) = 1]
  \]
  Finally, the IND-CCA insecurity function of $\Pi$ is defined by
  \[ \InSec{ind-cca}(\Pi; t, q_D) = \max_A \Adv{ind-cca}{\Pi}(A) \]
  where the maximum is taken over all adversaries~$A$ completing the game in
  time~$t$ and making at most $q_D$ queries to their decapsulation oracles.
\end{definition}

\subsection{Digital signatures}
\label{sec:sig}

Our definition for digital signatures is, more specifically, for signature
schemes with appendix: the signing algorithm produces a signature,
and the verification algorithm requires both the signature and the original
message in order to function.

\begin{definition}[Digital signature syntax]
  \label{def:sig-syntax}

  A \emph{digital signature scheme} is a triple $\Pi_\textnm{sig} = (G, S,
  V)$ of (maybe randomized) algorithms, as follows.
  \begin{itemize}
  \item The \emph{key-generation algorithm} $G$ accepts no parameters and
    outputs a pair $(x, X) \gets G()$.  We call $x$ the \emph{private key}
    and $X$ the \emph{public key}.
  \item The \emph{signature algorithm} $S$ accepts a private key~$x$ and a
    message~$m \in \Bin^*$, and outputs a signature~$\sigma \gets S_x(m)$.
  \item The \emph{verification algorithm} $V$ accepts a public key~$X$, a
    message~$m \in \Bin^*$, and a signature~$\sigma$, and outputs a bit $b
    \gets V_X(m, \sigma)$ subject to the condition that, if $(x, X)$ is any
    key pair output by $G$, $m \in \Bin^*$ is any message, and $\sigma$ is
    any signature output by $S_x(m)$, then $V_X(m, \sigma)$ outputs $1$.
    \qed
  \end{itemize}
\end{definition}

Our notion of security for digital signatures is \emph{existential
  unforgeability under chosen-message attack} (EUF-CMA).  It is essentially
that of \cite{Goldwasser:1988:DSS}, modified to measure concrete security.
We provide the adversary with a public key and a signing oracle which signs
input messages using the corresponding private key.  The scheme is considered
secure if no adversary can output a valid message/signature pair for a
message distinct from the adversary's signing queries.

\begin{definition}[Digital signature security]
  \label{def:sig-security}

  Let $\Pi = (G, S, V)$ be a digital signature scheme.  The \emph{advantage}
  of an adversary~$A$'s ability to attack $\Pi$ is given by
  \[ \Adv{euf-cma}{\Pi}(A) = \Pr[\textrm{
        $(x, X) \gets G()$;
        $(m, \sigma) \gets A^{S_x(\cdot)}$
      } : V_X(m, \sigma) = 1]
  \]
  where the adversary is forbidden from returning a message~$m$ if it queried
  its signing oracle~$S_x(\cdot)$ at $m$.

  The EUF-CMA \emph{insecurity function} of $\Pi$ is given by
  \[ \InSec{euf-cma}(\Pi; t, q) = \max_A \Adv{euf-cma}{\Pi}(A) \]
  where the maximum is taken over all adversaries~$A$ completing the game in
  time~$t$ and issuing at most $q$ signing-oracle queries.
\end{definition}

This notion is weaker than it might be.  A possible strengthening would be to
allow the adversary to return a pair~$(m, \sigma')$ even if it made a signing
query for $m$, as long as the signing oracle didn't return the
signature~$\sigma'$.  We shall not require this stronger definition.

\subsection{Authenticated asymmetric encryption}
\label{sec:aae}

Our definitions for authenticated asymmetric encryption are based on those of
\cite{Baek:2007:FPS}.

\begin{definition}[Authenticated asymmetric encryption syntax]
  \label{def:aae-syntax}

  An \emph{authenticated asymmetric encryption scheme} is a triple
  $\Pi_\textnm{aae} = (G, E, D)$ of (maybe randomized) algorithms, as
  follows.
  \begin{itemize}
  \item The \emph{key-generation algorithm} $G$ accepts no parameters and
    outputs a pair $(x, X) \gets G()$.  We call $x$ the \emph{private key}
    and $X$ the \emph{public key}.
  \item The \emph{encryption algorithm} $E$ accepts a private key~$x$, a
    public key~$Y$, and a message $m \in \Bin^*$, and outputs a ciphertext $c
    \gets E_x(Y, m)$.
  \item The \emph{decryption algorithm} $D$ accepts a private key~$x$, a
    public key~$Y$ and a ciphertext~$c$, and outputs a result~$m \gets D_x(Y,
    c)$ which is either a message $m \in \Bin^*$ or the distinguished
    symbol~$\bot$.  The decryption algorithm must be such that if $(x, X)$
    and $(y, Y)$ are any two pairs of keys produced by $G$, $m$ is any
    message, and $c$ is any output of $E_x(Y, m)$, then $D_y(X, m)$ outputs
    $m$. \qed
  \end{itemize}
\end{definition}

Our security notion for secrecy is \emph{indistinguishability under outsider
  chosen-ciphertext attack} (IND-OCCA).  We generate a key pair each for two
participants, a `sender' and a `recipient'.  The adversary is given the two
public keys and provided with two oracles: an encryption oracle, which
accepts a message and a public key, and encrypts the message using the public
key and the sender's private key, returning the resulting ciphertext; and a
decryption oracle, which accepts a ciphertext and a public key, and decrypts
the ciphertext using the recipient's private key and checks it against the
given public key, returning either the resulting plaintext or an indication
that the decryption failed.  The adversary runs in two stages: in the first
`find' stage, it chooses two messages $m_0$ and $m_1$ of equal lengths and
returns them; one of these messages is encrypted by the sender using the
recipient's public key.  The adversary's second stage is given the resulting
`challenge' ciphertext.  The scheme is considered secure if no adversary can
determine which of its messages was encrypted.  Since this is trivial if the
adversary queries its decryption oracle with the challenge ciphertext and the
sender's public key, (only) this is forbidden.  The resulting game is
precisely \cite{Baek:2007:FPS}'s `FSO/FUO-IND-CCA2', which corresponds to
\cite{An:2002:SJS}'s notion of `multi-user outsider privacy'.  A similar
`insider security' notion would provide the adversary with the sender's
private key.  We prefer outsider security: the idea that we must prevent
Alice from decrypting the message she just encrypted to send to Bob seems
unnecessary.

Our security notion for authenticity is \emph{unforgeability under outsider
  chosen-message attack} (UF-OCMA).  Again, we generate sender and recipient
keys, and the adversary is given the same two oracles.  This time, the
adversary's task is to submit to the decryption oracle a ciphertext which it
accepts as being constructed by the sender, but is not equal to any
ciphertext returned by the encryption oracle.  This notion is strictly weaker
than \cite{Baek:2007:FPS}'s FSO-UF-CMA, since it corresponds to
\cite{An:2002:SJS,cryptoeprint:2002:046}'s `multi-user outsider
authenticity', whereas FSO-UF-CMA corresponds to `multi-user \emph{insider}
authenticity'.  This weakening of security is a necessary consequence of our
deniability requirements: we \emph{want} Alice to be able to forge messages
that appear to be sent to her by Bob: see \xref{sec:deny.insider}.  On the
other hand, we allow the adversary to make multiple decryption queries; this
makes a difference to our quantitative results.

\begin{definition}[Authenticated asymmetric encryption scheme security]
  \label{def:aae-security}

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

  \begin{program}
    $\Game{ind-occa-$b$}{\Pi}(A)$: \+ \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $(m_0, m_1, s) \gets
        A^{E_x(\cdot, \cdot), D_y(\cdot, \cdot)}(\cookie{find}, X, Y)$; \\
      $c^* \gets E_x(Y, m_b)$; \\
      $b' \gets
        A^{E_x(\cdot, \cdot), D_y(\cdot, \cdot)}(\cookie{guess}, c^*, s)$; \\
      \RETURN $b'$; \-
    \\[\medskipamount]
    $\Game{uf-ocma}{\Pi}(A)$: \+ \\
      $w \gets 0$;
      $\mathcal{C} \gets \emptyset$; \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $A^{\id{enc}(\cdot, \cdot), \id{dec}}(X, Y)$; \\
      \RETURN $w$; \-
  \next
    $\id{enc}(Z, m)$: \+ \\
      $c \gets E_x(Z, m)$; \\
      \IF $Z = Y$ \THEN $\mathcal{C} \gets \mathcal{C} \cup \{ c \}$; \\
      \RETURN $c$; \-
    \\[\medskipamount]
    $\id{dec}(Z, c)$: \+ \\
      $m \gets D_y(Z, c)$; \\
      \IF $Z = X \land m \ne \bot \land c \notin \mathcal{C}$ \THEN
        $w \gets 1$; \\
      \RETURN $m$; \-
  \end{program}

  In the IND-OCCA games $\Game{ind-occa-$b$}{\Pi}$, the adversary is
  forbidden from querying its decryption oracle $D_y(\cdot, \cdot)$ on the
  pair $(X, c^*)$; in the UF-OCMA game $\Game{uf-ocma}{\Pi}$, the adversary
  is forbidden from returning any ciphertext $c$ that it obtained by querying
  its encryption oracle~$E_x(\cdot, \cdot)$.

  The adversary's \emph{advantage} in these games is measured as follows.
  \begin{eqnarray*}[c]
    \Adv{ind-occa}{\Pi}(A) =
        \Pr[\Game{ind-occa-$1$}{\Pi}(A) = 1] -
        \Pr[\Game{ind-occa-$0$}{\Pi}(A) = 1]
  \\[\medskipamount]
    \Adv{uf-ocma}{\Pi}(A) =
        \Pr[\Game{uf-ocma}{\Pi}(A) = 1]
  \end{eqnarray*}
  Finally, the IND-CCA and OUF-CMA insecurity functions of $\Pi$ are given by
  \begin{eqnarray*}[c]
    \InSec{ind-occa}(\Pi; t, q_E, q_D) = \max_A \Adv{ind-occa}{\Pi}(A)
  \\[\medskipamount]
    \InSec{uf-ocma}(\Pi; t, q_E, q_D) = \max_A \Adv{uf-ocma}{\Pi}(A)
  \end{eqnarray*}
  where the maxima are taken over all adversaries~$A$ completing the game in
  time~$t$ and making at most $q_E$ and $q_D$ queries to their encryption and
  decryption oracles, respectively.
\end{definition}

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

The basic intuition behind deniably authenticated encryption is fairly clear.
If Bob sends a message Alice, then she shouldn't later be able to convince a
third party -- Justin, say -- that Bob actually sent it.  Of course, we're
considering encrypted messages, so Alice will have to send something other
than just the message to Justin if he's to be convinced of anything.
(Otherwise Justin is able to compromise the indistinguishability of the
encryption scheme.)

This intuition seems fairly clear; but, as we shall see, the notion of
deniably authenticated encryption is somewhat slippery to formalize.

\subsection{An attempt at a formal definition}
\label{sec:deny.first}

Following our intuition above, we model Justin as an algorithm~$J$ which
receives as input a message~$m$ and ciphertext~$c$, and some other
information, and outputs either~$1$ or $0$ depending on whether it is
convinced that $c$ represents an authentic encryption of $m$ sent from Bob to
Alice.  For deniability, we shall require the existence of a \emph{simulator}
which forges ciphertexts sufficiently well that Justin can't distinguish them
from ones that Bob made.  The difficult questions concern which inputs we
should give Justin on the one hand, and the simulator on the other.

The simulator is easier.  We must provide at least Bob's public key, in order
to identify him as the `sender'.  We must also provide Alice's \emph{private}
key.  This initially seems excessive; but a simulator which can forge
messages without Alice's private key exhibits an outsider-authenticity
failure.  (We could get around this by providing Bob's private key and
Alice's public key instead, but we already know that Bob can construct
plausible ciphertexts, so this seems uninteresting -- for now.)  We should
also give the simulator the `target' message for which it is supposed to
concoct a ciphertext: allowing the simulator to make up the target message
yields a very poor notion of deniability.  Finally, we might give the
simulator a \emph{valid} ciphertext from Bob to Alice.  Doing this weakens
our deniability, because Bob may no longer be able to deny engaging in any
form of communication with Alice; but this seems a relatively minor
complaint.  We therefore end up with two different notions: \emph{strong
  deniability}, where the simulator is given only the keys and the target
message; and \emph{weak deniability}, where the simulator is also provided
with a valid ciphertext.

Now we turn to Justin's inputs.  It's clear that if he can say whether a
ciphertext is an encryption of some specified message given only Alice's and
Bob's public keys then he exhibits an outsider-secrecy failure.  If Alice is
to prove anything useful about the ciphertext to Justin, then, she must
provide additional information, possibly in the form of a zero-knowledge
proof.  We don't need to model this, though: it's clearly \emph{sufficient}
to hand Alice's private key to Justin.  On the other hand, this is also
\emph{necessary}, since \emph{in extremis} Alice could do precisely this.
Similarly, it might be the case that Justin demands that Bob engage in some
protocol in an attempt to demonstrate his innocence.  We can therefore also
give Bob's private key to Justin.

This gives us enough to define our notion of \emph{strong deniability}.  As
we shall see, however, weak deniability is somewhat trickier to capture.

\begin{definition}[Strongly deniable authenticated asymmetric encryption]
  \label{def:aae-sdeny}

  Let $\Pi = (G, E, D)$ be an asymmetric authenticated encryption scheme, and
  let $S$ (the `simulator') and $J$ (the `judge') be algorithms.  The
  simulator's ability to deceive the judge is measured by the following
  games.
  \begin{program}
    $\Game{sdeny-$b$}{\Pi, S}(J, m_0, m_1)$: \+ \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $c_0 \gets E_y(X, m_0)$; \\
      $c_1 \gets S(x, Y, m_1)$; \\
      $b' \gets J(x, X, y, Y, c_b, m_b)$; \\
      \RETURN $b'$;
  \end{program}

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

\subsection{Chameleon signatures and weak deniability}
\label{sec:deny.weak}

Unfortunately, this still isn't quite enough.  Chameleon signatures
\cite{cryptoeprint:1998:010} achieve weak deniability as we've outlined above
but still provide a kind of nonrepudiation property.  Briefly, a chameleon
signature uses trapdoor commitments: Alice generates a trapdoor and a public
key for the commitment scheme; Bob signs a message $m$ by creating a
commitment for $m$ using Alice's public key, signs the commitment (and
Alice's public commitment key) with an ordinary EUF-CMA signature scheme, and
presents the pair of this signature and an opening of the commitment as his
chameleon signature on~$m$.  This achieves a limited form of deniability
(called `non-transferability' in \cite{cryptoeprint:1998:010}): Alice can
forge signatures using her trapdoor, so she can't convince others of the
signature's validity -- but she can only do this for commitments that Bob has
already signed, or she'd break the unforgeability of the underlying signature
scheme.  In theory, then, a dispute can be settled by demanding that Bob
provide an opening to the commitment different from Alice's: if he can, then
Alice must have used her trapdoor; otherwise he is deemed to accept the
validity of the signature.  This looks like a deniability failure.

(Di~Raimondo and Gennaro \cite{Raimondo:2005:NAD} frame the same problem in
terms of a deniability failure for the receiver, and describe a notion of
`forward deniability' which excludes this failure.  The difference in point
of view is mainly whether we consider the sender acting voluntarily or under
compulsion.)

None of this affects strong deniability.  If Alice can make up plausible
messages from nothing but Bob's public key then Bob has nothing to prove.
(We prove a formal version of this statement in \xref{th:strong-weak}.)  But
it means that our weak deniability is still too weak.

The fundamental problem is that, if the recipient's simulator needs a valid
ciphertext to work on, then there must be at least one valid ciphertext for
any simulated one, and Bob should be able to produce it; if he can't, then we
conclude that the ciphertext we have is the valid original.  To avoid this,
then, we must demand a \emph{second} simulator: given a genuine
ciphertext~$c$ corresponding to a message~$m$, Alice's public key, Bob's
private key, and a target message~$m'$, the simulator must construct a new
ciphertext~$c'$.  To test the efficacy of this simulator, we ask that Justin
attempt to distinguish between, on the one hand, a legitimate
message/ciphertext pair and an `Alice-forgery' created by the first
simulator, and on the other hand, a `Bob-forgery' created by the second
simulator and a legitimate message/ciphertext pair: the simulator is good if
Justin can't distinguish these two cases.  The intuition here is Justin is
being asked to adjudicate between Alice and Bob: each of them claims to have
the `legitimate' ciphertext, but one of them has secretly used the
simulator.  Justin shouldn't be able to work out which is telling the truth.

A scheme based on chameleon signatures fails to meet this stricter
definition.  Justin looks at the two chameleon signatures: if they have the
same underlying signature, it's an Alice forgery; if the signatures differ
then it's a Bob forgery.  If the second simulator, which isn't given Alice's
trapdoor key, can make a second ciphertext using the same underlying
signature then either it can find a new commitment with the same signature,
which is an non-repudiation failure for the signature,\footnote{%
  Well, almost.  In fact, signature schemes as we've defined them don't have
  to be unforgeable in this case.  In the EUF-CMA game
  (\xref{def:sig-security}) the adversary is given only oracle access to the
  signing algorithm, while the legitimate signer has access to the signing
  algorithm's internal state which may help in the construction of forgeries.
  We conclude that EUF-CMA is insufficient for non-repudiation.}%
or it can find a second opening of the commitment, which is a binding failure
for the commitment scheme.

Again, we can distinguish two variant definitions, according to whether Bob's
simulator has to work only on the given ciphertext, or whether it's also
provided with a `hint' produced by the encryption algorithm but not made
available to the adversary in the IND-OCCA and UF-OCMA games.  We prefer this
latter formulation;\footnote{%
  As described in \cite{cryptoeprint:1998:010}, we could instead attach this
  hint to the ciphertext, encrypted under a symmetric key.  We shall describe
  how this can be done with our proposed scheme.} %
we must therefore define formally our `leaky' encryption schemes which
provide such hints.  As one would expect, the security notions carry over
directly because the adversary never gets to see the hints.

\begin{definition}[Leaky authenticated asymmetric encryption]
  \label{def:aae-leaky}

  A \emph{leaky authentic asymmetric encryption scheme} $\Pi_\textnm{laae} =
  (G, E', D)$ is a triple of (maybe randomized) algorithms as follows.
  \begin{itemize}
  \item The \emph{leaky encryption algorithm} $E'$ accepts as input a private
    key~$x$, a public key~$Y$, a message~$m$, and outputs a pair $(c, s)
    \gets E'_x(Y, m)$ consisting of a ciphertext~$c$ and a \emph{hint}~$\nu$.
  \item If we define $\bar E_x(Y, m)$ to perform $E$ and discard the hint
    \begin{program}
      $\bar E_x(Y, m)$: \+ \\
        $(c, \nu) \gets E_x(Y, m)$; \\
        \RETURN $c$
    \end{program}
    then $\bar\Pi_\textnm{laae} = (G, \bar E, D)$ is an authenticated
    asymmetric encryption scheme.\footnote{%
      Think of the bar as `plugging the leak'.} %
  \end{itemize}
  For any adversary~$A$, time bound~$t$ and query bounds~$q_E$ and $q_D$, we
  define
  \begin{eqnarray*}[x]
    \Adv{ind-occa}{\Pi_\textnm{laae}}(A) =
        \Adv{ind-occa}{\bar\Pi_\textnm{laae}}(A) \qquad
    \Adv{uf-ocma}{\Pi_\textnm{laae}}(A) =
        \Adv{uf-ocma}{\bar\Pi_\textnm{laae}}(A) \\
    \InSec{ind-occa}(\Pi_\textnm{laae}; t, q_D) =
        \InSec{ind-occa}(\bar\Pi_\textnm{laae}; t, q_D) \\
    \InSec{uf-ocma}(\Pi_\textnm{laae}; t, q_E) =
        \InSec{uf-ocma}(\bar\Pi_\textnm{laae}; t, q_E)
  \end{eqnarray*}
  inheriting security definitions from the non-leaky version.
\end{definition}

Obviously, any non-leaky scheme can easily be transformed into a leaky scheme
with a trivial `leak'.  We shall make use of this below.

We are now finally in a position to define \emph{weak deniability}.

\begin{definition}[Weakly deniable authenticated asymmetric encryption]
  \label{def:aae-wdeny}

  Let $\Pi = (G, E, D)$ be a leaky asymmetric authenticated encryption
  scheme, and let $S$ and $S'$ (the `simulators'), and $J$ and $J'$ (the
  `judges') be algorithms.  The simulators' ability to deceive the judges is
  measured using the following games.
  \begin{program}
    $\Game{wdeny-$b$}{\Pi, S}(J, m_0, m_1)$: \+ \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $(c_0, \nu) \gets E_y(X, m_0)$; \\
      $c_1 \gets S(x, Y, c_0, m_1)$; \\
      $b' \gets J(x, X, y, Y, c_b, m_b)$; \\
      \RETURN $b'$;
  \next
    $\Game{wdeny$'$-$0$}{\Pi, S, S'}(J', m_0, m_1)$: \+ \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $(c_0, \nu) \gets E_y(X, m_0)$; \\
      $c_1 \gets S'(X, y, c_0, \nu, m_1)$; \\
      $b' \gets J'(x, X, y, Y, c_0, m_0, c_1, m_1)$; \\
      \RETURN $b'$;
    \- \\[\medskipamount]
    $\Game{wdeny$'$-$1$}{\Pi, S, S'}(J', m_0, m_1)$: \+ \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $(c_1, \nu) \gets E_y(X, m_1)$; \\
      $c_0 \gets S(x, Y, c_1, m_0)$; \\
      $b' \gets J'(x, X, y, Y, c_0, m_0, c_1, m_1)$; \\
      \RETURN $b'$;
  \end{program}

  We define the judges' \emph{advantage} at distinguishing the simulators'
  output as follows.
  \begin{eqnarray*}[x]
    \begin{subsplit} \displaystyle
    \Adv{wdeny}{\Pi, S}(J) = \max_{m_0, m_1 \in \Bin^*} \bigl(
        \Pr[\Game{wdeny-$1$}{\Pi, S}(J, m_0, m_1) = 1] - {} \\
        \Pr[\Game{wdeny-$0$}{\Pi, S}(J, m_0, m_1) = 1] \bigr)
    \end{subsplit} \\[\bigskipamount]
    \begin{subsplit} \displaystyle
    \Adv{wdeny$'$}{\Pi, S, S'}(J') = \max_{m_0, m_1 \in \Bin^*} \bigl(
        \Pr[\Game{wdeny$'$-$1$}{\Pi, S, S'}(J', m_0, m_1) = 1] - {} \\
        \Pr[\Game{wdeny$'$-$0$}{\Pi, S, S'}(J', m_0, m_1) = 1] \bigr)
    \end{subsplit}
  \end{eqnarray*}
  Finally, the insecurity function of the simulators is defined by
  \[ \InSec{wdeny}(\Pi, S, S'; t) = \max\bigl(
       \max_J \Adv{wdeny}{\Pi, S}(J),
       \max_{J'} \Adv{wdeny$'$}{\Pi, S, S'}(J')
     \bigr)
  \]
  where the maxima are taken over all judges~$J$ and~$J'$ completing their
  respective games in time~$t$.
\end{definition}

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

\subsubsection{Strong deniability implies weak deniability}
By now, it's probably not at all clear that strong deniability actually
implies weak deniability; but this is nonetheless true.  The important
observation is that, since the recipient's simulator works without reference
to an existing ciphertext, the standard encryption algorithm works well as a
sender's simulator.  This is expressed in the following theorem.

\begin{theorem}[$\textrm{SDENY} \implies \textrm{WDENY}$]
  \label{th:strong-weak}

  Let $\Pi = (G, E, D)$ be an authenticated asymmetric encryption scheme, and
  let~$S$ be a simulator.  Let $\Pi' = (G, E', D)$ where $E'_x(Y, m) =
  (E_x(Y, m), \bot)$, so $\Pi'$ is a (trivially) `leaky' AAE scheme.  Then
  there exists a simulator~$S'$ such that
  \[ \InSec{wdeny}(\Pi', S, S'; t) \le  \InSec{sdeny}(\Pi, S; t') \]
  where $t' - t$ is the time required for a single encryption.
\end{theorem}
\begin{proof}
  The only difference between the SDENY and WDENY games is that the WDENY
  simulator is given an additional argument; the simulator's output is the
  same in both cases, as is the input to the judge.  It follows, then, that
  the strong-deniability simulator~$S$ is sufficient to show that, for
  any judge~$J$
  \[ \Adv{wdeny}{\Pi', S}(J, m_0, m_1) \le \InSec{sdeny}(\Pi, S; t) \]
  where $t$ is the running time of~$J$.

  The simulator~$S'$ simply uses the `proper' encryption algorithm:
  \begin{program}
    $S'(X, y, c, \nu, m)$: \+ \\
      $c' \gets E_y(X, m)$; \\
      \RETURN $c'$;
  \end{program}
  We must now show that this simulator is sufficient to convince any~$J'$ in
  the WDENY$'$ game.

  The notation is uncomfortably heavyweight; let us write $\G{b} =
  \Game{wdeny$'$-$b$}{\Pi', S, S'}$.  In $\G1$ both ciphertexts are `genuine'
  -- they were generated by the proper encryption algorithm, using the proper
  private key.  In $\G0$, on the other hand, the right-hand ciphertext is
  genuine but the left-hand ciphertext is simulated by~$S$.  However, $S$ is
  meant to be a good simulator of genuine ciphertexts.  Indeed, if $J'$ can
  tell a pair of good, independently generated ciphertexts from a good
  ciphertext and a (still independent) $S$-simulated one, then we can use it
  to distinguish $S$'s simulations.\footnote{%
    This independence, which follows from the fact that the strong
    deniability simulator is required to work \emph{ab initio} without
    reference to an existing ciphertext, is essential to the proof.  Without
    it, we'd `prove' that one needs only a single simulator to achieve weak
    deniability -- but the previous discussion of chameleon signatures shows
    that this is false.} %

  Choose some message~$m^*$.  We construct an explicit~$J$ as follows.
  \begin{program}
    $J(x, X, y, Y, c, m)$: \+ \\
      $c^* \gets E_y(X, m^*)$; \\
      $b \gets J'(x, X, y, Y, c, m, c^*, m^*)$; \\
      \RETURN $b$;
  \end{program}
  This $J$ is given either a genuine or an $S$-simulated ciphertext and
  message, allegedly for message~$m$.  It generates a genuine ciphertext
  independently for~$m'$.  It now has either two independent genuine
  ciphertexts or a genuine ciphertext and a simulation, and therefore
  distinguishes the two cases exactly as well as $J'$.  We conclude that
  \[ \Adv{wdeny$'$}{\Pi', S, S'}(J') \le \InSec{sdeny}(\Pi S; t') \]
  as required.
\end{proof}

\subsubsection{Insider authenticity}
\label{sec:deny.insider}
There is a kind of attack considered in the study of key-exchange protocols
(see, for example, \cite{Blake-Wilson:1997:KAP}) called \emph{key-compromise
  impersonation}.  The adversary is assumed to know the long-term secret
information of one of the participants -- Alice, say.  Clearly, he can now
impersonate Alice to Bob.  If the protocol is vulnerable to key-compromise
impersonation attacks, however, he can also impersonate Bob -- or anybody
else of his choosing -- to Alice.\footnote{%
  It is apparently considered unsatisfactory for a key-exchange protocol to
  admit key-compromise impersonation, though it's unclear to us why we might
  expect Alice to retain any useful security properties after having been
  corrupted.} %
The analogue of key-compromise-impersonation resistance in the context of
noninteractive asymmetric encryption is \emph{insider authenticity}.

Deniably authenticated asymmetric encryption schemes do not provide insider
authenticity: the two are fundamentally incompatible.  Indeed, the existence
of the receiver simulator~$S$ in \xref{def:aae-sdeny} or \xref{def:aae-wdeny}
constitutes an insider-authenticity attack.

Insider authenticity can be defined fairly easily by modifying the UF-OCMA
game of \xref{def:aae-security} to give the adversary the receiver's private
key~$y$; we shall omit the tedious formalities, but we shall end up with a
security measure $\InSec{uf-icma}(\Pi; t, q_E)$ (for `unforgeability under
insider chosen-message attack').  The attack is simple: retrieve a single
message~$m$ from the sender (if the scheme is only weakly deniable -- even
this is unnecessary if we have strong deniability), pass it to the
simulator~$S$, along with the private key~$y$ and a different message~$m' \ne
m$.  Let $y'$ be the simulator's output.  We know that the decryption
algorithm will always succeed on real ciphertexts; so if $p$ is the
probability that decryption fails, then
\[ \InSec{uf-icma}(\Pi; t_E + t_S, 1) \ge
        p \ge 1 - \InSec{wdeny}(\Pi, S; t_D) \]
where $t_E$, $t_S$ and $t_D$ are the respective times required to encrypt a
message, run the receiver simulator, and decrypt a message.

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

In this section we describe a generic construction meeting the definition of
`weak deniability' (\xref{def:aae-wdeny}), and prove its security.

\subsection{Description of the construction}
\label{sec:gwd.description}

Firstly, we give an informal description; then we present the formal version
as pseudocode.  We need the following ingredients.
\begin{itemize}
\item A key encapsulation mechanism (KEM;
  \xref{def:kem-syntax})~$\Pi_\textnm{kem} = (\ell, \mathcal{G}, \mathcal{E},
  \mathcal{D})$, secure against chosen-ciphertext attack (IND-CCA;
  \xref{def:kem-security}).
\item A symmetric encryption scheme (\xref{def:se-syntax})
  scheme~$\Pi_\textnm{se} = (k, E, D)$, secure against chosen-ciphertext
  attack and with integrity of ciphertexts (IND-CCA and INT-CTXT;
  \xref{def:se-security}), where $k < \ell$.
\item A digital signature (\xref{def:sig-syntax}) scheme~$\Pi_\textnm{sig} =
  (G, S, V)$, secure against existential forgery under chosen-message attack
  (EUF-CMA; \xref{def:sig-security}) and satisfying the additional property
  that the encoding $[\sigma]$ of any signature $\sigma$ has the same
  length.\footnote{%
    Most practical signature schemes, e.g., based on RSA
    \cite{Rivest:1978:MOD,Bellare:1996:ESD,RSA:2002:PVR,rfc3447} or DSA
    \cite{FIPS:2000:DSS}, have this property for arbitrary messages.
    Regardless, we investigate how to weaken this requirement in
    \xref{sec:gwd.variant}.} %
\end{itemize}

Alice's private key consists of a private key~$a$ for the KEM and a private
key~$a'$ for the signature scheme; her public key consists of the two
corresponding public keys $A$ and~$A'$.  Similarly, Bob's private key
consists of $b$ and $b'$ for the KEM and signature scheme, and his public key
is $B$ and $B'$.  A diagram of the scheme is shown in \xref{fig:gwd}.

To send a message~$m$ to Bob, Alice performs the following steps.
\begin{enumerate}
\item She runs the KEM on Bob's public key~$B$; it returns a `clue'~$u$ and
  an $\ell$-bit `key'~$Z$.
\item She splits $Z$ into a $k$-bit key~$K$ for the symmetric encryption
  scheme, and a $t$-bit `tag'~$\tau$.
\item She signs $[\tau, B]$ using the signature scheme and her private
  key~$a'$, producing a signature~$\sigma$.
\item She encrypts the signature and her message using the symmetric
  encryption scheme, with key~$K$, producing a ciphertext $y$.
\item The final ciphertext consists of two elements: the KEM clue~$u$ and the
  symmetric ciphertext~$y$.
\end{enumerate}
To decrypt the message represented by $(u, y)$, Bob performs these steps.
\begin{enumerate}
\item He applies the KEM to the clue~$u$ and his private key~$b$, obtaining
  an $\ell$-bit `key'~$Z$.
\item He splits $Z$ into a $k$-bit key~$K$ for the symmetric encryption
  scheme and a $t$-bit tag~$\tau$.
\item He decrypts the ciphertext~$y$ using the symmetric encryption scheme
  with key~$K$, obtaining a signature~$\sigma$ and a message~$m$.
\item He verifies the signature $\sigma$ on the pair~$[\tau, B]$, using
  Alice's public key~$A'$.
\end{enumerate}

\begin{figure}
  \centering
  \begin{tikzpicture}
    \tikzset{
      box/.style = {draw, minimum size = 14pt, fill = #1},
      around/.style = {inner sep = 0pt, fit = #1},
      node distance = 5mm,
      rounded/.style = {rounded corners = 2mm}
    }
    \node[box = blue!20] (kem) {$\mathcal{E}$};
    \node[box = red!20, left = -0.3pt] at (0, -1) (K) {$K$};
    \node[box = green!20, right = -0.3pt] at (0, -1) (tau) {$\tau$};
    \node[around = (K) (tau)] (Z) {};
    \draw[->] (kem) -- (Z);
    \node[box = green!20, right = of tau] (tau2) {$\tau$};
    \node[box = blue!20, right = -0.6pt of tau2] (B) {$B$};
    \node[around = (tau2) (B)] (sign-input) {};
    \node at (B |- kem) {$B$} edge [->] (kem)
          edge [->] (B);
    \draw[->] (tau) -- (tau2);
    \node[box = green!20, below = of sign-input] (sig) {$S$}
          edge [<-] (sign-input);
    \node[left = of sig] {$a'$} edge [->] (sig);
    \node[box = green!20, below = of sig] (sigma) {$\sigma$}
          edge [<-] (sig);
    \node[box = yellow!20, right = -0.6pt of sigma, minimum width = 30mm]
          (m) {$m$};
    \node at (m |- kem) {$m$} edge [->] (m);
    \node[around = (sigma) (m)] (enc-input) {};
    \node[box = red!20, below = of m.south west] (enc) {$E$};
    \draw[->, rounded] (enc-input) |- (enc);
    \draw[->, rounded] (K) |- (enc);
    \node[box = red!20, below = of enc, minimum width = 35mm] (y) {$y$};
    \node[box = blue!20, left = -0.6pt of y] (u) {$u$};
    \draw[->] (enc) -- (y);
    \draw[->, rounded] (kem) -- +(-1, 0) |- (u);
  \end{tikzpicture}
  \caption{Generic weakly-deniable asymmetric encryption}
  \label{fig:gwd}
\end{figure}

More formally, we define our generic weakly-deniable scheme
$\Pi_\textnm{aae-gwd}(\Pi_\textnm{kem}, \Pi_\textnm{sig}, \Pi_\textnm{se})$
to be the triple of algorithms $(\Xid{G}{aae-gwd}, \Xid{E'}{aae-gwd},
\Xid{D}{aae-gwd})$ as follows.
\begin{program}
  $\Xid{G}{aae-gwd}()$: \+ \\
    $(x, X) \gets \mathcal{G}()$; \\
    $(x', X') \gets G()$; \\
    \RETURN $\bigl( (x, x'), (X, X') \bigr)$; \-
\newline
  $\Xid{E'}{aae-gwd}_{x, x'}\bigl((Y, Y'), m\bigr)$: \+ \\
    $(Z, u) \gets \mathcal{E}_Y()$; \\
    $K \gets Z[0 \bitsto k]$;
    $\tau \gets Z[k \bitsto \ell]$; \\
    $\sigma \gets S_{x'}([\tau, Y])$; \\
    $y \gets E_K([\sigma] \cat m)$; \\
    \RETURN $\bigl((u, y), K\bigr)$; \-
\next
  $\Xid{D}{aae-gwd}_{x, x'}\bigl((Y, Y'), (u, y)\bigr)$: \+ \\
    $Z \gets \mathcal{D}_x(u)$;
    \IF $Z = \bot$ \THEN \RETURN $\bot$; \\
    $K \gets Z[0 \bitsto k]$;
    $\tau \gets Z[k \bitsto \ell]$; \\
    $\hat{m} \gets D_K(y)$;
    \IF $\hat{m} = \bot$ \THEN \RETURN $\bot$; \\
    $[\sigma] \cat m \gets \hat{m}$;
    \IF $V_{Y'}([\tau, X], \sigma) = 0$ \THEN \RETURN $\bot$; \\
    \RETURN $m$;
\end{program}

\subsection{Conventional security}
\label{sec:gwd.aae}

Before we embark on the formal security proof, it's worth reflecting on the
intuitive reason that the generic scheme is secure -- in the sense of
providing (outsider) secrecy and authenticity.

Secrecy is fairly straightforward: it follows directly from the security of
the KEM and the symmetric encryption scheme.


Firstly we consider secrecy, and initially restrict our attention to secrecy
under chosen-plaintext attack only.  If the KEM is any good then the key~$Z$
appears to be random and particularly the first $k$ bits -- i.e., the
symmetric key~$K$ -- are unknown to the adversary.  Since~$K$ is good, and we
assume that the symmetric scheme is good, then the ciphertext~$y$ hides~$m$,
and since~$y$ is the only part of the overall ciphertext that depends on~$m$
this is sufficient.

For secrecy under chosen-ciphertext attack we must show that a decryption
oracle doesn't help.  A decryption query may share a KEM clue with a given
target ciphertext.  If it does then we appeal to symmetric security; if not,
then the KEM security suffices.

Finally we deal with authenticity.  For a forgery to be successful, it must
contain a signature which can be verified using the purported sender's public
key; if the signature scheme is good, then this must be a signature actually
made by the purported sender.  If the KEM clue on the forgery doesn't match
the clue from the message from which the signature was extracted, then the
tag taken from the forgery will fail to match with high probability.  If the
KEM clue does match then the symmetric key must also match, and so the
symmetric scheme's authentication will ensure that the signature and message
are both unaltered -- so the forgery is trivial.

We now present the formal security theorems.

\begin{theorem}[AAE-GWD secrecy]
  \label{th:gwd-secrecy}
  Let $\Pi = \Pi_\textnm{aae-gwd}(\Pi_\textnm{kem}, \Pi_\textnm{sig},
  \Pi_\textnm{se})$ be as defined above.  Then
  \[ \InSec{ind-occa}(\Pi; t, q_E, q_D) \le \\
        2\,\InSec{ind-cca}(\Pi_\textnm{kem}; t, q_D) +
        \InSec{ind-cca}(\Pi_\textnm{se}; t, 1, q_D)
  \]
\end{theorem}
\begin{theorem}[AAE-GWD authenticity]
  \label{th:gwd-authenticity}
  Let $\Pi = \Pi_\textnm{aae-gwd}(\Pi_\textnm{kem}, \Pi_\textnm{sig},
  \Pi_\textnm{se})$ be as defined above.  Then
  \begin{spliteqn*}
    \InSec{uf-ocma}(\Pi; t, q_E, q_D) \le
       q_E \InSec{ind-cca}(\Pi_\textnm{kem}; t, 0) +
       q_E \InSec{int-ctxt}(\Pi_\textnm{se}; t, 1, q_D) + {} \\
       q_E \InSec{ind-cca}(\Pi_\textnm{se}; t, 1, 0) +
       \InSec{euf-cma}(\Pi_\textnm{sig}; t, q_E)
  \end{spliteqn*}
\end{theorem}
\begin{proof}[Proof of \xref{th:gwd-secrecy}]
  We use sequences of games over the same underlying probability space, as
  described in \cite{Shoup:2002:OR,cryptoeprint:2004:332}.

  Let $A$ be any adversary attacking the outsider secrecy of $\Pi$ which runs
  within the stated resource bounds.  It will therefore suffice to bound
  $A$'s advantage.

  In game~$\G0$, we toss a coin~$b \inr \{0, 1\}$, and play
  $\Game{ind-occa-$b$}{\Pi}(A)$.  The adversary's output is $b'$.  Let $S_0$
  be the event that $b = b'$.  We have, as a standard result, that
  \begin{eqnarray*}[rl]
    \Adv{ind-occa}{\Pi}(A)
    & = \Pr[S_0 \mid b = 1] - \Pr[\bar S_0 \mid b = 0] \\
    & = \Pr[S_0 \mid b = 1] + \Pr[S_0 \mid b = 0] - 1 \\
    & = \frac{\Pr[S_0 \land b = 1]}{\Pr[b = 1]} +
        \frac{\Pr[S_0 \land b = 0]}{\Pr[b = 0]} - 1 \\
    & = 2(\Pr[S_0 \land b = 1] + \Pr[S_0 \land b = 0]) - 1 \\
    & = 2\Pr[S_0] - 1 \eqnumber \label{eq:gwd-sec-s0}
  \end{eqnarray*}
  Hence bounding $\Pr[S_0]$ will be sufficient to complete the proof.  In
  each game~$\G{i}$ that we define, $S_i$ will be the event that $b' = b$ in
  that game.  As we define new games, we shall bound $\Pr[S_i]$ in terms of
  $\Pr[S_{i+1}]$ until eventually we shall be able to determine this
  probability explicitly.

  Before we start modifying the game, we shall pause to establish some
  notation.  The \emph{challenge ciphertext} passed to the \cookie{guess}
  stage of the adversary is a clue/signature/ciphertext triple $c^* = (u^*,
  y^*)$, where $(Z^*, u^*) \gets \mathcal{E}_Y()$, $K^* = Z^*[0 \bitsto k]$,
  $\tau^* = Z^*[k \bitsto \ell]$, $\sigma^* \gets S_x([\tau^*, Y])$, and $y^*
  \gets E_{K^*}([\sigma^*] \cat m_b)$.

  Game~$\G1$ works in almost the same way as $\G0$.  The difference is that
  rather than computing~$Z^*$ using the key-encapsulation algorithm
  $\mathcal{E}_Y$, we simply choose it uniformly at random from $\Bin^\ell$.
  Furthermore, the decryption oracle compensates for this by inspecting the
  input ciphertext $c = (u, y)$: if and only if $u = u^*$ then decryption
  proceeds using $Z = Z^*$ rather than using the key-decapsulation
  algorithm~$\mathcal{D}$.

  We claim that
  \begin{equation}
    \label{eq:gwd-sec-g1}
    \Pr[S_0] - \Pr[S_1] \le
        \InSec{ind-cca}(\Pi_\textnm{kem}; t, q_D)
  \end{equation}
  The proof of the claim is by a simple reduction argument: we define an
  adversary~$\hat{A}$ which attacks the KEM.  We describe the
  adversary~$\hat{A}$ in detail by way of example; future reduction arguments
  will be rather briefer.

  The adversary receives as input a public key~$Y$ for the KEM, an $\ell$-bit
  string $Z^*$ and a clue~$u^*$.  It generates signature key pairs ~$(x',
  X')$ and $(y', Y')$, and a KEM key pair~$(x, X)$, using the key-generation
  algorithms; it also chooses $b \in \{0, 1\}$ uniformly at random.  It runs
  the \cookie{find} stage of adversary~$A$, giving it $(X, X')$ and $(Y, Y')$
  as input.  Eventually, the \cookie{find} stage completes and outputs $m_0$
  and $m_1$ and a state~$s$.  Our KEM adversary computes $\sigma^*$ and $y^*$
  in terms of the $Z^*$ it was given and the message~$m_b$, and runs the
  \cookie{guess} stage of adversary~$A$, providing it with the
  ciphertext~$(u^*, \sigma^*, y^*)$ and the state~$s$.  Eventually, $A$
  completes, outputting its guess~$b'$.  If $b' = b$ then our KEM adversary
  outputs~$1$; otherwise it outputs~$0$.

  During all of this, we must simulate $A$'s encryption and decryption
  oracles.  The encryption oracle poses no special difficulty, since we have
  the signing key~$x'$.  On input $\bigl((Q, Q'), (u, \sigma, y)\bigr)$, the
  simulated decryption oracle works as follows.  If $u = u^*$ then set $Z =
  Z^*$; otherwise retrieve $Z$ by querying the decapsulation oracle at~$u$,
  since this is permitted by the KEM IND-CCA game rules.  Except for this
  slightly fiddly way of discovering~$Z$, the simulated decryption oracle
  uses the `proper' decryption algorithm, verifying the signature $\sigma$ on
  the tag~$\tau = Z[k \bitsto \ell]$ using the public key~$Q'$.

  If the KEM adversary is playing the `real'
  $\Game{ind-cca-$1$}{\Pi_\textnm{kem}}$ then our KEM adversary simulates
  $\G0$ perfectly; hence, the probability that it outputs $1$ is precisely
  $\Pr[S_0]$.  On the other hand, if it is playing
  $\Game{ind-cca-$0$}{\Pi_\textnm{kem}}$ then it simulates~$\G1$, and the
  probability that it outputs $1$ is $\Pr[S_1]$.  Hence
  \[ \Pr[S_0] - \Pr[S_1] = \Adv{ind-cca}{\Pi_\textnm{kem}}(\hat{A})
                       \le \InSec{ind-cca}(\Pi_\textnm{kem}; t, q_D)
  \]
  as claimed.

  Finally, we can bound $S_1$ explicitly in $\G1$:
  \begin{equation}
    \label{eq:gwd-sec-s1}
    \Pr[S_1] \le \frac{1}{2} \InSec{ind-cca}(\Pi_\textnm{se}; t, 1, q_D) +
                 \frac{1}{2}
  \end{equation}
  This follows by a simple reduction to the chosen-ciphertext secrecy of
  $\Pi_\textnm{se}$: $K^*$ will be known to the IND-CCA game, but not
  directly to our adversary.  It will generate all of the long-term
  asymmetric keys, and run $A$'s \cookie{find} stage, collects the two
  plaintext messages, encrypts them (making use of the left-or-right
  $\Pi_\textnm{se}$ encryption oracle to find $y^* = E_{K^*}([\sigma] \cat
  \id{lr}(m_0, m_1))$.  The challenge ciphertext is passed to $A$'s
  \cookie{guess} stage, which will eventually output a guess~$b'$; our
  adversary outputs this guess.

  The decryption oracle is simulated as follows.  Let $(u, y)$ be the
  chosen-ciphertext query.  If $u \ne u^*$ then we decrypt $y$ by recovering
  $K \cat \tau = \mathcal{D}_y(u)$ as usual; otherwise we must have $y \ne
  y^*$ so $y$ is a legitimate query to the symmetric decryption oracle, so we
  recover $\hat{m} = D_{K^*}(y)$ and continue from there.

  This is a valid adversary, and runs in the stated resource bounds, so the
  claim follows.

  We can bound the advantage of adversary~$A$ by combining
  equations~\ref{eq:gwd-sec-s0}--\ref{eq:gwd-sec-s1}:
  \begin{eqnarray*}[rl]
    \Adv{ind-occa}{\Pi}(A)
    & =   2\Pr[S_0] - 1 \\
    & \le 2 \, \InSec{ind-cca}(\Pi_\textnm{kem}; t, q_D) +
          \InSec{ind-cca}(\Pi_\textnm{se}; t, 1, q_D)
  \end{eqnarray*}
  completing the proof.
\end{proof}

\begin{proof}[Proof of \xref{th:gwd-authenticity}]
  We use a sequence of games again.

  Let $A$ be any adversary attacking the outsider authenticity of $\Pi$ and
  running within the specified resource bounds.  It will suffice to bound
  $A$'s advantage.

  Game~$\G0$ is precisely $\Game{uf-ocma}{\Pi}(A)$.  We let $S_0$ be the
  event that $A$ outputs a valid forgery, i.e.,
  \begin{equation}
    \label{eq:gwd-auth-s0}
    \Adv{uf-ocma}{\Pi}(A) = \Pr[S_0]
  \end{equation}
  As before, in each subsequent game~$\G{i}$ we let $S_i$ be the
  corresponding event.  The two key pairs will be $((x, x'), (X, X'))$ and
  $((y, y'), (Y, Y'))$.  For each $0 \le j < q_D$, let $(Q^*_j, u^*_j,
  y^*_j)$ be the adversary's $j$th decryption query, and define $Z^*_j =
  \mathcal{D}_y(u^*_j)$, $K^*_j = Z^*_i[0 \bitsto k]$, $\tau^*_j = Z^*_j[k
  \bitsto \ell]$, and $[\sigma^*_j] \cat m^*_j = \hat{m}^*_j =
  D_{K^*_j}(y^*_j)$, insofar as such quantities are well-defined.  For each
  $0 \le i < q_E$, we define $m_i$ to be the message in $A$'s $i$th
  encryption-oracle query and $(P, P_i)$ as the corresponding public key; and
  we set $(Z_i, u_i) \gets \mathcal{E}_{P_i}()$ to be the KEM output while
  responding to that query, with $K_i \cat \tau_i = Z_i$, $\sigma_i =
  S_{x'}([\tau_i, Q_i])$, and $y_i \gets E_{K_i}(m_i)$.

  Game~$\G1$ is the same as~$\G0$, except that the encryption oracle
  generates random keys $Z_i \inr \Bin^\ell$ if $Q_i = Y$ rather than using
  the keys output by the key encapsulation algorithm.  The clue~$u_i$
  returned is valid; but the key $K_i$ used for the symmetric encryption, and
  the tag~$\tau_i$ signed by the signature algorithm, are random and
  independent of the clue.  We also modify the decryption oracle: if $Q^*_j =
  X$, and $u^*_j = u_i$ matches a clue returned by the encryption oracle with
  $Q_i = Y$, then the decryption oracle sets $Z^*_j = Z_i$ rather than using
  the decapsulation algorithm.

  We claim that
  \begin{equation}
    \label{eq:gwd-auth-g1}
    \Pr[S_0] - \Pr[S_1] \le q_E \InSec{ind-cca}(\Pi_\textnm{kem}; t, 0)
  \end{equation}
  For this we use a hybrid argument: for $0 \le i \le q_E$ we define
  game~$\G[H]{i}$ to use random keys to generate $Z_k$ for $0 \le k < i$ and
  to use the `proper' encapsulation algorithm for the remaining $q_E - i$
  queries; let $T_i$ be the event that the adversary returns a valid forgery
  in~$\G[H]{i}$.  Then
  \[ \G[H]{0} \equiv \G0 \qquad \textrm{and} \qquad \G[H]{q_E} \equiv \G1 \]
  but a simple reduction argument shows that, for $0 \le i < q_E$,
  \[ \Pr[T_i] - \Pr[T_{i+1}] \le \InSec{ind-cca}(\Pi_\textnm{kem}; t, q_D) \]
  We construct an adversary~$\hat{A}$ attacking the KEM's secrecy by
  simulating one of a pair of hybrid games.  Let $\hat{A}$'s input be
  $\hat{Z}, \hat{u}$.  The KEM adversary proceeds by answering the first~$i$
  encryption queries using random keys, using $Z_i = \hat{Z}$ for query $i$,
  and the key encapsulation algorithm for the remaining $q_E - i - 1$
  queries.  A decryption query with $Q^*_j$ can be answered by using the key
  decapsulation if $u^*_j \ne u_k$, or by setting $Z^*_j = Z_k$ directly
  otherwise; clearly if $k = i$ then $Z^*_j = Z_i = \hat{Z}$.  If $\hat{Z}$
  is a real KEM output then we have simulated $\G[H]{i}$; otherwise we have
  simulated~$\G[H]{i+1}$.  The claim follows since
  \begin{eqnarray*}[rl]
    \Pr[S_0] - \Pr[S_1]
    & = \Pr[T_0] - \Pr[T_{q_E}] \\
    & = \sum_{0\le i<q_E} (\Pr[T_i] - \Pr[T_{i+1}]) \\
    & \le q_E \InSec{ind-cca}(\Pi_\textnm{kem}; t, 0)
  \end{eqnarray*}

  Game~$\G2$ is the same as $\G1$, except that the decryption oracle returns
  $\bot$ whenever a query is made with $Q^*_j = X$, $u^*_j = u_i$ and $y^*_j
  \ne y_i$, where $u_i$ is any clue returned by the encryption oracle so far
  and $y_i$ is the corresponding symmetric ciphertext.  Let $F_2$ be the
  event that a forgery 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}(\Pi_\textnm{se}; t, 1, q_D)
  \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 forgeries where
  $u^* = u_j$ are rejected if $0 \le j < 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 $u^*_j,
  y^*_j$ is be 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 \ne y_i \textrm{,} \qquad \textrm{and} \qquad
     D_{K_i}(y^*_i) \ne \bot \]
  $K_i$ is random in all of these games, so a simple reduction shows that
  \[ \Pr[T'_i] \le \InSec{int-ctxt}(\Pi_\textnm{se}; t, 1, q_D) \]
  The reduction uses the INT-CTXT encryption oracle to perform the $i$th
  encryption query, and the decryption oracle to respond to any decryption
  query with $Q^*_j = X \land u^*_j = u_i$.  If $F_2$ occurs then $y^*_j \ne
  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}(\Pi_\textnm{se}; t, 1, q_D) \]
  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
  = |[\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}(\Pi_\textnm{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 IND-CCA security shows that
  \[ \Pr[T''_i] - \Pr[T''_{i+1}] \le
        \InSec{ind-cca}(\Pi_\textnm{se}; t, 1, 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 using randomly generated keys.  We shall not require
  the decryption oracle: if $Q^*_j = X$ and $u^*j = u_i$ then either $y^*_j =
  y_i$, in which case we set $m^*_j = m_i$, or $y^*_j \ne y_i$ in which case
  we immediately return $\bot$.  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}(\Pi_\textnm{se}; t, 1, 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 $\Pi_\textnm{sig}$:
  \begin{equation}
    \label{eq:gwd-auth-s3}
    \Pr[S_2] \le \InSec{euf-cma}(\Pi_\textnm{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}(\Pi_\textnm{kem}; t, 0) +
          q_E \InSec{int-ctxt}(\Pi_\textnm{se}; t, 1, q_D) + {} \\
    & &   q_E \InSec{ind-cca}(\Pi_\textnm{se}; t, 1, 0) +
          \InSec{euf-cma}(\Pi_\textnm{sig}; t, q_E)
  \end{eqnarray*}
  and the theorem follows.
\end{proof}

\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}
  Let $\Pi = \Pi_\textnm{aae-gwd}(\Pi_\textnm{kem}, \Pi_\textnm{sig},
  \Pi_\textnm{se})$ as defined above.  There exist simulators $S$ and $S'$
  such that
  \[ \InSec{wdeny}(\Pi, S, S'; t) = 0 \]
\end{theorem}
\begin{proof}
  The simulators are simple.  Recall that the `leaky' version of $\Pi$ leaks
  the symmetric key, which the sender can use later to construct a new
  ciphertext.
  \begin{program}
    $S((x, x'), (Y, Y'), (u, y), m')$: \+ \\
      $Z \gets \mathcal{D}_x(u)$;
      \IF $Z = \bot$ \THEN \RETURN $\bot$; \\
      $K \gets Z[0 \bitsto k]$; \\
      $\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
    $S'((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}
  We claim that these simulators are perfect, i.e., no judge has nonzero
  advantage.  To see this, note 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, this scheme is not strongly deniable unless signatures are easily
forged.

\begin{theorem}
  Let $\Pi = \Pi_\textnm{aae-gwd}(\Pi_\textnm{kem}, \Pi_\textnm{sig},
  \Pi_\textnm{se})$ as defined above.  Then, for all simulators~$S$, we have
  \[ \InSec{sdeny}(\Pi, S; t) \ge
        1 - \InSec{euf-cma}(\Pi_\textnm{sig}; t_S + t', 0) \]
  where $t_S$ is the running time of $S$ and $t'$ is the time taken to
  decrypt a ciphertext of $\Pi$.
\end{theorem}
\begin{proof}
  Recall that a strong-deniability simulator does not require a sample
  ciphertext to work from.

  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.  We claim that
  \[ \epsilon \le \InSec{euf-cma}(\Pi_\textnm{sig}; t_S + 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; the theorem follows immediately.
\end{proof}

\subsubsection{Using one-time encryption schemes}
Given the secrecy and authenticity results, one might conclude that it
suffices to use a `one-time symmetric encryption scheme' -- i.e., one which
is secure only if used to encrypt a single plaintext.  This is, alas, not
true if one factors in the requirement of deniability.

Consider GCM \cite{McGrew:2004:SPG,cryptoeprint:2004:193}, which builds
authenticated encryption from a pseudorandom permutation.  Full GCM requires
a nonce as an additional input; for one-time encryption, a fixed nonce is
clearly sufficient.  However, if a nonce is reused, authenticity is
lost.\footnote{%
  None of the following should be considered an attack on, or a disparagement
  of, GCM.  Indeed, we consider GCM to be a fine mode of operation.} %

GCM uses a Carter--Wegman authenticator based on a polynomial-evaluation hash
in $\gf{2^{128}}$: the ciphertext blocks $c_i$ (for $0 \le i < \ell$) are
used as coefficients of a polynomial, evaluated at a secret point $x$
determined by the key; the authentication tag is
\[ t = E_K(n) + \sum_{0\le i<\ell} c_i x^i \]
Suppose that $c_i$ and $c'_i$ are distinct $\ell$-block ciphertexts
authenticated using the same nonce, giving tags $t$ and $t'$; then adding the
authentication equations (and recalling that we're working in characteristic
2), we have
\[ \sum_{0\le i<\ell} (c_i + c'_i) x^i = t + t' \]
This polynomial has at most $\ell$ roots in $\gf{2^{128}}$, so a candidate
can be verified in about $\ell$ chosen-ciphertext queries.

GCM encryption works using counter mode, i.e., $c_i = E_K(n + i + 1) \xor
m_i$ for message blocks $m_i$; so constructing \emph{meaningful} forgeries is
easy given a single known plaintext/ciphertext pair.

Suppose, then, that our scheme is instantiated using `one-time' GCM -- with
fixed nonce -- as the symmetric encryption scheme.  If a sender or a
recipient wishes to construct a simulated ciphertext, then anyone who can see
both the simulated ciphertext and a different (genuine or simulated)
ciphertext will be able to construct forgeries.  Obviously, if it causes
security failures, we should not expect users to construct simulated
ciphertexts, and therefore deniability suffers.

As a possible countermeasure, the recipient can record the KEM clues
previously received and reject messages which reuse clues; but this seems
cumbersome compared to simply allowing a variable -- randomized! -- nonce and
including it in the ciphertext.

\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}(\Pi_\textnm{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{Non-interactive deniable asymmetric authentication}
\label{sec:nidaa}

%% NADIA = Noninteractive Asymmetric Deniable Integrity Algorithm
%% NAIAD = Noninteractive Asymmetric Integrity Algorithm with Deniability

In this section, we describe and define an important ingredient in our
strongly deniable scheme, which we term \emph{non-interactive deniable
  asymmetric authentication}, or NIDAA for short.\footnote{%
  This could really do with a snappier name.  Suggestions are welcome.} %
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:nidaa.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:nidaa-syntax}

  A \emph{non-interactive deniable asymmetric authentication scheme} is a
  triple $\Pi_\textnm{nidaa} = (G, T, 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{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$. \qed
  \end{itemize}
\end{definition}

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

  Let $\Pi = (G, T, V)$ be a NIDAA scheme.  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:nidaa-deniability}

  Let $\Pi = (G, T, V)$ be a NIDAA scheme, and let $S$ (the `simulator') and
  $J$ (the `judge') be algorithms.  The simulator's ability to deceive the
  judge is measured by the following games.
  \begin{program}
    $\Game{sdeny-$b$}{\Pi, S}(J, m_0, m_1)$: \+ \\
      $(x, X) \gets G()$;
      $(y, Y) \gets G()$; \\
      $\tau_0 \gets T_y(X, m_0)$; \\
      $\tau_1 \gets S(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, S}(J) = \max_{m_0, m_1 \in \Bin^*} \bigl(
        \Pr[\Game{sdeny-$1$}{\Pi, S}(J, m_0, m_1) = 1] -
        \Pr[\Game{sdeny-$0$}{\Pi, S}(J, m_0, m_1) = 1] \bigr) \]
  Finally, we define the \emph{insecurity function} of $S$ as a simulator for
  the deniability of $\Pi$ by
  \[ \InSec{sdeny}(\Pi, S; t) = \max_J \Adv{sdeny}{\Pi, S}(J) \]
  where the maximum is taken over all algorithms~$J$ completing the game in
  time~$t$.
\end{definition}

Thinking about the nature of the problem reveals a few properties that a
solution must exhibit.
\begin{itemize}
\item The 
\end{itemize}


\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$;
\end{program}

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

  Let $\Pi = \Pi_\textnm{dh}^{G, H, k}$ be as described above.  Then
  \[ \InSec{uf-ocma}(\Pi; t, q_T, q_V, q_H) \le
        \InSec{cdh}(G; t + t') +
        \frac{4 q_H}{\#G} + \frac{q_V}{2^k}
  \]
  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~$\G1 \equiv \Game{uf-ocma}{\Pi}(A)$ is the standard NIDAA 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^k$ 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^k$}
        edge [<-, below] node {$H_m$} (d)
        edge [<-, above left] node {$T_m$} (xy);
    \node[right = of dd] (v) {$\Bin^k$}
        edge [<-, below] node {$H_m$} (dd)
        edge [<-, above right] node {$V_m$} (xy);
  \end{tikzpicture} \]

  We can consequently rewrite
  \[ T_{x, x'}((R, R'), m) = T_m(x P, x' P, R, R') \]
  and
  \[ V_{y, y'}((Q, Q'), m, \tau) = \begin{cases}
       1 & if $\tau = V_m(y P, y' P, Q, Q')$ \\
       0 & otherwise
     \end{cases}
  \]

  Now, $H$ -- and hence its restriction $H_m$ -- is a random function,
  assigning a uniformly distributed and independent $k$-bit string to each
  point in its domain.  Since $D$ and $D'$ are injective, the functions $T_m$
  and $V_m$ also have this property.  (Obviously the outputs of $H_m$, $T_m$
  and $V_m$ are not independent of \emph{each other}, merely of other outputs
  of the same function.)  It's also clear that the action of $H_m$ on
  $D(G^4)$ is determined by $T_m$, and similarly for $D'(G^4)$ and $V_m$.
  This observation motivates the definition of the next game~$\G2$.

  Game~$\G2$ redefines the three oracles provided to the adversary in terms
  of three new functions $T$, $V$ and $H$ shown in \xref{fig:dh-nidaa-g2}.
  We use the `lazy sampling' technique; we implement $T$ directly as a lazily
  sampled random function; $V$ consults $T$ where applicable, and otherwise
  uses a separate lazily sampled random function; and $H$ consults $T$ or $V$
  where applicable.

  \begin{figure}
    \begin{program}
      Initialization: \+ \\
        $\mathcal{H} \gets \emptyset$; \\
        $\mathcal{T} \gets \emptyset$; \\
        $\mathcal{V} \gets \emptyset$; \-
      \\[\medskipamount]
      $T(R, R', m)$: \+ \\
        \IF $(R, R', m) \in \dom \mathcal{T}$ \THEN \\
        \quad $\tau \gets \mathcal{T}(R, R', m)$; \\
        \ELSE \\ \ind
          $\tau \getsr \Bin^k$; \\
          $\mathcal{T} \gets \mathcal{T} \cup \{ (R, R', m) \mapsto \tau \}$;
          \- \\
        \RETURN $\tau$; \-
    \next
      $V'(Q, Q', m)$: \+ \\
        \IF $(Q, Q', m) \in \dom \mathcal{V}$ \THEN \\
        \quad $\tau' \gets \mathcal{V}(Q, Q', m)$; \\
        \ELSE \\ \ind
          \IF $Q = X \land Q' = X'$ \THEN
            $\tau' \gets T(Y, Y', m)$; \\
          \ELSE
            $\tau' \getsr \Bin^k$; \\
          $\mathcal{V} \gets \mathcal{V} \cup
                \{ (Q, Q', m) \mapsto \tau' \}$;
          \- \\
        \RETURN $\tau'$; \-
      \\[\medskipamount]
      $V(Q, Q', m, \tau)$: \+ \\
        $\tau' \gets V'(Q, Q', m)$; \\
        \IF $\tau = \tau'$ \THEN \RETURN $1$ \ELSE \RETURN $0$; \-
    \newline
      $H(s)$: \+ \\
        \IF $s \in \dom \mathcal{H}$ \THEN
          $h \gets \mathcal{H}(s)$; \\
        \ELSE \\ \ind
          \IF $s = [m, Q, Q', R, R', Z, Z', W, W']$ for some \\
          \hspace{4em}
          $(m, Q, Q', R, R', Z, Z', W, W') \in \Bin^* \times G^8$
          \THEN \\ \ind
            \IF $(Q, Q') = (X, X') \land
                  (Z, Z', W, W') = (x R, x R', x' R, x' R')$ \THEN
              $h \gets T(R, R', m)$; \\
            \ELSE \IF $(R, R') = (Y, Y') \land
                  (Z, Z', W, W') = (y Q, y' Q, y Q', y' R')$ \THEN
              $h \gets V'(Q, Q', m)$; \\
            \ELSE
              $h \getsr \Bin^k$; \- \\
          \ELSE
            $h \getsr \Bin^k$; \\
          $\mathcal{H} \gets \mathcal{H} \cup \{ s \mapsto h \}$; \- \\
        \RETURN $h$;
    \end{program}

    \caption{Tagging, verification and hashing functions for $\G2$}
    \label{fig:dh-nidaa-g2}
  \end{figure}

  The adversary's oracles map onto these functions in a simple way: $H$ is
  precisely the hashing oracle, and
  \[ T_{x, x'}((R, R'), m) = T(R, R', m) \qquad \textrm{and} \qquad
     V_{y, y'}((Q, Q'), m, \tau) = V(Q, Q', m) \]
  Given the foregoing discussion, we see that, despite the rather radical
  restructuring of the game, all of the quantities that the adversary sees
  are distributed identically, and therefore
  \begin{equation}
    \label{eq:dh-nidaa-s1}
    \Pr[S_2] = \Pr[S_1]
  \end{equation}

  Game~$\G3$ is the same as $\G2$, except that we no longer credit the
  adversary with a win if it makes a verification query $V_{y, y'}((X, X'),
  m, \tau)$ without previously making a hashing query $H([m, X, X', Y, Y', y
  X, y' X, y X', y' X'])$.  If this happens, either there has been a previous
  query to $T_{x, x'}((Y, Y'), m)$, in which case the verification query
  can't count as a win in any case, or there was no such query, in which case
  the true tag $\tau'$ will be freshly generated uniformly at random.
  Evidently, then,
  \begin{equation}
    \label{eq:dh-nidaa-s2}
    \Pr[S_2] - \Pr[S_3] \le \frac{q_V}{2^k}
  \end{equation}

  Game~$\G4$ is similar to $\G3$, except that we change the way that the keys
  are set up.  Rather than choosing $x'$ and $y'$ at random and setting $(X',
  Y') = (x' P, y' P)$, we choose $(u, u', v, v') \inr \gf{p}$ and set
  \[ X' = u P + u' X \qquad \textrm{and} \qquad Y' = v P + v' Y \]
  It's clear that (a) $X'$ and $Y'$ are still uniformly distributed on $G$,
  and (b) they are independent of $u'$ and $v'$.  Since this change doesn't
  affect the distribution of $X'$ and $Y'$, we conclude that
  \begin{equation}
    \label{eq:dh-nidaa-s3}
    \Pr[S_4] = \Pr[S_3]
  \end{equation}

  Finally, we bound $\Pr[S_4]$ by a reduction from the computational
  Diffie--Hellman problem in~$G$.  The reduction receives points $X^* = x P$
  and $Y^* = y P$ and must compute $Z^* = x y P$.  It sets $X = X^*$ and $Y =
  Y^*$.  It chooses $u$, $u'$, $v$, and $v'$, determines $X'$ and $Y'$ as in
  $\G4$, and runs $A$ with simulated oracles: the tagging and verification
  oracles work exactly as in $\G4$; however, it cannot implement the hashing
  function as described, so we must change it:
  \begin{itemize}
  \item rather than checking whether $(Z, Z', W, W') = (x R, x R', x' R, x'
    R')$, we check whether $(W, W') = (u R + u' Z, u R' + u' Z')$; and
  \item rather than checking whether $(Z, Z', W, W') = (y Q, y' Q, y Q', y'
    R')$, we check whether $(Z', W') = (v R + v' Z, v R' + v' W)$.
  \end{itemize}
  Let $F$ be the event that this change causes the reduction's hashing
  function to make a decision that the proper $\G4$ wouldn't make.

  Let $T$ be the event that the adversary (apparently, using the reduction's
  modified hashing function) makes a successful forgery.  In this case, we
  must have seen a hashing query $H([m, X, X', Y, Y', Z, v R + v' Z, W, v R'
  + v' W])$.  If $F$ doesn't occur, then we in fact have $Z = x y P = Z^*$;
  the work we must do in the reduction over and above $\G1$ is to choose $u$
  etc., to compute $X'$ and $Y'$, perform the dictionary maintenance, and
  use the twin-Diffie--Hellman detector, so
  \[ \Pr[T \mid \bar{F}] \le \InSec{cdh}(G; t + t') \]
  Furthermore, the reduction and $\G4$ proceed identically unless $F$ occurs,
  so \xref{lem:shoup} gives
  \[ \Pr[S_4] - \Pr[T] \le \Pr[F] \]
  A simple calculation bounds $\Pr[T]$:
  \begin{eqnarray*}[rl]
    \Pr[T] & =   \Pr[T \land F] + \Pr[T \land \bar{F}] \\
           & =   \Pr[T \land F] + \Pr[T \mid \bar{F}] \Pr[\bar{F}] \\
           & \le \Pr[F] + \Pr[T \mid \bar{F}] \\
           & \le \InSec{cdh}(G; t + t') + \Pr[F]
             \eqnumber \label{eq:dh-nidaa-t}
  \end{eqnarray*}
  Finally, we bound $\Pr[F]$ using \xref{lem:2dh-detect}:
  \begin{equation}
    \label{eq:dh-nidaa-f}
    \Pr[F] \le \frac{2 q_H}{\#G}
  \end{equation}
  Piecing together equations~\ref{eq:dh-nidaa-s1}--\ref{eq:dh-nidaa-f}
  completes the proof.
\end{proof}

\subsection{Magic tokens: an alternative to NIDAA}
\label{sec:magic}

For readers who dislike random oracles, we briefly sketch an alternative to
NIDAA schemes.  If we're willing to encrypt the NIDAA tag then we don't
actually have to reveal to the adversary any tag intended for the target
recipient: we can replace them all with nonsense strings of the same length,
as we did with the signatures in the proof of \xref{th:gwd-authenticity}.
And if we don't have to reveal them, they don't have to be message-dependent!
We call these \emph{magic tokens}.

The only requirements on a magic token are that the sender and recipient
should both be able to compute it, but the adversary shouldn't -- even if he
shares many other tokens with the sender.  So how do we make a token?  Well,
a Diffie--Hellman shared secret seems like a plausible choice.

Again we work in a cyclic group~$G = \langle P \rangle$ with $p = \#G$ prime
If Alice's and Bob's private keys are $a$ and $b$ respectively, and their
public keys are $A = a P$ and $B = b P$, then their token is simply $Z = a b
P$.

This doesn't quite work.  Suppose the adversary chooses $X = A - r P$ as his
public key, for some $r \inr \gf{p}$.  If Bob sends the adversary a token $Y
= b X = b A - b r P = Z - r B$, then the adversary computes $Z = Y + r B$
which is the token shared by Alice and Bob.

We can fix this.  Along with the shared group, we select a random common
reference string, and include in each user's public key a non-malleable
non-interactive zero-knowledge proof of knowledge \cite{DeSantis:2001:RNI} of
the corresponding private key.  Now before handing over a token, Bob will
check the NIZK.  For maliciously formed public keys like $Y$ above, the
adversary doesn't know the private key, and so Bob will fail to verify the
NIZK.

Slightly more formally, we sketch a reduction from the computational
Diffie--Hellman problem to forging Alice and Bob's token.  The reduction
passes $A$ and $B$ to the forger, along with a freshly generated common
reference string and simulated NIZKs for $A$ and $B$.  The forger runs and
outputs its guess as to the token, which (if the token is correct) is
precisely the solution to the CDH problem.  All that remains is to implement
a token-issuing oracle: given $(Y, N)$, we must compute $b Y$, where $B = b
P$ and $N$ is a NIZK proof of knowledge for $y$ such that $Y = y P$.  To do
this, we use the NIZK extractor to recover $y$ from the adversary and return
$y B = b Y$; this will work despite the adversary having seen the simulated
proofs for $A$ and $B$ because the NIZK is non-malleable.

\part{trailing cruft}
%%%--------------------------------------------------------------------------
\section{Diffie--Hellman-based strongly deniable construction}

This section describes an authenticated asymmetric encryption scheme which
achieves a stronger definition of deniability: a simulator can construct a
convincing ciphertext without having to see a genuine one.

The scheme's security depends on a number of ingredients:
\begin{itemize}
\item a cyclic group~$G = \langle P \rangle$, with prime order~$p$, in which
  the computational Diffie--Hellman problem is hard;
\item a symmetric encryption scheme~$\Pi_\textnm{se} = (k, E, D)$ which
  provides secrecy under chosen-plaintext attack; and
\item a cryptographic hash function~$H\colon \Bin^* \to \Bin^k$, which we
  shall model as a random oracle.
\end{itemize}

\subsection{Prologue: asymmetric deniable authentication}

Rather than present the entire scheme in one go, we first present the
important central part, which provides deniable authentication using
asymmetric keys.

\begin{definition}[$\Pi_\textnm{auth}^{G, H}$]
  \label{def:pi-auth}

  Let $G$ be a cyclic group, of prime order~$p$, generated by $P$; and let
  $H\colon \Bin^* \to \Bin^k$ be a hash function.

  The asymmetric authentication scheme $\Pi_\textnm{auth}^{G, H} =
  (\Xid{G}{auth}^{G, H}, \Xid{T}{auth}^{G, H}, \Xid{V}{auth}^{G, H})$ is
  defined as follows.
  \begin{program}
    $\Xid{G}{auth}^{G, H}()$: \+ \\
      $x \getsr \gf{p}$; $x' \getsr \gf{p}$;
      $X \gets x P$; $X' \gets x' P$; \\
      $y \getsr \gf{p}$;
      $Y \gets y' P$; \\
      \RETURN $\bigl( (x, x', y), (X, X', Y) \bigr)$;
  \- \\[\medskipamount]
    $\Xid{T}{auth}^{G, H}_{x, x', y}(m)$: \+ \\
      $h \gets H_p([\cookie{msg}, m]) + p \Z$; \\
      $Z \gets x y h P$;
      $Z' \gets x' y h P$; \\
      $\tau \gets H([\cookie{tag}, Z, Z'])$; \\
      \RETURN $\tau$;
  \- \\[\medskipamount]
    $\Xid{V}{auth}^{G, H}_{x, x', y}(m, \tau)$: \+ \\
      \IF $\tau = \Xid{T}{auth}^{G, H}_{x, x', y}(m)$
        \THEN \RETURN $1$ \\ \ELSE \RETURN $0$;
  \next
    $H_n(x)$: \+ \\
      $i \gets 0$; \\
      $\ell \gets \lfloor \log_2 n \rfloor + 1$; \\
      \REPEAT \\ \ind
        $h \gets \emptystring$; \\
        \WHILE $|h| < \ell$ \DO \\ \ind
          $h \gets h \cat H([i, n, x])$; \\
          $i \gets i + 1$; \- \\
        $[y]_\ell \gets h[0 \bitsto \ell]$; \- \\
      \UNTIL $y < n$; \\
      \RETURN $y$;
  \end{program}
\end{definition}

Observe that $Z = x h Y = y h X$ and $Z' = z' h Y = y h X'$, so either $(x,
x')$ or $y$, together with the public keys $(X, X', Y)$, are sufficient to
compute or verify tags.

The function~$H_n\colon \Bin^* \to \{0, 1, \ldots, n - 1\}$ is a random
mapping 

\subsubsection{System parameters}
Let $(G, +)$ be a finite, prime-order (necessarily cyclic) group in which the
computational Diffie--Hellman problem is difficult; let $p = \#G$ be the
order of $G$, and let $P \in G - \{ 0 \}$ be a generator of $G$.  Let
$H\colon \Bin^* \to \Bin^k$ be a hash function (to be modelled as a random
oracle) and $\Pi_{se} = (k, E, D)$ be a symmetric encryption scheme.

\subsubsection{Keys}
Each user chooses two indices $x, x' \getsr \gf{p}$.  The pair $(x, x')$ is
the user's private key, and the pair $(X, X') = (x P, x' P)$ is the
corresponding public key.

\begin{program}
  Algorithm $\Xid{G}{dh}^{G, \Pi_\textnm{se}, H}()$: \+ \\
    $x \getsr \gf{p}$; $X \gets x P$; \\
    $x' \getsr \gf{p}$; $X' \gets x' P$; \\
    \RETURN $\bigl( (x, x'), (X, X') \bigr)$; \-
\newline
  Algorithm $\Xid{E}{dh}^{G, \Pi_\textnm{se}, H}_{x, x'}(Y, Y', m)$: \+ \\
    $r \getsr \gf{p}$; $R \gets r P$; \\
    $K \gets H(\cookie{key}, R, r Y, r Y')$; \\
    $c \gets E_K(\empty, m)$; \\
    $h \gets H(\cookie{msg}, c)$; \\
    $\sigma \gets H(\cookie{sig}, R, x h Y, x h Y')$; \\
    \RETURN $(R, \sigma, c)$; \-
\next
  Algorithm $\Xid{D}{dh}^{G, \Pi_\textnm{se}, H}_{x, x'}
      (Y, Y', R, \sigma, c)$: \+ \\
    $h \gets H(\cookie{msg}, c)$; \\
    \IF $\sigma \ne H(\cookie{sig}, R, x h Y, x' h Y)$ \THEN
      \RETURN $\bot$; \\
    $K \gets H(\cookie{msg}, R, x R, x' R)$; \\
    $m \gets D_K(c)$; \\
    \RETURN $m$;
\end{program}

Deniable authentication is somewhat slippery to define.

Here, then, is a first stab at a definition.  We'll capture Alice's attempt
at presenting evidence as an algorithm.  It runs in two parts.  The first
part is given Alice's private key~$a$ and Bob's public key~$B$; it runs for a
while, and eventually produces a message~$m$, and a state~$s$ for the second
part.  We get Bob to encrypt this message, and then run the second part of
Alice's algorithm, giving it the state~$s$ from the first part and the
ciphertext $c = E_b(A, m)$; it too runs for a while, and eventually outputs
an evidence package~$v$.  Finally, we run Justin's algorithm~$J$ on~$c$, $m$
and $v$, and Justin outputs either 1 or~0 depending on whether he was
convinced.  For deniability, then, we'd demand that, for any Alice
algorithm~$A$, there's a simulator $S(A)$ which accepts $a$, $m$, $c$ and~$s$
from the first part of $A$, and some $m' \ne m$, and outputs $c'$ and $v'$
such that $J$ can't distinguish simulated inputs $(c', m', v')$ from genuine
ones $(c, m, v)$.

Unfortunately, it seems really hard to make this work.  For example, $v$
might contain a hash of $m$, which would make Justin's job really easy.  We
can't simulate this kind of evidence in a black-box way: the first part of
Alice's algorithm can encode the hash in its state, so the simulator can't
substitute a different message without understanding the structure of either
the state or the evidence package.

This isn't the only problem with the above definition.
\begin{itemize}
\item It only models Alice presenting her evidence noninteractively.  We'd
  like to be able to rule out interactive proofs between Alice and Justin.
\item It allows the simulator a choice of alternative message $m'$.  While
  the simulator might be able to raise a doubt that Alice's claimed
  message~$m$ might not have been sent by Bob, she might still be able to
  demonstrate that Bob's message was very \emph{similar} to~$m$.
\end{itemize}

In fact, the definition is unnecessarily complicated.  


%% What we /don't/ want to happen: Alice receives message from Bob, presents
%% judge with convincing evidence that Bob sent it.  So we want a simulator
%% which makes equally convincing evidence.
%%
%% Judge can't decrypt message sent to Alice without help.  Alice might just
%% turn over her private key, or maybe reveal some partial information
%% sufficient to decrypt the message.
%%
%% Oooh: Alice might try to prove stuff about the plaintext in
%% zero-knowledge.  Do I really need to capture full interaction?  This will
%% turn into a disaster.
%%
%% What inputs do I give Alice, the judge, and the simulator?  Simulation
%% without Alice's private key (or something like it) isn't going to work
%% well: IND-CCA!  We could consider partial information about Alice's key,
%% but it's going to have to come from somewhere, so we'll suppose that Alice
%% uses it directly.  (Working with partial information seems really hard, so
%% I'll leave that one for someone cleverer.)
%%
%% What does Alice give the judge?  Ciphertext, plaintext, supporting
%% evidence.  The supporting evidence is tough: want to allow stuff like
%% proofs or session keys, but disallow things like hashes of plaintext.
%%
%% Game, initial stab
%%
%%   1. Alice chooses message $m$.
%%   2. Sends $m$ to Bob.  Bob encrypts $m$, and returns ciphertext $y$.
%%   3. Alice examines $y$ and constructs evidence $v$.
%%   4. Alice sends $(m, y, v)$ to judge
%%
%% This is going to be hard.  Provide input message to Alice and universally
%% quantify?  Maximize?
%%
%% So, the real game, for a message $m$ is to run Alice with $m$ and $y$.

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

A number of problems remain outstanding.
\begin{itemize}
\item Construct a strongly deniably authenticated encryption scheme which is
  secure in the standard model.
\end{itemize}


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

I'm very grateful to Christine Swart for encouraging me to actually write
this up properly.

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

\end{document}

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