CommitLineData
41761fdc 1\xcalways\section{Integrated public-key encryption schemes}\x
2
3The formulation here is original work by the author. I've tried to
53aa10b5 4generalize the work by (among others), Shoup \cite{Shoup:2001:PIS}, and
5Abdalla, Bellare and Rogaway \cite{Abdalla:2001:DHIES}. The final proof is
6from a Usenet article prompted by David Hopwood, but based on the DHIES proof
7in \cite{Abdalla:2001:DHIES}.
41761fdc 8
9\xcalways\subsection{Introduction and definitions}\x
10
11\begin{slide}
12 \topic{motivation}
14
15 Public-key encryption schemes are very useful, but there are disadvantages:
16 \begin{itemize}
17 \item they tend not to be very fast; and
18 \item they don't tend to be able to encrypt arbitrarily large messages.
19 \end{itemize}
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.
23
24 Throughout the following, we'll consider our objective to be resistance to
26\end{slide}
27
28\begin{slide}
30
31 A simple approach would be to generate a random key for some secure (i.e.,
d7891575 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
34 public-key scheme).
41761fdc 35
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
38 rather flabby'.
39
40 Can we do \emph{better} than this na\"{\i}ve approach?
41\end{slide}
42
43\begin{slide}
44 \topic{key encapsulation}
46
47 A \emph{key-encapsulation mechanism} (KEM) $\mathcal{K} = (G, X, R)$ is a
48 triple of algorithms:
49 \begin{itemize}
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
52 $(P, K)$;
b912aadf 53 \item a probabilistic \emph{exchange} algorithm~$E$, which is given a
41761fdc 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$.
58 \end{itemize}
59 We require for correctness that, if $(P, K) \in G$ and $(y, h) \in X_P$,
60 then $R_K(y) = h$.
61
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.
65\end{slide}
66
67\begin{slide}
68 \topic{oracle hash decision problems}
70
71 We say that a key-encapsulation mechanisms is secure if the corresponding
72 \emph{oracle hash decision problem} is hard. Consider this experiment:
73 \begin{program}
74 Experiment $\Expt{ohd-$b$}{\mathcal{K}}(A)$: \+ \\
75 $(P, K) \gets G$; \\
76 $h_0 \getsr \{0, 1\}^k$; $(y, h_1) \gets X_P$; \\
77 $b' \gets A^{R_K(\cdot)}(P, y, h_b)$; \\
78 \RETURN $b'$;
79 \end{program}
80 We forbid the adversary from querying its $R_K$ oracle at $y$. We define
81 advantage and insecurity in the usual way:
82 \begin{eqnarray*}[rl]
84 \Pr[\Expt{ohd-$1$}{\mathcal{K}}(A) = 1] -
85 \Pr[\Expt{ohd-$0$}{\mathcal{K}}(A) = 1]
86 \\
87 \InSec{ohd}(\mathcal{K}; t, q) &=
89 \end{eqnarray*}
90 where the maximum is taken over adversaries $A$ running in time $t$ and
91 issuing $q$ recovery queries.
92\end{slide}
93
94\xcalways\subsection{Constructions for key-encapsulation mechanisms}\x
95
96\begin{slide}
97 \topic{trapdoor one-way permutations}
98 \head{Constructing a KEM from a trapdoor OWP}
99
100 Why might key-encapsulation mechanisms exist, and how do we construct them?
101
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:
107 \begin{program}
108 Algorithm $\Xid{X}{OWF}^{\mathcal{T}, H(\cdot)}_P$: \+ \\
109 $x \getsr \dom f_P$; \\
110 $h \gets H(x)$; \\
111 \RETURN $(f_P(x), h)$;
112 \next
113 Algorithm $\Xid{R}{OWF}^{\mathcal{T}, H(\cdot)}_K(y)$: \+ \\
114 $x \gets T_K(y)$; \\
115 $h \gets H(x)$; \\
116 \RETURN $f_P(x)$;
117 \end{program}
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)).$%
121\end{slide}
122
123\begin{proof}
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
129 $\frac{1}{2}$.
130
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
133 bit $b$. Then
134 $\Pr[S] = 135 \frac{\Adv{ohd}{\Xid{\mathcal{K}}{OWF}^{\mathcal{T}, H}}(A)}{2} + 136 \frac{1}{2}.$%
53aa10b5 137 Let $F$ be the event that $A$ queries $H$ at $x^*$. Then by
138 Lemma~\ref{lem:shoup} (slide~\pageref{lem:shoup}),
41761fdc 139 $\left|\Pr[S] - \frac{1}{2}\right| \le \Pr[F].$
140
141 Now consider this adversary $I$, attempting to invert the one-way function.
142 \begin{program}
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): \+ \\ 154 y \gets f_P(x); \\ 155 \IF y = y^* \THEN \\ \quad \= \+ \kill 156 x^* \gets x; \\ 157 \IF y \notin \dom\Xid{H}{map} \THEN \\ \quad \= \+ \kill 158 b^* \getsr \{0, 1\}; \\ 159 \IF b^* = 1 \THEN 160 \Xid{H}{map} \gets \Xid{H}{map} \cup \{ y \mapsto h^* \} \-\-\\ 161 \RETURN \Xid{R}{sim}(y); 162 \end{program} 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) 167 \ge \Pr[F] 168 \ge \frac{1}{2} \Adv{ohd}{\Xid{\mathcal{K}}{OWF}^{\mathcal{T}, H}}(A).$%
169 proving the result.
170\end{proof}
171
172\begin{slide}
173 \topic{Diffie-Hellman}
174 \head{A KEM based on Diffie-Hellman \cite{Abdalla:2001:DHIES}}
175
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.
179
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:
182 \begin{program}
183 Algorithm $\Xid{G}{DH}^{G, H(\cdot, \cdot)}$: \+ \\
184 $\alpha \getsr \Z/q\Z$; \\
185 \RETURN $(g^\alpha, \alpha)$;
186 \next
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)$;
191 \next
192 Algorithm $\Xid{R}{DH}^{G, H(\cdot, \cdot)}_\alpha(b)$: \+ \\
193 $h \gets H(b, b^\alpha)$; \\
194 \RETURN $h$;
195 \end{program}
196
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!
199\end{slide}
200
201\begin{slide}
203
204 The Gap Diffie-Hellman' problem is essentially the Computational problem,
205 but given an oracle which can answer the Decisional problem.
206
207 Consider this experiment.
208 \begin{program}
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$; \\
213 \ELSE \RETURN $0$;
214 \next
215 Oracle $C(x, y)$: \+ \\
216 \IF $y = x^\alpha$ \THEN \RETURN $1$; \\
217 \ELSE \RETURN $0$;
218 \end{program}
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$
222 oracle queries, is
223 $\InSec{gdh}(G; t, q_C) = \max_A \Succ{gdh}{G}(A).$
224\end{slide}
225
226\begin{slide}
227 \head{Security of the Diffie-Hellman KEM}
228
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).$%
232
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
MW
238 these queries given independent answers, even if the shared secret is the
239 same.
41761fdc 240\end{slide}
241
242\begin{proof}
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, b912aadf MW 245 h^*)$, where $a = g^\alpha$ and $b = g^\beta$; and let $h^* = 246 H(g^{\alpha\beta})$. $A$ must decide whether $h = h^*$. Clearly, if $A$
247 never queries $H$ at $(g^\beta, g^{\alpha\beta})$ then its advantage is
248 zero, since it has no information about $h^*$.
41761fdc 249
250 As in the one-way function case, we have
251 $\Pr[F] \ge \frac{1}{2} \Adv{ohd}{\Xid{\mathcal{K}}{DH}^{G, H}}(A)$
252 where $F$ is the event that $A$ queries $H$ at $(g^\beta, 253 g^{\alpha\beta})$.
254
255 We present an algorithm~$B$ which can solve an instance of the Gap
256 Diffie-Hellman problem in~$G$ whenever event $F$ occurs.
257 \begin{program}
258 Algorithm $B^{C(\cdot, \cdot)}(a^*, b^*)$: \+ \\
259 $\Xid{R}{map} \gets \emptyset$; $\Xid{H}{map} \gets \emptyset$; \\
b912aadf 260 $h^* \gets \{0, 1\}^k$; \\
41761fdc 261 $c^* \gets \bot$; \\
262 $b \gets A^{\Xid{R}{sim}(\cdot), \Xid{H}{sim}(\cdot)} 263 (a^*, b^*, h^*)$; \\
264 \RETURN $c^*$; \- \$\smallskipamount] 265 Oracle \Xid{R}{sim}(b): \+ \\ 266 \IF b \in \dom\Xid{R}{map} \\ 267 \THEN \RETURN \Xid{R}{map}(b); \\ b912aadf 268 h \gets \{0, 1\}^k; \\ 41761fdc 269 \Xid{R}{map} \gets \Xid{R}{map} \cup \{ b \mapsto h \}; \\ 270 \RETURN h; 271 \next 272 Oracle \Xid{H}{sim}(b, c): \+ \\ 273 \IF C(b, c) = 0 \THEN \\ \quad \= \+ \kill 274 \IF (b, c) \in \dom\Xid{H}{map} \THEN 275 \RETURN \Xid{H}{map}(b, c); \\ 276 h \gets \{0, 1\}^k; \\ b912aadf 277 \Xid{H}{map} \gets \Xid{H}{map} \cup \{ (b, c) \mapsto h \}; \\ 41761fdc 278 \RETURN h; \- \\ 279 \IF b = b^* \THEN \\ \quad \= \+ \kill 280 c^* \gets c; \\ 281 \IF c \notin \dom\Xid{R}{map} \THEN \\ \quad \= \+ \kill 282 b^* \getsr \{0, 1\}; \\ 283 \IF b^* = 1 \THEN 284 \Xid{R}{map} \gets \Xid{R}{map} \cup \{ y \mapsto h^* \} \-\-\\ 285 \RETURN \Xid{R}{sim}(c); \- \\ 286 \end{program} 287 Hence, we have 288 \[ \Succ{gdh}{G}(A) 289 \ge \frac{1}{2} \Adv{ohd}{\Xid{\mathcal{K}}{DH}^{G, H}}(A)$%
290 as required.
291\end{proof}
292
293\xcalways\subsection{An integrated encryption scheme}\x
294
295\begin{slide}
297
298 Let $\mathcal{K} = (G, X, R)$ be a key-encapsulation mechanism, and let
299 $\mathcal{E} = (E, D)$ be a symmetric encryption scheme. We define the
300 \emph{integrated encryption scheme} $\Xid{\mathcal{E}}{IES}^{\mathcal{K}, 301 \mathcal{E}} = (\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}, 302 \Xid{E}{IES}^{\mathcal{K}, \mathcal{E}}, \Xid{D}{IES}^{\mathcal{K}, 303 \mathcal{E}})$ as follows:
304 \begin{program}
305 Algorithm $\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}$: \+ \\
306 $(P, K) \gets G$; \\
307 \RETURN (P, K);
308 \next
309 Algorithm $\Xid{E}{IES}^{\mathcal{K}, \mathcal{E}}_P(x)$: \+ \\
310 $(y_0, h) \gets X_P$; \\
311 $y_1 \gets E_h(x)$; \\
312 \RETURN $(y_0, y_1)$;
313 \next
314 Algorithm $\Xid{D}{IES}^{\mathcal{K}, \mathcal{E}}_K(y_0, y_1)$: \+ \\
315 $h \gets R_K(y_0)$; \\
316 $x \gets D_h(y_1)$; \\
317 \RETURN $x$;
318 \end{program}
319 The security of this scheme relates tightly to that of the individual
320 components:
321 \begin{eqnarray*}[Ll]
322 \InSec{ind-cca2}(\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}; t, q_D) \\
323 & \le
324 2 \cdot \InSec{ohd}(\mathcal{K}; t + O(q_D), q_D) +
d7891575 325 \InSec{ftg-cca2}(\mathcal{E}; t + O(q_D), 0, q_D).
41761fdc 326 \end{eqnarray*}
327 Note how weak the security requirements on the encryption scheme are: no
328 chosen-plaintext queries are permitted!
329\end{slide}
330
331\begin{proof}
332 Suppose $A$ attacks $\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}$ in the
333 IND-CCA2 sense. We construct an adversary $B$ which attacks the KEM.
334 \begin{program}
335 Adversary $B^{R(\cdot)}(P, y, h)$: \+ \\
336 $(x_0, x_1, s) \gets A^{\Xid{D}{sim}(\cdot)}(\cookie{find}, P)$; \\
337 $b \gets \{0, 1\}$; \\
338 $z \gets E_h(x_b)$; \\
339 $b' \gets A^{\Xid{D}{sim}(\cdot)}(\cookie{guess}, (y, z), s)$; \\
340 \IF $b = b'$ \THEN \RETURN $1$; \\
341 \ELSE \RETURN $0$;
342 \next
343 Oracle $\Xid{D}{sim}(y_0, y_1)$: \+ \\
344 \IF $y_0 = y$ \THEN \RETURN $D_h(y_1)$; \\
345 $h' \gets R(y_0)$; \\
346 \RETURN $D_{h'}(y_1)$;
347 \end{program}
348 If the $h$-value matches the public value $y$ then $B$ provides a correct
349 simulation of $A$'s attack game, and hence wins with probability
350 $\frac{\Adv{ind-cca2}{\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}}}{2} + 351 \frac{1}{2}.$%
d7891575 352 We construct a new adversary $C$, attacking $\mathcal{E}$ in the FTG-CCA2
41761fdc 353 sense, to help us bound $B$'s probability of success when $h$ is chosen
354 randomly.
355 \begin{program}
356 Adversary $C^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\
357 $(P, K) \gets G$; \\
358 $y' \gets \bot$; \\
359 $(x_0, x_1, s_A) \gets A^{\Xid{D}{sim}(\cdot)}(\cookie{find}, P)$; \\
360 \RETURN $(x_0, x_1, (P, K, s_A))$;
361 \next
362 Adversary $C^{E(\cdot), D(\cdot)}(\cookie{guess}, y, s)$: \+ \\
363 $(P, K, s_A) \gets s$; \\
364 $(h', y') \gets X_P$; \\
365 $b <- A^{\Xid{D}{sim}(\cdot)}(\cookie{guess}, (y', y), s_A)$; \\
366 \RETURN $b$;
367 \newline
368 Oracle $\Xid{D}{sim}(y_0, y_1)$: \+ \\
369 \IF $y_0 = y'$ \THEN \RETURN $D(y_1)$; \\
370 $h \gets R_K(y_0)$; \\
371 \RETURN $D_h(y_1)$;
372 \end{program}
373 Clearly, $C$ provides the same environment as $B$ does when $h$ is random;
374 hence, in this case, $B$ wins with probability at most
375 $\frac{\Adv{ftg-cca2}{\mathcal{E}}(C)}{2} + \frac{1}{2}.$
376 But
377 $\Adv{ohd}{\mathcal{K}}(B) = 378 \frac{1}{2}\left( 379 \Adv{ind-cca2}{\Xid{G}{IES}^{\mathcal{K}, \mathcal{E}}} + 380 \Adv{ftg-cca2}{\mathcal{E}}(C) \right).$%
381 Rearranging yields the required result.
382\end{proof}
383
384\endinput
385
386%%% Local Variables:
387%%% mode: latex
388%%% TeX-master: "ips"
389%%% End: