initial version

[doc/ips] / enc-ies.tex

\xcalways\section{Integrated public-key encryption schemes}\x

The formulation here is original work by the author.  I've tried to
generalize the work by (among others), Shoup, and Abdalla, Bellare and
Rogaway.  The final proof is from a Usenet article prompted by David
Hopwood, but based on the DHAES proof by ABR.

\xcalways\subsection{Introduction and definitions}\x

\begin{slide}
  \topic{motivation}
  \head{Motivation for integrated encryption}
  
  Public-key encryption schemes are very useful, but there are disadvantages:
  \begin{itemize}
  \item they tend not to be very fast; and
  \item they don't tend to be able to encrypt arbitrarily large messages.
  \end{itemize}
  Symmetric schemes don't have these problems, but key distribution is
  harder.  It seems sensible to construct `hybrid' schemes which use
  public-key techniques for exchanging keys for symmetric encryption schemes.

  Throughout the following, we'll consider our objective to be resistance to
  \emph{adaptive chosen-ciphertext} attacks.
\end{slide}

\begin{slide}
  \head{An obvious approach}
  
  A simple approach would be to generate a random key for some secure (i.e.,
  IND-CCA) symmetric scheme, encrypt the message under that key, and, encrypt
  the key under the recipient's public key (using some IND-CCA2 public-key
  scheme).

  This is obviously secure.  But the security results for most public-key
  schemes are less than encouraging: the reductions, even for OAEP+, are
  rather `flabby'.

  Can we do \emph{better} than this na\"{\i}ve approach?
\end{slide}

\begin{slide}
  \topic{key encapsulation}
  \head{Key-encapsulation mechanisms \cite{Shoup:2001:PIS}}
  
  A \emph{key-encapsulation mechanism} (KEM) $\mathcal{K} = (G, X, R)$ is a
  triple of algorithms:
  \begin{itemize}
  \item a probabilistic \emph{key-generation} algorithm~$G$, which takes no
    input (or a security parameter for asymptotic types) and returns a pair
    $(P, K)$;
  \item a probabilistic \emph{exchange} algorithm~$E$, which is given a
    as input a public key~$P$ and returns a \emph{public value}~$y$ and a
    \emph{hash} $h \in \{0, 1\}^k$; and
  \item a deterministic \emph{recovery} algorithm~$R$, which is given as
    input a private key~$K$ and a public value~$y$ and returns a hash $h$.
  \end{itemize}
  We require for correctness that, if $(P, K) \in G$ and $(y, h) \in X_P$,
  then $R_K(y) = h$.

  The idea is that the key-encapsulation mechanism invents a key and public
  value simultaneously.  We'll look at such mechanisms constructed from both
  trapdoor one-way functions like RSA, and schemes like Diffie-Hellman.
\end{slide}

\begin{slide}
  \topic{oracle hash decision problems}
  \head{Oracle hash decision problems}

  We say that a key-encapsulation mechanisms is secure if the corresponding
  \emph{oracle hash decision problem} is hard.  Consider this experiment:
  \begin{program}
    Experiment $\Expt{ohd-$b$}{\mathcal{K}}(A)$: \+ \\
      $(P, K) \gets G$; \\
      $h_0 \getsr \{0, 1\}^k$; $(y, h_1) \gets X_P$; \\
      $b' \gets A^{R_K(\cdot)}(P, y, h_b)$; \\
      \RETURN $b'$;
  \end{program}
  We forbid the adversary from querying its $R_K$ oracle at $y$.  We define
  advantage and insecurity in the usual way:
  \begin{eqnarray*}[rl]
    \Adv{ohd}{\mathcal{K}}(A) &=
      \Pr[\Expt{ohd-$1$}{\mathcal{K}}(A) = 1] -
      \Pr[\Expt{ohd-$0$}{\mathcal{K}}(A) = 1]
    \\
    \InSec{ohd}(\mathcal{K}; t, q) &=
      \max_A \Adv{ohd}{\mathcal{K}}(A)
  \end{eqnarray*}
  where the maximum is taken over adversaries $A$ running in time $t$ and
  issuing $q$ recovery queries.
\end{slide}

\xcalways\subsection{Constructions for key-encapsulation mechanisms}\x

\begin{slide}
  \topic{trapdoor one-way permutations}
  \head{Constructing a KEM from a trapdoor OWP}
  
  Why might key-encapsulation mechanisms exist, and how do we construct them?
  
  In the random oracle model, we can construct a KEM from any trapdoor
  one-way permutation.  Let $\mathcal{T} = (G, f, T)$ be such a one-way
  permutation, and let $H\colon \{0, 1\}^* \to \{0, 1\}^k$ be a public random
  oracle.  We can construct $\Xid{\mathcal{K}}{OWF}^{\mathcal{T}, H} = (G,
  \Xid{X}{OWF}^{\mathcal{T}, H}, \Xid{R}{OWF}^{\mathcal{T}, H})$ as follows:
  \begin{program}
    Algorithm $\Xid{X}{OWF}^{\mathcal{T}, H(\cdot)}_P$: \+ \\
      $x \getsr \dom f_P$; \\
      $h \gets H(x)$; \\
      \RETURN $(f_P(x), h)$;
  \next
    Algorithm $\Xid{R}{OWF}^{\mathcal{T}, H(\cdot)}_K(y)$: \+ \\
      $x \gets T_K(y)$; \\
      $h \gets H(x)$; \\
      \RETURN $f_P(x)$;
  \end{program}
  The security of this scheme is then given by:
  \[ \InSec{ohd}(\Xid{\mathcal{K}}{OWF}^{\mathcal{T}, H}; t, q_R, q_H) \le
     2 \cdot \InSec{owf}(\mathcal{T}; t + O(q_H) + O(q_R)). \]%
\end{slide}

\begin{proof}
  Let $A$ be an adversary solving the oracle hash decision problem.  Let $y^*
  = f_P(x^*)$ be the challenge public value, and let $h^*$ be the challenge
  hash.  Suppose that $A$ never queries its random oracle $H$ at $x^*$: then
  obviously $h = H(x^*)$ is independent of $A$'s view, and $A$ has no
  advantage, and its probability of guessing the hidden bit is precisely
  $\frac{1}{2}$.
  
  Suppose that we choose which OHD experiment uniformly at random.  Let $S$
  be the event that the adversary wins, i.e., it correctly guesses the hidden
  bit $b$.  Then
  \[ \Pr[S] =
       \frac{\Adv{ohd}{\Xid{\mathcal{K}}{OWF}^{\mathcal{T}, H}}(A)}{2} +
       \frac{1}{2}. \]%
  Let $F$ be the event that $A$ queries $H$ at $x^*$.  Then by Shoup's Lemma
  (lemma~\ref{lem:shoup}, page~\pageref{lem:shoup}),
  \[ \left|\Pr[S] - \frac{1}{2}\right| \le \Pr[F]. \]

  Now consider this adversary $I$, attempting to invert the one-way function.
  \begin{program}
    Inverter $I(P, y^*)$: \+ \\
      $\Xid{H}{map} \gets \emptyset$; \\
      $h^* \gets \{0, 1\}^k$; $x^* \gets \bot$; \\
      $b \gets A^{\Xid{R}{sim}(\cdot), \Xid{H}{sim}(\cdot)}(P, y^*, h^*)$; \\
      \RETURN $x^*$; \- \\[\smallskipamount]
    Oracle $\Xid{R}{sim}(y)$: \+ \\
      \IF $y \in \dom\Xid{H}{map}$ \THEN \RETURN $\Xid{H}{map}(y)$; \\
      $h \gets \{0, 1\}^k$; \\
      $\Xid{H}{map} \gets \Xid{H}{map} \cup \{ y \mapsto h \}$; \\
      \RETURN $h$; \- \\[\smallskipamount]
    Oracle $\Xid{H}{sim}(x)$: \+ \\
      $y \gets f_P(x)$; \\
      \IF $y = y^*$ \THEN \\ \quad \= \+ \kill
        $x^* \gets x$; \\
        \IF $y \notin \dom\Xid{H}{map}$ \THEN \\ \quad \= \+ \kill
          $b^* \getsr \{0, 1\}$; \\
          \IF $b^* = 1$ \THEN
            $\Xid{H}{map} \gets \Xid{H}{map} \cup \{ y \mapsto h^* \}$ \-\-\\
      \RETURN $\Xid{R}{sim}(y)$;
  \end{program}
  The simulation of the random and `recovery' oracles is a little subtle, but
  from the adversary's point of view perfect.  Clearly, then, $I$ inverts
  $f_P$ whenever $F$ occurs, and
  \[ \Succ{owf}{\mathcal{T}}(I)
     \ge \Pr[F]
     \ge \frac{1}{2} \Adv{ohd}{\Xid{\mathcal{K}}{OWF}^{\mathcal{T}, H}}(A). \]%
  proving the result.
\end{proof}

\begin{slide}
  \topic{Diffie-Hellman}
  \head{A KEM based on Diffie-Hellman \cite{Abdalla:2001:DHIES}}

  Let $G = \langle g \rangle$ be a cyclic group, with $q = |G|$.  Then we can
  construct a KEM based on the difficulty of the Diffie-Hellman problem in
  $G$.  Let $H\colon G^2 \to \{0, 1\}^k$ be a public random oracle.
  
  We define $\Xid{\mathcal{K}}{DH}^{G, H} = (\Xid{G}{DH}^{G, H},
  \Xid{X}{DH}^{G, H}, \Xid{R}{DH}^{G, H})$ as follows:
  \begin{program}
    Algorithm $\Xid{G}{DH}^{G, H(\cdot, \cdot)}$: \+ \\
      $\alpha \getsr \Z/q\Z$; \\
      \RETURN $(g^\alpha, \alpha)$;
  \next
    Algorithm $\Xid{X}{DH}^{G, H(\cdot, \cdot)}_a$: \+ \\
      $\beta \getsr \Z/q\Z$; \\
      $h \gets H(g^\beta, a^\beta)$; \\
      \RETURN $(g^\beta, h)$;
  \next
    Algorithm $\Xid{R}{DH}^{G, H(\cdot, \cdot)}_\alpha(b)$: \+ \\
      $h \gets H(b, b^\alpha)$; \\
      \RETURN $h$;
  \end{program}

  But the question of this scheme's security is tricky.  It doesn't seem to
  fit any of our standard problems.  We therefore have to invent a new one!
\end{slide}

\begin{slide}
  \head{The Gap Diffie-Hellman problem}
  
  The `Gap Diffie-Hellman' problem is essentially the Computational problem,
  but given an oracle which can answer the Decisional problem.

  Consider this experiment.
  \begin{program}
    Experiment $\Expt{gdh}{G}(A)$: \+ \\
      $\alpha \getsr \Z/q\Z$; $\beta \getsr \Z/q\Z$; \\
      $c \gets A^{C(\cdot, \cdot)}(g^\alpha, g^\beta)$; \\
      \IF $c = g^{\alpha\beta}$ \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \next
    Oracle $C(x, y)$: \+ \\
      \IF $y = x^\alpha$ \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \end{program}
  We define the success probability of an adversary $A$ as
  \[ \Succ{gdh}{G}(A) = \Pr[\Expt{gdh}{G}(A) = 1] \]
  and the insecurity, against algorithms running in time $t$ and making $q_C$
  oracle queries, is
  \[ \InSec{gdh}(G; t, q_C) = \max_A \Succ{gdh}{G}(A). \]
\end{slide}

\begin{slide}
  \head{Security of the Diffie-Hellman KEM}
  
  Now that we have our new problem, the security result is relatively easy.
  \[ \InSec{ohd}(\Xid{\mathcal{K}}{DH}^{G, H}; t, q_R, q_H)
     \le 2\cdot \InSec{gdh}(G; t + O(q_R + q_H), q_H). \]%

  Note that it's very important that the random oracle is given \emph{both}
  the public value $b$ and the shared secret $b^\alpha$!  Otherwise, the
  scheme is \emph{malleable} in a group of composite order.  For example,
  suppose that $q = 2r$ for some $r$; then if $\alpha$ is even, we have
  $(b\cdot g^r)^\alpha = b^\alpha$.  Passing $b$ to the oracle ensures that
  these queries given independent answers, even if the shared secret is the
  same.
