41761fdc |
1 | \xcalways\section{Integrated public-key encryption schemes}\x |
2 | |
3 | The formulation here is original work by the author. I've tried to |
53aa10b5 |
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}. |
41761fdc |
8 | |
9 | \xcalways\subsection{Introduction and definitions}\x |
10 | |
11 | \begin{slide} |
12 | \topic{motivation} |
13 | \head{Motivation for integrated encryption} |
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 |
25 | \emph{adaptive chosen-ciphertext} attacks. |
26 | \end{slide} |
27 | |
28 | \begin{slide} |
29 | \head{An obvious approach} |
30 | |
31 | A simple approach would be to generate a random key for some secure (i.e., |
32 | IND-CCA) symmetric scheme, encrypt the message under that key, and, encrypt |
33 | the key under the recipient's public key (using some IND-CCA2 public-key |
34 | scheme). |
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} |
45 | \head{Key-encapsulation mechanisms \cite{Shoup:2001:PIS}} |
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)$; |
53 | \item a probabilistic \emph{exchange} algorithm~$E$, 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$. |
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} |
69 | \head{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] |
83 | \Adv{ohd}{\mathcal{K}}(A) &= |
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) &= |
88 | \max_A \Adv{ohd}{\mathcal{K}}(A) |
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} |
202 | \head{The Gap Diffie-Hellman problem} |
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 |
238 | these queries given independent answers, even if the shared secret is the |
239 | same. |
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, |
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^*$. |
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$; \\ |
260 | $h^* \gets \{0, 1\}^k$; \\ |
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)$; \\ |
268 | $h \gets \{0, 1\}^k$; \\ |
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$; \\ |
277 | $\Xid{H}{map} \gets \Xid{H}{map} \cup \{ (b, c) \mapsto h \}$; \\ |
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} |
296 | \head{An integrated encryption scheme} |
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) + |
325 | \InSec{ftg-cca}(\mathcal{E}; t + O(q_D), 0, q_D). |
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}. \]% |
352 | We construct a new adversary $C$, attacking $\mathcal{E}$ in the FTG-CCA |
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: |