1 \xcalways\section{Public-key encryption
}\x
3 \xcalways\subsection{Syntax
}\x
6 \head{Syntax of public-key encryption schemes
}
8 A public-key encryption scheme $
\mathcal{E
} = (G, E, D)$ is a triple of
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
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).
26 \xcalways\subsection{Semantic security and indistinguishability
}\x
29 \head{Notation for oracles
}
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
}
35 Attack & D_0(c) & D_1(c) \\
\hlx{vhv
}
37 CCA1 & D_K(c) &
\bot \\
38 CCA2 & D_K(c) & D_K(c) \\
\hlx*
{vh
}
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.
45 \topic{semantic security
}
46 \head{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
}:
52 Experiment $
\Expt{sem-
\id{atk
}-$b$
}{\mathcal{E
}}(A)$: \+ \\
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$; \\
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$.
67 \head{Semantic security (cont.)
}
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.
77 \topic{indistinguishability
}
78 \head{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:
84 Experiment $
\Expt{ind-
\id{atk
}-$b$
}{\mathcal{E
}}(A)$: \+ \\
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)$; \\
92 In the first stage, the adversary has to choose two plaintexts. One is
93 then chosen by the experimenter, encrypted, and the corresponding
94 ciphertext given to the adversary. The adversary must decide which
95 plaintext was encrypted.
99 \topic{advantage and insecurity
}
100 \head{Advantage and insecurity
}
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
]
106 \Adv{ind-
\id{atk
}}{\mathcal{E
}}(A) &=
107 \Pr[\Expt{ind-
\id{atk
}-$
1$
}{\mathcal{E
}}(A) =
1] -
108 \Pr[\Expt{ind-
\id{atk
}-$
0$
}{\mathcal{E
}}(A) =
1];
110 \Adv{sem-
\id{atk
}}{\mathcal{E
}}(A) &=
111 \Pr[\Expt{sem-
\id{atk
}-$
1$
}{\mathcal{E
}}(A) =
1] -
112 \Pr[\Expt{sem-
\id{atk
}-$
0$
}{\mathcal{E
}}(A) =
1].
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:
118 \InSec{\id{goal
}-cpa
}(
\mathcal{E
}; t) &=
119 \max_A \Adv{\id{goal
}-cpa
}{\mathcal{E
}}(A);
121 \InSec{\id{goal
}-
\id{cca
}}(
\mathcal{E
}; t, q_D) &=
122 \max_A \Adv{\id{goal
}-
\id{cca
}}{\mathcal{E
}}(A).
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.
130 \head{Some 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
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
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'))$;
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$; \\
163 Here, $A$ is simulating the semantic security experiment itself, drawing
164 plaintexts from $A'$'s distribution $
\mathcal{M
}$ and evaluating its chosen
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:
181 Adversary $A'^
{D(
\cdot)
}(
\cookie{select
}, P)$: \+ \\
182 $(x'_0, x'_1, s)
\gets A^
{D(
\cdot)
}(
\cookie{find
}, P)$; \\
184 \
{ x'_0
\mapsto \frac{1}{2}, x'_1
\mapsto \frac{1}{2} \
}$; \\
185 \RETURN $(x'_0, x'_1, s')$;
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)$;
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
206 \
[ \Adv{sem-
\id{atk
}}{\mathcal{E
}}(A') =
207 \frac{1}{2} \Adv{ind-
\id{atk
}}{\mathcal{E
}}(A) \
]%
208 completing the proof.
211 \xcalways\subsection{Non-malleability
}\x
215 \head{Non-malleability
}
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
}:
224 Experiment $
\Expt{cnm-
\id{atk
}-$b$
}{\mathcal{E
}}(A)$: \+ \\
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$;
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]. \
]%
243 \topic{more good news
}
244 \head{Non-malleability (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:
251 Experiment $
\Expt{nm-
\id{atk
}-$b$
}{\mathcal{E
}}(A)$: \+ \\
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)$;
261 We define advantage by
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]. \
]%
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:
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'))$;
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))$;
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$; \\
286 Studying the behaviour of $A$, we see that it succeeds precisely when $A'$
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
})$.
309 Adversary $A'^
{D(
\cdot)
}(
\cookie{find
}, P)$: \+ \\
310 $(x'_0, x'_1, s)
\gets A^
{D(
\cdot)
}(
\cookie{find
}, P)$; \\
312 \
{ x'_0
\mapsto \frac{1}{2}, x'_1
\mapsto \frac{1}{2} \
}$; \\
313 \RETURN $(
\mathcal{M
}, (x'_0, x'_1, P, s))$;
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$; \\
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.
348 \xcalways\subsection{Relations between security notions
}\x
351 \head{Relations between security notions
\cite{Bellare:
1998:RAN
}}
354 %% NM-CPA <--------- NM-CCA1 <--------- NM-CCA2
356 %% | \__ 6 | \__ 7 | |
357 %% 1| \/_ |1 \/_ 4| |1
358 %% | 5/ \__ | / \_ | |
360 %% IND-CPA <-------- IND-CCA1 <------- IND-CCA2
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 \\
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 \\
375 \settowidth{\labelwidth}{\textbf{Key
}}
376 \leftmargin\labelwidth\advance\leftmargin\labelsep
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
385 \item The numbers refer to sections of the proof provided in the notes.
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.
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.
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)$;
407 Adversary $A'^
{D(
\cdot)
}(
\cookie{choose
}, y, s)$: \+ \\
408 \RETURN $(
[], (y, s))$;
410 Adversary $A'^
{D(
\cdot)
}(
\cookie{guess
},
\vect{x
}, s')$: \+ \\
411 $(y, s)
\gets s'$; \\
412 $b'
\gets A^
{D(
\cdot)
}(y, s)$; \\
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.
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)$;
430 Adversary $A'^
{D(
\cdot)
}(
\cookie{guess
}, y, s)$: \+ \\
431 $b'
\gets A^
{D_1(
\cdot)
}(
\cookie{guess
}, y, s)$; \\
434 The oracles $D_0$ and $D_1$ are defined according to
\id{atk
}, as
435 shown in table~
\ref{tab:se-rel-oracle
}.
437 \begin{tabular
}[C
]{l Mc Mc
} \hlx*
{hv
}
438 \id{atk
} & D_0(x) & D_1(x) \\
\hlx{vhv
}
440 CCA1 & D(x) &
\bot \\
\hlx*
{vh
}
442 \caption{Relations between notions of security for public key
443 encryption: decryption oracles
}
444 \label{tab:se-rel-oracle
}
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.
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)$;
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)$;
465 Adversary $A'^
{D(
\cdot)
}(
\cookie{guess
},
\vect{x
}, t)$: \+ \\
466 $b'
\gets A^
{D_1(
\cdot)
}(
\cookie{guess
},
\vect{x
}, t)$; \\
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.
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)$;
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)$; \\
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')$:
500 Algorithm $G'(k)$: \+ \\
504 Algorithm $E'_P(x)$: \+ \\
508 Algorithm $D'_K(y')$: \+ \\
509 $(b, y)
\gets y'$; \\
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
}$:
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'$; \\
527 Adversary $A^
\bot(
\cookie{guess
}, y, s)$: \+ \\
528 $b'
\gets A'^
\bot(
\cookie{guess
}, y, s)$; \\
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
537 Adversary $C'^
{D(
\cdot)
}(
\cookie{find
}, P')$: \+ \\
538 \RETURN $(
0,
1,
\bot)$;
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)$;
545 Adversary $C'^
{D(
\cdot)
}(
\cookie{guess
},
\vect{x
}, t)$: \+ \\
546 \RETURN $
\vect{x
}[0]$;
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
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
}' =
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))$;
563 Algorithm $E'_
{P'
}(x)$: \+ \\
564 $(P, u)
\gets P'$; \\
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$; \\
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
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))$;
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'))$;
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')$; \\
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.
621 Consider this adversary:
623 Adversary $C'^
{D(
\cdot)
}(
\cookie{find
}, P')$: \+ \\
624 $(P, u)
\gets P'$; \\
625 $v
\gets D(u)$; $K
\gets D(v)$; \\
628 Adversary $C'^
\bot(
\cookie{guess
}, y, K)$: \+ \\
629 $b'
\gets D_K(y)$; \\
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')$:
641 Algorithm $G'(k)$: \+ \\
642 $(P, K)
\gets G(k)$; \\
643 $i
\getsr \keys \mathcal{M
}$; \\
644 \RETURN $(P, (K, i))$;
646 Algorithm $E'_P(x)$: \+ \\
648 \RETURN $(
0, y,
\bot)$;
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$; \\
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
}$.
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')$; \\
697 Adversary $A''^
{T(
\cdot), V(
\cdot)
}$: \+ \\
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$; \\
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
}
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.
737 Adversary $C'^
{D(
\cdot)
}(
\cookie{find
}, P')$: \+ \\
738 \RETURN $(
0,
1,
\bot)$;
740 Adversary $C'^
{D(
\cdot)
}(
\cookie{guess
}, y, s)$: \+ \\
741 $
\tau \gets D(
1, y,
\bot)$; \\
742 $b'
\gets D(
1, y,
\tau)$; \\
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.
750 All present and correct.
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.
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
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;
793 To prove malleability, simply note that multiplying an element
794 $
\vect{y
}[i
]$ by $z$ toggles the corresponding plaintext bit.
797 \xcalways\subsection{The ElGamal scheme
}\x
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:
810 $
\Xid{G
}{ElGamal
}^G$: \+ \\
811 $
\alpha \getsr \
{1,
2,
\ldots, q -
1\
}$; \\
812 \RETURN $(g^
\alpha,
\alpha)$;
814 $
\Xid{E
}{ElGamal
}^G_a(x)$: \+ \\
815 $
\beta \getsr \
{1,
2,
\ldots, q -
1\
}$; \\
816 \RETURN $(g^
\beta, x a^
\beta)$;
818 $
\Xid{D
}{ElGamal
}^G_
\alpha(y)$: \+ \\
820 $x
\gets b^
{-
\alpha} c$; \\
823 This scheme is secure in the IND-CPA sense if the Decisional Diffie-Hellman
824 problem is hard in $G$.
828 \topic{security proof
}
829 \head{Security proof for ElGamal
}
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 =
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$; \\
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
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). \
]%
866 \head{Notes about ElGamal
}
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
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)$.
892 \xcalways\subsection{Encrypting using trapdoor one-way functions
}\x
895 \head{Trapdoor one-way functions
}
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
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
912 \topic{simple embedding schemes
}
913 \head{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
}.
928 \topic{\PKCS1 padding
}
929 \head{\PKCS1 encryption padding for RSA
\cite{RSA:
1993:PRE
}}
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:
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
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.
948 \head{\PKCS1 encryption padding for RSA (cont.)
}
950 Diagrammatically,
\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 &
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).
966 \topic{Optimal Asymmetric Encryption Padding (OAEP)
}
967 \head{Optimal Asymmetric Encryption Padding (OAEP)
\cite{Bellare:
1995:OAE
}}
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:
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$; \\
984 Algorithm $
\Xid{D
}{OAEP
}^
{\mathcal{T
}, G(
\cdot), H(
\cdot)
}_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$;
995 \head{Optimal Asymmetric Encryption Padding (OAEP) (cont.)
}
997 %% x <- {0, 1}^{n-2k} r <-R {0, 1}^k
1005 %% (+)<-----------[G]--------------|
1009 %% |-------------[H]------------>(+)
1013 %% < s = (x || 0^k) (+) G(r) > < t = r (+) H(s) >
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"
1032 \head{Security of OAEP,
\seq: 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). \
]%
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.
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.
1057 *!UR
{\parbox{0.5\linewidth}{
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
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"
1078 Nevertheless, OAEP
\emph{does
} provide security against chosen-ciphertext
1079 attacks when used with the RSA and Rabin functions.
1082 \xcalways\subsection{Plaintext awareness and OAEP+
}\x
1085 \head{Plaintext awareness
}
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.
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,
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.
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
1123 \head{Definition of plaintext awareness (cont.)
}
1125 An
\emph{$
\epsilon$-plaintext extractor
} for $
\mathcal{E
}$ is an algorithm
1127 \begin{eqnarray*
}[rl
]
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 .
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.)
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
1154 Quantitatively, 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.
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
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)$: \+ \\
1177 $
\Xid{H
}{map
} \gets \Xid{H
}{map
} \cup \
{ x
\mapsto h \
}$; \\
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^* \
})$; \\
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
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')$:
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))$;
1208 Algorithm $E'^
{H(
\cdot)
}_
{P, c
}(x)$: \+ \\
1209 $y
\gets E^
{H(
\cdot)
}_P(x)$; \\
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)$; \\
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, achieves
1219 the same advantage against $
\mathcal{E
}$.
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')$;
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')$; \\
1232 Oracle $
\Xid{D
}{sim
}(y)$: \+ \\
1233 \IF $y = c$
\THEN $x
\gets p$; \\
1234 \ELSE $x
\gets D(y)$; \\
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
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))$;
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$;
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.
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.
1279 \head{Plaintext-aware encryption: OAEP+
\cite{Shoup:
2001:OAEPR
},
\seq}
1281 OAEP+ is a simple embedding scheme, very similar to OAEP, which achieves
1282 plaintext-awareness.
1284 We assume that our one-way function $f_P$ operates on $n$-bit strings. Fix
1285 a security parameter $k$. We require three random oracles $G
\colon \
{0,
1286 1\
}^k
\to \
{0,
1\
}^
{n-
2k
}$, $H
\colon \
{0,
1\
}^
{n-k
} \to \
{0,
1\
}^k$, and
1287 $H'
\colon \
{0,
1\
}^
{n-k
} \to \
{0,
1\
}^k$.
1289 Algorithm $
\Xid{E
}{OAEP+
}
1290 ^
{\mathcal{T
}, G(
\cdot), H(
\cdot), H'(
\cdot)
}_P(x)$: \+ \\
1291 $r
\getsr \
{0,
1\
}^k$; \\
1292 $c
\gets H'(x
\cat r)$; \\
1293 $s
\gets (x
\xor G(r))
\cat c$; \\
1294 $t
\gets r
\xor H(s)$; \\
1295 $w
\gets s
\cat t$; \\
1298 Algorithm $
\Xid{D
}{OAEP+
}
1299 ^
{\mathcal{T
}, G(
\cdot), H(
\cdot), H'(
\cdot)
}_K(y)$: \+ \\
1300 $w
\gets T_K(y)$; \\
1301 \PARSE $w$
\AS $s, k
\colon t$; \\
1302 $r
\gets t
\xor H(s)$; \\
1303 \PARSE $s$
\AS $s', k
\colon c$; \\
1304 $x
\gets s'
\xor G(r)$; \\
1305 \IF $c = H'(x
\cat r)$
\THEN \RETURN $x$; \\
1306 \ELSE \RETURN $
\bot$;
1311 \head{Plaintext-aware encryption: OAEP+,
\seq}
1313 %% x <- {0, 1}^{n-2k} r <-R {0, 1}^k
1317 %% |-------->[H']<----------------|
1321 %% (+)<-------------[G]<-----------|
1329 %% |-------------->[H]---------->(+)
1333 %% < s = (x (+) G(r)) || H'(x || r) > < t = r (+) H(s) >
1338 {x
\in \
{0,
1\
}^n
}="x"
[rrrr
] {r
\inr \
{0,
1\
}^k
}="r"
1339 "x"
[d
] :
[r
] *+
[F
]{H'
}="h'" "r"
[d
] :"h'"
1340 "r" :
[dddd
] *
{\xor}="h-xor"
1341 :
[d
] *++=(
2,
0)
[F:thicker
]{\strut t = r
\xor H(s)
}
1342 "x" :
[dd
] *
{\xor}="g-xor"
1344 :
[dd
] *++=(
4,
0)
[F:thicker
]
1345 {\strut s = (x
\xor G(r))
\cat H'(x
\cat r)
}
1346 [u
] :
[rr
] *+
[F
]{H
} :"h-xor"
1347 "r"
[dd
] :
[ll
] *+
[F
]{G
} :"g-xor"
1348 "h'" :'
[d
]*=<
8pt>
\cir<
4pt>
{r_l
} `d"cat" "cat"
1354 \head{Plaintext-aware encryption: OAEP+,
\seq}
1356 Let $
\mathcal{T
}$ be a trapdoor one-way function. Then the insecurity of
1357 the public-key encryption scheme $
\Xid{\mathcal{E
}}{OAEP+
}^
{\mathcal{T
}}$
1358 in the IND-CPA sense is given by
1359 \
[ \InSec{ind-cpa
}(
\Xid{\mathcal{E
}}{OAEP+
}^
{\mathcal{T
}};
1360 t, q_G, q_H, q_
{H'
})
1362 2 \left (
\frac{q_G
}{2^k
} +
1363 \InSec{owf
}(
\mathcal{T
}; t + O(q_G q_H))
\right). \
]%
1364 Also, $
\Xid{\mathcal{E
}}{OAEP+
}^
{\mathcal{T
}}$ is $(q_G +
1)
1365 2^
{-k
}$-plaintext aware, the plaintext extractor running time being
1366 $O(q_
{H'
} t_f)$, where $t_f$ is the time required to execute the one-way
1369 Tying up the various results, then, we can derive that
1370 \begin{eqnarray*
}[Ll
]
1371 \InSec{ind-cca2
}(
\Xid{\mathcal{E
}}{OAEP+
}^
{\mathcal{T
}};
1372 t, q_D, q_G, q_H, q_
{H'
}) \\
1374 \frac{(
2 + q_D) (q_G +
1) -
2}{2^k
} +
1375 2 \cdot \InSec{owf
}(
\mathcal{T
}; t + O(q_G q_H + q_D q_
{H'
} t_f)).
1379 \begin{proof
}[Proof of the main OAEP+ result
]
1381 We assume throughout that, before querying its $H'$ oracle at $x
\cat r$,
1382 the adversary has queried $G$ at $r$.
1384 First, we show that OAEP+ meets the IND-CPA notion. Suppose that $A$
1385 attacks the OAEP+ scheme in the IND-CPA sense. We shall play a series of
1386 games with the adversary, and vary the rules as we go along. The adversary
1387 remains the same throughout.
1389 At any point in a game, let $Q_G$ be the list of queries the adversary has
1390 made to the oracle $G$, let $Q_H$ be the queries made to $H$, and let
1391 $Q_
{H'
}$ be the queries made to $H'$.
1393 \paragraph{Game $
\G0$
}
1394 This is effectively the original attack game: the adversary chooses two
1395 plaintexts: one is chosen uniformly at random, the adversary is given the
1396 ciphertext and asked to identify which plaintext was chosen. Label the
1397 selected plaintext $x^*$, and the target ciphertext $y^*$. Let $c^*$,
1398 $s^*$, $t^*$ and $w^*$ be the intermediate results of the OAEP+ padding, as
1399 described above. Let $S_0$ be the event that the adversary wins the game.
1400 Our objective is to bound the probability $
\Pr[S_0
] =
1401 (
\Adv{ind-cpa
}{\Xid{\mathcal{E
}}{OAEP+
}^
{\mathcal{T
}}}(A) +
1)/
2$.
1403 \paragraph{Game $
\G1$
}
1404 At the beginning of the game, we select at random:
1406 \item $s^*
\inr \
{0,
1\
}^
{n-k
}$;
1407 \item $t^*
\inr \
{0,
1\
}^k$; and
1408 \item $r^*
\inr \
{0,
1\
}^k$.
1410 We compute $w^* = s^*
\cat t^*$ and $y^* = f_P(w^*)$. Note, then, that
1411 \emph{$y^*$ is fixed at the start of the game
}.
1413 We also `rig' the random oracle $H$ so that $H(s^*) = r^*
\xor t^*$.
1414 This isn't much of a fix, because this value is evidently uniformly
1415 distributed and independent of everything except $r^*
\xor t^*$.
1417 We could rig $G$ and $H'$ too, once we knew $x^*$, so that $s^* = (x^*
\xor
1418 G(r))
\cat H'(x^*
\cat r)$. But we don't. Instead, consider the event
1419 $F_1$ that the adversary queries $G$ at $r^*$. Since we have opted for the
1420 bare-faced lie rather than oracle subterfuge, the target ciphertext $y^*$
1421 and the oracles are entirely independent of the target plaintext $x^*$,
1422 whatever that might be. Hence, $A$'s probability of guessing which
1423 plaintext was chosen, $
\Pr[S_1
] =
\frac{1}{2}$.
1425 When attempting to bound $
\Pr[F_1
]$, there are two cases to consider:
1428 \item The adversary has not previously queried $H$ at $s^*$. In this
1429 case, the value of $r^*$ is independent of the adversary's view -- it has
1430 no information at all about $r^*$. This can occur, therefore, with
1431 probability at most $q_G
2^
{-k
}$.
1433 \item The adversary has previously queried $H$ at $s^*$. Then we can
1434 construct an inverter. Note that $f_P$ is a permutation (by assumption);
1435 hence, selecting a $y^*$ at random implies the values of $w^*$, and hence
1436 $s^*$ and $t^*$, even though they can't be computed easily.
1438 Inverter $I(P, y)$: \+ \\
1439 $
\Xid{G
}{map
} \gets \emptyset$;
1440 $
\Xid{H
}{map
} \gets \emptyset$;
1441 $
\Xid{H'
}{map
} \gets \emptyset$; \\
1443 $(x_0, x_1, s)
\gets A^
{G(
\cdot), H(
\cdot), H'(
\cdot)
}
1444 (
\cookie{find
}, P)$; \\
1445 $b
\gets A^
{G(
\cdot), H(
\cdot), H'(
\cdot)
}(
\cookie{guess
}, y, s)$; \\
1446 \RETURN $z$; \- \\
[\smallskipamount]
1447 Oracle $H(s)$: \+ \\
1448 \IF $s
\in \dom \Xid{H
}{map
}$ \\
1449 \THEN \RETURN $
\Xid{H
}{map
}(s)$; \\
1450 $h
\getsr \
{0,
1\
}^k$; \\
1451 $
\Xid{H
}{map
} \gets \Xid{H
}{map
} \cup \
{s
\mapsto h\
}$; \\
1454 Oracle $H'(s)$: \+ \\
1455 \IF $s
\in \dom \Xid{H'
}{map
}$ \\
1456 \THEN \RETURN $
\Xid{H'
}{map
}(s)$; \\
1457 $h'
\getsr \
{0,
1\
}^k$; \\
1458 $
\Xid{H'
}{map
} \gets \Xid{H'
}{map
} \cup \
{s
\mapsto h'\
}$; \\
1459 \RETURN $h$; \- \\
[\smallskipamount]
1460 Oracle $G(r)$: \+ \\
1461 \IF $r
\in \dom \Xid{G
}{map
}$
\THEN \\
1462 \RETURN $
\Xid{G
}{map
}(r)$; \\
1463 \FOR $s
\in \dom \Xid{H
}{map
}$
\DO \\
\quad \= \+
\kill
1464 $t
\gets r
\xor \Xid{H
}{map
}(s);$ \\
1465 $w
\gets s
\cat t$; \\
1466 \IF $f_P(w) = y$
\THEN $z
\gets w$; \- \\
1467 $g
\getsr \
{0,
1\
}^
{n-
2k
}$; \\
1468 $
\Xid{G
}{map
} \gets \Xid{G
}{map
} \cup \
{r
\mapsto g\
}$; \\
1471 Clearly, $I$ succeeds whenever $A$ queries both $H$ at $s^*$ and $G$ at
1472 $r^*$. $I$'s running time is about $O(q_G q_H)$ because of all of the
1473 searching in the $G$ oracle.
1478 \frac{q_G
}{2^k
} +
\InSec{owf
}(
\mathcal{T
}; t + O(q_G q_H)). \
]%
1479 Now observe that, if $F_1$ doesn't occur, Games $
\G0$ and~$
\G1$ are
1480 indistinguishable. So
1481 \
[ \Pr[S_0
\land \lnot F_1
] =
\Pr[S_1
\land \lnot F_1
], \
]
1482 so by Lemma~
\ref{lem:shoup
} (slide~
\pageref{lem:shoup
}),
1483 \
[ |
{\Pr[S_0
]} -
\Pr[S_1
]|
\le \Pr[F_1
]. \
]
1485 \
[ \Adv{ind-cpa
}{\Xid{\mathcal{E
}}{OAEP+
}^
{\mathcal{T
}}}(A)
1486 \le 2 \left (
\frac{q_G
}{2^k
} +
1487 \InSec{owf
}(
\mathcal{T
}; t + O(q_G q_H))
\right). \
]%
1488 But $A$ was arbitrary. The result follows.
1490 To complete the plaintext-awareness proof, we must present a plaintext
1493 Plaintext extractor $X(y, P, Q_G, Q_H, Q_
{H'
}, C)$: \+ \\
1494 \FOR $z
\in \dom Q_
{H'
}$
\DO \\
\quad \= \+
\kill
1495 \PARSE $z$
\AS $x, k
\colon r$; \\
1496 $c
\gets Q_
{H'
}(z)$; \\
1497 $s
\gets (x
\xor Q_G(r))
\cat c$; \\
1498 \IF $s
\in \dom Q_H$
\THEN \\
\quad \= \+
\kill
1499 $t
\gets r
\xor Q_H(s)$; \\
1500 $w
\gets s
\cat t$; \\
1501 $y'
\gets f_P(w)$; \\
1502 \IF $y = y'$
\THEN \RETURN $x$; \-\- \\
1505 To obtain a lower bound on the success probability of $X$, consider an
1506 adversary $A$ which queries its various oracles and returns a ciphertext
1507 $y$. We aim to show that, if $A$ did not query all of its oracles as
1508 required for $X$ to work then its probability of producing a valid
1509 ciphertext (i.e., one for which the decryption algorithm does not return
1512 We consider the decryption algorithm applied to $y$, and analyse the
1513 probability that $y$ is a valid ciphertext even though $A$ did not make all
1514 of the appropriate oracle queries.
1516 We shall take some of our notation from the decryption algorithm, which
1517 proceeds as follows:
1519 Algorithm $
\Xid{D
}{OAEP+
}^
1520 {\mathcal{T
}, G(
\cdot), H(
\cdot), H'(
\cdot)
}_K(y)$: \+ \\
1521 $w
\gets T_K(y)$; \\
1522 \PARSE $w$
\AS $s, k
\colon t$; \\
1523 $r
\gets t
\xor H(s)$; \\
1524 \PARSE $s$
\AS $s'
\cat k
\colon c$; \\
1525 $x
\gets s'
\xor G(r)$; \\
1526 \IF $c = H'(x
\cat r)$
\THEN \RETURN $x$; \\
1527 \ELSE \RETURN $
\bot$;
1530 Firstly, suppose that $A$ did not query $H'$ at $x
\cat r$. Then obviously
1531 there is only a $
2^
{-k
}$ probability that $c$ is correct and the ciphertext
1532 will be accepted. By our assumption about adversary behaviour, if $A$
1533 didn't query $G$ at $r$ then it also didn't query $H'$ at $x
\cat r$ for
1534 any $x$. Hence, a decryption algorithm which rejected immediately if it
1535 discovered that $G$ hadn't been queried at $r$, or that $H'$ hadn't been
1536 queried at $x
\cat r$, would be incorrect with probability at most
1539 Secondly, suppose that $A$ did not query $H$ at $s$. Then $c$ is still
1540 fixed, but $r$ is now random and independent of $A$'s view. The
1541 probability that $G$ has been queried at $r$ is then at most $q_G
2^
{-k
}$.
1542 So a decryption algorithm which, in addition to the changes above, also
1543 rejected if it discovered that $H$ had not been queried at $s$ would be
1544 incorrect with probability at most $q_G
2^
{-k
}$.
1546 But our plaintext extractor $X$ is just such a decryption algorithm.
1547 Hence, $X$'s failure probability is
1548 \
[ \epsilon =
\frac{q_G +
1}{2^k
}. \
]
1553 %%% Local Variables:
1555 %%% TeX-master: "ips"