\end{slide}

\begin{proof}
  Suppose that $A$ solves the oracle hash decision problem for
  $\Xid{\mathcal{K}}{DH}^{G, H}$.  Let the input to~$A$ be the triple $(a, b,
  h^*)$, where $a = g^\alpha$ and $b = g^\beta$; and let $h^* =
  H(g^{\alpha\beta})$.  $A$ must decide whether $h = h^*$.  Clearly, if $A$
  never queries $H$ at $(g^\beta, g^{\alpha\beta})$ then its advantage is
  zero, since it has no information about $h^*$.

  As in the one-way function case, we have
  \[ \Pr[F] \ge \frac{1}{2} \Adv{ohd}{\Xid{\mathcal{K}}{DH}^{G, H}}(A) \]
  where $F$ is the event that $A$ queries $H$ at $(g^\beta,
  g^{\alpha\beta})$.
  
  We present an algorithm~$B$ which can solve an instance of the Gap
  Diffie-Hellman problem in~$G$ whenever event $F$ occurs.
  \begin{program}
    Algorithm $B^{C(\cdot, \cdot)}(a^*, b^*)$: \+ \\
      $\Xid{R}{map} \gets \emptyset$; $\Xid{H}{map} \gets \emptyset$; \\
      $h^* \gets \{0, 1\}^k$; \\
      $c^* \gets \bot$; \\
      $b \gets A^{\Xid{R}{sim}(\cdot), \Xid{H}{sim}(\cdot)}
        (a^*, b^*, h^*)$; \\
      \RETURN $c^*$; \- \\[\smallskipamount]
    Oracle $\Xid{R}{sim}(b)$: \+ \\
      \IF $b \in \dom\Xid{R}{map}$ \\
      \THEN \RETURN $\Xid{R}{map}(b)$; \\
      $h \gets \{0, 1\}^k$; \\
      $\Xid{R}{map} \gets \Xid{R}{map} \cup \{ b \mapsto h \}$; \\
      \RETURN $h$;
  \next
    Oracle $\Xid{H}{sim}(b, c)$: \+ \\
      \IF $C(b, c) = 0$ \THEN \\ \quad \= \+ \kill
        \IF $(b, c) \in \dom\Xid{H}{map}$ \THEN
          \RETURN $\Xid{H}{map}(b, c)$; \\
        $h \gets \{0, 1\}^k$; \\
        $\Xid{H}{map} \gets \Xid{H}{map} \cup \{ (b, c) \mapsto h \}$; \\
        \RETURN $h$; \- \\
      \IF $b = b^*$ \THEN \\ \quad \= \+ \kill
        $c^* \gets c$; \\
        \IF $c \notin \dom\Xid{R}{map}$ \THEN \\ \quad \= \+ \kill
          $b^* \getsr \{0, 1\}$; \\
          \IF $b^* = 1$ \THEN
            $\Xid{R}{map} \gets \Xid{R}{map} \cup \{ y \mapsto h^* \}$ \-\-\\
      \RETURN $\Xid{R}{sim}(c)$; \- \\
  \end{program}
  Hence, we have
  \[ \Succ{gdh}{G}(A)
     \ge \frac{1}{2} \Adv{ohd}{\Xid{\mathcal{K}}{DH}^{G, H}}(A) \]%
  as required.
\end{proof}

\xcalways\subsection{An integrated encryption scheme}\x

