X-Git-Url: https://git.distorted.org.uk/~mdw/doc/ips/blobdiff_plain/41761fdc7bb8f1ed87f5e1116d389158513ee280..6278c386d4ce1feeab4adba11c161602ade00414:/enc-ies.tex 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}