| 1 | \xcalways\section{Integrated public-key encryption schemes}\x |
| 2 | |
| 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}. |
| 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-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). |
| 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}. \]% |
| 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]. \] |
| 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-cca2}(\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-CCA2 |
| 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: |