\begin{slide}
  \head{An integrated encryption scheme}

  Let $\mathcal{K} = (G, X, R)$ be a key-encapsulation mechanism, and let
  $\mathcal{E} = (E, D)$ be a symmetric encryption scheme.  We define the
  \emph{integrated encryption scheme} $\Xid{\mathcal{E}}{IES}^{\mathcal{K},
  \mathcal{E}} = (\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}},
  \Xid{E}{IES}^{\mathcal{K}, \mathcal{E}}, \Xid{D}{IES}^{\mathcal{K},
  \mathcal{E}})$ as follows:
  \begin{program}
    Algorithm $\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}$: \+ \\
      $(P, K) \gets G$; \\
      \RETURN (P, K);
  \next
    Algorithm $\Xid{E}{IES}^{\mathcal{K}, \mathcal{E}}_P(x)$: \+ \\
      $(y_0, h) \gets X_P$; \\
      $y_1 \gets E_h(x)$; \\
      \RETURN $(y_0, y_1)$;
  \next
    Algorithm $\Xid{D}{IES}^{\mathcal{K}, \mathcal{E}}_K(y_0, y_1)$: \+ \\
      $h \gets R_K(y_0)$; \\
      $x \gets D_h(y_1)$; \\
      \RETURN $x$;
  \end{program}
  The security of this scheme relates tightly to that of the individual
  components:
  \begin{eqnarray*}[Ll]
     \InSec{ind-cca2}(\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}; t, q_D) \\
     & \le
       2 \cdot \InSec{ohd}(\mathcal{K}; t + O(q_D), q_D) +
       \InSec{ftg-cca}(\mathcal{E}; t + O(q_D), 0, q_D).
  \end{eqnarray*}
  Note how weak the security requirements on the encryption scheme are: no
  chosen-plaintext queries are permitted!
\end{slide}

\begin{proof}
  Suppose $A$ attacks $\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}$ in the
  IND-CCA2 sense.  We construct an adversary $B$ which attacks the KEM.
  \begin{program}
    Adversary $B^{R(\cdot)}(P, y, h)$: \+ \\
      $(x_0, x_1, s) \gets A^{\Xid{D}{sim}(\cdot)}(\cookie{find}, P)$; \\
      $b \gets \{0, 1\}$; \\
      $z \gets E_h(x_b)$; \\
      $b' \gets A^{\Xid{D}{sim}(\cdot)}(\cookie{guess}, (y, z), s)$; \\
      \IF $b = b'$ \THEN \RETURN $1$; \\
      \ELSE \RETURN $0$;
  \next
    Oracle $\Xid{D}{sim}(y_0, y_1)$: \+ \\
      \IF $y_0 = y$ \THEN \RETURN $D_h(y_1)$; \\
      $h' \gets R(y_0)$; \\
      \RETURN $D_{h'}(y_1)$;
  \end{program}
  If the $h$-value matches the public value $y$ then $B$ provides a correct
  simulation of $A$'s attack game, and hence wins with probability
  \[ \frac{\Adv{ind-cca2}{\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}}}{2} +
     \frac{1}{2}. \]%
  We construct a new adversary $C$, attacking $\mathcal{E}$ in the FTG-CCA
  sense, to help us bound $B$'s probability of success when $h$ is chosen
  randomly.
  \begin{program}
    Adversary $C^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\
      $(P, K) \gets G$; \\
      $y' \gets \bot$; \\
      $(x_0, x_1, s_A) \gets A^{\Xid{D}{sim}(\cdot)}(\cookie{find}, P)$; \\
      \RETURN $(x_0, x_1, (P, K, s_A))$;
  \next
    Adversary $C^{E(\cdot), D(\cdot)}(\cookie{guess}, y, s)$: \+ \\
      $(P, K, s_A) \gets s$; \\
      $(h', y') \gets X_P$; \\
      $b <- A^{\Xid{D}{sim}(\cdot)}(\cookie{guess}, (y', y), s_A)$; \\
      \RETURN $b$;
  \newline
    Oracle $\Xid{D}{sim}(y_0, y_1)$: \+ \\
      \IF $y_0 = y'$ \THEN \RETURN $D(y_1)$; \\
      $h \gets R_K(y_0)$; \\
      \RETURN $D_h(y_1)$;
  \end{program}
  Clearly, $C$ provides the same environment as $B$ does when $h$ is random;
  hence, in this case, $B$ wins with probability at most
  \[ \frac{\Adv{ftg-cca2}{\mathcal{E}}(C)}{2} + \frac{1}{2}. \]
  But
  \[ \Adv{ohd}{\mathcal{K}}(B) =
       \frac{1}{2}\left(
           \Adv{ind-cca2}{\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}} +
           \Adv{ftg-cca2}{\mathcal{E}}(C) \right). \]%
  Rearranging yields the required result.
\end{proof}

\endinput

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