X-Git-Url: https://git.distorted.org.uk/~mdw/doc/ips/blobdiff_plain/34a3c16f0357851cbb61abdd050194bc1a952045..refs/heads/svn:/enc-symm.tex?ds=sidebyside

diff --git a/enc-symm.tex b/enc-symm.tex
index 6434b4f..e3ec156 100644
--- a/enc-symm.tex
+++ b/enc-symm.tex
@@ -404,7 +404,7 @@
   Prove that
   \[ \InSec{lor-cpa}(\mathcal{E}; t, q, \mu) \le
      2 \cdot \InSec{prf}(F; t, q) +
-     2 q \mu \cdot \InSec{prg}(g; t) + q(q - 1), \]%
+     2 q \mu \cdot \InSec{prg}(g; t) + q(q - 1)/2^l, \]%
   where $\mu$ is the maximum value of $n$, as computed by $E_K(\cdot)$, for
   any encryption query.
   Hints:
@@ -421,12 +421,12 @@
   selected uniformly).  Game~$\G1$ is the same, except that if, for any pair
   of ciphertexts, the $i$-values are equal, the game ends immediately: the
   standard collision bound shows that $|{\Pr[S_1]} - \Pr[S_0]| \le q(q -
-  1)/2$.  In game~$\G2$, rather than using $F_K$ to compute the seeds~$s$, we
-  just choose $s \in \{0, 1\}^l$ at random each time.  Note that the
-  $i$-values are distinct; hence considering an adversary attacking $F$ as a
-  PRF, which simulates either $\G1$ or $\G2$ depending on whether its oracle
-  is an instance of~$F$ or a random function respectively, shows that
-  $|{\Pr[S_2]} - \Pr[S_1]| \le \InSec{prf}(F; t, q)$.
+  1)/2^{l+1}$.  In game~$\G2$, rather than using $F_K$ to compute the
+  seeds~$s$, we just choose $s \in \{0, 1\}^l$ at random each time.  Note
+  that the $i$-values are distinct; hence considering an adversary attacking
+  $F$ as a PRF, which simulates either $\G1$ or $\G2$ depending on whether
+  its oracle is an instance of~$F$ or a random function respectively, shows
+  that $|{\Pr[S_2]} - \Pr[S_1]| \le \InSec{prf}(F; t, q)$.
   
   In game~$\G3$, rather than using the PRG~$g^{(n)}$, we generate the strings
   $p$ uniformly at random from $\{0, 1\}^{l(n+1)}$, and claim that
@@ -438,25 +438,28 @@
   adversary's ciphertext, however, so $\Pr[S_4] = \Pr[S_3] = \frac{1}{2}$.
   Tying all of this together, $(\Adv{lor-cpa}{\mathcal{E}}(A) + 1)/2 \le
   \frac{1}{2} + \InSec{prf}(F; t, q) + q\mu \cdot \InSec{prg}(g; t) + q(q -
-  1)/2$.  Multiplying through by~2 and rearranging yields the required
+  1)/2^{l+1}$.  Multiplying through by~2 and rearranging yields the required
   result.
 
   \def\H#1{\G[H]{#1}}%
+
   We finally turn to the claim made earlier.  In $\G2$, we use the PRG; in
