Various small fixes.

[doc/ips] / enc-pub.tex

\xcalways\section{Public-key encryption}\x

\xcalways\subsection{Syntax}\x

\begin{slide}
  \head{Syntax of public-key encryption schemes}

  A public-key encryption scheme $\mathcal{E} = (G, E, D)$ is a triple of
  algorithms:
  \begin{itemize}
  \item A probabilistic \emph{key-generation} algorithm $G(k)$ which returns
    a matching public/private key pair $(P, K)$.
  \item A probabilistic \emph{encryption} algorithm $E(P, m)$ which returns a
    ciphertext $c$.  We write $E_P(m)$ for $E(P, m)$.
  \item A deterministic \emph{decryption} algorithm $D(K, c)$.  If $(P, K)
    \in G(k)$ and $c \in E(P, m)$ then $m = D(K, c)$.  We write $D_K(c)$ for
    $D(K, c)$.
  \end{itemize}
  On those occasions it matters, we write $\mathcal{P} = \dom E_P$ as the
  \emph{plaintext space}, and $\mathcal{C} = \dom D_K$ as the
  \emph{ciphertext space}.  Hence, $E_P\colon \mathcal{P} \to \mathcal{C}$
  and $D_K\colon \mathcal{C} \to \mathcal{P} \cup \{ \bot \}$ (allowing an
  `invalid ciphertext' return).
\end{slide}

\xcalways\subsection{Semantic security and indistinguishability}\x

\begin{slide}
  \head{Notation for oracles}

  We'll use the following decryption oracles throughout, to abbreviate the
  properties of the various attacks:
  \begin{tabular}[C]{l Mc Mc }
                                \hlx*{hv}
    Attack & D_0(c) & D_1(c) \\ \hlx{vhv}
    CPA    & \bot   & \bot   \\
    CCA1   & D_K(c) & \bot   \\
    CCA2   & D_K(c) & D_K(c) \\ \hlx*{vh}
  \end{tabular}
  In all cases, we forbid the adversary from querying a decryption oracle on
  a challenge ciphertext, i.e., one returned to it by the experiment.
\end{slide}

\begin{slide}
  \topic{semantic security}
  \head{Semantic security}
  
  Semantic security for $\mathcal{E} = (G, E, D)$, against an adversary
  $A$ and attack $\id{atk} \in \{\text{cpa}, \text{cca1}, \text{cca2}\}$
  is measured using the following game \cite{Bellare:2000:CST}:
  \begin{program}
    Experiment $\Expt{sem-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
      $(P, K) \gets G$; \\
      $(\mathcal{M}, s) \gets A^{D_0(\cdot)}(\cookie{select}, P)$; \\
      $x_0 \getsr \mathcal{M}$; $x_1 \getsr \mathcal{M}$; \\
      $y \gets E_P(x_1)$; \\
      $(f, \alpha) \gets A^{D_1(\cdot)}(\cookie{predict}, y, s)$; \\
      \IF $f(x_b) = \alpha$ \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
  Here, $\mathcal{M}\colon \mathcal{P} \to [0, 1]$ is a \emph{distribution}
  over the plaintext space, and $f\colon \mathcal{P} \to \ran f$ is a
  \emph{function} on plaintexts, with $\alpha \in \ran f$.
\end{slide}

\begin{slide}
  \head{Semantic security (cont.)}

  We include the time required to sample the distribution $\mathcal{M}$ and
  to compute the function $f$ in the adversary's running time.

  We require that $\mathcal{M}$ is \emph{valid}: i.e., that all messages in
  $\supp \mathcal{M}$ have the same length.
\end{slide}

\begin{slide}
  \topic{indistinguishability}
  \head{Indistinguishability}
  
  Indistinguishability for $\mathcal{E} = (G, E, D)$, against an adversary
  $A$ and attack $\id{atk} \in \{\text{cpa}, \text{cca1}, \text{cca2}\}$
  is measured using the following game:
  \begin{program}
    Experiment $\Expt{ind-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
      $(P, K) \gets G$; \\
      $(x_0, x_1, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$; \\
      \IF $|x_0| \ne |x_1|$ \THEN \RETURN $0$; \\
      $y \gets E_P(x_b)$; \\
      $b' \gets A^{D_1(\cdot)}(\cookie{guess}, y, s)$; \\
      \RETURN $b'$;
  \end{program}
  In the first stage, the adversary has to choose two plaintexts.  One is
  then chosen by the experimenter, encrypted, and the corresponding
  ciphertext given to the adversary.  The adversary must decide which
  plaintext was encrypted.
\end{slide}

\begin{slide}
  \topic{advantage and insecurity}
  \head{Advantage and insecurity}
  
  For a public-key encryption scheme $\mathcal{E}$, under attack $\id{atk}
  \in \{\text{cpa}, \text{cca1}, \text{cca2}\}$ by an adversary $A$, we
  define $A$'s advantage by:
  \begin{eqnarray*}[rl]
    \Adv{ind-\id{atk}}{\mathcal{E}}(A) &=
      \Pr[\Expt{ind-\id{atk}-$1$}{\mathcal{E}}(A) = 1] -
      \Pr[\Expt{ind-\id{atk}-$0$}{\mathcal{E}}(A) = 1];
  \\
    \Adv{sem-\id{atk}}{\mathcal{E}}(A) &=
      \Pr[\Expt{sem-\id{atk}-$1$}{\mathcal{E}}(A) = 1] -
      \Pr[\Expt{sem-\id{atk}-$0$}{\mathcal{E}}(A) = 1].    
  \end{eqnarray*}
  We define insecurities for $\id{goal} \in \{\text{ind}, \text{sem}\}$ under
  chosen plaintext attacks, and chosen ciphertext attacks $\id{cca} \in
  \{\text{cca1}, \text{cca2}\}$ by:
  \begin{eqnarray*}
    \InSec{\id{goal}-cpa}(\mathcal{E}; t) &=
      \max_A \Adv{\id{goal}-cpa}{\mathcal{E}}(A);
  \\
     \InSec{\id{goal}-\id{cca}}(\mathcal{E}; t, q_D) &=
       \max_A \Adv{\id{goal}-\id{cca}}{\mathcal{E}}(A).
  \end{eqnarray*}
  where the maxima are taken over adversaries $A$ which run in time $t$ and
  issue $q_E$ encryption and $q_D$ decryption queries.
\end{slide}

\begin{slide}
  \topic{good news}
  \head{Some good news}

  Now there's some good news: \emph{semantic security and (find-then-guess)
  indistinguishability are almost equivalent}.

  More precisely, if we fix a collection of resource constraints $R$, we have
  \[ \InSec{sem-\id{atk}}(\mathcal{E}; R) \le
     \InSec{ind-\id{atk}}(\mathcal{E}; R) \le
     2 \cdot \InSec{sem-\id{atk}}(\mathcal{E}; R). \]%
  It's useful to realise that a relatively strong notion like semantic
  security is actually equivalent to a simpler notion like
  indistinguishability.  The latter is certainly easier to work with in
  proofs of security.
\end{slide}

\begin{proof}
  \label{pf:pub-ind-eq-sem}
  Proving that $\text{IND-\id{atk}} \implies \text{SEM-\id{atk}}$ is
  pretty easy, so we do that first.  Suppose that $A'$ attacks $\mathcal{E}$
  in the semantic security sense.  Consider the find-then-guess adversary
  $A$:
  \begin{program}
    Adversary $A^{D(\cdot)}(\cookie{find}, P)$: \+ \\
      $(\mathcal{M}, s') \gets A'^{D(\cdot)}(\cookie{select}, P)$; \\
      $x_0 \getsr \mathcal{M}$; $x_1 \getsr \mathcal{M}$; \\
      \RETURN $(x_0, x_1, (x_1, s'))$;
  \next
    Adversary $A^{D(\cdot)}(\cookie{guess}, y, s)$: \+ \\
      $(x_1, s') \gets s$; \\
      $(f, \alpha) \gets A'^{D(\cdot)}(\cookie{predict}, y, s')$; \\
      \IF $f(x_1) = \alpha$ \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
  Here, $A$ is simulating the semantic security experiment itself, drawing
  plaintexts from $A'$'s distribution $\mathcal{M}$ and evaluating its chosen
  function.
  
  We study the result of the experiment
  $\Expt{ind-\id{atk}-$b$}{\mathcal{E}}(A)$.  Firstly, suppose $b = 1$.
  Then $y \in E_P(x_1)$, and $A$ succeeds with the same probability that $A'$
  wins in $\Expt{sem-\id{atk}-$1$}{\mathcal{E}}(A')$.  Secondly, suppose $b
  = 0$.  Then $y \in E_P(x_0)$, but we still compare $A'$'s answer against
  $x_1$, as in $\Expt{sem-\id{atk}-$0$}{\mathcal{E}}(A')$, up to
  relabelling of $x_0$ and $x_1$.  Hence,
  \[ \Adv{ind-\id{atk}}{\mathcal{E}}(A) =
       \Adv{sem-\id{atk}}{\mathcal{E}}(A'). \]%
  
  Now we show that $\text{SEM-\id{atk}} \implies \text{IND-\id{atk}}$.
  Suppose that $A$ attacks $\mathcal{E}$ in the indistinguishability sense.
  Then consider the adversary $A'$ attacking its semantic security:
  \begin{program}
    Adversary $A'^{D(\cdot)}(\cookie{select}, P)$: \+ \\
      $(x'_0, x'_1, s) \gets A^{D(\cdot)}(\cookie{find}, P)$; \\
      $\mathcal{M} \gets
        \{ x'_0 \mapsto \frac{1}{2}, x'_1 \mapsto \frac{1}{2} \}$; \\
      \RETURN $(x'_0, x'_1, s')$;
  \next
    Adversary $A'^{D(\cdot)}(\cookie{predict}, y, s')$: \+ \\
      $(x'_0, x'_1, s) \gets s'$; \\
      $b \gets A^{D(\cdot)}(\cookie{guess}, y, s)$; \\
      \RETURN $(\lambda x.x, x'_b)$;
  \end{program}
  Here $A'$ is simply running the indistinguishability experiment.  In the
  $\cookie{select}$ stage, it runs $A$'s $\cookie{find}$ stage, and returns
  the uniform distribution over $A$'s two chosen plaintexts.  In the
  $\cookie{predict}$ stage, $A'$ collects $A$'s $\cookie{guess}$ and returns
  the identity function $\lambda x.x$ and the guessed plaintext.

  In the case of experiment $\Expt{sem-\id{atk}-$1$}{\mathcal{E}}(A')$, the
  rules are fair, and we win with probability
  \[  p = \frac{1}{2} + \frac{\Adv{ind-\id{atk}}{\mathcal{E}}(A)}{2}. \]
  In the case of $\Expt{sem-\id{atk}-$0$}{\mathcal{E}}(A')$, however, we
  \emph{lose} in the event that $x_0 = x'_b$.  This happens if \emph{either}
  $x_0 = x_1$ and we guess correctly (probability $p/2$), \emph{or} if $x_0
  \ne x_1$ and we guess incorrectly (probability $(1 - p)/2$).  Hence, we see
  that have
  \[ \Adv{sem-\id{atk}}{\mathcal{E}}(A') =
       \frac{1}{2} \Adv{ind-\id{atk}}{\mathcal{E}}(A) \]%
  completing the proof.
\end{proof}

\xcalways\subsection{Non-malleability}\x

\begin{slide}
  \topic{definition}
  \head{Non-malleability}
  
  The intuition behind non-malleability is that an adversary can't easily
  take some ciphertext and turn it into some other ciphertext such that the
  plaintexts have a simple relationship to each other.

  Here's a relatively standard definition of non-malleability, from
  \cite{Bellare:1998:RAN, Bellare:1999:NEE}:
  \begin{program}
    Experiment $\Expt{cnm-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
      $(P, K) \gets G$; \\
      $(\mathcal{M}, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$;
      $x_0 \getsr \mathcal{M}$; $x_1 \getsr \mathcal{M}$;
      $y \gets E_P(x_1)$; \\
      $(R, \vect{y}) \gets A^{D_1(\cdot)}(\cookie{guess}, y, s)$;
      $\vect{x} \gets D_K(\vect{y})$; \\
      \IF $y \notin \vect{y} \land
           R(x_b, \vect{x})$ \THEN \RETURN $1$;
      \ELSE \RETURN $0$;
  \end{program}
  In the above, $\mathcal{M}$ is a valid distribution on plaintexts, and $R$
  is an $n$-ary relation on plaintexts.  The adversary's advantage is
  \[ \Adv{cnm-\id{atk}}{\mathcal{E}}(A) =
       \Pr[\Expt{cnm-\id{atk}-$1$}{\mathcal{E}}(A) = 1] -
       \Pr[\Expt{cnm-\id{atk}-$0$}{\mathcal{E}}(A) = 1]. \]%
\end{slide}

\begin{slide}
  \topic{more good news}
  \head{Non-malleability (more good news)}

  The previous definition involved all sorts of nasties like distributions
  and relations.  Fortunately, there's an approximately equivalent notion,
  based on indistinguishability with a single \emph{parallel}
  chosen-ciphertext query:
  \begin{program}
    Experiment $\Expt{nm-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
      $(P, K) \gets G$; \\
      $(x_0, x_1, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$;
      $y \gets E_P(x_b)$; \\
      $(\vect{y}, t) \gets A^{D_1(\cdot)}(\cookie{choose}, y, s)$;
      \IF $y \in \vect{y}$ \THEN \RETURN $0$; \\
      $\vect{x} \gets D_K(\vect{y})$;
      $b \gets A^{D_1(\cdot)}(\cookie{guess}, \vect{x}, t)$;
      \RETURN $b$;
  \end{program}
  We define advantage by
  \[ \Adv{nm-\id{atk}}{\mathcal{E}}(A) =
       \Pr[\Expt{nm-\id{atk}-$1$}{\mathcal{E}}(A) = 1] -
       \Pr[\Expt{nm-\id{atk}-$0$}{\mathcal{E}}(A) = 1]. \]%
\end{slide}

\begin{proof}
  Firstly, $\text{NM} \implies \text{CNM}$.  Suppose $A'$ attacks
  $\mathcal{E}$ in the CNM sense.  Then we construct $A$ in the obvious way:
  \begin{program}
    Adversary $A^{D(\cdot)}(\cookie{find}, P)$: \+ \\
      $(\mathcal{M}, s') \gets A'^{D(\cdot)}(\cookie{find}, P)$; \\
      $x_0 \getsr \mathcal{M}$; $x_1 \getsr \mathcal{M}$; \\
      \RETURN $(x_0, x_1, (x_1, s'))$;
  \next
    Adversary $A^{D(\cdot)}(\cookie{choose}, y, s)$: \+ \\
      $(x_1, s') \gets s$; \\
      $(R, \vect{y}) \gets A'^{D(\cdot)}(\cookie{guess}, y, s')$; \\
      \RETURN $(\vect{y}, (x_1, R))$;
  \next
    Adversary $A^{D(\cdot)}(\cookie{guess}, \vect{x}, s)$: \+ \\
      $(x_1, R) \gets s$; \\
      \IF $R(x_1, \vect{x})$ \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
  Studying the behaviour of $A$, we see that it succeeds precisely when $A'$
  succeeds.  Hence
  \[ \Adv{nm-\id{atk}}{\mathcal{E}}(A) =
     \Adv{cnm-\id{atk}}{\mathcal{E}}(A'). \]%
  
  Secondly, suppose that $A$ attacks $\mathcal{E}$ in the NM sense.  Then we
  construct $A'$ in a somewhat tricky manner: $A'$ aims to run the final
  stage of $A$ from its relation $R$.
  
  We can suppose, without loss of generality, that $A$ doesn't require its
  chosen ciphertext oracle $D$ during its final $\cookie{guess}$ phase.  If
  it is allowed an adaptive chosen ciphertext oracle, it can make its
  parallel query through $D$ (admittedly at the cost of $|\vect{y}|$
  additional decryption queries).  Hence, we don't need to provide
  $A(\cookie{guess})$ with a decryption oracle.
  
  The relation isn't allowed to be probabilistic.  Hence, we choose the coins
  $\rho \in \{0, 1\}^n$ that $A(\cookie{guess})$ requires in advance.  Since
  $A$'s running time is bounded, $n$ must also be bounded.  We encode the
  values $(x'_0, x'_1, t, \rho)$ into the description of $R$ output by
  $A'(\cookie{guess})$.

  \begin{program}
    Adversary $A'^{D(\cdot)}(\cookie{find}, P)$: \+ \\
      $(x'_0, x'_1, s) \gets A^{D(\cdot)}(\cookie{find}, P)$; \\
      $\mathcal{M} \gets
        \{ x'_0 \mapsto \frac{1}{2}, x'_1 \mapsto \frac{1}{2} \}$; \\
      \RETURN $(\mathcal{M}, (x'_0, x'_1, P, s))$;
  \next
    Adversary $A'^{D(\cdot)}(\cookie{guess}, y, s')$: \+ \\
      $(x'_0, x'_1, P, s) \gets s'$; \\
      $(\vect{y}, t) \gets A^{D(\cdot)}(\cookie{choose}, y, s)$; \\
      $\rho \getsr \{0, 1\}^n$; \\
      \RETURN $(R, \vect{y})$; \- \\[\smallskipamount]
    Relation $R(x, \vect{x})$: \+ \\
      $b' \gets A(\cookie{guess}, \vect{x}, t)$ (with coins $\rho$); \\
      \IF $x = x'_{b'}$ \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
  
  The analysis of $A'$'s success probability is very similar to the proof
  that $\text{SEM} \implies \text{IND}$ above.  When the CNM experiment's
  hidden bit $b = 1$, $A'$ succeeds whenever $A$ correctly guesses which
  plaintext was encrypted, which occurs with probability
  \[  p = \frac{1}{2} + \frac{\Adv{nm-\id{atk}}{\mathcal{E}}(A)}{2}. \]
  When $b = 0$, $A'$ fails when $A$ guesses correctly and $x_0 = x_1$
  (probability $p/2$), or when $A$ guesses wrongly and $x_0 \ne x_1$
  (probability $(1 - p)/2$).  Hence, finally,
  \[ \Adv{cnm-\id{atk}}{\mathcal{E}}(A) =
       \frac{\Adv{nm-\id{atk}}{\mathcal{E}}(A)}{2}. \]%
  
  For any arbitrary resource bounds $R$, we have
  \[ \InSec{cnm-\id{atk}}(\mathcal{E}; R) \le
     \InSec{nm-\id{atk}}(\mathcal{E}; R) \le
     2 \cdot \InSec{cnm-\id{atk}}(\mathcal{E}; R'), \]%
  where $R'$ is related to $R$, but may need to allow additional decryption
  queries, to cope with NM-CCA2 adversaries which use decryption queries in
  their final $\cookie{guess}$ stages.
  
  We conclude that the two notions are almost equivalent, as claimed.
\end{proof}

\xcalways\subsection{Relations between security notions}\x

\begin{slide}
  \head{Relations between security notions \cite{Bellare:1998:RAN}}

  %%               3                   3
  %%   NM-CPA <--------- NM-CCA1 <--------- NM-CCA2
  %%      |  \__            |   \__           ^ ^
  %%      |     \__  6      |      \__ 7      | |
  %%     1|        \/_      |1        \/_    4| |1
  %%      |       5/  \__   |         /  \_   | |
  %%      v            __\  v             __\ v |
  %%   IND-CPA <-------- IND-CCA1 <------- IND-CCA2
  %%                2                 2

  \[ \xymatrix @=2cm {
    \txt{NM-CPA}   \ar[d]_1
                   \POS !<1ex, 0pt> \ar[dr]!<1ex, 0pt>|-@{/}^6 &
    \txt{NM-CCA1}  \ar[d]^1 \ar[l]_3 \ar[dr]|-@{/}^7 &
    \txt{NM-CCA2}  \ar[l]_3 \ar@<0.5ex>[d]^1 \\
    \txt{IND-CPA}  &
    \txt{IND-CCA1} \ar[l]^2
                   \POS !<-1ex, 0pt> \ar[ul]!<-1ex, 0pt>|-@{/}^5 &
    \txt{IND-CCA2} \ar[l]^2 \ar@<0.5ex>[u]^4 \\
  } \]

  \begin{list}{}{
      \settowidth{\labelwidth}{\textbf{Key}}
      \leftmargin\labelwidth\advance\leftmargin\labelsep
      \itemindent0pt\let\makelabel\textbf}
  \item[Key] \begin{itemize}
    \item An arrow $\xy\ar*+{A};<1.5cm, 0cm>*+{B}\endxy$ indicates an
      \emph{implication}: if a scheme is secure in notion $A$ then it is also
      secure in notion $B$.
    \item A crossed arrow $\xy\ar|-@{/}*+{A};<1.5cm, 0cm>*+{B}\endxy$
      indicates a \emph{separation}: there exists a scheme secure in notion
      $A$ but not in $B$.
    \item The numbers refer to sections of the proof provided in the notes.
    \end{itemize}
  \end{list}
\end{slide}

\begin{proof}
  Most of these are fairly simple.  We use the indistinguishability-based
  characterization of non-malleability that we showed earlier, because it
  makes life much easier.  We assume that schemes meeting each of the
  definitions exist, else the theorems are all vacuously true.

  \begin{enumerate}
    
  \item We show $\text{NM-\id{atk}} \implies \text{IND-\id{atk}}$ for
    $\id{atk} \in \{\text{CPA}, \text{CCA1}, \text{CCA2}\}$.  Let $[]$ denote
    the empty vector.  Suppose that $A$ attacks $\mathcal{E}$ in the
    $\text{IND-\id{atk}}$ sense.
    \begin{program}
      Adversary $A'^{D(\cdot)}(\cookie{find}, P)$: \+ \\
        $(x_0, x_1, s) \gets A^{D(\cdot)}(\cookie{find}, P)$; \\
        \RETURN $(x_0, x_1, s)$;
    \newline
      Adversary $A'^{D(\cdot)}(\cookie{choose}, y, s)$: \+ \\
        \RETURN $([], (y, s))$;
    \next
      Adversary $A'^{D(\cdot)}(\cookie{guess}, \vect{x}, s')$: \+ \\
        $(y, s) \gets s'$; \\
        $b' \gets A^{D(\cdot)}(y, s)$; \\
        \RETURN $b'$;
    \end{program}
    Evidently $\Adv{nm-\id{atk}}{\mathcal{E}}(A') =
    \Adv{ind-\id{atk}}{\mathcal{E}}(A)$, and hence
    \[ \InSec{ind-\id{atk}}(\mathcal{E}; t, q_D) \le
         \InSec{nm-\id{atk}}(\mathcal{E}; t, q_D), \]%
    proving the implication.
    
  \item We show that $\text{IND-$\id{atk}'$} \implies \text{IND-\id{atk}}$
    for $(\id{atk}', \id{atk}) \in \{(\text{CCA1}, \text{CPA}), (\text{CCA2},
    \text{CCA1})\}$.  Suppose that $A$ attacks $\mathcal{E}$ in the
    $\text{IND-\id{atk}}$ sense.
    \begin{program}
      Adversary $A'^{D(\cdot)}(\cookie{find}, P)$: \+ \\
        $(x_0, x_1, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$; \\
        \RETURN $(x_0, x_1, s)$;
    \next
      Adversary $A'^{D(\cdot)}(\cookie{guess}, y, s)$: \+ \\
        $b' \gets A^{D_1(\cdot)}(\cookie{guess}, y, s)$; \\
        \RETURN $b'$;
    \end{program}
    The oracles $D_0$ and $D_1$ are defined according to \id{atk}, as
    shown in table~\ref{tab:se-rel-oracle}.
    \begin{table}
      \begin{tabular}[C]{l Mc Mc}        \hlx*{hv}
        \id{atk}    & D_0(x) & D_1(x) \\ \hlx{vhv}
        CPA         & \bot   & \bot   \\
        CCA1        & D(x)   & \bot   \\ \hlx*{vh}
      \end{tabular}
      \caption{Relations between notions of security for public key
        encryption: decryption oracles}
      \label{tab:se-rel-oracle}
    \end{table}
    Evidently $\Adv{ind-$\id{atk}'$}{\mathcal{E}}(A') =
    \Adv{ind-\id{atk}}{\mathcal{E}}(A)$, and hence
    \[ \InSec{ind-\id{atk}}(\mathcal{E}; t, q_D) \le
         \InSec{ind-$\id{atk}'$}(\mathcal{E}; t, q_D), \]%
    proving the implication.

  \item We show that $\text{NM-$\id{atk}'$} \implies \text{NM-\id{atk}}$
    for $(\id{atk}', \id{atk}) \in \{(\text{CCA1}, \text{CPA}), (\text{CCA2},
    \text{CCA1})\}$.  Suppose that $A$ attacks $\mathcal{E}$ in the
    $\text{NM-\id{atk}}$ sense.
    \begin{program}
      Adversary $A'^{D(\cdot)}(\cookie{find}, P)$: \+ \\
        $(x_0, x_1, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$; \\
        \RETURN $(x_0, x_1, s)$;
    \newline
      Adversary $A'^{D(\cdot)}(\cookie{choose}, y, s)$: \+ \\
        $(\vect{y}, t) \gets A^{D_1(\cdot)}(\cookie{choose}, y, s)$; \\
        \RETURN $(\vect{y}, t)$;
    \next
      Adversary $A'^{D(\cdot)}(\cookie{guess}, \vect{x}, t)$: \+ \\
        $b' \gets A^{D_1(\cdot)}(\cookie{guess}, \vect{x}, t)$; \\
        \RETURN $b'$;
    \end{program}
    The oracles $D_0$ and $D_1$ are defined according to $\id{atk}'$, as
    shown in table~\ref{tab:se-rel-oracle}.  Evidently
    $\Adv{nm-$\id{atk}'$}{\mathcal{E}}(A') =
    \Adv{nm-\id{atk}}{\mathcal{E}}(A)$, and hence
    \[ \InSec{nm-\id{atk}}(\mathcal{E}; t, q_D) \le
         \InSec{nm-$\id{atk}'$}(\mathcal{E}; t, q_D), \]%
    proving the implication.

  \item We show that $\text{IND-CCA2} \implies \text{NM-CCA2}$.  Suppose that
    $A$ is an adversary attacking $\mathcal{E}$ in the NM-CCA2 sense.
    \begin{program}
      Adversary $A'^{D(\cdot)}(\cookie{find}, P)$: \+ \\
        $(x_0, x_1, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$; \\
        \RETURN $(x_0, x_1, s)$;
    \next
      Adversary $A'^{D(\cdot)}(\cookie{guess}, y, s)$: \+ \\
        $(\vect{y}, t) \gets A^{D(\cdot)}(\cookie{choose}, y, s)$; \\
        $\vect{x} = D(\vect{y})$; \\
        $b' \gets A^{D(\cdot)}(\cookie{guess}, \vect{x}, t)$; \\
        \RETURN $b'$;
    \end{program}
    Evidently $\Adv{ind-cca2}{\mathcal{E}}(A') =
    \Adv{nm-cca2}{\mathcal{E}}(A)$, and hence
    \[ \InSec{nm-cca2}(\mathcal{E}; t, q_D) \le
         \InSec{ind-cca2}(\mathcal{E}; t, q_D), \]%
    proving the implication.
    
  \item We show that $\text{IND-CCA1} \not\implies \text{NM-CPA}$.  Suppose
    that $\mathcal{E} = (G, E, D)$ is secure in the IND-CCA1 sense.  Consider
    the encryption scheme $\mathcal{E}' = (G', E', D')$:
    \begin{program}
      Algorithm $G'(k)$: \+ \\
        $(P, K) \gets G$; \\
        \RETURN $(P, K)$;
    \next
      Algorithm $E'_P(x)$: \+ \\
        $y \gets E_P(x)$; \\
        \RETURN $(0, y)$;
    \next
      Algorithm $D'_K(y')$: \+ \\
        $(b, y) \gets y'$; \\
        $x \gets D_K(y)$; \\
        \RETURN $x$;
    \end{program}
    This is a classic example of a malleable encryption scheme.

    Firstly, we show that $\mathcal{E}'$ is still IND-CCA1.  Suppose that
    $A'$ is an adversary attacking $\mathcal{E}'$ in the sense of IND-CCA1.
    Consider $A$, attacking $\mathcal{E}$:
    \begin{program}
      Adversary $A^{D(\cdot)}(\cookie{find}, P)$: \+ \\
        $(x_0, x_1, s) \gets A'^{\Xid{D'}{sim}(\cdot)}(\cookie{find}, P)$; \\
        \RETURN $(x_0, x_1, s)$; \- \\[\smallskipamount]
      Oracle $\Xid{D'}{sim}(y')$: \+ \\
        $(b, y) \gets y'$; \\
        $x \gets D(y)$; \\
        \RETURN $x$;
    \next
      Adversary $A^\bot(\cookie{guess}, y, s)$: \+ \\
        $b' \gets A'^\bot(\cookie{guess}, y, s)$; \\
        \RETURN $b'$;
    \end{program}
    Clearly, $A$ simulates the expected environment for $A'$ perfectly; hence
    \[ \Adv{ind-cca1}{\mathcal{E}'}(A') = \Adv{ind-cca1}{\mathcal{E}}(A). \]

    Now, we show that $\mathcal{E}'$ is not NM-CPA.  Consider the adversary
    $C'$:
    \begin{program}
      Adversary $C'^{D(\cdot)}(\cookie{find}, P')$: \+ \\
        \RETURN $(0, 1, \bot)$;
    \newline
      Adversary $C'^{D(\cdot)}(\cookie{choose}, y', s)$: \+ \\
        $(b, y) \gets y'$; \\
        $\vect{y} \gets [(1, y)]$; \\
        \RETURN $(\vect{y}, \bot)$;
    \next
      Adversary $C'^{D(\cdot)}(\cookie{guess}, \vect{x}, t)$: \+ \\
        \RETURN $\vect{x}[0]$;
    \end{program}
    Since $(0, y) \ne (1, y)$, the experiment provides the plaintext
    corresponding to the challenge ciphertext $y'$.
    $\Adv{nm-cpa}{\mathcal{E}'}(C') = 1$.  Hence, $\mathcal{E}'$ is insecure
    in the NM-CPA sense.

  \item We show that $\text{NM-CPA} \not\implies \text{IND-CCA1}$.  Suppose
    that $\mathcal{E} = (G, E, D)$ is secure in the NM-CPA sense.  Fix a
    security parameter $k$.  Consider the encryption scheme $\mathcal{E}' =
    (G', E', D')$:
    \begin{program}
      Algorithm $G'(k)$: \+ \\
        $(P, K) \gets G(k)$; \\
        $u \getsr \{0, 1\}^k$; $v \getsr \{0, 1\}^k$; \\
        \RETURN $((P, u), (K, u, v))$;
    \next
      Algorithm $E'_{P'}(x)$: \+ \\
        $(P, u) \gets P'$; \\
        $y \gets E_P(x)$; \\
        \RETURN $(0, y)$;
    \next
      Algorithm $D'_{K'}(y')$: \+ \\
        $(b, y) \gets y'$; \\
        $(K, u, v) \gets K'$; \\
        \IF $b = 0$ \THEN $x \gets D_K(y)$; \\
        \ELSE \IF $y = u$ \THEN $x \gets v$; \\
        \ELSE \IF $y = v$ \THEN $x \gets K$; \\
        \ELSE $x \gets \bot$; \\
        \RETURN $x$;
    \end{program}
    The idea is that the decryption oracle can be used to leak the key by
    following the little $u \to v \to K$ chain, but the parallel
    non-malleability oracle can't do this.

    We first show that $\mathcal{E}'$ is still NM-CPA.  Suppose that $A'$ is
    an adversary attacking $\mathcal{E}'$ in the NM-CPA sense.  Consider
    this adversary $A$:
    \begin{program}
      Adversary $A^\bot(\cookie{find}, P)$: \+ \\
        $u \getsr \{0, 1\}^k$; $v \getsr \{0, 1\}^k$; \\        
        $(x_0, x_1, s') \gets A'^\bot(\cookie{find}, (P, u))$; \\
        \RETURN $(x_0, x_1, (s', u, v))$;
    \newline
      Adversary $A^\bot(\cookie{choose}, y, s)$: \+ \\
        $(s', u, v) \gets s$; \\
        $(\vect{y}', t') \gets A'^\bot(\cookie{choose}, y, s')$; \\
        \FOR $j = 0$ \TO $|\vect{y}'| - 1$ \DO
          $\vect{x}'[j] \gets \bot$; \\
        \FOR $j = 0$ \TO $|\vect{y}'| - 1$ \DO \\ \quad \= \+ \kill
          $(b', y') \gets \vect{y}'[j]$; \\
          \IF $b' = 0$ \THEN $\vect{y}[j] \gets y'$; \\
          \ELSE \IF $y' = u$ \THEN \= $\vect{x}'[j] \gets v$; \\
                                   \> $\vect{y}[j] \gets \bot$; \\
          \ELSE \IF $y' = v$ \THEN \ABORT; \\
          \ELSE \= $\vect{x}'[j] \gets \bot$; \\
                \> $\vect{y}[j] \gets \bot$; \\
        \RETURN $(\vect{y}, (\vect{x}', t'))$;
    \next
      Adversary $A^\bot(\cookie{guess}, \vect{x}, t)$: \+ \\
        $(\vect{x}', t') \gets t$; \\
        \FOR $j = 0$ \TO $|\vect{x}| - 1$ \DO \\
        \quad \IF $\vect{x}'[j] = \bot$ \THEN
          $\vect{x}'[j] \gets \vect{x}[j]$; \\
        $b' \gets A'^\bot(\cookie{guess}, \vect{x}', t')$; \\
        \RETURN $b'$;
    \end{program}
    Clearly, $A$ behaves indistinguishably from the NM-CPA experiment
    expected by $A'$, unless $A$ aborts because $A'$ guesses $v$ during its
    $\cookie{choose}$ phase.  But $v$ is independent of $A'$'s view at that
    moment, so the probability this occurs is $2^{-k}$.  Hence
    \[ \Adv{nm-cpa}{\mathcal{E}'} \le
         \Adv{nm-cpa}{\mathcal{E}} + \frac{1}{2^k}. \]%

    Now to show that $\mathcal{E}'$ is insecure in the IND-CCA1 sense.
    Consider this adversary:
    \begin{program}
      Adversary $C'^{D(\cdot)}(\cookie{find}, P')$: \+ \\
        $(P, u) \gets P'$; \\
        $v \gets D(u)$; $K \gets D(v)$; \\
        \RETURN $(0, 1, K)$;
    \next
      Adversary $C'^\bot(\cookie{guess}, y, K)$: \+ \\
        $b' \gets D_K(y)$; \\
        \RETURN $b'$;
    \end{program}
    The adversary $C'$ makes 2 decryption queries, and
    $\Adv{ind-cca1}{\mathcal{E}'}(C') = 1$.  Hence, $\mathcal{E}'$ is
    insecure in the IND-CCA1 sense.
    
  \item We show that $\text{NM-CCA1} \not\implies \text{IND-CCA2}$.  Suppose
    that $\mathcal{E} = (G, E, D)$ is secure in the NM-CCA1 sense.  Let
    $\mathcal{M} = (T, V)$ be a secure MAC.  Consider the encryption scheme
    $\mathcal{E}' = (G', E', D')$:
    \begin{program}
      Algorithm $G'(k)$: \+ \\
        $(P, K) \gets G(k)$; \\
        $i \getsr \keys \mathcal{M}$; \\
        \RETURN $(P, (K, i))$;
    \next
      Algorithm $E'_P(x)$: \+ \\
        $y \gets E_P(x)$; \\
        \RETURN $(0, y, \bot)$;
    \next
      Algorithm $D'_{K'}(y')$: \+ \\
        $(b, y, \tau) \gets y'$; \\
        $(K, i) \gets K'$; \\
        \IF $b = 0$ \THEN $x \gets D_K(y)$; \\
        \ELSE \IF $\tau = \bot$ \THEN $x \gets T_i(y)$; \\
        \ELSE \IF $V_i(y, \tau) = 1$ \THEN $x \gets D_K(y)$; \\
        \ELSE $x \gets \bot$; \\
        \RETURN $x$;
    \end{program}
    Answering decryption queries only when presented with a correct tag
    ensures that the NM-CCA1 adversary can't obtain anything useful with its
    queries (hence the scheme remains NM-CCA1-secure), but the IND-CCA2
    adversary can use its adaptive queries to discover the required tag.

    Firstly, we show that $\mathcal{E}'$ is still NM-CCA1-secure.  Suppose
    $A'$ attacks $\mathcal{E}'$ in the sense of NM-CCA1.  Consider the two
    adversaries shown in \ref{fig:nm-cca1-sep-ind-cca2}: $A$ attacks the
    original $\mathcal{E}$; $A''$ attacks the MAC $\mathcal{M}$.
    \begin{figure}
    \begin{program}
      Adversary $A^{D(\cdot)}(\cookie{find}, P)$: \+ \\
        $i \getsr \keys F$; \\
        $(x_0, x_1, s') \gets A'^{\Xid{D}{sim}(\cdot)}(\cookie{find}, P)$; \\
        \RETURN $(x_0, x_1, (s', i))$; \- \\[\smallskipamount]
      Adversary $A^\bot(\cookie{choose}, y, s)$: \+ \\
        $(s', i) \gets s$; \\
        $(\vect{y}', t') \gets A'^\bot(\cookie{choose}, y, s')$; \\
        \FOR $j = 0$ \TO $|\vect{y}'| - 1$ \DO
          $\vect{x}'[j] \gets \bot$; \\
        \FOR $j = 0$ \TO $|\vect{y}'| - 1$ \DO \\ \quad \= \+ \kill
          $(b', y', \tau') \gets \vect{y}'[j]$; \\
          \IF $b' = 0$ \THEN $\vect{y}[j] \gets y'$; \\
          \ELSE \IF $z' = \bot$ \THEN \= $\vect{x}'[j] \gets T_i(y')$; \\
                                      \> $\vect{y}[j] \gets \bot$; \\
          \ELSE \IF $V_i(y', \tau') \ne 1$
          \THEN $\vect{y}[j] \gets \bot$; \\
          \ELSE \IF $y' = y$ \THEN \ABORT; \\
          \ELSE $\vect{y}[j] \gets y'$; \- \\
        \RETURN $(\vect{y}, (\vect{x}', t'))$; \- \\[\smallskipamount]
      Adversary $A^\bot(\cookie{guess}, \vect{x}, t)$: \+ \\
        $(\vect{x}', t') \gets t$; \\
        \FOR $j = 0$ \TO $|\vect{x}| - 1$ \DO \\
        \quad \IF $\vect{x}'[j] = \bot$ \THEN
          $\vect{x}'[j] \gets \vect{x}[j]$; \\
        $b' \gets A'^\bot(\cookie{guess}, \vect{x}', t')$; \\
        \RETURN $b'$;
    \next
      Adversary $A''^{T(\cdot), V(\cdot)}$: \+ \\
        $(P, K) \gets G$;
        $b \getsr \{0, 1\}$; \\
        $(x_0, x_1, s) \gets A'^{\Xid{D}{sim}(\cdot)}(\cookie{find}, P)$; \\
        $y \gets (0, E_P(x_b), \bot)$; \\
        $(\vect{y}, t) \gets A'^\bot(\cookie{choose}, y, s)$; \\
        \FOR $j = 0$ \TO $|\vect{y}| - 1$ \DO \\ \quad \= \+ \kill
          $(b', y', \tau') \gets \vect{y}'[j]$; \\
          \IF $b' = 1 \land V(y', \tau') = 1$
          \THEN \RETURN $(y', \tau')$; \- \\
        \ABORT; \- \\[\smallskipamount]
      Oracle $\Xid{D}{sim}(y')$: \+ \\
        $(b, y, \tau) \gets y'$; \\
        \IF $b = 0$ \THEN $x \gets D_K(y)$; \\
        \ELSE \IF $\tau = \bot$ \THEN $x \gets T(y)$; \\
        \ELSE \IF $V(y, \tau) = 1$ \THEN $x \gets D_K(y)$; \\
        \ELSE $x \gets \bot$; \\
        \RETURN $x$;
    \end{program}
    \caption{From the proof that $\text{NM-CCA1} \not\implies
      \text{IND-CCA2}$ -- adversaries $A$ and $A''$, attacking $\mathcal{E}$
      in the NM-CCA1 sense and the MAC $\mathcal{M}$ respectively}
    \label{fig:nm-cca1-sep-ind-cca2}
    \end{figure}

    Suppose, without loss of generality, that if the challenge ciphertext $y$
    returned to $A'$ matches one of $A'$'s earlier decryption queries then
    $A'$ wins without making its parallel chosen ciphertext query.

    Let $B$ be the event that $A$ aborts; let $S$ be the event that $A$ wins,
    and let $S'$ be the event that $A'$ wins.  Since unless it aborts, $A$
    implements the NM-CCA1 game for $\mathcal{E}'$ perfectly, we must have
    \[ \Pr[A] = \Pr[A'] - \Pr[B]. \]
    But $B$ is precisely the event in which $A''$ wins its game.  Hence
    \[ \Adv{nm-cca1}{\mathcal{E}'}(A') \le
         \Adv{nm-cca1}{\mathcal{E}}(A) + \Adv{suf-cma}{\mathcal{E}}(A'') \]%
    proving the claim that $\mathcal{E}'$ remains NM-CCA1 secure.

    Now to show that $\mathcal{E}'$ is not IND-CCA2 secure.
    \begin{program}
      Adversary $C'^{D(\cdot)}(\cookie{find}, P')$: \+ \\
        \RETURN $(0, 1, \bot)$;
    \next
      Adversary $C'^{D(\cdot)}(\cookie{guess}, y, s)$: \+ \\
        $\tau \gets D(1, y, \bot)$; \\
        $b' \gets D(1, y, \tau)$; \\
        \RETURN $b'$;
    \end{program}
    The adversary $C'$ makes 2 decryption queries, and
    $\Adv{ind-cca2}{\mathcal{E}'}(C') = 1$.  Hence, $\mathcal{E}'$ is
    insecure in the IND-CCA2 sense.
    
  \end{enumerate}
  All present and correct.
\end{proof}

\begin{exercise}
  In \cite{Goldwasser:1984:PE}, Shafi Goldwasser and Silvio Micali first
  introduced the concept of semantic security as a definition of
  \emph{computationally} secure encryption, and presented the first
  provably-secure probabilistic encryption scheme.  For this scheme, the
  private key is a pair of $k$-bit primes $(p, q)$; the public key is their
  product $n = pq$ and a \emph{pseudosquare} $z$.  Given this starting point,
  define a public-key encryption scheme, and relate its security in the
  IND-CPA sense to the difficulty of the Quadratic Residuosity Problem.  Show
  that the encryption scheme is malleable.
  
  Hints:
  \begin{parenum}
  \item Encrypt the message one bit at a time.
  \item Choosing a random element of $(\Z/n\Z)^*$ and squaring gives you a
    random element of $Q_n$.
  \item You will need to define a formal game for the Quadratic Residuosity
    Problem.
  \end{parenum}
  \answer%
  Encryption works as $\Xid{E}{GM}_{(n, z)}(x)$: \{ \FOREACH $1\colon x_i$
  \FROM $x$ \DO \{ $a_i \getsr (\Z/n\Z)^*$; $\vect{y}[i] \gets a_i^2
  z^{x_i}$~\} \RETURN $\vect{y}$;~\}.  Decryption works as $\Xid{D}{GM}_{(p,
    q)}(\vect{y})$: \{ $x \gets \emptystring$; \FOR $i = 0$ \TO $|\vect{y}| -
  1$ \DO \{ \IF $\jacobi{\vect{y}[i]}{p} = 1 \land \jacobi{\vect{y}[i]}{q} =
  1$ \THEN $x \gets x \cat 0$; \ELSE $x \gets x \cat 1$;~\} \RETURN $x$;~\}.

  To prove that this is meets IND-CPA, let $A$ be an adversary attacking the
  GM scheme.  Now, we present an algorithm which, given an odd composite
  integer $n$ and an element $z$ with $\jacobi{x}{n} = 1$, decides whether $x
  \in Q_n$: Algorithm $B(n, z)$: $(x_0, x_1, s) \gets A(\cookie{find}, (n,
  z))$; $b \getsr \{0, 1\}$; $y \gets \Xid{E}{GM}_{(n, z)}(x_b)$; $b' \gets
  A(\cookie{guess}, y, s)$; \IF $b = b'$ \THEN \RETURN $0$; \ELSE \RETURN
  $1$;~\}.  If $z$ is a nonresidue, then $B$ returns $0$ whenever $A$
  successfully guesses the right bit; if $z \in Q_n$ then the ciphertext $y$
  returned by $B$ is a string of random quadratic residues independent of the
  challenge plaintext, and $A$ can have no advantage.  Hence
  $\InSec{ind-cpa}(\Xid{\mathcal{E}}{GM-$k$}; t) \le 2 \cdot \InSec{qrp}(k;
  t)$.
  
  To prove malleability, simply note that multiplying an element
  $\vect{y}[i]$ by $z$ toggles the corresponding plaintext bit.
\end{exercise}

\xcalways\subsection{The ElGamal scheme}\x

\begin{slide}
  \topic{description}
  \head{The ElGamal public-key encryption scheme}

  ElGamal's encryption scheme is based on Diffie-Hellman.  Let $G = \langle g
  \rangle$ be a cyclic group of order $q$.  Plaintexts and ciphertexts in the
  scheme are elements of $G$.

  The scheme $\Xid{\mathcal{E}}{ElGamal}^G = (\Xid{G}{ElGamal}^G,
  \Xid{E}{ElGamal}^G, \Xid{D}{ElGamal}^G)$ is defined by:
  \begin{program}
    $\Xid{G}{ElGamal}^G$: \+ \\
      $\alpha \getsr \{1, 2, \ldots, q - 1\}$; \\
      \RETURN $(g^\alpha, \alpha)$;
  \next
    $\Xid{E}{ElGamal}^G_a(x)$: \+ \\
      $\beta \getsr \{1, 2, \ldots, q - 1\}$; \\
      \RETURN $(g^\beta, x a^\beta)$;
  \next
    $\Xid{D}{ElGamal}^G_\alpha(y)$: \+ \\
      $(b, c) \gets y$; \\
      $x \gets b^{-\alpha} c$; \\
      \RETURN $x$;
  \end{program}
  This scheme is secure in the IND-CPA sense if the Decisional Diffie-Hellman
  problem is hard in $G$.
\end{slide}

\begin{slide}
  \topic{security proof}
  \head{Security proof for ElGamal}

  Suppose $A$ is an adversary attacking the ElGamal scheme in the IND-CPA
  sense.  We construct from it an algorithm which solves the DDH problem
  (i.e., given a triple $g^\alpha, g^\beta, c$, decides whether $c =
  g^{\alpha\beta}$):
  \begin{program}
    Algorithm $D(a, b, c)$: \+ \\
      $(x_0, x_1, s) \gets A(\cookie{find}, a)$; \\
      $z \getsr \{0, 1\}$; \\
      $y \gets (b, x_z c)$; \\
      $z' \gets A(\cookie{guess}, y, s)$; \\
      \IF $z = z'$ \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
\end{slide}

\begin{slide}
  \head{Security proof for ElGamal (cont.)}
  
  Let $\alpha$ and $\beta$ be the discrete logs of $a$ and $b$.
  
  If $c = g^{\alpha\beta}$, then $D$'s success probability is equal to $A$'s
  probability of guessing the hidden bit correctly, which is
  \[ \frac{\Adv{ind-cpa}{\Xid{\mathcal{E}}{ElGamal}^G}(A)}{2} + \frac{1}{2}. \]%
  If $c$ is random, then $x_z c$ is uniformly distributed in $G$, and
  independent of $b$, so $A$ answers correctly with probability exactly
  $\frac{1}{2}$.
  
  Hence, $\Adv{ddh}{G}(D) =
  \Adv{ind-cpa}{\Xid{\mathcal{E}}{ElGamal}^G}(A)/2$, and
  \[ \InSec{ind-cpa}(\Xid{\mathcal{E}}{ElGamal}^G; t) \le
     2 \cdot \InSec{ddh}(G; t). \]%
\end{slide}

\begin{slide}
  \topic{other notes}
  \head{Notes about ElGamal}

  \begin{itemize}
    
  \item We needed the Decisional Diffie-Hellman assumption to prove the
    security.  As noted before, this is a very strong assumption.  Still, a
    proof based on DDH is a lot better than nothing.
    
    We really do need the Decisional Diffie-Hellman assumption.  An adversary
    with a DDH algorithm can submit $x_0 \inr G$ and $x_1 = 1$; it receives a
    ciphertext $(b, y)$, and returns $1$ if $(a, b, y)$ looks like a
    Diffie-Hellman triple, or $0$ if it looks random.
    
  \item The plaintexts must be elements of the cyclic group $G$.  For
    example, if $G$ is a subgroup of $\F_p^*$, it's \emph{not} safe to allow
    elements outside the subgroup as plaintexts: an adversary can compare
    orders of ciphertext elements to break the semantic security of the
    scheme.

  \item ElGamal is malleable.  We can decrypt a challenge ciphertext $y =
    (g^\beta, a^\beta x)$ by choosing a random $\gamma$ and requesting a
    decryption of $y' = (g^{\beta\gamma}, a^{\beta\gamma} x^\gamma)$.

  \end{itemize}
\end{slide}

\xcalways\subsection{Encrypting using trapdoor one-way functions}\x

\begin{slide}
  \head{Trapdoor one-way functions}
  
  Trapdoor one-way functions RSA ($x \mapsto x^e \bmod n$) and Rabin ($x
  \mapsto x^2 \bmod n$) functions are well-studied.  Can we make secure
  schemes from them?

  We can't use them directly, however.  For a start, the functions are
  deterministic, so `encrypting' messages just by doing the modular
  exponentiation on the plaintext will leak equality of plaintexts.

  How can we fix these schemes?

  We'll focus on RSA, because decryption is simpler; Rabin works in a very
  similar way.
\end{slide}

\begin{slide}
  \topic{simple embedding schemes}
  \head{Simple embedding schemes}
  
  If we restrict our attention to plaintext messages which are `about' the
  input size of our one-way function, we'd like to be able to use ciphertexts
  which are no bigger than the output size of the function.

  Perhaps if we encode the message in some way before passing it through the
  function, we can improve security.  Ideally, we'd like security against
  chosen-ciphertext attacks.

  An encryption scheme which processes messages like this is called a
  \emph{simple embedding scheme}.
\end{slide}

\begin{slide}
  \topic{\PKCS1 padding}
  \head{\PKCS1 encryption padding for RSA \cite{RSA:1993:PRE}}

  Let $n = p q$ be an RSA modulus, with $2^{8(k-1)} < n < 2^{8k)}$ -- i.e.,
  $n$ is a $k$-byte number.  Let $m$ be the message to be signed.
  
  We compute $\hat{m} = 0^8 \cat T \cat r \cat 0^8 \cat x$ for
  some hash function $m$, where:
  \begin{itemize}
  \item $|\hat{m}| = 8k$, i.e., $\hat{m}$ is a $k$-byte string;
  \item $0^8$ is the string of 8 zero-bits;
  \item $T = 00000002$ is an 8-bit \emph{type} code; and
  \item $r$ is a string of random \emph{non-zero} bytes (\PKCS1 requires at
    least 8 bytes)
  \end{itemize}
  This bit string is then converted into an integer, using a big-endian
  representation.  Note that $\hat{m} < n$, since its top byte is zero.
\end{slide}

\begin{slide}
  \head{\PKCS1 encryption padding for RSA (cont.)}

  Diagrammatically, \PKCS1 encryption padding looks like this:
  \begin{tabular}[C]{r|c|c|c|c|} \hlx{c{2-5}v}
    \hex{00} & \hex{01} &
    \ldots\ random nonzero bytes \ldots &
    \hex{00} &
    $m$
    \\ \hlx{vc{2-5}}
  \end{tabular}
  
  Unfortunately, this scheme isn't capable of resisting chosen-ciphertext
  attacks: Bleichenbacher \cite{Bleichenbacher:1998:CCA} shows how to decrypt
  a ciphertext $y$ given an oracle (say, an SSL server) which returns whether
  a given ciphertext is valid (i.e., its padding is correct).
\end{slide}

\begin{slide}
  \topic{Optimal Asymmetric Encryption Padding (OAEP)}
  \head{Optimal Asymmetric Encryption Padding (OAEP) \cite{Bellare:1995:OAE}}
  
  OAEP is a simple embedding scheme for use with an arbitrary trapdoor
  one-way function.  It requires two hash functions, $H$ and $H'$, which we
  model as random oracles.

  We assume that our one-way function $f_P$ operates on $n$-bit strings.  Fix
  a security parameter $k$.  We require two random oracles $G\colon \{0,
  1\}^k \to \{0, 1\}^{n-k}$ and $H\colon \{0, 1\}^{n-k} \to \{0, 1\}^k$.
  Given a message $x \in \{0, 1\}^{n-2k}$, we encrypt it as follows:
  \begin{program}
    Algorithm $\Xid{E}{OAEP}^{\mathcal{T}, G(\cdot), H(\cdot)}_P(x)$: \+ \\
      $r \getsr \{0, 1\}^k$; \\
      $s \gets (x \cat 0^k) \xor G(r)$; $t \gets r \xor H(s)$; \\
      $w \gets s \cat t$; \\
      \RETURN $f_P(w)$;
  \next
    Algorithm $\Xid{D}{OAEP}^{\mathcal{T}, G(\cdot), H(\cdot)}_K(y)$: \+ \\
      $w \gets T_K(y)$; \\
      \PARSE $w$ \AS $s, k\colon t$; \\
      $r \gets t \xor H(s)$; $x' \gets s \xor G(r)$; \\
      \PARSE $x'$ \AS $x, k\colon c$; \\
      \IF $c = 0^k$ \THEN \RETURN $x$; \\
      \ELSE \RETURN $\bot$;
  \end{program}
\end{slide}

\begin{slide}
  \head{Optimal Asymmetric Encryption Padding (OAEP) (cont.)}

  %%        x <- {0, 1}^{n-2k}               r <-R {0, 1}^k
  %%                |                              |
  %%                |                              |
  %%                v                              |
  %%               [||]<--- 0^k                    |
  %%                |                              |
  %%                |                              |
  %%                v                              |
  %%               (+)<-----------[G]--------------|
  %%                |                              |
  %%                |                              |
  %%                |                              v
  %%                |-------------[H]------------>(+)
  %%                |                              |
  %%                |                              |
  %%                v                              v
  %%    < s = (x || 0^k) (+) G(r) >       < t = r (+) H(s) >

  \vfil
  \[ \begin{graph}
    []!{0; <1cm, 0cm>:}
    {x \in \{0, 1\}^n}="x" [rrrr] {r \inr \{0, 1\}^k}="r"
    "r" :[ddd] *{\xor}="h-xor"
        :[d] *++=(2, 0)[F:thicker]{\strut t = r \xor H(s)}
    "x" :[d] *{\ocat}="cat"
        [r] *+[r]{\mathstrut 0^k} :"cat"
        :[d] *{\xor}="g-xor"
        :[dd] *++=(4, 0)[F:thicker]{\strut s = (x \cat 0^k) \xor G(r)}
        [u] :[rr] *+[F]{H'} :"h-xor"
    "r" [dd] :[ll] *+[F]{H} :"g-xor"
  \end{graph} \]
  \vfil
\end{slide}

\begin{slide}
  \head{Security of OAEP, \seq: chosen plaintext attacks}
  
  We write the encryption scheme formed by using the trapdoor one-way
  function $\mathcal{T}$ with OAEP embedding as
  $\Xid{\mathcal{E}}{OAEP}^{\mathcal{T}}$.

  The security of OAEP in the IND-CPA sense is given by:
  \[ \InSec{ind-cpa}(\Xid{\mathcal{E}}{OAEP}^{\mathcal{T}}; t, q_G, q_H)
     \le 2 \left (\frac{q_G}{2^k} +
                    \InSec{owf}(\mathcal{T}; t + O(q_G q_H)) \right). \]%
\end{slide}

We omit the security proof of OAEP, because it's very similar to the proof
for OAEP+ which is presented in full later.

\begin{slide}
  \topic{possible malleability of OAEP}
  \head{OAEP is not (generically) non-malleable \cite{Shoup:2001:OAEPR}}
  
  If a one-way function might be \emph{XOR-malleable} -- i.e., given $f_P(x)$
  and $\delta$, it's possible to construct $f_P(x \xor \delta)$ without
  knowledge of the trapdoor -- then the OAEP encryption scheme is malleable.

  \begin{graph}
    []!{0; <1cm, 0cm>:}
    *!UR{\parbox{0.5\linewidth}{
      \raggedright
      We need to suppose, in addition, that the function leaks the leftmost
      $n-k$ bits of its input; e.g., $f(s \cat t) = s \cat f'(t)$.  Then
      exploiting the differential (pictured right) only requires a pair of
      queries to the $H$ oracle, not $G$.  Using its parallel
      chosen-ciphertext query, the adversary can decrypt its target
      plaintext.
    }}
    !{+(1.5, 0)}
    {x}="x" [rr] {r}="r"
    "r" :[ddd] *{\xor}="h-xor" ^{0}
        :[d] {t}^{H(s) \xor H(s \xor (\delta \cat 0^k))}
    "x" :[d] *{\ocat}="cat" _{\delta}
        [r] *+[r]{\mathstrut 0^k} :"cat"
        :[d] *{\xor}="g-xor" _{\delta \cat 0^k}
        :[dd] {s}_{\delta \cat 0^k}
        [u] :[r] *+[F]{H'} :"h-xor"
    "r" [dd] :[l] *+[F]{H} :"g-xor"
  \end{graph}

  Nevertheless, OAEP \emph{does} provide security against chosen-ciphertext
  attacks when used with the RSA and Rabin functions.
\end{slide}

\xcalways\subsection{Plaintext awareness and OAEP+}\x

\begin{slide}
  \head{Plaintext awareness}
  
  The intuitive idea behind plaintext awareness is that it's hard to
  construct a new ciphertext for which you can't easily guess the plaintext
  (or guess that the ciphertext is invalid).  Obviously, such an idea would
  imply security against chosen ciphertext attack -- since the adversary
  effectively knows the plaintext anyway, the decryption oracle is useless.
  
  The formalization introduces a \emph{plaintext extractor} -- an algorithm
  which, given a ciphertext and the random oracle queries of the program
  which created it, returns the corresponding plaintext.
  
  Note, then, that plaintext awareness (as currently defined) only works in
  the random oracle model.
\end{slide}

\begin{slide}
  \topic{definition of plaintext awareness}
  \head{Definition of plaintext awareness \cite{Bellare:1998:RAN}}
  
  Let $\mathcal{E} = (G, E, D)$ be a public-key encryption scheme.  Consider
  an adversary $A$ which takes a public key as input and returns a ciphertext
  $y$.  We run the adversary, providing it with an \emph{encryption} oracle,
  and record
  \begin{itemize}
  \item the set $Q_H$, which contains a pair $(q, h)$ for each random oracle
    query $q$ made by the adversary, together with its reply $h$; and
  \item the set $C$, which contains the responses (only: not the queries)
    from $A$'s encryption oracle.
  \end{itemize}
  We write $(y, Q_H, C) \gets \id{transcript}(A; z)$ to denote running $A$ on
  the arguments $z$ and collecting this information.

  Note that $Q_H$ doesn't include the oracle queries required by the
  encryption oracle.
\end{slide}

\begin{slide}
  \head{Definition of plaintext awareness (cont.)}

  An \emph{$\epsilon$-plaintext extractor} for $\mathcal{E}$ is an algorithm
  $X$ for which
  \begin{eqnarray*}[rl]
     \min_A \Pr[
     &
       (P, K) \gets G;
       (y, Q_H, C) \gets \id{transcript}(A^{E(\cdot), H(\cdot)}; P); \\
     & x \gets X(y, P, Q_H, C) : x = D_K(y)] \ge 1 - \epsilon .
  \end{eqnarray*}
  
  The scheme $\mathcal{E}$ is \emph{$\epsilon$-plaintext aware} (PA) if there
  exists an $\epsilon$-plaintext extractor for $\mathcal{E}$ \emph{and}
  $\mathcal{E}$ is IND-CPA.

  (The requirement that the scheme meet IND-CPA prevents trivial schemes such
  as the identity function from being considered plaintext aware.)
\end{slide}

\begin{slide}
  \topic{chosen-ciphertext security}
  \head{Plaintext awareness and chosen-ciphertext security
    \cite{Bellare:1998:RAN}}

  If a public key encryption scheme $\mathcal{E}$ is PA, then it is also
  IND-CCA2 (and hence NM-CCA2).  This is proven using the plaintext extractor
  to simulate the decryption oracle.  The encryption oracle in the PA
  definition is used to feed the challenge ciphertext to the plaintext
  extractor.

  Quantitatively, if $\mathcal{E}$ is $\epsilon$-plaintext aware, and the
  plaintext extractor runs in time $t_X(q_H)$, then
  \[ \InSec{ind-cca2}(\mathcal{E}; t, q_D, q_H) \le
     \InSec{ind-cpa}(\mathcal{E}; t + q_D t_X(q_H), q_H) + q_D \epsilon. \]%

  The converse is not true: IND-CCA2 does not imply plaintext awareness.
\end{slide}

\begin{proof}
  Firstly, we prove that $\text{PA} \implies \text{IND-CCA2}$.  Let
  $\mathcal{E} = (G, E, D)$ be an $\epsilon$-plaintext aware public-key
  encryption scheme.  Suppose $A'$ is an adversary attacking $\mathcal{E}$ in
  the IND-CCA2 sense.  Let $X$ be the $\epsilon$-plaintext extractor for
  $\mathcal{E}$.  We construct an adversary attacking $\mathcal{E}$ in the
  IND-CPA sense.
  \begin{program}
    Adversary $A^{H(\cdot)}(\cookie{find}, P)$: \+ \\
      $\Xid{H}{map} \gets \emptyset$; $y^* \gets \bot$; \\
      $(x_0, x_1, s') \gets A'^{\Xid{D}{sim}(\cdot), \Xid{H}{sim}(\cdot)}
        (\cookie{find}, P)$; \\
      \RETURN $(x_0, x_1, (\Xid{H}{map}, P, s')$; \- \\[\smallskipamount]
    Oracle $\Xid{H}{sim}(x)$: \+ \\
      $h \gets H(x)$; \\
      $\Xid{H}{map} \gets \Xid{H}{map} \cup \{ x \mapsto h \}$; \\
      \RETURN $h$;
  \next
    Adversary $A^{H(\cdot)}(\cookie{guess}, y^*, s)$: \+ \\
      $(\Xid{H}{map}, P, s') \gets s$; \\
      $b \gets A'^{\Xid{D}{sim}(\cdot), \Xid{H}{sim}(\cdot)}
        (\cookie{guess}, y^*, s')$; \\
      \RETURN $b$; \- \\[\smallskipamount]
    Oracle $\Xid{D}{sim}(y)$: \+ \\
      $x \gets X(y, P, \Xid{H}{map}, \{ y^* \})$; \\
      \RETURN $x$;
  \end{program}
  Let $q_D$ be the number of decryption queries made by the adversary.  We
  can see that, if the plaintext extractor does its job correctly, $A$
  simulates the decryption oracle for $A'$ correctly.  Hence
  \[ \Adv{ind-cpa}{\mathcal{E}}(A) \ge
       \Adv{ind-cca2}{\mathcal{E}}(A') - q_D \epsilon. \]%
  Notice how the encryption oracle from the plaintext awareness definition is
  used in the proof.
  
  We can show that $\text{IND-CCA2} \not\implies \text{PA}$ easily enough by
  amending an existing IND-CCA2 scheme $\mathcal{E}$ so that it has a
  `magical' ciphertext, attached to the public key.  Here is our modified
  scheme $\mathcal{E}' = (G', E', D')$:
  \begin{program}
    Algorithm $G'^{H(\cdot)}(k)$: \+ \\
      $(P, K) \gets G^{H(\cdot)}$; \\
      $p \getsr \dom E^{H(\cdot)}_P$; \\
      $c \getsr \ran E^{H(\cdot)}_P$; \\
      \RETURN $((P, c), (K, c, p))$;
  \next
    Algorithm $E'^{H(\cdot)}_{P, c}(x)$: \+ \\
      $y \gets E^{H(\cdot)}_P(x)$; \\
      \RETURN $y$;
  \next
    Algorithm $D'^{H(\cdot)}_{K, c, p}(y)$: \+ \\
      \IF $y = c$ \THEN $x \gets p$; \\
      \ELSE $x \gets D^{H(\cdot)}_K(y)$; \\
      \RETURN $x$;
  \end{program}
  Firstly, we show that it still meets IND-CCA2.  Let $A'$ be an adversary
  attacking $\mathcal{E}'$ in the IND-CCA2 sense.  Then $A$, below, achieves
  the same advantage against $\mathcal{E}$.
  \begin{program}
    Adversary $A^{D(\cdot), H(\cdot)}(\cookie{find}, P)$: \+ \\
      $p \getsr \dom E^{H(\cdot)}_P$; $c \getsr \ran E^{H(\cdot)}_P$; \\
      $(x_0, x_1, s') \gets A'^{\Xid{D}{sim}(\cdot), H(\cdot)}
        (\cookie{find}, (P, c))$; \\
      \RETURN $(x_0, x_1, (p, c, s')$;
  \next
    Adversary $A^{D(\cdot), H(\cdot)}(\cookie{guess}, y, s)$: \+ \\
      $(p, c, s') \gets s$; \\
      $b \gets A'^{\Xid{D}{sim}(\cdot), H(\cdot)}(\cookie{guess}, y, s')$; \\
      \RETURN $y$;
  \newline
    Oracle $\Xid{D}{sim}(y)$: \+ \\
      \IF $y = c$ \THEN $x \gets p$; \\
      \ELSE $x \gets D(y)$; \\
      \RETURN $x$;
  \end{program}
  
  Now to show that $\mathcal{E}'$ is not plaintext-aware.  Suppose that it
  is, and there is a plaintext extractor $X$.  We show that $\mathcal{E}$ is
  not IND-CPA (contradicting the earlier assumption that $\mathcal{E}$ was
  IND-CCA2).
  \begin{program}
    Adversary $A''^{H(\cdot)}(\cookie{find}, P)$: \+ \\
      $x_0 \getsr \dom E_P$; $x_1 \getsr \dom E_P$; \\
      \RETURN $(x_0, x_1, (P, x_1))$;
  \next
    Adversary $A''^{H(\cdot)}(\cookie{guess}, y, s)$: \+ \\
      $(P, x_1) \gets s$; \\
      $x \gets X(y, (P, y), \emptyset, \emptyset)$; \\
      \IF $x = x_1$ \THEN \RETURN $1$;
      \ELSE \RETURN $0$;
  \end{program}
  Since $x_0$ and $x_1$ are uniform in $\dom E_P$, the transcript $(y, (P,
  y), \emptyset, \emptyset)$ passed to the extractor is distributed exactly
  as for the $\mathcal{E}'$ adversary which, given the public key $(P, c)$
  returns $c$; hence it succeeds with its usual probability $1 - \epsilon$.
  Then, $A''$'s advantage is
  \[ \Adv{ind-cpa}{\mathcal{E}}(A'') =
       1 - 2\epsilon - \frac{1}{|{\dom E_P}|}. \]%
  This completes the proof.
\end{proof}

\begin{slide}
  \topic{old definition}
  \head{The old definition of plaintext awareness}

  An earlier definition of plaintext awareness omitted the encryption oracle
  provided to the adversary.  The designers of OAEP proved that it met this
  definition of plaintext awareness and asserted, without proof, that this
  implied security against adaptive chosen-ciphertext attacks.

  The original definition of plaintext-awareness is sufficient to guarantee
  IND-CCA1 security, but it doesn't provide any sort of non-malleability.
\end{slide}

\begin{slide}
  \topic{OAEP+}
  \resetseq
  \head{Plaintext-aware encryption: OAEP+ \cite{Shoup:2001:OAEPR}, \seq}
  
  OAEP+ is a simple embedding scheme, very similar to OAEP, which achieves
  plaintext-awareness.
  
  We assume that our one-way function $f_P$ operates on $n$-bit strings.  Fix
  a security parameter $k$.  We require three random oracles $G\colon \{0,
  1\}^k \to \{0, 1\}^{n-2k}$, $H\colon \{0, 1\}^{n-k} \to \{0, 1\}^k$, and
  $H'\colon \{0, 1\}^{n-k} \to \{0, 1\}^k$.
  \begin{program}
    Algorithm $\Xid{E}{OAEP+}
                ^{\mathcal{T}, G(\cdot), H(\cdot), H'(\cdot)}_P(x)$: \+ \\
      $r \getsr \{0, 1\}^k$; \\
      $c \gets H'(x \cat r)$; \\
      $s \gets (x \xor G(r)) \cat c$; \\
      $t \gets r \xor H(s)$; \\
      $w \gets s \cat t$; \\
      \RETURN $f_P(w)$;
  \next
    Algorithm $\Xid{D}{OAEP+}
                ^{\mathcal{T}, G(\cdot), H(\cdot), H'(\cdot)}_K(y)$: \+ \\
      $w \gets T_K(y)$; \\
      \PARSE $w$ \AS $s, k\colon t$; \\
      $r \gets t \xor H(s)$; \\
      \PARSE $s$ \AS $s', k\colon c$; \\
      $x \gets s' \xor G(r)$; \\
      \IF $c = H'(x \cat r)$ \THEN \RETURN $x$; \\
      \ELSE \RETURN $\bot$;
  \end{program}
\end{slide}

\begin{slide}
  \head{Plaintext-aware encryption: OAEP+, \seq}

  %%        x <- {0, 1}^{n-2k}                r <-R {0, 1}^k
  %%                |                              |
  %%                |                              |
  %%                |                              |
  %%                |-------->[H']<----------------|
  %%                |          |                   |
  %%                |          |                   |
  %%                v          |                   |
  %%               (+)<-------------[G]<-----------|
  %%                |          |                   |
  %%                |          |                   |
  %%                v          |                   |
  %%               [||]<-------'                   |
  %%                |                              |
  %%                |                              |
  %%                |                              v
  %%                |-------------->[H]---------->(+)
  %%                |                              |
  %%                |                              |
  %%                v                              v
  %%  < s = (x (+) G(r)) || H'(x || r) >  < t = r (+) H(s) >

  \vfil
  \[ \begin{graph}
    []!{0; <1cm, 0cm>:}
    {x \in \{0, 1\}^n}="x" [rrrr] {r \inr \{0, 1\}^k}="r"
    "x" [d] :[r] *+[F]{H'}="h'" "r" [d] :"h'"
    "r" :[dddd] *{\xor}="h-xor"
        :[d] *++=(2, 0)[F:thicker]{\strut t = r \xor H(s)}
    "x" :[dd] *{\xor}="g-xor"
        :[d] *{\ocat}="cat"
        :[dd] *++=(4, 0)[F:thicker]
          {\strut s = (x \xor G(r)) \cat H'(x \cat r)}
        [u] :[rr] *+[F]{H} :"h-xor"
    "r" [dd] :[ll] *+[F]{G} :"g-xor"
    "h'" :'[d]*=<8pt>\cir<4pt>{r_l} `d"cat" "cat"
  \end{graph} \]
  \vfil
\end{slide}

\begin{slide}
  \head{Plaintext-aware encryption: OAEP+, \seq}
  
  Let $\mathcal{T}$ be a trapdoor one-way function.  Then the insecurity of
  the public-key encryption scheme $\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}$
  in the IND-CPA sense is given by
  \[ \InSec{ind-cpa}(\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}};
                     t, q_G, q_H, q_{H'})
     \le
     2 \left (\frac{q_G}{2^k} +
                \InSec{owf}(\mathcal{T}; t + O(q_G q_H)) \right). \]%
  Also, $\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}$ is $(q_G + 1)
  2^{-k}$-plaintext aware, the plaintext extractor running time being
  $O(q_{H'} t_f)$, where $t_f$ is the time required to execute the one-way
  function $f$.

  Tying up the various results, then, we can derive that
  \begin{eqnarray*}[Ll]
     \InSec{ind-cca2}(\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}};
                      t, q_D, q_G, q_H, q_{H'}) \\
     & \le
     \frac{(2 + q_D) (q_G + 1) - 2}{2^k} +
     2 \cdot \InSec{owf}(\mathcal{T}; t + O(q_G q_H + q_D q_{H'} t_f)).
  \end{eqnarray*}
\end{slide}

\begin{proof}[Proof of the main OAEP+ result]
  
  We assume throughout that, before querying its $H'$ oracle at $x \cat r$,
  the adversary has queried $G$ at $r$.
  
  First, we show that OAEP+ meets the IND-CPA notion.  Suppose that $A$
  attacks the OAEP+ scheme in the IND-CPA sense.  We shall play a series of
  games with the adversary, and vary the rules as we go along.  The adversary
  remains the same throughout.
  
  At any point in a game, let $Q_G$ be the list of queries the adversary has
  made to the oracle $G$, let $Q_H$ be the queries made to $H$, and let
  $Q_{H'}$ be the queries made to $H'$.
  
  \paragraph{Game $\G0$}
  This is effectively the original attack game: the adversary chooses two
  plaintexts: one is chosen uniformly at random, the adversary is given the
  ciphertext and asked to identify which plaintext was chosen.  Label the
  selected plaintext $x^*$, and the target ciphertext $y^*$.  Let $c^*$,
  $s^*$, $t^*$ and $w^*$ be the intermediate results of the OAEP+ padding, as
  described above.  Let $S_0$ be the event that the adversary wins the game.
  Our objective is to bound the probability $\Pr[S_0] =
  (\Adv{ind-cpa}{\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}}(A) + 1)/2$.

  \paragraph{Game $\G1$}
  At the beginning of the game, we select at random:
  \begin{itemize}
  \item $s^* \inr \{0, 1\}^{n-k}$;
  \item $t^* \inr \{0, 1\}^k$; and
  \item $r^* \inr \{0, 1\}^k$.
  \end{itemize}
  We compute $w^* = s^* \cat t^*$ and $y^* = f_P(w^*)$.  Note, then, that
  \emph{$y^*$ is fixed at the start of the game}.

  We also `rig' the random oracle $H$ so that $H(s^*) = r^* \xor t^*$.
  This isn't much of a fix, because this value is evidently uniformly
  distributed and independent of everything except $r^* \xor t^*$.
  
  We could rig $G$ and $H'$ too, once we knew $x^*$, so that $s^* = (x^* \xor
  G(r)) \cat H'(x^* \cat r)$.  But we don't.  Instead, consider the event
  $F_1$ that the adversary queries $G$ at $r^*$.  Since we have opted for the
  bare-faced lie rather than oracle subterfuge, the target ciphertext $y^*$
  and the oracles are entirely independent of the target plaintext $x^*$,
  whatever that might be.  Hence, $A$'s probability of guessing which
  plaintext was chosen, $\Pr[S_1] = \frac{1}{2}$.

  When attempting to bound $\Pr[F_1]$, there are two cases to consider:
  \begin{enumerate}

  \item The adversary has not previously queried $H$ at $s^*$.  In this
    case, the value of $r^*$ is independent of the adversary's view -- it has
    no information at all about $r^*$.  This can occur, therefore, with
    probability at most $q_G 2^{-k}$.

  \item The adversary has previously queried $H$ at $s^*$.  Then we can
    construct an inverter.  Note that $f_P$ is a permutation (by assumption);
    hence, selecting a $y^*$ at random implies the values of $w^*$, and hence
    $s^*$ and $t^*$, even though they can't be computed easily.
    \begin{program}
      Inverter $I(P, y)$: \+ \\
        $\Xid{G}{map} \gets \emptyset$;
          $\Xid{H}{map} \gets \emptyset$;
          $\Xid{H'}{map} \gets \emptyset$; \\
        $z \gets \bot$; \\
        $(x_0, x_1, s) \gets A^{G(\cdot), H(\cdot), H'(\cdot)}
          (\cookie{find}, P)$; \\
        $b \gets A^{G(\cdot), H(\cdot), H'(\cdot)}(\cookie{guess}, y, s)$; \\
        \RETURN $z$; \- \\[\smallskipamount]
      Oracle $H(s)$: \+ \\
        \IF $s \in \dom \Xid{H}{map}$ \\
        \THEN \RETURN $\Xid{H}{map}(s)$; \\
        $h \getsr \{0, 1\}^k$; \\
        $\Xid{H}{map} \gets \Xid{H}{map} \cup \{s \mapsto h\}$; \\
        \RETURN $h$;
    \next
      Oracle $H'(s)$: \+ \\
        \IF $s \in \dom \Xid{H'}{map}$ \\
        \THEN \RETURN $\Xid{H'}{map}(s)$; \\
        $h' \getsr \{0, 1\}^k$; \\
        $\Xid{H'}{map} \gets \Xid{H'}{map} \cup \{s \mapsto h'\}$; \\
        \RETURN $h$; \- \\[\smallskipamount]
      Oracle $G(r)$: \+ \\
        \IF $r \in \dom \Xid{G}{map}$ \THEN \\
        \RETURN $\Xid{G}{map}(r)$; \\
        \FOR $s \in \dom \Xid{H}{map}$ \DO \\ \quad \= \+ \kill
          $t \gets r \xor \Xid{H}{map}(s);$ \\
          $w \gets s \cat t$; \\
          \IF $f_P(w) = y$ \THEN $z \gets w$; \- \\
        $g \getsr \{0, 1\}^{n-2k}$; \\
        $\Xid{G}{map} \gets \Xid{G}{map} \cup \{r \mapsto g\}$; \\
        \RETURN $g$;
    \end{program}
    Clearly, $I$ succeeds whenever $A$ queries both $H$ at $s^*$ and $G$ at
    $r^*$.  $I$'s running time is about $O(q_G q_H)$ because of all of the
    searching in the $G$ oracle.

  \end{enumerate}
  Thus,
  \[ \Pr[F_1] \le
       \frac{q_G}{2^k} + \InSec{owf}(\mathcal{T}; t + O(q_G q_H)). \]%
  Now observe that, if $F_1$ doesn't occur, Games $\G0$ and~$\G1$ are
  indistinguishable.  So
  \[ \Pr[S_0 \land \lnot F_1] = \Pr[S_1 \land \lnot F_1], \]
  so by Lemma~\ref{lem:shoup} (slide~\pageref{lem:shoup}),
  \[ |{\Pr[S_0]} - \Pr[S_1]| \le \Pr[F_1]. \]
  Rearranging yields:
  \[ \Adv{ind-cpa}{\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}}(A)
     \le 2 \left (\frac{q_G}{2^k} +
                  \InSec{owf}(\mathcal{T}; t + O(q_G q_H)) \right). \]%
  But $A$ was arbitrary.  The result follows.

  To complete the plaintext-awareness proof, we must present a plaintext
  extractor.
  \begin{program}
    Plaintext extractor $X(y, P, Q_G, Q_H, Q_{H'}, C)$: \+ \\
      \FOR $z \in \dom Q_{H'}$ \DO \\ \quad \= \+ \kill
        \PARSE $z$ \AS $x, k\colon r$; \\
        $c \gets Q_{H'}(z)$; \\
        $s \gets (x \xor Q_G(r)) \cat c$; \\
        \IF $s \in \dom Q_H$ \THEN \\ \quad \= \+ \kill
          $t \gets r \xor Q_H(s)$; \\
          $w \gets s \cat t$; \\
          $y' \gets f_P(w)$; \\
          \IF $y = y'$ \THEN \RETURN $x$; \-\- \\
      \RETURN $\bot$;
  \end{program}
  To obtain a lower bound on the success probability of $X$, consider an
  adversary $A$ which queries its various oracles and returns a ciphertext
  $y$.  We aim to show that, if $A$ did not query all of its oracles as
  required for $X$ to work then its probability of producing a valid
  ciphertext (i.e., one for which the decryption algorithm does not return
  $\bot$) is small.

  We consider the decryption algorithm applied to $y$, and analyse the
  probability that $y$ is a valid ciphertext even though $A$ did not make all
  of the appropriate oracle queries.
  
  We shall take some of our notation from the decryption algorithm, which
  proceeds as follows:
  \begin{program}
    Algorithm $\Xid{D}{OAEP+}^
                {\mathcal{T}, G(\cdot), H(\cdot), H'(\cdot)}_K(y)$: \+ \\
      $w \gets T_K(y)$; \\
      \PARSE $w$ \AS $s, k\colon t$; \\
      $r \gets t \xor H(s)$; \\
      \PARSE $s$ \AS $s', k\colon c$; \\
      $x \gets s' \xor G(r)$; \\
      \IF $c = H'(x \cat r)$ \THEN \RETURN $x$; \\
      \ELSE \RETURN $\bot$;
  \end{program}
  
  Firstly, suppose that $A$ did not query $H'$ at $x \cat r$.  Then obviously
  there is only a $2^{-k}$ probability that $c$ is correct and the ciphertext
  will be accepted.  By our assumption about adversary behaviour, if $A$
  didn't query $G$ at $r$ then it also didn't query $H'$ at $x \cat r$ for
  any $x$.  Hence, a decryption algorithm which rejected immediately if it
  discovered that $G$ hadn't been queried at $r$, or that $H'$ hadn't been
  queried at $x \cat r$, would be incorrect with probability at most
  $2^{-k}$.

  Secondly, suppose that $A$ did not query $H$ at $s$.  Then $c$ is still
  fixed, but $r$ is now random and independent of $A$'s view.  The
  probability that $G$ has been queried at $r$ is then at most $q_G 2^{-k}$.
  So a decryption algorithm which, in addition to the changes above, also
  rejected if it discovered that $H$ had not been queried at $s$ would be
  incorrect with probability at most $q_G 2^{-k}$.

  But our plaintext extractor $X$ is just such a decryption algorithm.
  Hence, $X$'s failure probability is
  \[ \epsilon = \frac{q_G + 1}{2^k}. \]
\end{proof}

\endinput

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "ips"
%%% End: