1 \xcalways\section{Integrated public-key encryption schemes
}\x
3 The formulation here is original work by the author. I've tried to
4 generalize the work by (among others), Shoup
\cite{Shoup:
2001:PIS
}, and
5 Abdalla, Bellare and Rogaway
\cite{Abdalla:
2001:DHIES
}. The final proof is
6 from a Usenet article prompted by David Hopwood, but based on the DHIES proof
7 in
\cite{Abdalla:
2001:DHIES
}.
9 \xcalways\subsection{Introduction and definitions
}\x
13 \head{Motivation for integrated encryption
}
15 Public-key encryption schemes are very useful, but there are disadvantages:
17 \item they tend not to be very fast; and
18 \item they don't tend to be able to encrypt arbitrarily large messages.
20 Symmetric schemes don't have these problems, but key distribution is
21 harder. It seems sensible to construct `hybrid' schemes which use
22 public-key techniques for exchanging keys for symmetric encryption schemes.
24 Throughout the following, we'll consider our objective to be resistance to
25 \emph{adaptive chosen-ciphertext
} attacks.
29 \head{An obvious approach
}
31 A simple approach would be to generate a random key for some secure (i.e.,
32 IND-CCA2) symmetric scheme, encrypt the message under that key, and,
33 encrypt the key under the recipient's public key (using some IND-CCA2
36 This is obviously secure. But the security results for most public-key
37 schemes are less than encouraging: the reductions, even for OAEP+, are
40 Can we do
\emph{better
} than this na\"
{\i}ve approach?
44 \topic{key encapsulation
}
45 \head{Key-encapsulation mechanisms
\cite{Shoup:
2001:PIS
}}
47 A
\emph{key-encapsulation mechanism
} (KEM) $
\mathcal{K
} = (G, X, R)$ is a
50 \item a probabilistic
\emph{key-generation
} algorithm~$G$, which takes no
51 input (or a security parameter for asymptotic types) and returns a pair
53 \item a probabilistic
\emph{exchange
} algorithm~$X$, which is given a
54 as input a public key~$P$ and returns a
\emph{public value
}~$y$ and a
55 \emph{hash
} $h
\in \
{0,
1\
}^k$; and
56 \item a deterministic
\emph{recovery
} algorithm~$R$, which is given as
57 input a private key~$K$ and a public value~$y$ and returns a hash $h$.
59 We require for correctness that, if $(P, K)
\in G$ and $(y, h)
\in X_P$,
62 The idea is that the key-encapsulation mechanism invents a key and public
63 value simultaneously. We'll look at such mechanisms constructed from both
64 trapdoor one-way functions like RSA, and schemes like Diffie-Hellman.
68 \topic{oracle hash decision problems
}
69 \head{Oracle hash decision problems
}
71 We say that a key-encapsulation mechanisms is secure if the corresponding
72 \emph{oracle hash decision problem
} is hard. Consider this experiment:
74 Experiment $
\Expt{ohd-$b$
}{\mathcal{K
}}(A)$: \+ \\
76 $h_0
\getsr \
{0,
1\
}^k$; $(y, h_1)
\gets X_P$; \\
77 $b'
\gets A^
{R_K(
\cdot)
}(P, y, h_b)$; \\
80 We forbid the adversary from querying its $R_K$ oracle at $y$. We define
81 advantage and insecurity in the usual way:
83 \Adv{ohd
}{\mathcal{K
}}(A) &=
84 \Pr[\Expt{ohd-$
1$
}{\mathcal{K
}}(A) =
1] -
85 \Pr[\Expt{ohd-$
0$
}{\mathcal{K
}}(A) =
1]
87 \InSec{ohd
}(
\mathcal{K
}; t, q) &=
88 \max_A \Adv{ohd
}{\mathcal{K
}}(A)
90 where the maximum is taken over adversaries $A$ running in time $t$ and
91 issuing $q$ recovery queries.
94 \xcalways\subsection{Constructions for key-encapsulation mechanisms
}\x
97 \topic{trapdoor one-way permutations
}
98 \head{Constructing a KEM from a trapdoor OWP
}
100 Why might key-encapsulation mechanisms exist, and how do we construct them?
102 In the random oracle model, we can construct a KEM from any trapdoor
103 one-way permutation. Let $
\mathcal{T
} = (G, f, T)$ be such a one-way
104 permutation, and let $H
\colon \
{0,
1\
}^*
\to \
{0,
1\
}^k$ be a public random
105 oracle. We can construct $
\Xid{\mathcal{K
}}{OWF
}^
{\mathcal{T
}, H
} = (G,
106 \Xid{X
}{OWF
}^
{\mathcal{T
}, H
},
\Xid{R
}{OWF
}^
{\mathcal{T
}, H
})$ as follows:
108 Algorithm $
\Xid{X
}{OWF
}^
{\mathcal{T
}, H(
\cdot)
}_P$: \+ \\
109 $x
\getsr \dom f_P$; \\
111 \RETURN $(f_P(x), h)$;
113 Algorithm $
\Xid{R
}{OWF
}^
{\mathcal{T
}, H(
\cdot)
}_K(y)$: \+ \\
118 The security of this scheme is then given by:
119 \
[ \InSec{ohd
}(
\Xid{\mathcal{K
}}{OWF
}^
{\mathcal{T
}, H
}; t, q_R, q_H)
\le
120 2 \cdot \InSec{owf
}(
\mathcal{T
}; t + O(q_H) + O(q_R)). \
]%
124 Let $A$ be an adversary solving the oracle hash decision problem. Let $y^*
125 = f_P(x^*)$ be the challenge public value, and let $h^*$ be the challenge
126 hash. Suppose that $A$ never queries its random oracle $H$ at $x^*$: then
127 obviously $h = H(x^*)$ is independent of $A$'s view, and $A$ has no
128 advantage, and its probability of guessing the hidden bit is precisely
131 Suppose that we choose which OHD experiment uniformly at random. Let $S$
132 be the event that the adversary wins, i.e., it correctly guesses the hidden
135 \frac{\Adv{ohd
}{\Xid{\mathcal{K
}}{OWF
}^
{\mathcal{T
}, H
}}(A)
}{2} +
137 Let $F$ be the event that $A$ queries $H$ at $x^*$. Then by
138 Lemma~
\ref{lem:shoup
} (slide~
\pageref{lem:shoup
}),
139 \
[ \left|
\Pr[S
] -
\frac{1}{2}\right|
\le \Pr[F
]. \
]
141 Now consider this adversary $I$, attempting to invert the one-way function.
143 Inverter $I(P, y^*)$: \+ \\
144 $
\Xid{H
}{map
} \gets \emptyset$; \\
145 $h^*
\gets \
{0,
1\
}^k$; $x^*
\gets \bot$; \\
146 $b
\gets A^
{\Xid{R
}{sim
}(
\cdot),
\Xid{H
}{sim
}(
\cdot)
}(P, y^*, h^*)$; \\
147 \RETURN $x^*$; \- \\
[\smallskipamount]
148 Oracle $
\Xid{R
}{sim
}(y)$: \+ \\
149 \IF $y
\in \dom\Xid{H
}{map
}$
\THEN \RETURN $
\Xid{H
}{map
}(y)$; \\
150 $h
\gets \
{0,
1\
}^k$; \\
151 $
\Xid{H
}{map
} \gets \Xid{H
}{map
} \cup \
{ y
\mapsto h \
}$; \\
152 \RETURN $h$; \- \\
[\smallskipamount]
153 Oracle $
\Xid{H
}{sim
}(x)$: \+ \\
155 \IF $y = y^*$
\THEN \\
\quad \= \+
\kill
157 \IF $y
\notin \dom\Xid{H
}{map
}$
\THEN \\
\quad \= \+
\kill
158 $b^*
\getsr \
{0,
1\
}$; \\
160 $
\Xid{H
}{map
} \gets \Xid{H
}{map
} \cup \
{ y
\mapsto h^* \
}$ \-\-\\
161 \RETURN $
\Xid{R
}{sim
}(y)$;
163 The simulation of the random and `recovery' oracles is a little subtle, but
164 from the adversary's point of view perfect. Clearly, then, $I$ inverts
165 $f_P$ whenever $F$ occurs, and
166 \
[ \Succ{owf
}{\mathcal{T
}}(I)
168 \ge \frac{1}{2} \Adv{ohd
}{\Xid{\mathcal{K
}}{OWF
}^
{\mathcal{T
}, H
}}(A). \
]%
173 \topic{Diffie-Hellman
}
174 \head{A KEM based on Diffie-Hellman
\cite{Abdalla:
2001:DHIES
}}
176 Let $G =
\langle g
\rangle$ be a cyclic group, with $q = |G|$. Then we can
177 construct a KEM based on the difficulty of the Diffie-Hellman problem in
178 $G$. Let $H
\colon G^
2 \to \
{0,
1\
}^k$ be a public random oracle.
180 We define $
\Xid{\mathcal{K
}}{DH
}^
{G, H
} = (
\Xid{G
}{DH
}^
{G, H
},
181 \Xid{X
}{DH
}^
{G, H
},
\Xid{R
}{DH
}^
{G, H
})$ as follows:
183 Algorithm $
\Xid{G
}{DH
}^
{G, H(
\cdot,
\cdot)
}$: \+ \\
184 $
\alpha \getsr \Z/q
\Z$; \\
185 \RETURN $(g^
\alpha,
\alpha)$;
187 Algorithm $
\Xid{X
}{DH
}^
{G, H(
\cdot,
\cdot)
}_a$: \+ \\
188 $
\beta \getsr \Z/q
\Z$; \\
189 $h
\gets H(g^
\beta, a^
\beta)$; \\
190 \RETURN $(g^
\beta, h)$;
192 Algorithm $
\Xid{R
}{DH
}^
{G, H(
\cdot,
\cdot)
}_
\alpha(b)$: \+ \\
193 $h
\gets H(b, b^
\alpha)$; \\
197 But the question of this scheme's security is tricky. It doesn't seem to
198 fit any of our standard problems. We therefore have to invent a new one!
202 \head{The Gap Diffie-Hellman problem
}
204 The `Gap Diffie-Hellman' problem is essentially the Computational problem,
205 but given an oracle which can answer the Decisional problem.
207 Consider this experiment.
209 Experiment $
\Expt{gdh
}{G
}(A)$: \+ \\
210 $
\alpha \getsr \Z/q
\Z$; $
\beta \getsr \Z/q
\Z$; \\
211 $c
\gets A^
{C(
\cdot,
\cdot)
}(g^
\alpha, g^
\beta)$; \\
212 \IF $c = g^
{\alpha\beta}$
\THEN \RETURN $
1$; \\
215 Oracle $C(x, y)$: \+ \\
216 \IF $y = x^
\alpha$
\THEN \RETURN $
1$; \\
219 We define the success probability of an adversary $A$ as
220 \
[ \Succ{gdh
}{G
}(A) =
\Pr[\Expt{gdh
}{G
}(A) =
1] \
]
221 and the insecurity, against algorithms running in time $t$ and making $q_C$
223 \
[ \InSec{gdh
}(G; t, q_C) =
\max_A \Succ{gdh
}{G
}(A). \
]
227 \head{Security of the Diffie-Hellman KEM
}
229 Now that we have our new problem, the security result is relatively easy.
230 \
[ \InSec{ohd
}(
\Xid{\mathcal{K
}}{DH
}^
{G, H
}; t, q_R, q_H)
231 \le 2\cdot \InSec{gdh
}(G; t + O(q_R + q_H), q_H). \
]%
233 Note that it's very important that the random oracle is given
\emph{both
}
234 the public value $b$ and the shared secret $b^
\alpha$! Otherwise, the
235 scheme is
\emph{malleable
} in a group of composite order. For example,
236 suppose that $q =
2r$ for some $r$; then if $
\alpha$ is even, we have
237 $(b
\cdot g^r)^
\alpha = b^
\alpha$. Passing $b$ to the oracle ensures that
238 these queries are given independent answers, even if the shared secret is
243 Suppose that $A$ solves the oracle hash decision problem for
244 $
\Xid{\mathcal{K
}}{DH
}^
{G, H
}$. Let the input to~$A$ be the triple $(a, b,
245 h)$, where $a = g^
\alpha$, $b = g^
\beta$ and $h$ is some string in $\
{0,
246 1\
}^k$; and let $h^* = H(g^
\beta, g^
{\alpha\beta})$. $A$ must decide
247 whether $h = h^*$. Clearly, if $A$ never queries $H$ at $(g^
\beta,
248 g^
{\alpha\beta})$ then its advantage is zero, since it has no information
251 As in the one-way function case, we have
252 \
[ \Pr[F
] \ge \frac{1}{2} \Adv{ohd
}{\Xid{\mathcal{K
}}{DH
}^
{G, H
}}(A) \
]
253 where $F$ is the event that $A$ queries $H$ at $(g^
\beta,
256 We present an algorithm~$B$ which can solve an instance of the Gap
257 Diffie-Hellman problem in~$G$ whenever event $F$ occurs.
259 Algorithm $B^
{C(
\cdot,
\cdot)
}(a^*, b^*)$: \+ \\
260 $
\Xid{R
}{map
} \gets \emptyset$; $
\Xid{H
}{map
} \gets \emptyset$; \\
261 $h^*
\getsr \
{0,
1\
}^k$; \\
263 $b
\gets A^
{\Xid{R
}{sim
}(
\cdot),
\Xid{H
}{sim
}(
\cdot)
}
265 \RETURN $c^*$; \- \\
[\smallskipamount]
266 Oracle $
\Xid{R
}{sim
}(b)$: \+ \\
267 \IF $b
\in \dom\Xid{R
}{map
}$ \\
268 \THEN \RETURN $
\Xid{R
}{map
}(b)$; \\
269 $h
\getsr \
{0,
1\
}^k$; \\
270 $
\Xid{R
}{map
} \gets \Xid{R
}{map
} \cup \
{ b
\mapsto h \
}$; \\
273 Oracle $
\Xid{H
}{sim
}(b, c)$: \+ \\
274 \IF $C(b, c) =
0$
\THEN \\
\quad \= \+
\kill
275 \IF $(b, c)
\in \dom\Xid{H
}{map
}$
\THEN
276 \RETURN $
\Xid{H
}{map
}(b, c)$; \\
277 $h
\gets \
{0,
1\
}^k$; \\
278 $
\Xid{H
}{map
} \getsr \Xid{H
}{map
} \cup \
{ (b, c)
\mapsto h \
}$; \\
280 \IF $b = b^*$
\THEN \\
\quad \= \+
\kill
282 \IF $c
\notin \dom\Xid{R
}{map
}$
\THEN \\
\quad \= \+
\kill
283 $b^*
\getsr \
{0,
1\
}$; \\
285 $
\Xid{R
}{map
} \gets \Xid{R
}{map
} \cup \
{ y
\mapsto h^* \
}$ \-\-\\
286 \RETURN $
\Xid{R
}{sim
}(c)$; \- \\
290 \ge \frac{1}{2} \Adv{ohd
}{\Xid{\mathcal{K
}}{DH
}^
{G, H
}}(A) \
]%
294 \xcalways\subsection{An integrated encryption scheme
}\x
297 \head{An integrated encryption scheme
}
299 Let $
\mathcal{K
} = (G, X, R)$ be a key-encapsulation mechanism, and let
300 $
\mathcal{E
} = (E, D)$ be a symmetric encryption scheme. We define the
301 \emph{integrated encryption scheme
} $
\Xid{\mathcal{E
}}{IES
}^
{\mathcal{K
},
302 \mathcal{E
}} = (
\Xid{G
}{IES
}^
{\mathcal{K
},
\mathcal{E
}},
303 \Xid{E
}{IES
}^
{\mathcal{K
},
\mathcal{E
}},
\Xid{D
}{IES
}^
{\mathcal{K
},
304 \mathcal{E
}})$ as follows:
306 Algorithm $
\Xid{G
}{IES
}^
{\mathcal{K
},
\mathcal{E
}}$: \+ \\
310 Algorithm $
\Xid{E
}{IES
}^
{\mathcal{K
},
\mathcal{E
}}_P(x)$: \+ \\
311 $(y_0, h)
\gets X_P$; \\
312 $y_1
\gets E_h(x)$; \\
313 \RETURN $(y_0, y_1)$;
315 Algorithm $
\Xid{D
}{IES
}^
{\mathcal{K
},
\mathcal{E
}}_K(y_0, y_1)$: \+ \\
316 $h
\gets R_K(y_0)$; \\
317 $x
\gets D_h(y_1)$; \\
320 The security of this scheme relates tightly to that of the individual
322 \begin{eqnarray*
}[Ll
]
323 \InSec{ind-cca2
}(
\Xid{G
}{IES
}^
{\mathcal{K
},
\mathcal{E
}}; t, q_D) \\
325 2 \cdot \InSec{ohd
}(
\mathcal{K
}; t + O(q_D), q_D) +
326 \InSec{ftg-cca2
}(
\mathcal{E
}; t + O(q_D),
0, q_D).
328 Note how weak the security requirements on the encryption scheme are: no
329 chosen-plaintext queries are permitted!
333 Suppose $A$ attacks $
\Xid{G
}{IES
}^
{\mathcal{K
},
\mathcal{E
}}$ in the
334 IND-CCA2 sense. We construct an adversary $B$ which attacks the KEM.
336 Adversary $B^
{R(
\cdot)
}(P, y, h)$: \+ \\
337 $(x_0, x_1, s)
\gets A^
{\Xid{D
}{sim
}(
\cdot)
}(
\cookie{find
}, P)$; \\
338 $b
\gets \
{0,
1\
}$; \\
339 $z
\gets E_h(x_b)$; \\
340 $b'
\gets A^
{\Xid{D
}{sim
}(
\cdot)
}(
\cookie{guess
}, (y, z), s)$; \\
341 \IF $b = b'$
\THEN \RETURN $
1$; \\
344 Oracle $
\Xid{D
}{sim
}(y_0, y_1)$: \+ \\
345 \IF $y_0 = y$
\THEN \RETURN $D_h(y_1)$; \\
346 $h'
\gets R(y_0)$; \\
347 \RETURN $D_
{h'
}(y_1)$;
349 If the $h$-value matches the public value $y$ then $B$ provides a correct
350 simulation of $A$'s attack game, and hence wins with probability
351 \
[ \frac{\Adv{ind-cca2
}{\Xid{G
}{IES
}^
{\mathcal{K
},
\mathcal{E
}}}}{2} +
353 We construct a new adversary $C$, attacking $
\mathcal{E
}$ in the FTG-CCA2
354 sense, to help us bound $B$'s probability of success when $h$ is chosen
357 Adversary $C^
{E(
\cdot), D(
\cdot)
}(
\cookie{find
})$: \+ \\
360 $(x_0, x_1, s_A)
\gets A^
{\Xid{D
}{sim
}(
\cdot)
}(
\cookie{find
}, P)$; \\
361 \RETURN $(x_0, x_1, (P, K, s_A))$;
363 Adversary $C^
{E(
\cdot), D(
\cdot)
}(
\cookie{guess
}, y, s)$: \+ \\
364 $(P, K, s_A)
\gets s$; \\
365 $(h', y')
\gets X_P$; \\
366 $b <- A^
{\Xid{D
}{sim
}(
\cdot)
}(
\cookie{guess
}, (y', y), s_A)$; \\
369 Oracle $
\Xid{D
}{sim
}(y_0, y_1)$: \+ \\
370 \IF $y_0 = y'$
\THEN \RETURN $D(y_1)$; \\
371 $h
\gets R_K(y_0)$; \\
374 Clearly, $C$ provides the same environment as $B$ does when $h$ is random;
375 hence, in this case, $B$ wins with probability at most
376 \
[ \frac{\Adv{ftg-cca2
}{\mathcal{E
}}(C)
}{2} +
\frac{1}{2}. \
]
378 \
[ \Adv{ohd
}{\mathcal{K
}}(B) =
380 \Adv{ind-cca2
}{\Xid{G
}{IES
}^
{\mathcal{K
},
\mathcal{E
}}} +
381 \Adv{ftg-cca2
}{\mathcal{E
}}(C)
\right). \
]%
382 Rearranging yields the required result.
389 %%% TeX-master: "ips"