Commit | Line | Data |
---|---|---|
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., | |
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} | |
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)$; | |
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} | |
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 | |
b912aadf 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} | |
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) + | |
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: |