-  $\G3$ we don't.  We construct a number of hybrid games~$\H{i}$ for $0 \le i
-  \le q$ in which encryption query~$j$ (for $0 \le j < q$) is handled as
-  follows: if $0 \le j < i$ then the query is handled as in $\G3$; if $i \le
-  j < q$ then the query is handed as in $\G2$.  Let $T_i$ be the event that
-  the adversary wins in game $\H{i}$.  Clearly, $\H0 \equiv \G2$, and $\H{q}
-  \equiv \G3$.  For each adjacent pair of hybrid games $\H{i}, \H{i+1}$ (for
-  $0 \le i < q$), we can bound $|{\Pr[T_{i+1}} - \Pr[T_i]|$ by considering an
-  adversary attacking~$g^{(n)}$ by running~$A$ and using its input as the XOR
-  mask~$p$ for query~$i$, and following the rules of game~$\H{i}$ for the
-  other queries: then if $y$~is random, it simulates $\H{i+1}$, whereas if
-  $y$ is the output of $g^{(n)}$ then it simulates $\H{i}$.  Thus
-  $|{\Pr[T_{i+1}} - \Pr[T_i]| \le \mu \cdot \InSec{prg}(g; t)$ (by the answer
-  to \ref{ex:dbl-prg}), and $|{\Pr[S_3]} - \Pr[S_2]| = |{\Pr[T_{q-1}]} -
-  \Pr[T_0]| \le q \mu \cdot \InSec{prg}(g; t)$ as claimed.
+  $\G3$ we don't.  Unfortunately, while the left-or-right attack game allows
+  multiple queries and hence multiple samples from the PRG, the PRG attack
+  game only provides one sample.  To bridge the gap, we construct a number of
+  hybrid games~$\H{i}$ for $0 \le i \le q$ in which encryption query~$j$ (for
+  $0 \le j < q$) is handled as follows: if $0 \le j < i$ then the query is
+  handled as in $\G3$; if $i \le j < q$ then the query is handed as in $\G2$.
+  Let $T_i$ be the event that the adversary wins in game $\H{i}$.  Clearly,
+  $\H0 \equiv \G2$, and $\H{q} \equiv \G3$.  For each adjacent pair of hybrid
+  games $\H{i}, \H{i+1}$ (for $0 \le i < q$), we can bound $|{\Pr[T_{i+1}} -
+  \Pr[T_i]|$ by considering an adversary attacking~$g^{(n)}$ by running~$A$,
+  using as its input the XOR mask~$p$ for query~$i$, and following the rules
+  of game~$\H{i}$ for the other queries: then if $y$~is random, it simulates
+  $\H{i+1}$, whereas if $y$ is the output of $g^{(n)}$ then it simulates
+  $\H{i}$.  Thus $|{\Pr[T_{i+1}} - \Pr[T_i]| \le \mu \cdot \InSec{prg}(g; t)$
+  (by the answer to \ref{ex:dbl-prg}), and $|{\Pr[S_3]} - \Pr[S_2]| =
+  |{\Pr[T_{q-1}]} - \Pr[T_0]| \le q \mu \cdot \InSec{prg}(g; t)$ as claimed.
 \end{exercise}
 
 \xcalways\subsection{Block cipher modes}\x
@@ -808,7 +811,7 @@
   Show that CTR and CBC modes are not secure against adaptive
   chosen-ciphertext attacks.
   \answer%
-  We use the FTG-CCA2 notion.  For CTR mode: \cookie{find}: \RETURN $(0, 1,
+  We use the FTG-CCA1 notion.  For CTR mode: \cookie{find}: \RETURN $(0, 1,
   \bot)$; \cookie{guess}: $y' \gets D(y \xor 0^L1)$; \RETURN $y' \xor 1$;
   For CBC mode: same find stage, $y' \gets D(y \xor 1)$; \RETURN $y' \xor 1$;
 \end{exercise}
@@ -1016,7 +1019,7 @@
   
   We prove security relationships using the LOR-CPA notion because this is
   strongest, and bounds for other notions can be derived readily from the
-  left-or-right analysis.  We prove insecurity using the FTG-CCA or FTG-CPA
+  left-or-right analysis.  We prove insecurity using the FTG-CCA1 or FTG-CPA
   notions, because they are weakest and show the strength of our results
   best.
   
@@ -1048,7 +1051,7 @@
   We construct a new encryption scheme $\mathcal{E}' = (E', D')$ in terms of
   $\mathcal{E}$, such that the combined scheme
   $\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}}$ is insecure in the
-  FTG-CCA sense.  Our modified encryption scheme has $\keys\mathcal{E}' =
+  FTG-CCA1 sense.  Our modified encryption scheme has $\keys\mathcal{E}' =
   \keys\mathcal{E}$, and works as follows:
   \begin{program}
     Algorithm $E'_K(x)$: \+ \\
@@ -1073,9 +1076,9 @@
   
   Secondly, we show that the combined MAC-then-encrypt scheme
   $\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}}$ is insecure in the
-  FTG-CCA sense.  Consider this adversary:
+  FTG-CCA1 sense.  Consider this adversary:
   \begin{program}
-    Adversary $B^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\
+    Adversary $B^{E(\cdot)}(\cookie{find})$: \+ \\
       \RETURN $(0, 1, \bot)$;
   \next
     Adversary $B^{E(\cdot), D(\cdot)}(\cookie{guess}, y', s)$: \+ \\
@@ -1085,8 +1088,8 @@
   The ciphertext $1 \cat y$ was never returned by the encryption oracle
   (because it always returns the first bit zero); but the plaintext of $1
   \cat y$ is the challenge plaintext.  Hence, $B$ wins always, and
-  \[ \InSec{ftg-cca}(\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}};
-                     t, 0, 1) = 1, \]%
+  \[ \InSec{ftg-cca1}(\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}};
+                      t, 0, 1) = 1, \]%
   where $t$ is the running time of the adversary $B$ above.
   
   We now address the separate encrypt-and-MAC scheme, which we define
@@ -1147,8 +1150,8 @@
       \RETURN $(0, \tau)$;
   \end{program}
   We see readily that
-  \[ \InSec{ftg-cca}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}};
-                     t, 1, 1) \ge
+  \[ \InSec{ftg-cca1}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}};
+                      t, 1, 1) \ge
      1 - \InSec{suf-cma}(\mathcal{M}; t', 1, 0), \]%
   where $t$ and $t'$ are the running times of adversaries $B$ and $B'$
   respectively.
