X-Git-Url: https://git.distorted.org.uk/~mdw/doc/ips/blobdiff_plain/41761fdc7bb8f1ed87f5e1116d389158513ee280..refs/heads/svn:/enc-ies.tex?ds=sidebyside

diff --git a/enc-ies.tex b/enc-ies.tex
index cd0f5c6..9916a18 100644
--- a/enc-ies.tex
+++ b/enc-ies.tex
@@ -1,9 +1,10 @@
 \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.
+generalize the work by (among others), Shoup \cite{Shoup:2001:PIS}, and
+Abdalla, Bellare and Rogaway \cite{Abdalla:2001:DHIES}.  The final proof is
+from a Usenet article prompted by David Hopwood, but based on the DHIES proof
+in \cite{Abdalla:2001:DHIES}.
 
 \xcalways\subsection{Introduction and definitions}\x
 
@@ -28,9 +29,9 @@ Hopwood, but based on the DHAES proof by ABR.
   \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).
+  IND-CCA2) 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
@@ -49,7 +50,7 @@ Hopwood, but based on the DHAES proof by ABR.
   \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
+  \item a probabilistic \emph{exchange} algorithm~$X$, 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
@@ -133,8 +134,8 @@ Hopwood, but based on the DHAES proof by ABR.
   \[ \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}),
+  Let $F$ be the event that $A$ queries $H$ at $x^*$.  Then by 
+  Lemma~\ref{lem:shoup} (slide~\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.
@@ -234,17 +235,18 @@ Hopwood, but based on the DHAES proof by ABR.
   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.
+  these queries are 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^*$.
+  h)$, where $a = g^\alpha$, $b = g^\beta$ and $h$ is some string in $\{0,
+  1\}^k$; and let $h^* = H(g^\beta, 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) \]
@@ -256,7 +258,7 @@ Hopwood, but based on the DHAES proof by ABR.
   \begin{program}
     Algorithm $B^{C(\cdot, \cdot)}(a^*, b^*)$: \+ \\
       $\Xid{R}{map} \gets \emptyset$; $\Xid{H}{map} \gets \emptyset$; \\
-      $h^* \gets \{0, 1\}^k$; \\
+      $h^* \getsr \{0, 1\}^k$; \\
       $c^* \gets \bot$; \\
       $b \gets A^{\Xid{R}{sim}(\cdot), \Xid{H}{sim}(\cdot)}
         (a^*, b^*, h^*)$; \\
@@ -264,7 +266,7 @@ Hopwood, but based on the DHAES proof by ABR.
     Oracle $\Xid{R}{sim}(b)$: \+ \\
       \IF $b \in \dom\Xid{R}{map}$ \\
       \THEN \RETURN $\Xid{R}{map}(b)$; \\
-      $h \gets \{0, 1\}^k$; \\
+      $h \getsr \{0, 1\}^k$; \\
       $\Xid{R}{map} \gets \Xid{R}{map} \cup \{ b \mapsto h \}$; \\
       \RETURN $h$;
   \next
@@ -273,7 +275,7 @@ Hopwood, but based on the DHAES proof by ABR.
         \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 \}$; \\
+        $\Xid{H}{map} \getsr \Xid{H}{map} \cup \{ (b, c) \mapsto h \}$; \\
         \RETURN $h$; \- \\
       \IF $b = b^*$ \THEN \\ \quad \= \+ \kill
         $c^* \gets c$; \\
@@ -321,7 +323,7 @@ Hopwood, but based on the DHAES proof by ABR.
      \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).
+       \InSec{ftg-cca2}(\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!
@@ -348,7 +350,7 @@ Hopwood, but based on the DHAES proof by ABR.
   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
+  We construct a new adversary $C$, attacking $\mathcal{E}$ in the FTG-CCA2
   sense, to help us bound $B$'s probability of success when $h$ is chosen
   randomly.
   \begin{program}
