+\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.)}
+
+ Diagramatically, \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, 1: 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.
+
+ Quantatively, 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, acheives
+ 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+}
+ \head{Plaintext-aware encryption: OAEP+ \cite{Shoup:2001:OAEPR}, 1}
+
+ OAEP+ is a simple embedding scheme, very similar to OAEP, which acheives
+ 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+, 2}
+
+ %% 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+, 3}
+
+ 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}
+
+Before we move on to the OAEP+ security results, we state and prove the
+following lemma, due (I believe) to Victor Shoup.
+
+\begin{lemma}[Shoup]
+ \label{lem:shoup}
+ If $X$, $Y$ and $F$ are events, and
+ \[ \Pr[X \land \lnot F] = \Pr[Y \land \lnot F] \]
+ then
+ \[ |{\Pr[X]} - \Pr[Y]| \le \Pr[F]. \]
+\end{lemma}
+\begin{proof}
+ We have:
+ \begin{eqnarray*}[rll]
+ \Pr[X] &= \Pr[X \land F] &+ \Pr[X \land \lnot F] \\
+ \Pr[Y] &= \Pr[Y \land F] &+ \Pr[Y \land \lnot F]
+ \end{eqnarray*}
+ Subtracting gives
+ \[ |{\Pr[X]} - \Pr[Y]| = |{\Pr[X \land F]} - \Pr[Y \land F]| \le \Pr[F] \]
+ as required.
+\end{proof}
+
+\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 unformly 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 probabilty $\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 Shoup's lemma,
+ \[ |{\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' \cat 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: