| 1 | \xcalways\section{Public-key encryption}\x |
| 2 | |
| 3 | \xcalways\subsection{Syntax}\x |
| 4 | |
| 5 | \begin{slide} |
| 6 | \head{Syntax of public-key encryption schemes} |
| 7 | |
| 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} |
| 25 | |
| 26 | \xcalways\subsection{Semantic security and indistinguishability}\x |
| 27 | |
| 28 | \begin{slide} |
| 29 | \head{Notation for oracles} |
| 30 | |
| 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} |
| 43 | |
| 44 | \begin{slide} |
| 45 | \topic{semantic security} |
| 46 | \head{Semantic security} |
| 47 | |
| 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} |
| 65 | |
| 66 | \begin{slide} |
| 67 | \head{Semantic security (cont.)} |
| 68 | |
| 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. |
| 71 | |
| 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} |
| 75 | |
| 76 | \begin{slide} |
| 77 | \topic{indistinguishability} |
| 78 | \head{Indistinguishability} |
| 79 | |
| 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 |
| 94 | ciphertext given to the adversary. The adversary must decide which |
| 95 | plaintext was encrypted. |
| 96 | \end{slide} |
| 97 | |
| 98 | \begin{slide} |
| 99 | \topic{advantage and insecurity} |
| 100 | \head{Advantage and insecurity} |
| 101 | |
| 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]; |
| 109 | \\ |
| 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]. |
| 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) &= |
| 119 | \max_A \Adv{\id{goal}-cpa}{\mathcal{E}}(A); |
| 120 | \\ |
| 121 | \InSec{\id{goal}-\id{cca}}(\mathcal{E}; t, q_D) &= |
| 122 | \max_A \Adv{\id{goal}-\id{cca}}{\mathcal{E}}(A). |
| 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} |
| 127 | |
| 128 | \begin{slide} |
| 129 | \topic{good news} |
| 130 | \head{Some good news} |
| 131 | |
| 132 | Now there's some good news: \emph{semantic security and (find-then-guess) |
| 133 | indistinguishability are almost equivalent}. |
| 134 | |
| 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} |
| 144 | |
| 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. |
| 166 | |
| 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'). \]% |
| 176 | |
| 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. |
| 197 | |
| 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} |
| 210 | |
| 211 | \xcalways\subsection{Non-malleability}\x |
| 212 | |
| 213 | \begin{slide} |
| 214 | \topic{definition} |
| 215 | \head{Non-malleability} |
| 216 | |
| 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. |
| 220 | |
| 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} |
| 241 | |
| 242 | \begin{slide} |
| 243 | \topic{more good news} |
| 244 | \head{Non-malleability (more good news)} |
| 245 | |
| 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} |
| 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]. \]% |
| 265 | \end{slide} |
| 266 | |
| 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'). \]% |
| 290 | |
| 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$. |
| 294 | |
| 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. |
| 301 | |
| 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})$. |
| 307 | |
| 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} |
| 325 | |
| 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}. \]% |
| 336 | |
| 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. |
| 344 | |
| 345 | We conclude that the two notions are almost equivalent, as claimed. |
| 346 | \end{proof} |
| 347 | |
| 348 | \xcalways\subsection{Relations between security notions}\x |
| 349 | |
| 350 | \begin{slide} |
| 351 | \head{Relations between security notions \cite{Bellare:1998:RAN}} |
| 352 | |
| 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 |
| 362 | |
| 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 | } \] |
| 373 | |
| 374 | \begin{list}{}{ |
| 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 |
| 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} |
| 389 | |
| 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. |
| 395 | |
| 396 | \begin{enumerate} |
| 397 | |
| 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. |
| 420 | |
| 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. |
| 451 | |
| 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. |
| 476 | |
| 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. |
| 495 | |
| 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. |
| 514 | |
| 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). \] |
| 533 | |
| 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. |
| 552 | |
| 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. |
| 580 | |
| 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}. \]% |
| 619 | |
| 620 | Now to show that $\mathcal{E}'$ is insecure in the IND-CCA1 sense. |
| 621 | Consider this adversary: |
| 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. |
| 635 | |
| 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. |
| 663 | |
| 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} |
| 721 | |
| 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. |
| 725 | |
| 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. |
| 734 | |
| 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. |
| 748 | |
| 749 | \end{enumerate} |
| 750 | All present and correct. |
| 751 | \end{proof} |
| 752 | |
| 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. |
| 763 | |
| 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} |
| 772 | \answer% |
| 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$;~\}. |
| 779 | |
| 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)$. |
| 792 | |
| 793 | To prove malleability, simply note that multiplying an element |
| 794 | $\vect{y}[i]$ by $z$ toggles the corresponding plaintext bit. |
| 795 | \end{exercise} |
| 796 | |
| 797 | \xcalways\subsection{The ElGamal scheme}\x |
| 798 | |
| 799 | \begin{slide} |
| 800 | \topic{description} |
| 801 | \head{The ElGamal public-key encryption scheme} |
| 802 | |
| 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$. |
| 806 | |
| 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} |
| 826 | |
| 827 | \begin{slide} |
| 828 | \topic{security proof} |
| 829 | \head{Security proof for ElGamal} |
| 830 | |
| 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} |
| 845 | |
| 846 | \begin{slide} |
| 847 | \head{Security proof for ElGamal (cont.)} |
| 848 | |
| 849 | Let $\alpha$ and $\beta$ be the discrete logs of $a$ and $b$. |
| 850 | |
| 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}$. |
| 857 | |
| 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} |
| 863 | |
| 864 | \begin{slide} |
| 865 | \topic{other notes} |
| 866 | \head{Notes about ElGamal} |
| 867 | |
| 868 | \begin{itemize} |
| 869 | |
| 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. |
| 873 | |
| 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. |
| 878 | |
| 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. |
| 884 | |
| 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)$. |
| 888 | |
| 889 | \end{itemize} |
| 890 | \end{slide} |
| 891 | |
| 892 | \xcalways\subsection{Encrypting using trapdoor one-way functions}\x |
| 893 | |
| 894 | \begin{slide} |
| 895 | \head{Trapdoor one-way functions} |
| 896 | |
| 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? |
| 900 | |
| 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. |
| 904 | |
| 905 | How can we fix these schemes? |
| 906 | |
| 907 | We'll focus on RSA, because decryption is simpler; Rabin works in a very |
| 908 | similar way. |
| 909 | \end{slide} |
| 910 | |
| 911 | \begin{slide} |
| 912 | \topic{simple embedding schemes} |
| 913 | \head{Simple embedding schemes} |
| 914 | |
| 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. |
| 918 | |
| 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. |
| 922 | |
| 923 | An encryption scheme which processes messages like this is called a |
| 924 | \emph{simple embedding scheme}. |
| 925 | \end{slide} |
| 926 | |
| 927 | \begin{slide} |
| 928 | \topic{\PKCS1 padding} |
| 929 | \head{\PKCS1 encryption padding for RSA \cite{RSA:1993:PRE}} |
| 930 | |
| 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. |
| 933 | |
| 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} |
| 946 | |
| 947 | \begin{slide} |
| 948 | \head{\PKCS1 encryption padding for RSA (cont.)} |
| 949 | |
| 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 & |
| 954 | \hex{00} & |
| 955 | $m$ |
| 956 | \\ \hlx{vc{2-5}} |
| 957 | \end{tabular} |
| 958 | |
| 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} |
| 964 | |
| 965 | \begin{slide} |
| 966 | \topic{Optimal Asymmetric Encryption Padding (OAEP)} |
| 967 | \head{Optimal Asymmetric Encryption Padding (OAEP) \cite{Bellare:1995:OAE}} |
| 968 | |
| 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. |
| 972 | |
| 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} |
| 993 | |
| 994 | \begin{slide} |
| 995 | \head{Optimal Asymmetric Encryption Padding (OAEP) (cont.)} |
| 996 | |
| 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) > |
| 1014 | |
| 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} |
| 1030 | |
| 1031 | \begin{slide} |
| 1032 | \head{Security of OAEP, \seq: chosen plaintext attacks} |
| 1033 | |
| 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}}$. |
| 1037 | |
| 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} |
| 1043 | |
| 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. |
| 1046 | |
| 1047 | \begin{slide} |
| 1048 | \topic{possible malleability of OAEP} |
| 1049 | \head{OAEP is not (generically) non-malleable \cite{Shoup:2001:OAEPR}} |
| 1050 | |
| 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. |
| 1054 | |
| 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} |
| 1077 | |
| 1078 | Nevertheless, OAEP \emph{does} provide security against chosen-ciphertext |
| 1079 | attacks when used with the RSA and Rabin functions. |
| 1080 | \end{slide} |
| 1081 | |
| 1082 | \xcalways\subsection{Plaintext awareness and OAEP+}\x |
| 1083 | |
| 1084 | \begin{slide} |
| 1085 | \head{Plaintext awareness} |
| 1086 | |
| 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. |
| 1092 | |
| 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. |
| 1096 | |
| 1097 | Note, then, that plaintext awareness (as currently defined) only works in |
| 1098 | the random oracle model. |
| 1099 | \end{slide} |
| 1100 | |
| 1101 | \begin{slide} |
| 1102 | \topic{definition of plaintext awareness} |
| 1103 | \head{Definition of plaintext awareness \cite{Bellare:1998:RAN}} |
| 1104 | |
| 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. |
| 1117 | |
| 1118 | Note that $Q_H$ doesn't include the oracle queries required by the |
| 1119 | encryption oracle. |
| 1120 | \end{slide} |
| 1121 | |
| 1122 | \begin{slide} |
| 1123 | \head{Definition of plaintext awareness (cont.)} |
| 1124 | |
| 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*} |
| 1134 | |
| 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. |
| 1138 | |
| 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} |
| 1142 | |
| 1143 | \begin{slide} |
| 1144 | \topic{chosen-ciphertext security} |
| 1145 | \head{Plaintext awareness and chosen-ciphertext security |
| 1146 | \cite{Bellare:1998:RAN}} |
| 1147 | |
| 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. |
| 1153 | |
| 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. \]% |
| 1158 | |
| 1159 | The converse is not true: IND-CCA2 does not imply plaintext awareness. |
| 1160 | \end{slide} |
| 1161 | |
| 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. |
| 1196 | |
| 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, achieves |
| 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} |
| 1237 | |
| 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} |
| 1262 | |
| 1263 | \begin{slide} |
| 1264 | \topic{old definition} |
| 1265 | \head{The old definition of plaintext awareness} |
| 1266 | |
| 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. |
| 1271 | |
| 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} |
| 1275 | |
| 1276 | \begin{slide} |
| 1277 | \topic{OAEP+} |
| 1278 | \resetseq |
| 1279 | \head{Plaintext-aware encryption: OAEP+ \cite{Shoup:2001:OAEPR}, \seq} |
| 1280 | |
| 1281 | OAEP+ is a simple embedding scheme, very similar to OAEP, which achieves |
| 1282 | plaintext-awareness. |
| 1283 | |
| 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$. |
| 1288 | \begin{program} |
| 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$; \\ |
| 1296 | \RETURN $f_P(w)$; |
| 1297 | \next |
| 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$; |
| 1307 | \end{program} |
| 1308 | \end{slide} |
| 1309 | |
| 1310 | \begin{slide} |
| 1311 | \head{Plaintext-aware encryption: OAEP+, \seq} |
| 1312 | |
| 1313 | %% x <- {0, 1}^{n-2k} r <-R {0, 1}^k |
| 1314 | %% | | |
| 1315 | %% | | |
| 1316 | %% | | |
| 1317 | %% |-------->[H']<----------------| |
| 1318 | %% | | | |
| 1319 | %% | | | |
| 1320 | %% v | | |
| 1321 | %% (+)<-------------[G]<-----------| |
| 1322 | %% | | | |
| 1323 | %% | | | |
| 1324 | %% v | | |
| 1325 | %% [||]<-------' | |
| 1326 | %% | | |
| 1327 | %% | | |
| 1328 | %% | v |
| 1329 | %% |-------------->[H]---------->(+) |
| 1330 | %% | | |
| 1331 | %% | | |
| 1332 | %% v v |
| 1333 | %% < s = (x (+) G(r)) || H'(x || r) > < t = r (+) H(s) > |
| 1334 | |
| 1335 | \vfil |
| 1336 | \[ \begin{graph} |
| 1337 | []!{0; <1cm, 0cm>:} |
| 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" |
| 1343 | :[d] *{\ocat}="cat" |
| 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" |
| 1349 | \end{graph} \] |
| 1350 | \vfil |
| 1351 | \end{slide} |
| 1352 | |
| 1353 | \begin{slide} |
| 1354 | \head{Plaintext-aware encryption: OAEP+, \seq} |
| 1355 | |
| 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'}) |
| 1361 | \le |
| 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 |
| 1367 | function $f$. |
| 1368 | |
| 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'}) \\ |
| 1373 | & \le |
| 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)). |
| 1376 | \end{eqnarray*} |
| 1377 | \end{slide} |
| 1378 | |
| 1379 | \begin{proof}[Proof of the main OAEP+ result] |
| 1380 | |
| 1381 | We assume throughout that, before querying its $H'$ oracle at $x \cat r$, |
| 1382 | the adversary has queried $G$ at $r$. |
| 1383 | |
| 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. |
| 1388 | |
| 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'$. |
| 1392 | |
| 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$. |
| 1402 | |
| 1403 | \paragraph{Game $\G1$} |
| 1404 | At the beginning of the game, we select at random: |
| 1405 | \begin{itemize} |
| 1406 | \item $s^* \inr \{0, 1\}^{n-k}$; |
| 1407 | \item $t^* \inr \{0, 1\}^k$; and |
| 1408 | \item $r^* \inr \{0, 1\}^k$. |
| 1409 | \end{itemize} |
| 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}. |
| 1412 | |
| 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^*$. |
| 1416 | |
| 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}$. |
| 1424 | |
| 1425 | When attempting to bound $\Pr[F_1]$, there are two cases to consider: |
| 1426 | \begin{enumerate} |
| 1427 | |
| 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}$. |
| 1432 | |
| 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. |
| 1437 | \begin{program} |
| 1438 | Inverter $I(P, y)$: \+ \\ |
| 1439 | $\Xid{G}{map} \gets \emptyset$; |
| 1440 | $\Xid{H}{map} \gets \emptyset$; |
| 1441 | $\Xid{H'}{map} \gets \emptyset$; \\ |
| 1442 | $z \gets \bot$; \\ |
| 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\}$; \\ |
| 1452 | \RETURN $h$; |
| 1453 | \next |
| 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\}$; \\ |
| 1469 | \RETURN $g$; |
| 1470 | \end{program} |
| 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. |
| 1474 | |
| 1475 | \end{enumerate} |
| 1476 | Thus, |
| 1477 | \[ \Pr[F_1] \le |
| 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]. \] |
| 1484 | Rearranging yields: |
| 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. |
| 1489 | |
| 1490 | To complete the plaintext-awareness proof, we must present a plaintext |
| 1491 | extractor. |
| 1492 | \begin{program} |
| 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$; \-\- \\ |
| 1503 | \RETURN $\bot$; |
| 1504 | \end{program} |
| 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 |
| 1510 | $\bot$) is small. |
| 1511 | |
| 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. |
| 1515 | |
| 1516 | We shall take some of our notation from the decryption algorithm, which |
| 1517 | proceeds as follows: |
| 1518 | \begin{program} |
| 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', k\colon c$; \\ |
| 1525 | $x \gets s' \xor G(r)$; \\ |
| 1526 | \IF $c = H'(x \cat r)$ \THEN \RETURN $x$; \\ |
| 1527 | \ELSE \RETURN $\bot$; |
| 1528 | \end{program} |
| 1529 | |
| 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 |
| 1537 | $2^{-k}$. |
| 1538 | |
| 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}$. |
| 1545 | |
| 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}. \] |
| 1549 | \end{proof} |
| 1550 | |
| 1551 | \endinput |
| 1552 | |
| 1553 | %%% Local Variables: |
| 1554 | %%% mode: latex |
| 1555 | %%% TeX-master: "ips" |
| 1556 | %%% End: |