1 \xcalways\section{Public-key encryption}\x
3 \xcalways\subsection{Syntax}\x
5 \begin{slide}
6 \head{Syntax of public-key encryption schemes}
8 A public-key encryption scheme $\mathcal{E} = (G, E, D)$ is a triple of
9 algorithms:
10 \begin{itemize}
11 \item A probabilistic \emph{key-generation} algorithm $G(k)$ which returns
12 a matching public/private key pair $(P, K)$.
13 \item A probabilistic \emph{encryption} algorithm $E(P, m)$ which returns a
14 ciphertext $c$. We write $E_P(m)$ for $E(P, m)$.
15 \item A deterministic \emph{decryption} algorithm $D(K, c)$. If $(P, K) 16 \in G(k)$ and $c \in E(P, m)$ then $m = D(K, c)$. We write $D_K(c)$ for
17 $D(K, c)$.
18 \end{itemize}
19 On those occasions it matters, we write $\mathcal{P} = \dom E_P$ as the
20 \emph{plaintext space}, and $\mathcal{C} = \dom D_K$ as the
21 \emph{ciphertext space}. Hence, $E_P\colon \mathcal{P} \to \mathcal{C}$
22 and $D_K\colon \mathcal{C} \to \mathcal{P} \cup \{ \bot \}$ (allowing an
23 invalid ciphertext' return).
24 \end{slide}
26 \xcalways\subsection{Semantic security and indistinguishability}\x
28 \begin{slide}
31 We'll use the following decryption oracles throughout, to abbreviate the
32 properties of the various attacks:
33 \begin{tabular}[C]{l Mc Mc }
34 \hlx*{hv}
35 Attack & D_0(c) & D_1(c) \\ \hlx{vhv}
36 CPA & \bot & \bot \\
37 CCA1 & D_K(c) & \bot \\
38 CCA2 & D_K(c) & D_K(c) \\ \hlx*{vh}
39 \end{tabular}
40 In all cases, we forbid the adversary from querying a decryption oracle on
41 a challenge ciphertext, i.e., one returned to it by the experiment.
42 \end{slide}
44 \begin{slide}
45 \topic{semantic security}
48 Semantic security for $\mathcal{E} = (G, E, D)$, against an adversary
49 $A$ and attack $\id{atk} \in \{\text{cpa}, \text{cca1}, \text{cca2}\}$
50 is measured using the following game \cite{Bellare:2000:CST}:
51 \begin{program}
52 Experiment $\Expt{sem-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
53 $(P, K) \gets G$; \\
54 $(\mathcal{M}, s) \gets A^{D_0(\cdot)}(\cookie{select}, P)$; \\
55 $x_0 \getsr \mathcal{M}$; $x_1 \getsr \mathcal{M}$; \\
56 $y \gets E_P(x_1)$; \\
57 $(f, \alpha) \gets A^{D_1(\cdot)}(\cookie{predict}, y, s)$; \\
58 \IF $f(x_b) = \alpha$ \THEN \RETURN $1$; \\
59 \ELSE \RETURN $0$;
60 \end{program}
61 Here, $\mathcal{M}\colon \mathcal{P} \to [0, 1]$ is a \emph{distribution}
62 over the plaintext space, and $f\colon \mathcal{P} \to \ran f$ is a
63 \emph{function} on plaintexts, with $\alpha \in \ran f$.
64 \end{slide}
66 \begin{slide}
69 We include the time required to sample the distribution $\mathcal{M}$ and
70 to compute the function $f$ in the adversary's running time.
72 We require that $\mathcal{M}$ is \emph{valid}: i.e., that all messages in
73 $\supp \mathcal{M}$ have the same length.
74 \end{slide}
76 \begin{slide}
77 \topic{indistinguishability}
80 Indistinguishability for $\mathcal{E} = (G, E, D)$, against an adversary
81 $A$ and attack $\id{atk} \in \{\text{cpa}, \text{cca1}, \text{cca2}\}$
82 is measured using the following game:
83 \begin{program}
84 Experiment $\Expt{ind-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
85 $(P, K) \gets G$; \\
86 $(x_0, x_1, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$; \\
87 \IF $|x_0| \ne |x_1|$ \THEN \RETURN $0$; \\
88 $y \gets E_P(x_b)$; \\
89 $b' \gets A^{D_1(\cdot)}(\cookie{guess}, y, s)$; \\
90 \RETURN $b'$;
91 \end{program}
92 In the first stage, the adversary has to choose two plaintexts. One is
93 then chosen by the experimenter, encrypted, and the corresponding
95 plaintext was encrypted.
96 \end{slide}
98 \begin{slide}
102 For a public-key encryption scheme $\mathcal{E}$, under attack $\id{atk} 103 \in \{\text{cpa}, \text{cca1}, \text{cca2}\}$ by an adversary $A$, we
104 define $A$'s advantage by:
105 \begin{eqnarray*}[rl]
107 \Pr[\Expt{ind-\id{atk}-$1$}{\mathcal{E}}(A) = 1] -
108 \Pr[\Expt{ind-\id{atk}-$0$}{\mathcal{E}}(A) = 1];
109 \\
111 \Pr[\Expt{sem-\id{atk}-$1$}{\mathcal{E}}(A) = 1] -
112 \Pr[\Expt{sem-\id{atk}-$0$}{\mathcal{E}}(A) = 1].
113 \end{eqnarray*}
114 We define insecurities for $\id{goal} \in \{\text{ind}, \text{sem}\}$ under
115 chosen plaintext attacks, and chosen ciphertext attacks $\id{cca} \in 116 \{\text{cca1}, \text{cca2}\}$ by:
117 \begin{eqnarray*}
118 \InSec{\id{goal}-cpa}(\mathcal{E}; t) &=
120 \\
121 \InSec{\id{goal}-\id{cca}}(\mathcal{E}; t, q_D) &=
123 \end{eqnarray*}
124 where the maxima are taken over adversaries $A$ which run in time $t$ and
125 issue $q_E$ encryption and $q_D$ decryption queries.
126 \end{slide}
128 \begin{slide}
129 \topic{good news}
132 Now there's some good news: \emph{semantic security and (find-then-guess)
133 indistinguishability are almost equivalent}.
135 More precisely, if we fix a collection of resource constraints $R$, we have
136 $\InSec{sem-\id{atk}}(\mathcal{E}; R) \le 137 \InSec{ind-\id{atk}}(\mathcal{E}; R) \le 138 2 \cdot \InSec{sem-\id{atk}}(\mathcal{E}; R).$%
139 It's useful to realise that a relatively strong notion like semantic
140 security is actually equivalent to a simpler notion like
141 indistinguishability. The latter is certainly easier to work with in
142 proofs of security.
143 \end{slide}
145 \begin{proof}
146 \label{pf:pub-ind-eq-sem}
147 Proving that $\text{IND-\id{atk}} \implies \text{SEM-\id{atk}}$ is
148 pretty easy, so we do that first. Suppose that $A'$ attacks $\mathcal{E}$
149 in the semantic security sense. Consider the find-then-guess adversary
150 $A$:
151 \begin{program}
152 Adversary $A^{D(\cdot)}(\cookie{find}, P)$: \+ \\
153 $(\mathcal{M}, s') \gets A'^{D(\cdot)}(\cookie{select}, P)$; \\
154 $x_0 \getsr \mathcal{M}$; $x_1 \getsr \mathcal{M}$; \\
155 \RETURN $(x_0, x_1, (x_1, s'))$;
156 \next
157 Adversary $A^{D(\cdot)}(\cookie{guess}, y, s)$: \+ \\
158 $(x_1, s') \gets s$; \\
159 $(f, \alpha) \gets A'^{D(\cdot)}(\cookie{predict}, y, s')$; \\
160 \IF $f(x_1) = \alpha$ \THEN \RETURN $1$; \\
161 \ELSE \RETURN $0$;
162 \end{program}
163 Here, $A$ is simulating the semantic security experiment itself, drawing
164 plaintexts from $A'$'s distribution $\mathcal{M}$ and evaluating its chosen
165 function.
167 We study the result of the experiment
168 $\Expt{ind-\id{atk}-$b$}{\mathcal{E}}(A)$. Firstly, suppose $b = 1$.
169 Then $y \in E_P(x_1)$, and $A$ succeeds with the same probability that $A'$
170 wins in $\Expt{sem-\id{atk}-$1$}{\mathcal{E}}(A')$. Secondly, suppose $b 171 = 0$. Then $y \in E_P(x_0)$, but we still compare $A'$'s answer against
172 $x_1$, as in $\Expt{sem-\id{atk}-$0$}{\mathcal{E}}(A')$, up to
173 relabelling of $x_0$ and $x_1$. Hence,
174 $\Adv{ind-\id{atk}}{\mathcal{E}}(A) = 175 \Adv{sem-\id{atk}}{\mathcal{E}}(A').$%
177 Now we show that $\text{SEM-\id{atk}} \implies \text{IND-\id{atk}}$.
178 Suppose that $A$ attacks $\mathcal{E}$ in the indistinguishability sense.
179 Then consider the adversary $A'$ attacking its semantic security:
180 \begin{program}
181 Adversary $A'^{D(\cdot)}(\cookie{select}, P)$: \+ \\
182 $(x'_0, x'_1, s) \gets A^{D(\cdot)}(\cookie{find}, P)$; \\
183 $\mathcal{M} \gets 184 \{ x'_0 \mapsto \frac{1}{2}, x'_1 \mapsto \frac{1}{2} \}$; \\
185 \RETURN $(x'_0, x'_1, s')$;
186 \next
187 Adversary $A'^{D(\cdot)}(\cookie{predict}, y, s')$: \+ \\
188 $(x'_0, x'_1, s) \gets s'$; \\
189 $b \gets A^{D(\cdot)}(\cookie{guess}, y, s)$; \\
190 \RETURN $(\lambda x.x, x'_b)$;
191 \end{program}
192 Here $A'$ is simply running the indistinguishability experiment. In the
193 $\cookie{select}$ stage, it runs $A$'s $\cookie{find}$ stage, and returns
194 the uniform distribution over $A$'s two chosen plaintexts. In the
195 $\cookie{predict}$ stage, $A'$ collects $A$'s $\cookie{guess}$ and returns
196 the identity function $\lambda x.x$ and the guessed plaintext.
198 In the case of experiment $\Expt{sem-\id{atk}-$1$}{\mathcal{E}}(A')$, the
199 rules are fair, and we win with probability
200 $p = \frac{1}{2} + \frac{\Adv{ind-\id{atk}}{\mathcal{E}}(A)}{2}.$
201 In the case of $\Expt{sem-\id{atk}-$0$}{\mathcal{E}}(A')$, however, we
202 \emph{lose} in the event that $x_0 = x'_b$. This happens if \emph{either}
203 $x_0 = x_1$ and we guess correctly (probability $p/2$), \emph{or} if $x_0 204 \ne x_1$ and we guess incorrectly (probability $(1 - p)/2$). Hence, we see
205 that have
206 $\Adv{sem-\id{atk}}{\mathcal{E}}(A') = 207 \frac{1}{2} \Adv{ind-\id{atk}}{\mathcal{E}}(A)$%
208 completing the proof.
209 \end{proof}
211 \xcalways\subsection{Non-malleability}\x
213 \begin{slide}
214 \topic{definition}
217 The intuition behind non-malleability is that an adversary can't easily
218 take some ciphertext and turn it into some other ciphertext such that the
219 plaintexts have a simple relationship to each other.
221 Here's a relatively standard definition of non-malleability, from
222 \cite{Bellare:1998:RAN, Bellare:1999:NEE}:
223 \begin{program}
224 Experiment $\Expt{cnm-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
225 $(P, K) \gets G$; \\
226 $(\mathcal{M}, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$;
227 $x_0 \getsr \mathcal{M}$; $x_1 \getsr \mathcal{M}$;
228 $y \gets E_P(x_1)$; \\
229 $(R, \vect{y}) \gets A^{D_1(\cdot)}(\cookie{guess}, y, s)$;
230 $\vect{x} \gets D_K(\vect{y})$; \\
231 \IF $y \notin \vect{y} \land 232 R(x_b, \vect{x})$ \THEN \RETURN $1$;
233 \ELSE \RETURN $0$;
234 \end{program}
235 In the above, $\mathcal{M}$ is a valid distribution on plaintexts, and $R$
236 is an $n$-ary relation on plaintexts. The adversary's advantage is
237 $\Adv{cnm-\id{atk}}{\mathcal{E}}(A) = 238 \Pr[\Expt{cnm-\id{atk}-1}{\mathcal{E}}(A) = 1] - 239 \Pr[\Expt{cnm-\id{atk}-0}{\mathcal{E}}(A) = 1].$%
240 \end{slide}
242 \begin{slide}
243 \topic{more good news}
246 The previous definition involved all sorts of nasties like distributions
247 and relations. Fortunately, there's an approximately equivalent notion,
248 based on indistinguishability with a single \emph{parallel}
249 chosen-ciphertext query:
250 \begin{program}
251 Experiment $\Expt{nm-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
252 $(P, K) \gets G$; \\
253 $(x_0, x_1, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$;
254 $y \gets E_P(x_b)$; \\
255 $(\vect{y}, t) \gets A^{D_1(\cdot)}(\cookie{choose}, y, s)$;
256 \IF $y \in \vect{y}$ \THEN \RETURN $0$; \\
257 $\vect{x} \gets D_K(\vect{y})$;
258 $b \gets A^{D_1(\cdot)}(\cookie{guess}, \vect{x}, t)$;
259 \RETURN $b$;
260 \end{program}
262 $\Adv{nm-\id{atk}}{\mathcal{E}}(A) = 263 \Pr[\Expt{nm-\id{atk}-1}{\mathcal{E}}(A) = 1] - 264 \Pr[\Expt{nm-\id{atk}-0}{\mathcal{E}}(A) = 1].$%
265 \end{slide}
267 \begin{proof}
268 Firstly, $\text{NM} \implies \text{CNM}$. Suppose $A'$ attacks
269 $\mathcal{E}$ in the CNM sense. Then we construct $A$ in the obvious way:
270 \begin{program}
271 Adversary $A^{D(\cdot)}(\cookie{find}, P)$: \+ \\
272 $(\mathcal{M}, s') \gets A'^{D(\cdot)}(\cookie{find}, P)$; \\
273 $x_0 \getsr \mathcal{M}$; $x_1 \getsr \mathcal{M}$; \\
274 \RETURN $(x_0, x_1, (x_1, s'))$;
275 \next
276 Adversary $A^{D(\cdot)}(\cookie{choose}, y, s)$: \+ \\
277 $(x_1, s') \gets s$; \\
278 $(R, \vect{y}) \gets A'^{D(\cdot)}(\cookie{guess}, y, s')$; \\
279 \RETURN $(\vect{y}, (x_1, R))$;
280 \next
281 Adversary $A^{D(\cdot)}(\cookie{guess}, \vect{x}, s)$: \+ \\
282 $(x_1, R) \gets s$; \\
283 \IF $R(x_1, \vect{x})$ \THEN \RETURN $1$; \\
284 \ELSE \RETURN $0$;
285 \end{program}
286 Studying the behaviour of $A$, we see that it succeeds precisely when $A'$
287 succeeds. Hence
288 $\Adv{nm-\id{atk}}{\mathcal{E}}(A) = 289 \Adv{cnm-\id{atk}}{\mathcal{E}}(A').$%
291 Secondly, suppose that $A$ attacks $\mathcal{E}$ in the NM sense. Then we
292 construct $A'$ in a somewhat tricky manner: $A'$ aims to run the final
293 stage of $A$ from its relation $R$.
295 We can suppose, without loss of generality, that $A$ doesn't require its
296 chosen ciphertext oracle $D$ during its final $\cookie{guess}$ phase. If
297 it is allowed an adaptive chosen ciphertext oracle, it can make its
298 parallel query through $D$ (admittedly at the cost of $|\vect{y}|$
299 additional decryption queries). Hence, we don't need to provide
300 $A(\cookie{guess})$ with a decryption oracle.
302 The relation isn't allowed to be probabilistic. Hence, we choose the coins
303 $\rho \in \{0, 1\}^n$ that $A(\cookie{guess})$ requires in advance. Since
304 $A$'s running time is bounded, $n$ must also be bounded. We encode the
305 values $(x'_0, x'_1, t, \rho)$ into the description of $R$ output by
306 $A'(\cookie{guess})$.
308 \begin{program}
309 Adversary $A'^{D(\cdot)}(\cookie{find}, P)$: \+ \\
310 $(x'_0, x'_1, s) \gets A^{D(\cdot)}(\cookie{find}, P)$; \\
311 $\mathcal{M} \gets 312 \{ x'_0 \mapsto \frac{1}{2}, x'_1 \mapsto \frac{1}{2} \}$; \\
313 \RETURN $(\mathcal{M}, (x'_0, x'_1, P, s))$;
314 \next
315 Adversary $A'^{D(\cdot)}(\cookie{guess}, y, s')$: \+ \\
316 $(x'_0, x'_1, P, s) \gets s'$; \\
317 $(\vect{y}, t) \gets A^{D(\cdot)}(\cookie{choose}, y, s)$; \\
318 $\rho \getsr \{0, 1\}^n$; \\
319 \RETURN $(R, \vect{y})$; \- \$\smallskipamount] 320 Relation R(x, \vect{x}): \+ \\ 321 b' \gets A(\cookie{guess}, \vect{x}, t) (with coins \rho); \\ 322 \IF x = x'_{b'} \THEN \RETURN 1; \\ 323 \ELSE \RETURN 0; 324 \end{program} 326 The analysis of A''s success probability is very similar to the proof 327 that \text{SEM} \implies \text{IND} above. When the CNM experiment's 328 hidden bit b = 1, A' succeeds whenever A correctly guesses which 329 plaintext was encrypted, which occurs with probability 330 \[ p = \frac{1}{2} + \frac{\Adv{nm-\id{atk}}{\mathcal{E}}(A)}{2}.$
331 When $b = 0$, $A'$ fails when $A$ guesses correctly and $x_0 = x_1$
332 (probability $p/2$), or when $A$ guesses wrongly and $x_0 \ne x_1$
333 (probability $(1 - p)/2$). Hence, finally,
334 $\Adv{cnm-\id{atk}}{\mathcal{E}}(A) = 335 \frac{\Adv{nm-\id{atk}}{\mathcal{E}}(A)}{2}.$%
337 For any arbitrary resource bounds $R$, we have
338 $\InSec{cnm-\id{atk}}(\mathcal{E}; R) \le 339 \InSec{nm-\id{atk}}(\mathcal{E}; R) \le 340 2 \cdot \InSec{cnm-\id{atk}}(\mathcal{E}; R'),$%
341 where $R'$ is related to $R$, but may need to allow additional decryption
342 queries, to cope with NM-CCA2 adversaries which use decryption queries in
343 their final $\cookie{guess}$ stages.
345 We conclude that the two notions are almost equivalent, as claimed.
346 \end{proof}
348 \xcalways\subsection{Relations between security notions}\x
350 \begin{slide}
351 \head{Relations between security notions \cite{Bellare:1998:RAN}}
353 %% 3 3
354 %% NM-CPA <--------- NM-CCA1 <--------- NM-CCA2
355 %% | \__ | \__ ^ ^
356 %% | \__ 6 | \__ 7 | |
357 %% 1| \/_ |1 \/_ 4| |1
358 %% | 5/ \__ | / \_ | |
359 %% v __\ v __\ v |
360 %% IND-CPA <-------- IND-CCA1 <------- IND-CCA2
361 %% 2 2
363 $\xymatrix @=2cm { 364 \txt{NM-CPA} \ar[d]_1 365 \POS !<1ex, 0pt> \ar[dr]!<1ex, 0pt>|-@{/}^6 & 366 \txt{NM-CCA1} \ar[d]^1 \ar[l]_3 \ar[dr]|-@{/}^7 & 367 \txt{NM-CCA2} \ar[l]_3 \ar@<0.5ex>[d]^1 \\ 368 \txt{IND-CPA} & 369 \txt{IND-CCA1} \ar[l]^2 370 \POS !<-1ex, 0pt> \ar[ul]!<-1ex, 0pt>|-@{/}^5 & 371 \txt{IND-CCA2} \ar[l]^2 \ar@<0.5ex>[u]^4 \\ 372 }$
374 \begin{list}{}{
375 \settowidth{\labelwidth}{\textbf{Key}}
377 \itemindent0pt\let\makelabel\textbf}
378 \item[Key] \begin{itemize}
379 \item An arrow $\xy\ar*+{A};<1.5cm, 0cm>*+{B}\endxy$ indicates an
380 \emph{implication}: if a scheme is secure in notion $A$ then it is also
381 secure in notion $B$.
382 \item A crossed arrow $\xy\ar|-@{/}*+{A};<1.5cm, 0cm>*+{B}\endxy$
383 indicates a \emph{separation}: there exists a scheme secure in notion
384 $A$ but not in $B$.
385 \item The numbers refer to sections of the proof provided in the notes.
386 \end{itemize}
387 \end{list}
388 \end{slide}
390 \begin{proof}
391 Most of these are fairly simple. We use the indistinguishability-based
392 characterization of non-malleability that we showed earlier, because it
393 makes life much easier. We assume that schemes meeting each of the
394 definitions exist, else the theorems are all vacuously true.
396 \begin{enumerate}
398 \item We show $\text{NM-\id{atk}} \implies \text{IND-\id{atk}}$ for
399 $\id{atk} \in \{\text{CPA}, \text{CCA1}, \text{CCA2}\}$. Let $[]$ denote
400 the empty vector. Suppose that $A$ attacks $\mathcal{E}$ in the
401 $\text{IND-\id{atk}}$ sense.
402 \begin{program}
403 Adversary $A'^{D(\cdot)}(\cookie{find}, P)$: \+ \\
404 $(x_0, x_1, s) \gets A^{D(\cdot)}(\cookie{find}, P)$; \\
405 \RETURN $(x_0, x_1, s)$;
406 \newline
407 Adversary $A'^{D(\cdot)}(\cookie{choose}, y, s)$: \+ \\
408 \RETURN $([], (y, s))$;
409 \next
410 Adversary $A'^{D(\cdot)}(\cookie{guess}, \vect{x}, s')$: \+ \\
411 $(y, s) \gets s'$; \\
412 $b' \gets A^{D(\cdot)}(y, s)$; \\
413 \RETURN $b'$;
414 \end{program}
415 Evidently $\Adv{nm-\id{atk}}{\mathcal{E}}(A') = 416 \Adv{ind-\id{atk}}{\mathcal{E}}(A)$, and hence
417 $\InSec{ind-\id{atk}}(\mathcal{E}; t, q_D) \le 418 \InSec{nm-\id{atk}}(\mathcal{E}; t, q_D),$%
419 proving the implication.
421 \item We show that $\text{IND-$\id{atk}'$} \implies \text{IND-\id{atk}}$
422 for $(\id{atk}', \id{atk}) \in \{(\text{CCA1}, \text{CPA}), (\text{CCA2}, 423 \text{CCA1})\}$. Suppose that $A$ attacks $\mathcal{E}$ in the
424 $\text{IND-\id{atk}}$ sense.
425 \begin{program}
426 Adversary $A'^{D(\cdot)}(\cookie{find}, P)$: \+ \\
427 $(x_0, x_1, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$; \\
428 \RETURN $(x_0, x_1, s)$;
429 \next
430 Adversary $A'^{D(\cdot)}(\cookie{guess}, y, s)$: \+ \\
431 $b' \gets A^{D_1(\cdot)}(\cookie{guess}, y, s)$; \\
432 \RETURN $b'$;
433 \end{program}
434 The oracles $D_0$ and $D_1$ are defined according to \id{atk}, as
435 shown in table~\ref{tab:se-rel-oracle}.
436 \begin{table}
437 \begin{tabular}[C]{l Mc Mc} \hlx*{hv}
438 \id{atk} & D_0(x) & D_1(x) \\ \hlx{vhv}
439 CPA & \bot & \bot \\
440 CCA1 & D(x) & \bot \\ \hlx*{vh}
441 \end{tabular}
442 \caption{Relations between notions of security for public key
443 encryption: decryption oracles}
444 \label{tab:se-rel-oracle}
445 \end{table}
446 Evidently $\Adv{ind-$\id{atk}'$}{\mathcal{E}}(A') = 447 \Adv{ind-\id{atk}}{\mathcal{E}}(A)$, and hence
448 $\InSec{ind-\id{atk}}(\mathcal{E}; t, q_D) \le 449 \InSec{ind-\id{atk}'}(\mathcal{E}; t, q_D),$%
450 proving the implication.
452 \item We show that $\text{NM-$\id{atk}'$} \implies \text{NM-\id{atk}}$
453 for $(\id{atk}', \id{atk}) \in \{(\text{CCA1}, \text{CPA}), (\text{CCA2}, 454 \text{CCA1})\}$. Suppose that $A$ attacks $\mathcal{E}$ in the
455 $\text{NM-\id{atk}}$ sense.
456 \begin{program}
457 Adversary $A'^{D(\cdot)}(\cookie{find}, P)$: \+ \\
458 $(x_0, x_1, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$; \\
459 \RETURN $(x_0, x_1, s)$;
460 \newline
461 Adversary $A'^{D(\cdot)}(\cookie{choose}, y, s)$: \+ \\
462 $(\vect{y}, t) \gets A^{D_1(\cdot)}(\cookie{choose}, y, s)$; \\
463 \RETURN $(\vect{y}, t)$;
464 \next
465 Adversary $A'^{D(\cdot)}(\cookie{guess}, \vect{x}, t)$: \+ \\
466 $b' \gets A^{D_1(\cdot)}(\cookie{guess}, \vect{x}, t)$; \\
467 \RETURN $b'$;
468 \end{program}
469 The oracles $D_0$ and $D_1$ are defined according to $\id{atk}'$, as
470 shown in table~\ref{tab:se-rel-oracle}. Evidently
471 $\Adv{nm-$\id{atk}'$}{\mathcal{E}}(A') = 472 \Adv{nm-\id{atk}}{\mathcal{E}}(A)$, and hence
473 $\InSec{nm-\id{atk}}(\mathcal{E}; t, q_D) \le 474 \InSec{nm-\id{atk}'}(\mathcal{E}; t, q_D),$%
475 proving the implication.
477 \item We show that $\text{IND-CCA2} \implies \text{NM-CCA2}$. Suppose that
478 $A$ is an adversary attacking $\mathcal{E}$ in the NM-CCA2 sense.
479 \begin{program}
480 Adversary $A'^{D(\cdot)}(\cookie{find}, P)$: \+ \\
481 $(x_0, x_1, s) \gets A^{D_0(\cdot)}(\cookie{find}, P)$; \\
482 \RETURN $(x_0, x_1, s)$;
483 \next
484 Adversary $A'^{D(\cdot)}(\cookie{guess}, y, s)$: \+ \\
485 $(\vect{y}, t) \gets A^{D(\cdot)}(\cookie{choose}, y, s)$; \\
486 $\vect{x} = D(\vect{y})$; \\
487 $b' \gets A^{D(\cdot)}(\cookie{guess}, \vect{x}, t)$; \\
488 \RETURN $b'$;
489 \end{program}
490 Evidently $\Adv{ind-cca2}{\mathcal{E}}(A') = 491 \Adv{nm-cca2}{\mathcal{E}}(A)$, and hence
492 $\InSec{nm-cca2}(\mathcal{E}; t, q_D) \le 493 \InSec{ind-cca2}(\mathcal{E}; t, q_D),$%
494 proving the implication.
496 \item We show that $\text{IND-CCA1} \not\implies \text{NM-CPA}$. Suppose
497 that $\mathcal{E} = (G, E, D)$ is secure in the IND-CCA1 sense. Consider
498 the encryption scheme $\mathcal{E}' = (G', E', D')$:
499 \begin{program}
500 Algorithm $G'(k)$: \+ \\
501 $(P, K) \gets G$; \\
502 \RETURN $(P, K)$;
503 \next
504 Algorithm $E'_P(x)$: \+ \\
505 $y \gets E_P(x)$; \\
506 \RETURN $(0, y)$;
507 \next
508 Algorithm $D'_K(y')$: \+ \\
509 $(b, y) \gets y'$; \\
510 $x \gets D_K(y)$; \\
511 \RETURN $x$;
512 \end{program}
513 This is a classic example of a malleable encryption scheme.
515 Firstly, we show that $\mathcal{E}'$ is still IND-CCA1. Suppose that
516 $A'$ is an adversary attacking $\mathcal{E}'$ in the sense of IND-CCA1.
517 Consider $A$, attacking $\mathcal{E}$:
518 \begin{program}
519 Adversary $A^{D(\cdot)}(\cookie{find}, P)$: \+ \\
520 $(x_0, x_1, s) \gets A'^{\Xid{D'}{sim}(\cdot)}(\cookie{find}, P)$; \\
521 \RETURN $(x_0, x_1, s)$; \- \$\smallskipamount] 522 Oracle \Xid{D'}{sim}(y'): \+ \\ 523 (b, y) \gets y'; \\ 524 x \gets D(y); \\ 525 \RETURN x; 526 \next 527 Adversary A^\bot(\cookie{guess}, y, s): \+ \\ 528 b' \gets A'^\bot(\cookie{guess}, y, s); \\ 529 \RETURN b'; 530 \end{program} 531 Clearly, A simulates the expected environment for A' perfectly; hence 532 \[ \Adv{ind-cca1}{\mathcal{E}'}(A') = \Adv{ind-cca1}{\mathcal{E}}(A).$
534 Now, we show that $\mathcal{E}'$ is not NM-CPA. Consider the adversary
535 $C'$:
536 \begin{program}
537 Adversary $C'^{D(\cdot)}(\cookie{find}, P')$: \+ \\
538 \RETURN $(0, 1, \bot)$;
539 \newline
540 Adversary $C'^{D(\cdot)}(\cookie{choose}, y', s)$: \+ \\
541 $(b, y) \gets y'$; \\
542 $\vect{y} \gets [(1, y)]$; \\
543 \RETURN $(\vect{y}, \bot)$;
544 \next
545 Adversary $C'^{D(\cdot)}(\cookie{guess}, \vect{x}, t)$: \+ \\
546 \RETURN $\vect{x}[0]$;
547 \end{program}
548 Since $(0, y) \ne (1, y)$, the experiment provides the plaintext
549 corresponding to the challenge ciphertext $y'$.
550 $\Adv{nm-cpa}{\mathcal{E}'}(C') = 1$. Hence, $\mathcal{E}'$ is insecure
551 in the NM-CPA sense.
553 \item We show that $\text{NM-CPA} \not\implies \text{IND-CCA1}$. Suppose
554 that $\mathcal{E} = (G, E, D)$ is secure in the NM-CPA sense. Fix a
555 security parameter $k$. Consider the encryption scheme $\mathcal{E}' = 556 (G', E', D')$:
557 \begin{program}
558 Algorithm $G'(k)$: \+ \\
559 $(P, K) \gets G(k)$; \\
560 $u \getsr \{0, 1\}^k$; $v \getsr \{0, 1\}^k$; \\
561 \RETURN $((P, u), (K, u, v))$;
562 \next
563 Algorithm $E'_{P'}(x)$: \+ \\
564 $(P, u) \gets P'$; \\
565 $y \gets E_P(x)$; \\
566 \RETURN $(0, y)$;
567 \next
568 Algorithm $D'_{K'}(y')$: \+ \\
569 $(b, y) \gets y'$; \\
570 $(K, u, v) \gets K'$; \\
571 \IF $b = 0$ \THEN $x \gets D_K(y)$; \\
572 \ELSE \IF $y = u$ \THEN $x \gets v$; \\
573 \ELSE \IF $y = v$ \THEN $x \gets K$; \\
574 \ELSE $x \gets \bot$; \\
575 \RETURN $x$;
576 \end{program}
577 The idea is that the decryption oracle can be used to leak the key by
578 following the little $u \to v \to K$ chain, but the parallel
579 non-malleability oracle can't do this.
581 We first show that $\mathcal{E}'$ is still NM-CPA. Suppose that $A'$ is
582 an adversary attacking $\mathcal{E}'$ in the NM-CPA sense. Consider
583 this adversary $A$:
584 \begin{program}
585 Adversary $A^\bot(\cookie{find}, P)$: \+ \\
586 $u \getsr \{0, 1\}^k$; $v \getsr \{0, 1\}^k$; \\
587 $(x_0, x_1, s') \gets A'^\bot(\cookie{find}, (P, u))$; \\
588 \RETURN $(x_0, x_1, (s', u, v))$;
589 \newline
590 Adversary $A^\bot(\cookie{choose}, y, s)$: \+ \\
591 $(s', u, v) \gets s$; \\
592 $(\vect{y}', t') \gets A'^\bot(\cookie{choose}, y, s')$; \\
593 \FOR $j = 0$ \TO $|\vect{y}'| - 1$ \DO
594 $\vect{x}'[j] \gets \bot$; \\
595 \FOR $j = 0$ \TO $|\vect{y}'| - 1$ \DO \\ \quad \= \+ \kill
596 $(b', y') \gets \vect{y}'[j]$; \\
597 \IF $b' = 0$ \THEN $\vect{y}[j] \gets y'$; \\
598 \ELSE \IF $y' = u$ \THEN \= $\vect{x}'[j] \gets v$; \\
599 \> $\vect{y}[j] \gets \bot$; \\
600 \ELSE \IF $y' = v$ \THEN \ABORT; \\
601 \ELSE \= $\vect{x}'[j] \gets \bot$; \\
602 \> $\vect{y}[j] \gets \bot$; \\
603 \RETURN $(\vect{y}, (\vect{x}', t'))$;
604 \next
605 Adversary $A^\bot(\cookie{guess}, \vect{x}, t)$: \+ \\
606 $(\vect{x}', t') \gets t$; \\
607 \FOR $j = 0$ \TO $|\vect{x}| - 1$ \DO \\
608 \quad \IF $\vect{x}'[j] = \bot$ \THEN
609 $\vect{x}'[j] \gets \vect{x}[j]$; \\
610 $b' \gets A'^\bot(\cookie{guess}, \vect{x}', t')$; \\
611 \RETURN $b'$;
612 \end{program}
613 Clearly, $A$ behaves indistinguishably from the NM-CPA experiment
614 expected by $A'$, unless $A$ aborts because $A'$ guesses $v$ during its
615 $\cookie{choose}$ phase. But $v$ is independent of $A'$'s view at that
616 moment, so the probability this occurs is $2^{-k}$. Hence
617 $\Adv{nm-cpa}{\mathcal{E}'} \le 618 \Adv{nm-cpa}{\mathcal{E}} + \frac{1}{2^k}.$%
620 Now to show that $\mathcal{E}'$ is insecure in the IND-CCA1 sense.
622 \begin{program}
623 Adversary $C'^{D(\cdot)}(\cookie{find}, P')$: \+ \\
624 $(P, u) \gets P'$; \\
625 $v \gets D(u)$; $K \gets D(v)$; \\
626 \RETURN $(0, 1, K)$;
627 \next
628 Adversary $C'^\bot(\cookie{guess}, y, K)$: \+ \\
629 $b' \gets D_K(y)$; \\
630 \RETURN $b'$;
631 \end{program}
632 The adversary $C'$ makes 2 decryption queries, and
633 $\Adv{ind-cca1}{\mathcal{E}'}(C') = 1$. Hence, $\mathcal{E}'$ is
634 insecure in the IND-CCA1 sense.
636 \item We show that $\text{NM-CCA1} \not\implies \text{IND-CCA2}$. Suppose
637 that $\mathcal{E} = (G, E, D)$ is secure in the NM-CCA1 sense. Let
638 $\mathcal{M} = (T, V)$ be a secure MAC. Consider the encryption scheme
639 $\mathcal{E}' = (G', E', D')$:
640 \begin{program}
641 Algorithm $G'(k)$: \+ \\
642 $(P, K) \gets G(k)$; \\
643 $i \getsr \keys \mathcal{M}$; \\
644 \RETURN $(P, (K, i))$;
645 \next
646 Algorithm $E'_P(x)$: \+ \\
647 $y \gets E_P(x)$; \\
648 \RETURN $(0, y, \bot)$;
649 \next
650 Algorithm $D'_{K'}(y')$: \+ \\
651 $(b, y, \tau) \gets y'$; \\
652 $(K, i) \gets K'$; \\
653 \IF $b = 0$ \THEN $x \gets D_K(y)$; \\
654 \ELSE \IF $\tau = \bot$ \THEN $x \gets T_i(y)$; \\
655 \ELSE \IF $V_i(y, \tau) = 1$ \THEN $x \gets D_K(y)$; \\
656 \ELSE $x \gets \bot$; \\
657 \RETURN $x$;
658 \end{program}
659 Answering decryption queries only when presented with a correct tag
660 ensures that the NM-CCA1 adversary can't obtain anything useful with its
661 queries (hence the scheme remains NM-CCA1-secure), but the IND-CCA2
662 adversary can use its adaptive queries to discover the required tag.
664 Firstly, we show that $\mathcal{E}'$ is still NM-CCA1-secure. Suppose
665 $A'$ attacks $\mathcal{E}'$ in the sense of NM-CCA1. Consider the two
666 adversaries shown in \ref{fig:nm-cca1-sep-ind-cca2}: $A$ attacks the
667 original $\mathcal{E}$; $A''$ attacks the MAC $\mathcal{M}$.
668 \begin{figure}
669 \begin{program}
670 Adversary $A^{D(\cdot)}(\cookie{find}, P)$: \+ \\
671 $i \getsr \keys F$; \\
672 $(x_0, x_1, s') \gets A'^{\Xid{D}{sim}(\cdot)}(\cookie{find}, P)$; \\
673 \RETURN $(x_0, x_1, (s', i))$; \- \$\smallskipamount] 674 Adversary A^\bot(\cookie{choose}, y, s): \+ \\ 675 (s', i) \gets s; \\ 676 (\vect{y}', t') \gets A'^\bot(\cookie{choose}, y, s'); \\ 677 \FOR j = 0 \TO |\vect{y}'| - 1 \DO 678 \vect{x}'[j] \gets \bot; \\ 679 \FOR j = 0 \TO |\vect{y}'| - 1 \DO \\ \quad \= \+ \kill 680 (b', y', \tau') \gets \vect{y}'[j]; \\ 681 \IF b' = 0 \THEN \vect{y}[j] \gets y'; \\ 682 \ELSE \IF z' = \bot \THEN \= \vect{x}'[j] \gets T_i(y'); \\ 683 \> \vect{y}[j] \gets \bot; \\ 684 \ELSE \IF V_i(y', \tau') \ne 1 685 \THEN \vect{y}[j] \gets \bot; \\ 686 \ELSE \IF y' = y \THEN \ABORT; \\ 687 \ELSE \vect{y}[j] \gets y'; \- \\ 688 \RETURN (\vect{y}, (\vect{x}', t')); \- \\[\smallskipamount] 689 Adversary A^\bot(\cookie{guess}, \vect{x}, t): \+ \\ 690 (\vect{x}', t') \gets t; \\ 691 \FOR j = 0 \TO |\vect{x}| - 1 \DO \\ 692 \quad \IF \vect{x}'[j] = \bot \THEN 693 \vect{x}'[j] \gets \vect{x}[j]; \\ 694 b' \gets A'^\bot(\cookie{guess}, \vect{x}', t'); \\ 695 \RETURN b'; 696 \next 697 Adversary A''^{T(\cdot), V(\cdot)}: \+ \\ 698 (P, K) \gets G; 699 b \getsr \{0, 1\}; \\ 700 (x_0, x_1, s) \gets A'^{\Xid{D}{sim}(\cdot)}(\cookie{find}, P); \\ 701 y \gets (0, E_P(x_b), \bot); \\ 702 (\vect{y}, t) \gets A'^\bot(\cookie{choose}, y, s); \\ 703 \FOR j = 0 \TO |\vect{y}| - 1 \DO \\ \quad \= \+ \kill 704 (b', y', \tau') \gets \vect{y}'[j]; \\ 705 \IF b' = 1 \land V(y', \tau') = 1 706 \THEN \RETURN (y', \tau'); \- \\ 707 \ABORT; \- \\[\smallskipamount] 708 Oracle \Xid{D}{sim}(y'): \+ \\ 709 (b, y, \tau) \gets y'; \\ 710 \IF b = 0 \THEN x \gets D_K(y); \\ 711 \ELSE \IF \tau = \bot \THEN x \gets T(y); \\ 712 \ELSE \IF V(y, \tau) = 1 \THEN x \gets D_K(y); \\ 713 \ELSE x \gets \bot; \\ 714 \RETURN x; 715 \end{program} 716 \caption{From the proof that \text{NM-CCA1} \not\implies 717 \text{IND-CCA2} -- adversaries A and A'', attacking \mathcal{E} 718 in the NM-CCA1 sense and the MAC \mathcal{M} respectively} 719 \label{fig:nm-cca1-sep-ind-cca2} 720 \end{figure} 722 Suppose, without loss of generality, that if the challenge ciphertext y 723 returned to A' matches one of A''s earlier decryption queries then 724 A' wins without making its parallel chosen ciphertext query. 726 Let B be the event that A aborts; let S be the event that A wins, 727 and let S' be the event that A' wins. Since unless it aborts, A 728 implements the NM-CCA1 game for \mathcal{E}' perfectly, we must have 729 \[ \Pr[A] = \Pr[A'] - \Pr[B].$
730 But $B$ is precisely the event in which $A''$ wins its game. Hence
731 $\Adv{nm-cca1}{\mathcal{E}'}(A') \le 732 \Adv{nm-cca1}{\mathcal{E}}(A) + \Adv{suf-cma}{\mathcal{E}}(A'')$%
733 proving the claim that $\mathcal{E}'$ remains NM-CCA1 secure.
735 Now to show that $\mathcal{E}'$ is not IND-CCA2 secure.
736 \begin{program}
737 Adversary $C'^{D(\cdot)}(\cookie{find}, P')$: \+ \\
738 \RETURN $(0, 1, \bot)$;
739 \next
740 Adversary $C'^{D(\cdot)}(\cookie{guess}, y, s)$: \+ \\
741 $\tau \gets D(1, y, \bot)$; \\
742 $b' \gets D(1, y, \tau)$; \\
743 \RETURN $b'$;
744 \end{program}
745 The adversary $C'$ makes 2 decryption queries, and
746 $\Adv{ind-cca2}{\mathcal{E}'}(C') = 1$. Hence, $\mathcal{E}'$ is
747 insecure in the IND-CCA2 sense.
749 \end{enumerate}
750 All present and correct.
751 \end{proof}
753 \begin{exercise}
754 In \cite{Goldwasser:1984:PE}, Shafi Goldwasser and Silvio Micali first
755 introduced the concept of semantic security as a definition of
756 \emph{computationally} secure encryption, and presented the first
757 provably-secure probabilistic encryption scheme. For this scheme, the
758 private key is a pair of $k$-bit primes $(p, q)$; the public key is their
759 product $n = pq$ and a \emph{pseudosquare} $z$. Given this starting point,
760 define a public-key encryption scheme, and relate its security in the
761 IND-CPA sense to the difficulty of the Quadratic Residuosity Problem. Show
762 that the encryption scheme is malleable.
764 Hints:
765 \begin{parenum}
766 \item Encrypt the message one bit at a time.
767 \item Choosing a random element of $(\Z/n\Z)^*$ and squaring gives you a
768 random element of $Q_n$.
769 \item You will need to define a formal game for the Quadratic Residuosity
770 Problem.
771 \end{parenum}
773 Encryption works as $\Xid{E}{GM}_{(n, z)}(x)$: \{ \FOREACH $1\colon x_i$
774 \FROM $x$ \DO \{ $a_i \getsr (\Z/n\Z)^*$; $\vect{y}[i] \gets a_i^2 775 z^{x_i}$~\} \RETURN $\vect{y}$;~\}. Decryption works as $\Xid{D}{GM}_{(p, 776 q)}(\vect{y})$: \{ $x \gets \emptystring$; \FOR $i = 0$ \TO $|\vect{y}| - 777 1$ \DO \{ \IF $\jacobi{\vect{y}[i]}{p} = 1 \land \jacobi{\vect{y}[i]}{q} = 778 1$ \THEN $x \gets x \cat 0$; \ELSE $x \gets x \cat 1$;~\} \RETURN $x$;~\}.
780 To prove that this is meets IND-CPA, let $A$ be an adversary attacking the
781 GM scheme. Now, we present an algorithm which, given an odd composite
782 integer $n$ and an element $z$ with $\jacobi{x}{n} = 1$, decides whether $x 783 \in Q_n$: Algorithm $B(n, z)$: $(x_0, x_1, s) \gets A(\cookie{find}, (n, 784 z))$; $b \getsr \{0, 1\}$; $y \gets \Xid{E}{GM}_{(n, z)}(x_b)$; $b' \gets 785 A(\cookie{guess}, y, s)$; \IF $b = b'$ \THEN \RETURN $0$; \ELSE \RETURN
786 $1$;~\}. If $z$ is a nonresidue, then $B$ returns $0$ whenever $A$
787 successfully guesses the right bit; if $z \in Q_n$ then the ciphertext $y$
788 returned by $B$ is a string of random quadratic residues independent of the
789 challenge plaintext, and $A$ can have no advantage. Hence
790 $\InSec{ind-cpa}(\Xid{\mathcal{E}}{GM-$k$}; t) \le 2 \cdot \InSec{qrp}(k; 791 t)$.
793 To prove malleability, simply note that multiplying an element
794 $\vect{y}[i]$ by $z$ toggles the corresponding plaintext bit.
795 \end{exercise}
797 \xcalways\subsection{The ElGamal scheme}\x
799 \begin{slide}
800 \topic{description}
801 \head{The ElGamal public-key encryption scheme}
803 ElGamal's encryption scheme is based on Diffie-Hellman. Let $G = \langle g 804 \rangle$ be a cyclic group of order $q$. Plaintexts and ciphertexts in the
805 scheme are elements of $G$.
807 The scheme $\Xid{\mathcal{E}}{ElGamal}^G = (\Xid{G}{ElGamal}^G, 808 \Xid{E}{ElGamal}^G, \Xid{D}{ElGamal}^G)$ is defined by:
809 \begin{program}
810 $\Xid{G}{ElGamal}^G$: \+ \\
811 $\alpha \getsr \{1, 2, \ldots, q - 1\}$; \\
812 \RETURN $(g^\alpha, \alpha)$;
813 \next
814 $\Xid{E}{ElGamal}^G_a(x)$: \+ \\
815 $\beta \getsr \{1, 2, \ldots, q - 1\}$; \\
816 \RETURN $(g^\beta, x a^\beta)$;
817 \next
818 $\Xid{D}{ElGamal}^G_\alpha(y)$: \+ \\
819 $(b, c) \gets y$; \\
820 $x \gets b^{-\alpha} c$; \\
821 \RETURN $x$;
822 \end{program}
823 This scheme is secure in the IND-CPA sense if the Decisional Diffie-Hellman
824 problem is hard in $G$.
825 \end{slide}
827 \begin{slide}
828 \topic{security proof}
831 Suppose $A$ is an adversary attacking the ElGamal scheme in the IND-CPA
832 sense. We construct from it an algorithm which solves the DDH problem
833 (i.e., given a triple $g^\alpha, g^\beta, c$, decides whether $c = 834 g^{\alpha\beta}$):
835 \begin{program}
836 Algorithm $D(a, b, c)$: \+ \\
837 $(x_0, x_1, s) \gets A(\cookie{find}, a)$; \\
838 $z \getsr \{0, 1\}$; \\
839 $y \gets (b, x_z c)$; \\
840 $z' \gets A(\cookie{guess}, y, s)$; \\
841 \IF $z = z'$ \THEN \RETURN $1$; \\
842 \ELSE \RETURN $0$;
843 \end{program}
844 \end{slide}
846 \begin{slide}
847 \head{Security proof for ElGamal (cont.)}
849 Let $\alpha$ and $\beta$ be the discrete logs of $a$ and $b$.
851 If $c = g^{\alpha\beta}$, then $D$'s success probability is equal to $A$'s
852 probability of guessing the hidden bit correctly, which is
853 $\frac{\Adv{ind-cpa}{\Xid{\mathcal{E}}{ElGamal}^G}(A)}{2} + \frac{1}{2}.$%
854 If $c$ is random, then $x_z c$ is uniformly distributed in $G$, and
855 independent of $b$, so $A$ answers correctly with probability exactly
856 $\frac{1}{2}$.
858 Hence, $\Adv{ddh}{G}(D) = 859 \Adv{ind-cpa}{\Xid{\mathcal{E}}{ElGamal}^G}(A)/2$, and
860 $\InSec{ind-cpa}(\Xid{\mathcal{E}}{ElGamal}^G; t) \le 861 2 \cdot \InSec{ddh}(G; t).$%
862 \end{slide}
864 \begin{slide}
865 \topic{other notes}
868 \begin{itemize}
870 \item We needed the Decisional Diffie-Hellman assumption to prove the
871 security. As noted before, this is a very strong assumption. Still, a
872 proof based on DDH is a lot better than nothing.
874 We really do need the Decisional Diffie-Hellman assumption. An adversary
875 with a DDH algorithm can submit $x_0 \inr G$ and $x_1 = 1$; it receives a
876 ciphertext $(b, y)$, and returns $1$ if $(a, b, y)$ looks like a
877 Diffie-Hellman triple, or $0$ if it looks random.
879 \item The plaintexts must be elements of the cyclic group $G$. For
880 example, if $G$ is a subgroup of $\F_p^*$, it's \emph{not} safe to allow
881 elements outside the subgroup as plaintexts: an adversary can compare
882 orders of ciphertext elements to break the semantic security of the
883 scheme.
885 \item ElGamal is malleable. We can decrypt a challenge ciphertext $y = 886 (g^\beta, a^\beta x)$ by choosing a random $\gamma$ and requesting a
887 decryption of $y' = (g^{\beta\gamma}, a^{\beta\gamma} x^\gamma)$.
889 \end{itemize}
890 \end{slide}
892 \xcalways\subsection{Encrypting using trapdoor one-way functions}\x
894 \begin{slide}
897 Trapdoor one-way functions RSA ($x \mapsto x^e \bmod n$) and Rabin ($x 898 \mapsto x^2 \bmod n$) functions are well-studied. Can we make secure
899 schemes from them?
901 We can't use them directly, however. For a start, the functions are
902 deterministic, so encrypting' messages just by doing the modular
903 exponentiation on the plaintext will leak equality of plaintexts.
905 How can we fix these schemes?
907 We'll focus on RSA, because decryption is simpler; Rabin works in a very
908 similar way.
909 \end{slide}
911 \begin{slide}
912 \topic{simple embedding schemes}
915 If we restrict our attention to plaintext messages which are about' the
916 input size of our one-way function, we'd like to be able to use ciphertexts
917 which are no bigger than the output size of the function.
919 Perhaps if we encode the message in some way before passing it through the
920 function, we can improve security. Ideally, we'd like security against
921 chosen-ciphertext attacks.
923 An encryption scheme which processes messages like this is called a
924 \emph{simple embedding scheme}.
925 \end{slide}
927 \begin{slide}
931 Let $n = p q$ be an RSA modulus, with $2^{8(k-1)} < n < 2^{8k)}$ -- i.e.,
932 $n$ is a $k$-byte number. Let $m$ be the message to be signed.
934 We compute $\hat{m} = 0^8 \cat T \cat r \cat 0^8 \cat x$ for
935 some hash function $m$, where:
936 \begin{itemize}
937 \item $|\hat{m}| = 8k$, i.e., $\hat{m}$ is a $k$-byte string;
938 \item $0^8$ is the string of 8 zero-bits;
939 \item $T = 00000002$ is an 8-bit \emph{type} code; and
940 \item $r$ is a string of random \emph{non-zero} bytes (\PKCS1 requires at
941 least 8 bytes)
942 \end{itemize}
943 This bit string is then converted into an integer, using a big-endian
944 representation. Note that $\hat{m} < n$, since its top byte is zero.
945 \end{slide}
947 \begin{slide}
950 Diagramatically, \PKCS1 encryption padding looks like this:
951 \begin{tabular}[C]{r|c|c|c|c|} \hlx{c{2-5}v}
952 \hex{00} & \hex{01} &
953 \ldots\ random nonzero bytes \ldots &
954 \hex{00} &
955 $m$
956 \\ \hlx{vc{2-5}}
957 \end{tabular}
959 Unfortunately, this scheme isn't capable of resisting chosen-ciphertext
960 attacks: Bleichenbacher \cite{Bleichenbacher:1998:CCA} shows how to decrypt
961 a ciphertext $y$ given an oracle (say, an SSL server) which returns whether
962 a given ciphertext is valid (i.e., its padding is correct).
963 \end{slide}
965 \begin{slide}
966 \topic{Optimal Asymmetric Encryption Padding (OAEP)}
969 OAEP is a simple embedding scheme for use with an arbitrary trapdoor
970 one-way function. It requires two hash functions, $H$ and $H'$, which we
971 model as random oracles.
973 We assume that our one-way function $f_P$ operates on $n$-bit strings. Fix
974 a security parameter $k$. We require two random oracles $G\colon \{0, 975 1\}^k \to \{0, 1\}^{n-k}$ and $H\colon \{0, 1\}^{n-k} \to \{0, 1\}^k$.
976 Given a message $x \in \{0, 1\}^{n-2k}$, we encrypt it as follows:
977 \begin{program}
978 Algorithm $\Xid{E}{OAEP}^{\mathcal{T}, G(\cdot), H(\cdot)}_P(x)$: \+ \\
979 $r \getsr \{0, 1\}^k$; \\
980 $s \gets (x \cat 0^k) \xor G(r)$; $t \gets r \xor H(s)$; \\
981 $w \gets s \cat t$; \\
982 \RETURN $f_P(w)$;
983 \next
984 Algorithm $\Xid{D}{OAEP}^{\mathcal{T}, G(\cdot), H(\cdot)}_K(y)$: \+ \\
985 $w \gets T_K(y)$; \\
986 \PARSE $w$ \AS $s, k\colon t$; \\
987 $r \gets t \xor H(s)$; $x' \gets s \xor G(r)$; \\
988 \PARSE $x'$ \AS $x, k\colon c$; \\
989 \IF $c = 0^k$ \THEN \RETURN $x$; \\
990 \ELSE \RETURN $\bot$;
991 \end{program}
992 \end{slide}
994 \begin{slide}
997 %% x <- {0, 1}^{n-2k} r <-R {0, 1}^k
998 %% | |
999 %% | |
1000 %% v |
1001 %% [||]<--- 0^k |
1002 %% | |
1003 %% | |
1004 %% v |
1005 %% (+)<-----------[G]--------------|
1006 %% | |
1007 %% | |
1008 %% | v
1009 %% |-------------[H]------------>(+)
1010 %% | |
1011 %% | |
1012 %% v v
1013 %% < s = (x || 0^k) (+) G(r) > < t = r (+) H(s) >
1015 \vfil
1016 $\begin{graph} 1017 []!{0; <1cm, 0cm>:} 1018 {x \in \{0, 1\}^n}="x" [rrrr] {r \inr \{0, 1\}^k}="r" 1019 "r" :[ddd] *{\xor}="h-xor" 1020 :[d] *++=(2, 0)[F:thicker]{\strut t = r \xor H(s)} 1021 "x" :[d] *{\ocat}="cat" 1022 [r] *+[r]{\mathstrut 0^k} :"cat" 1023 :[d] *{\xor}="g-xor" 1024 :[dd] *++=(4, 0)[F:thicker]{\strut s = (x \cat 0^k) \xor G(r)} 1025 [u] :[rr] *+[F]{H'} :"h-xor" 1026 "r" [dd] :[ll] *+[F]{H} :"g-xor" 1027 \end{graph}$
1028 \vfil
1029 \end{slide}
1031 \begin{slide}
1032 \head{Security of OAEP, 1: chosen plaintext attacks}
1034 We write the encryption scheme formed by using the trapdoor one-way
1035 function $\mathcal{T}$ with OAEP embedding as
1036 $\Xid{\mathcal{E}}{OAEP}^{\mathcal{T}}$.
1038 The security of OAEP in the IND-CPA sense is given by:
1039 $\InSec{ind-cpa}(\Xid{\mathcal{E}}{OAEP}^{\mathcal{T}}; t, q_G, q_H) 1040 \le 2 \left (\frac{q_G}{2^k} + 1041 \InSec{owf}(\mathcal{T}; t + O(q_G q_H)) \right).$%
1042 \end{slide}
1044 We omit the security proof of OAEP, because it's very similar to the proof
1045 for OAEP+ which is presented in full later.
1047 \begin{slide}
1048 \topic{possible malleability of OAEP}
1049 \head{OAEP is not (generically) non-malleable \cite{Shoup:2001:OAEPR}}
1051 If a one-way function might be \emph{XOR-malleable} -- i.e., given $f_P(x)$
1052 and $\delta$, it's possible to construct $f_P(x \xor \delta)$ without
1053 knowledge of the trapdoor -- then the OAEP encryption scheme is malleable.
1055 \begin{graph}
1056 []!{0; <1cm, 0cm>:}
1057 *!UR{\parbox{0.5\linewidth}{
1058 \raggedright
1059 We need to suppose, in addition, that the function leaks the leftmost
1060 $n-k$ bits of its input; e.g., $f(s \cat t) = s \cat f'(t)$. Then
1061 exploiting the differential (pictured right) only requires a pair of
1062 queries to the $H$ oracle, not $G$. Using its parallel
1063 chosen-ciphertext query, the adversary can decrypt its target
1064 plaintext.
1065 }}
1066 !{+(1.5, 0)}
1067 {x}="x" [rr] {r}="r"
1068 "r" :[ddd] *{\xor}="h-xor" ^{0}
1069 :[d] {t}^{H(s) \xor H(s \xor (\delta \cat 0^k))}
1070 "x" :[d] *{\ocat}="cat" _{\delta}
1071 [r] *+[r]{\mathstrut 0^k} :"cat"
1072 :[d] *{\xor}="g-xor" _{\delta \cat 0^k}
1073 :[dd] {s}_{\delta \cat 0^k}
1074 [u] :[r] *+[F]{H'} :"h-xor"
1075 "r" [dd] :[l] *+[F]{H} :"g-xor"
1076 \end{graph}
1078 Nevertheless, OAEP \emph{does} provide security against chosen-ciphertext
1079 attacks when used with the RSA and Rabin functions.
1080 \end{slide}
1082 \xcalways\subsection{Plaintext awareness and OAEP+}\x
1084 \begin{slide}
1087 The intuitive idea behind plaintext awareness is that it's hard to
1088 construct a new ciphertext for which you can't easily guess the plaintext
1089 (or guess that the ciphertext is invalid). Obviously, such an idea would
1090 imply security against chosen ciphertext attack -- since the adversary
1091 effectively knows the plaintext anyway, the decryption oracle is useless.
1093 The formalization introduces a \emph{plaintext extractor} -- an algorithm
1094 which, given a ciphertext and the random oracle queries of the program
1095 which created it, returns the corresponding plaintext.
1097 Note, then, that plaintext awareness (as currently defined) only works in
1098 the random oracle model.
1099 \end{slide}
1101 \begin{slide}
1102 \topic{definition of plaintext awareness}
1103 \head{Definition of plaintext awareness \cite{Bellare:1998:RAN}}
1105 Let $\mathcal{E} = (G, E, D)$ be a public-key encryption scheme. Consider
1106 an adversary $A$ which takes a public key as input and returns a ciphertext
1107 $y$. We run the adversary, providing it with an \emph{encryption} oracle,
1108 and record
1109 \begin{itemize}
1110 \item the set $Q_H$, which contains a pair $(q, h)$ for each random oracle
1111 query $q$ made by the adversary, together with its reply $h$; and
1112 \item the set $C$, which contains the responses (only: not the queries)
1113 from $A$'s encryption oracle.
1114 \end{itemize}
1115 We write $(y, Q_H, C) \gets \id{transcript}(A; z)$ to denote running $A$ on
1116 the arguments $z$ and collecting this information.
1118 Note that $Q_H$ doesn't include the oracle queries required by the
1119 encryption oracle.
1120 \end{slide}
1122 \begin{slide}
1123 \head{Definition of plaintext awareness (cont.)}
1125 An \emph{$\epsilon$-plaintext extractor} for $\mathcal{E}$ is an algorithm
1126 $X$ for which
1127 \begin{eqnarray*}[rl]
1128 \min_A \Pr[
1129 &
1130 (P, K) \gets G;
1131 (y, Q_H, C) \gets \id{transcript}(A^{E(\cdot), H(\cdot)}; P); \\
1132 & x \gets X(y, P, Q_H, C) : x = D_K(y)] \ge 1 - \epsilon .
1133 \end{eqnarray*}
1135 The scheme $\mathcal{E}$ is \emph{$\epsilon$-plaintext aware} (PA) if there
1136 exists an $\epsilon$-plaintext extractor for $\mathcal{E}$ \emph{and}
1137 $\mathcal{E}$ is IND-CPA.
1139 (The requirement that the scheme meet IND-CPA prevents trivial schemes such
1140 as the identity function from being considered plaintext aware.)
1141 \end{slide}
1143 \begin{slide}
1144 \topic{chosen-ciphertext security}
1145 \head{Plaintext awareness and chosen-ciphertext security
1146 \cite{Bellare:1998:RAN}}
1148 If a public key encryption scheme $\mathcal{E}$ is PA, then it is also
1149 IND-CCA2 (and hence NM-CCA2). This is proven using the plaintext extractor
1150 to simulate the decryption oracle. The encryption oracle in the PA
1151 definition is used to feed the challenge ciphertext to the plaintext
1152 extractor.
1154 Quantatively, if $\mathcal{E}$ is $\epsilon$-plaintext aware, and the
1155 plaintext extractor runs in time $t_X(q_H)$, then
1156 $\InSec{ind-cca2}(\mathcal{E}; t, q_D, q_H) \le 1157 \InSec{ind-cpa}(\mathcal{E}; t + q_D t_X(q_H), q_H) + q_D \epsilon.$%
1159 The converse is not true: IND-CCA2 does not imply plaintext awareness.
1160 \end{slide}
1162 \begin{proof}
1163 Firstly, we prove that $\text{PA} \implies \text{IND-CCA2}$. Let
1164 $\mathcal{E} = (G, E, D)$ be an $\epsilon$-plaintext aware public-key
1165 encryption scheme. Suppose $A'$ is an adversary attacking $\mathcal{E}$ in
1166 the IND-CCA2 sense. Let $X$ be the $\epsilon$-plaintext extractor for
1167 $\mathcal{E}$. We construct an adversary attacking $\mathcal{E}$ in the
1168 IND-CPA sense.
1169 \begin{program}
1170 Adversary $A^{H(\cdot)}(\cookie{find}, P)$: \+ \\
1171 $\Xid{H}{map} \gets \emptyset$; $y^* \gets \bot$; \\
1172 $(x_0, x_1, s') \gets A'^{\Xid{D}{sim}(\cdot), \Xid{H}{sim}(\cdot)} 1173 (\cookie{find}, P)$; \\
1174 \RETURN $(x_0, x_1, (\Xid{H}{map}, P, s')$; \- \$\smallskipamount] 1175 Oracle \Xid{H}{sim}(x): \+ \\ 1176 h \gets H(x); \\ 1177 \Xid{H}{map} \gets \Xid{H}{map} \cup \{ x \mapsto h \}; \\ 1178 \RETURN h; 1179 \next 1180 Adversary A^{H(\cdot)}(\cookie{guess}, y^*, s): \+ \\ 1181 (\Xid{H}{map}, P, s') \gets s; \\ 1182 b \gets A'^{\Xid{D}{sim}(\cdot), \Xid{H}{sim}(\cdot)} 1183 (\cookie{guess}, y^*, s'); \\ 1184 \RETURN b; \- \\[\smallskipamount] 1185 Oracle \Xid{D}{sim}(y): \+ \\ 1186 x \gets X(y, P, \Xid{H}{map}, \{ y^* \}); \\ 1187 \RETURN x; 1188 \end{program} 1189 Let q_D be the number of decryption queries made by the adversary. We 1190 can see that, if the plaintext extractor does its job correctly, A 1191 simulates the decryption oracle for A' correctly. Hence 1192 \[ \Adv{ind-cpa}{\mathcal{E}}(A) \ge 1193 \Adv{ind-cca2}{\mathcal{E}}(A') - q_D \epsilon.$%
1194 Notice how the encryption oracle from the plaintext awareness definition is
1195 used in the proof.
1197 We can show that $\text{IND-CCA2} \not\implies \text{PA}$ easily enough by
1198 amending an existing IND-CCA2 scheme $\mathcal{E}$ so that it has a
1199 magical' ciphertext, attached to the public key. Here is our modified
1200 scheme $\mathcal{E}' = (G', E', D')$:
1201 \begin{program}
1202 Algorithm $G'^{H(\cdot)}(k)$: \+ \\
1203 $(P, K) \gets G^{H(\cdot)}$; \\
1204 $p \getsr \dom E^{H(\cdot)}_P$; \\
1205 $c \getsr \ran E^{H(\cdot)}_P$; \\
1206 \RETURN $((P, c), (K, c, p))$;
1207 \next
1208 Algorithm $E'^{H(\cdot)}_{P, c}(x)$: \+ \\
1209 $y \gets E^{H(\cdot)}_P(x)$; \\
1210 \RETURN $y$;
1211 \next
1212 Algorithm $D'^{H(\cdot)}_{K, c, p}(y)$: \+ \\
1213 \IF $y = c$ \THEN $x \gets p$; \\
1214 \ELSE $x \gets D^{H(\cdot)}_K(y)$; \\
1215 \RETURN $x$;
1216 \end{program}
1217 Firstly, we show that it still meets IND-CCA2. Let $A'$ be an adversary
1218 attacking $\mathcal{E}'$ in the IND-CCA2 sense. Then $A$, below, acheives
1219 the same advantage against $\mathcal{E}$.
1220 \begin{program}
1221 Adversary $A^{D(\cdot), H(\cdot)}(\cookie{find}, P)$: \+ \\
1222 $p \getsr \dom E^{H(\cdot)}_P$; $c \getsr \ran E^{H(\cdot)}_P$; \\
1223 $(x_0, x_1, s') \gets A'^{\Xid{D}{sim}(\cdot), H(\cdot)} 1224 (\cookie{find}, (P, c))$; \\
1225 \RETURN $(x_0, x_1, (p, c, s')$;
1226 \next
1227 Adversary $A^{D(\cdot), H(\cdot)}(\cookie{guess}, y, s)$: \+ \\
1228 $(p, c, s') \gets s$; \\
1229 $b \gets A'^{\Xid{D}{sim}(\cdot), H(\cdot)}(\cookie{guess}, y, s')$; \\
1230 \RETURN $y$;
1231 \newline
1232 Oracle $\Xid{D}{sim}(y)$: \+ \\
1233 \IF $y = c$ \THEN $x \gets p$; \\
1234 \ELSE $x \gets D(y)$; \\
1235 \RETURN $x$;
1236 \end{program}
1238 Now to show that $\mathcal{E}'$ is not plaintext-aware. Suppose that it
1239 is, and there is a plaintext extractor $X$. We show that $\mathcal{E}$ is
1240 not IND-CPA (contradicting the earlier assumption that $\mathcal{E}$ was
1241 IND-CCA2).
1242 \begin{program}
1243 Adversary $A''^{H(\cdot)}(\cookie{find}, P)$: \+ \\
1244 $x_0 \getsr \dom E_P$; $x_1 \getsr \dom E_P$; \\
1245 \RETURN $(x_0, x_1, (P, x_1))$;
1246 \next
1247 Adversary $A''^{H(\cdot)}(\cookie{guess}, y, s)$: \+ \\
1248 $(P, x_1) \gets s$; \\
1249 $x \gets X(y, (P, y), \emptyset, \emptyset)$; \\
1250 \IF $x = x_1$ \THEN \RETURN $1$;
1251 \ELSE \RETURN $0$;
1252 \end{program}
1253 Since $x_0$ and $x_1$ are uniform in $\dom E_P$, the transcript $(y, (P, 1254 y), \emptyset, \emptyset)$ passed to the extractor is distributed exactly
1255 as for the $\mathcal{E}'$ adversary which, given the public key $(P, c)$
1256 returns $c$; hence it succeeds with its usual probability $1 - \epsilon$.
1257 Then, $A''$'s advantage is
1258 $\Adv{ind-cpa}{\mathcal{E}}(A'') = 1259 1 - 2\epsilon - \frac{1}{|{\dom E_P}|}.$%
1260 This completes the proof.
1261 \end{proof}
1263 \begin{slide}
1264 \topic{old definition}
1265 \head{The old definition of plaintext awareness}
1267 An earlier definition of plaintext awareness omitted the encryption oracle
1268 provided to the adversary. The designers of OAEP proved that it met this
1269 definition of plaintext awareness and asserted, without proof, that this
1270 implied security against adaptive chosen-ciphertext attacks.
1272 The original definition of plaintext-awareness is sufficient to guarantee
1273 IND-CCA1 security, but it doesn't provide any sort of non-malleability.
1274 \end{slide}
1276 \begin{slide}
1277 \topic{OAEP+}
1278 \head{Plaintext-aware encryption: OAEP+ \cite{Shoup:2001:OAEPR}, 1}
1280 OAEP+ is a simple embedding scheme, very similar to OAEP, which acheives
1281 plaintext-awareness.
1283 We assume that our one-way function $f_P$ operates on $n$-bit strings. Fix
1284 a security parameter $k$. We require three random oracles $G\colon \{0, 1285 1\}^k \to \{0, 1\}^{n-2k}$, $H\colon \{0, 1\}^{n-k} \to \{0, 1\}^k$, and
1286 $H'\colon \{0, 1\}^{n-k} \to \{0, 1\}^k$.
1287 \begin{program}
1288 Algorithm $\Xid{E}{OAEP+} 1289 ^{\mathcal{T}, G(\cdot), H(\cdot), H'(\cdot)}_P(x)$: \+ \\
1290 $r \getsr \{0, 1\}^k$; \\
1291 $c \gets H'(x \cat r)$; \\
1292 $s \gets (x \xor G(r)) \cat c$; \\
1293 $t \gets r \xor H(s)$; \\
1294 $w \gets s \cat t$; \\
1295 \RETURN $f_P(w)$;
1296 \next
1297 Algorithm $\Xid{D}{OAEP+} 1298 ^{\mathcal{T}, G(\cdot), H(\cdot), H'(\cdot)}_K(y)$: \+ \\
1299 $w \gets T_K(y)$; \\
1300 \PARSE $w$ \AS $s, k\colon t$; \\
1301 $r \gets t \xor H(s)$; \\
1302 \PARSE $s$ \AS $s', k\colon c$; \\
1303 $x \gets s' \xor G(r)$; \\
1304 \IF $c = H'(x \cat r)$ \THEN \RETURN $x$; \\
1305 \ELSE \RETURN $\bot$;
1306 \end{program}
1307 \end{slide}
1309 \begin{slide}
1312 %% x <- {0, 1}^{n-2k} r <-R {0, 1}^k
1313 %% | |
1314 %% | |
1315 %% | |
1316 %% |-------->[H']<----------------|
1317 %% | | |
1318 %% | | |
1319 %% v | |
1320 %% (+)<-------------[G]<-----------|
1321 %% | | |
1322 %% | | |
1323 %% v | |
1324 %% [||]<-------' |
1325 %% | |
1326 %% | |
1327 %% | v
1328 %% |-------------->[H]---------->(+)
1329 %% | |
1330 %% | |
1331 %% v v
1332 %% < s = (x (+) G(r)) || H'(x || r) > < t = r (+) H(s) >
1334 \vfil
1335 $\begin{graph} 1336 []!{0; <1cm, 0cm>:} 1337 {x \in \{0, 1\}^n}="x" [rrrr] {r \inr \{0, 1\}^k}="r" 1338 "x" [d] :[r] *+[F]{H'}="h'" "r" [d] :"h'" 1339 "r" :[dddd] *{\xor}="h-xor" 1340 :[d] *++=(2, 0)[F:thicker]{\strut t = r \xor H(s)} 1341 "x" :[dd] *{\xor}="g-xor" 1342 :[d] *{\ocat}="cat" 1343 :[dd] *++=(4, 0)[F:thicker] 1344 {\strut s = (x \xor G(r)) \cat H'(x \cat r)} 1345 [u] :[rr] *+[F]{H} :"h-xor" 1346 "r" [dd] :[ll] *+[F]{G} :"g-xor" 1347 "h'" :'[d]*=<8pt>\cir<4pt>{r_l} d"cat" "cat" 1348 \end{graph}$
1349 \vfil
1350 \end{slide}
1352 \begin{slide}
1355 Let $\mathcal{T}$ be a trapdoor one-way function. Then the insecurity of
1356 the public-key encryption scheme $\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}$
1357 in the IND-CPA sense is given by
1358 $\InSec{ind-cpa}(\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}; 1359 t, q_G, q_H, q_{H'}) 1360 \le 1361 2 \left (\frac{q_G}{2^k} + 1362 \InSec{owf}(\mathcal{T}; t + O(q_G q_H)) \right).$%
1363 Also, $\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}$ is $(q_G + 1) 1364 2^{-k}$-plaintext aware, the plaintext extractor running time being
1365 $O(q_{H'} t_f)$, where $t_f$ is the time required to execute the one-way
1366 function $f$.
1368 Tying up the various results, then, we can derive that
1369 \begin{eqnarray*}[Ll]
1370 \InSec{ind-cca2}(\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}};
1371 t, q_D, q_G, q_H, q_{H'}) \\
1372 & \le
1373 \frac{(2 + q_D) (q_G + 1) - 2}{2^k} +
1374 2 \cdot \InSec{owf}(\mathcal{T}; t + O(q_G q_H + q_D q_{H'} t_f)).
1375 \end{eqnarray*}
1376 \end{slide}
1378 Before we move on to the OAEP+ security results, we state and prove the
1379 following lemma, due (I believe) to Victor Shoup.
1381 \begin{lemma}[Shoup]
1382 \label{lem:shoup}
1383 If $X$, $Y$ and $F$ are events, and
1384 $\Pr[X \land \lnot F] = \Pr[Y \land \lnot F]$
1385 then
1386 $|{\Pr[X]} - \Pr[Y]| \le \Pr[F].$
1387 \end{lemma}
1388 \begin{proof}
1389 We have:
1390 \begin{eqnarray*}[rll]
1391 \Pr[X] &= \Pr[X \land F] &+ \Pr[X \land \lnot F] \\
1392 \Pr[Y] &= \Pr[Y \land F] &+ \Pr[Y \land \lnot F]
1393 \end{eqnarray*}
1394 Subtracting gives
1395 $|{\Pr[X]} - \Pr[Y]| = |{\Pr[X \land F]} - \Pr[Y \land F]| \le \Pr[F]$
1396 as required.
1397 \end{proof}
1399 \begin{proof}[Proof of the main OAEP+ result]
1401 We assume throughout that, before querying its $H'$ oracle at $x \cat r$,
1402 the adversary has queried $G$ at $r$.
1404 First, we show that OAEP+ meets the IND-CPA notion. Suppose that $A$
1405 attacks the OAEP+ scheme in the IND-CPA sense. We shall play a series of
1406 games with the adversary, and vary the rules as we go along. The adversary
1407 remains the same throughout.
1409 At any point in a game, let $Q_G$ be the list of queries the adversary has
1410 made to the oracle $G$, let $Q_H$ be the queries made to $H$, and let
1411 $Q_{H'}$ be the queries made to $H'$.
1413 \paragraph{Game $\G0$}
1414 This is effectively the original attack game: the adversary chooses two
1415 plaintexts: one is chosen unformly at random, the adversary is given the
1416 ciphertext and asked to identify which plaintext was chosen. Label the
1417 selected plaintext $x^*$, and the target ciphertext $y^*$. Let $c^*$,
1418 $s^*$, $t^*$ and $w^*$ be the intermediate results of the OAEP+ padding, as
1419 described above. Let $S_0$ be the event that the adversary wins the game.
1420 Our objective is to bound the probabilty $\Pr[S_0] = 1421 (\Adv{ind-cpa}{\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}}(A) + 1)/2$.
1423 \paragraph{Game $\G1$}
1424 At the beginning of the game, we select at random:
1425 \begin{itemize}
1426 \item $s^* \inr \{0, 1\}^{n-k}$;
1427 \item $t^* \inr \{0, 1\}^k$; and
1428 \item $r^* \inr \{0, 1\}^k$.
1429 \end{itemize}
1430 We compute $w^* = s^* \cat t^*$ and $y^* = f_P(w^*)$. Note, then, that
1431 \emph{$y^*$ is fixed at the start of the game}.
1433 We also rig' the random oracle $H$ so that $H(s^*) = r^* \xor t^*$.
1434 This isn't much of a fix, because this value is evidently uniformly
1435 distributed and independent of everything except $r^* \xor t^*$.
1437 We could rig $G$ and $H'$ too, once we knew $x^*$, so that $s^* = (x^* \xor 1438 G(r)) \cat H'(x^* \cat r)$. But we don't. Instead, consider the event
1439 $F_1$ that the adversary queries $G$ at $r^*$. Since we have opted for the
1440 bare-faced lie rather than oracle subterfuge, the target ciphertext $y^*$
1441 and the oracles are entirely independent of the target plaintext $x^*$,
1442 whatever that might be. Hence, $A$'s probability of guessing which
1443 plaintext was chosen, $\Pr[S_1] = \frac{1}{2}$.
1445 When attempting to bound $\Pr[F_1]$, there are two cases to consider:
1446 \begin{enumerate}
1448 \item The adversary has not previously queried $H$ at $s^*$. In this
1449 case, the value of $r^*$ is independent of the adversary's view -- it has
1450 no information at all about $r^*$. This can occur, therefore, with
1451 probability at most $q_G 2^{-k}$.
1453 \item The adversary has previously queried $H$ at $s^*$. Then we can
1454 construct an inverter. Note that $f_P$ is a permutation (by assumption);
1455 hence, selecting a $y^*$ at random implies the values of $w^*$, and hence
1456 $s^*$ and $t^*$, even though they can't be computed easily.
1457 \begin{program}
1458 Inverter $I(P, y)$: \+ \\
1459 $\Xid{G}{map} \gets \emptyset$;
1460 $\Xid{H}{map} \gets \emptyset$;
1461 $\Xid{H'}{map} \gets \emptyset$; \\
1462 $z \gets \bot$; \\
1463 $(x_0, x_1, s) \gets A^{G(\cdot), H(\cdot), H'(\cdot)} 1464 (\cookie{find}, P)$; \\
1465 $b \gets A^{G(\cdot), H(\cdot), H'(\cdot)}(\cookie{guess}, y, s)$; \\
1466 \RETURN $z$; \- \$\smallskipamount] 1467 Oracle H(s): \+ \\ 1468 \IF s \in \dom \Xid{H}{map} \\ 1469 \THEN \RETURN \Xid{H}{map}(s); \\ 1470 h \getsr \{0, 1\}^k; \\ 1471 \Xid{H}{map} \gets \Xid{H}{map} \cup \{s \mapsto h\}; \\ 1472 \RETURN h; 1473 \next 1474 Oracle H'(s): \+ \\ 1475 \IF s \in \dom \Xid{H'}{map} \\ 1476 \THEN \RETURN \Xid{H'}{map}(s); \\ 1477 h' \getsr \{0, 1\}^k; \\ 1478 \Xid{H'}{map} \gets \Xid{H'}{map} \cup \{s \mapsto h'\}; \\ 1479 \RETURN h; \- \\[\smallskipamount] 1480 Oracle G(r): \+ \\ 1481 \IF r \in \dom \Xid{G}{map} \THEN \\ 1482 \RETURN \Xid{G}{map}(r); \\ 1483 \FOR s \in \dom \Xid{H}{map} \DO \\ \quad \= \+ \kill 1484 t \gets r \xor \Xid{H}{map}(s); \\ 1485 w \gets s \cat t; \\ 1486 \IF f_P(w) = y \THEN z \gets w; \- \\ 1487 g \getsr \{0, 1\}^{n-2k}; \\ 1488 \Xid{G}{map} \gets \Xid{G}{map} \cup \{r \mapsto g\}; \\ 1489 \RETURN g; 1490 \end{program} 1491 Clearly, I succeeds whenever A queries both H at s^* and G at 1492 r^*. I's running time is about O(q_G q_H) because of all of the 1493 searching in the G oracle. 1495 \end{enumerate} 1496 Thus, 1497 \[ \Pr[F_1] \le 1498 \frac{q_G}{2^k} + \InSec{owf}(\mathcal{T}; t + O(q_G q_H)).$%
1499 Now observe that, if $F_1$ doesn't occur, Games $\G0$ and~$\G1$ are
1500 indistinguishable. So
1501 $\Pr[S_0 \land \lnot F_1] = \Pr[S_1 \land \lnot F_1],$
1502 so by Shoup's lemma,
1503 $|{\Pr[S_0]} - \Pr[S_1]| \le \Pr[F_1].$
1504 Rearranging yields:
1505 $\Adv{ind-cpa}{\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}}(A) 1506 \le 2 \left (\frac{q_G}{2^k} + 1507 \InSec{owf}(\mathcal{T}; t + O(q_G q_H)) \right).$%
1508 But $A$ was arbitrary. The result follows.
1510 To complete the plaintext-awareness proof, we must present a plaintext
1511 extractor.
1512 \begin{program}
1513 Plaintext extractor $X(y, P, Q_G, Q_H, Q_{H'}, C)$: \+ \\
1514 \FOR $z \in \dom Q_{H'}$ \DO \\ \quad \= \+ \kill
1515 \PARSE $z$ \AS $x, k\colon r$; \\
1516 $c \gets Q_{H'}(z)$; \\
1517 $s \gets (x \xor Q_G(r)) \cat c$; \\
1518 \IF $s \in \dom Q_H$ \THEN \\ \quad \= \+ \kill
1519 $t \gets r \xor Q_H(s)$; \\
1520 $w \gets s \cat t$; \\
1521 $y' \gets f_P(w)$; \\
1522 \IF $y = y'$ \THEN \RETURN $x$; \-\- \\
1523 \RETURN $\bot$;
1524 \end{program}
1525 To obtain a lower bound on the success probability of $X$, consider an
1526 adversary $A$ which queries its various oracles and returns a ciphertext
1527 $y$. We aim to show that, if $A$ did not query all of its oracles as
1528 required for $X$ to work then its probability of producing a valid
1529 ciphertext (i.e., one for which the decryption algorithm does not return
1530 $\bot$) is small.
1532 We consider the decryption algorithm applied to $y$, and analyse the
1533 probability that $y$ is a valid ciphertext even though $A$ did not make all
1534 of the appropriate oracle queries.
1536 We shall take some of our notation from the decryption algorithm, which
1537 proceeds as follows:
1538 \begin{program}
1539 Algorithm $\Xid{D}{OAEP+}^ 1540 {\mathcal{T}, G(\cdot), H(\cdot), H'(\cdot)}_K(y)$: \+ \\
1541 $w \gets T_K(y)$; \\
1542 \PARSE $w$ \AS $s, k\colon t$; \\
1543 $r \gets t \xor H(s)$; \\
1544 \PARSE $s$ \AS $s' \cat k\colon c$; \\
1545 $x \gets s' \xor G(r)$; \\
1546 \IF $c = H'(x \cat r)$ \THEN \RETURN $x$; \\
1547 \ELSE \RETURN $\bot$;
1548 \end{program}
1550 Firstly, suppose that $A$ did not query $H'$ at $x \cat r$. Then obviously
1551 there is only a $2^{-k}$ probability that $c$ is correct and the ciphertext
1552 will be accepted. By our assumption about adversary behaviour, if $A$
1553 didn't query $G$ at $r$ then it also didn't query $H'$ at $x \cat r$ for
1554 any $x$. Hence, a decryption algorithm which rejected immediately if it
1555 discovered that $G$ hadn't been queried at $r$, or that $H'$ hadn't been
1556 queried at $x \cat r$, would be incorrect with probability at most
1557 $2^{-k}$.
1559 Secondly, suppose that $A$ did not query $H$ at $s$. Then $c$ is still
1560 fixed, but $r$ is now random and independent of $A$'s view. The
1561 probability that $G$ has been queried at $r$ is then at most $q_G 2^{-k}$.
1562 So a decryption algorithm which, in addition to the changes above, also
1563 rejected if it discovered that $H$ had not been queried at $s$ would be
1564 incorrect with probability at most $q_G 2^{-k}$.
1566 But our plaintext extractor $X$ is just such a decryption algorithm.
1567 Hence, $X$'s failure probability is
1568 $\epsilon = \frac{q_G + 1}{2^k}.$
1569 \end{proof}
1571 \endinput
1573 %%% Local Variables:
1574 %%% mode: latex
1575 %%% TeX-master: "ips"
1576 %%% End: