\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
\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
\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
\[ \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.
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) \]
\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^*)$; \\
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
\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$; \\
\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!
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}
~mdw / doc / ips / blobdiff