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-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
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~$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$.
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 given independent answers, even if the shared secret is the
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^*$.
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,
255 We present an algorithm~$B$ which can solve an instance of the Gap
256 Diffie-Hellman problem in~$G$ whenever event $F$ occurs.
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$; \\
262 $b
\gets A^
{\Xid{R
}{sim
}(
\cdot),
\Xid{H
}{sim
}(
\cdot)
}
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 \
}$; \\
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 \
}$; \\
279 \IF $b = b^*$
\THEN \\
\quad \= \+
\kill
281 \IF $c
\notin \dom\Xid{R
}{map
}$
\THEN \\
\quad \= \+
\kill
282 $b^*
\getsr \
{0,
1\
}$; \\
284 $
\Xid{R
}{map
} \gets \Xid{R
}{map
} \cup \
{ y
\mapsto h^* \
}$ \-\-\\
285 \RETURN $
\Xid{R
}{sim
}(c)$; \- \\
289 \ge \frac{1}{2} \Adv{ohd
}{\Xid{\mathcal{K
}}{DH
}^
{G, H
}}(A) \
]%
293 \xcalways\subsection{An integrated encryption scheme
}\x
296 \head{An integrated encryption scheme
}
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:
305 Algorithm $
\Xid{G
}{IES
}^
{\mathcal{K
},
\mathcal{E
}}$: \+ \\
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)$;
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)$; \\
319 The security of this scheme relates tightly to that of the individual
321 \begin{eqnarray*
}[Ll
]
322 \InSec{ind-cca2
}(
\Xid{G
}{IES
}^
{\mathcal{K
},
\mathcal{E
}}; t, q_D) \\
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).
327 Note how weak the security requirements on the encryption scheme are: no
328 chosen-plaintext queries are permitted!
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.
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$; \\
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)$;
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} +
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
356 Adversary $C^
{E(
\cdot), D(
\cdot)
}(
\cookie{find
})$: \+ \\
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))$;
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)$; \\
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)$; \\
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}. \
]
377 \
[ \Adv{ohd
}{\mathcal{K
}}(B) =
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.
388 %%% TeX-master: "ips"