From 9907b634a7bc6c9db6381a578e192178a28e9799 Mon Sep 17 00:00:00 2001
From: mdw
Date: Wed, 30 Jan 2002 09:57:06 +0000
Subject: [PATCH] Miscellaneous rewordings and fixings.

authmac.tex  55 ++++++++++++++++++++++++++++
basics.tex  5 +++
2 files changed, 31 insertions(+), 29 deletions()
diff git a/authmac.tex b/authmac.tex
index cd3defa..60e0034 100644
 a/authmac.tex
+++ b/authmac.tex
@@ 384,8 +384,8 @@
for any adversary $A$ constrained to run in time $t$ and permitted $q$
oracle queries,
\[ \Pr[K \getsr \{0, 1\}^k;
 (x, y) \gets A^{F_K(\cdot)}] \le \epsilon :
 x \ne y \land F_K(x) = F_K(y) \]%
+ (x, y) \gets A^{F_K(\cdot)} :
+ x \ne y \land F_K(x) = F_K(y)] \le \epsilon \]%
If $H_K$ is a $(t, q_T, q_V, \epsilon)$secure MAC on $k$bit messages, and
moreover $(t, q_T + q_V, \epsilon')$weakly collision resistant, then
@@ 397,8 +397,8 @@
Let $A$ be an adversary which forges a $\Xid{T}{NMAC}^H$ tag in time $t$,
using $q_T$ tagging queries and $q_V$ verification queries with probability
 $\epsilon$. We construct an adversary $A'$ which forces a $H$ tag for a
 $k$bit in essentially the same time.
+ $\epsilon$. We construct an adversary $A'$ which forges an $H$tag for a
+ $k$bit message in essentially the same time.
\begin{program}
Adversary $A'^{T(\cdot), V(\cdot, \cdot)}$ \+ \\
$K \getsr \{0, 1\}^k$; \\
@@ 485,38 +485,39 @@
function $F$. For the sake of simplicity, we allow the adversary $A$
to query on \emph{padded} messages, rather than the raw unpadded
messages. We count the number $q'$ of individual message blocks.

 As the game with $A$ progresses, we can construct a directed
 \emph{graph} of the query results so far. We start with a node
 labelled $I$. When processing an $H$query, each time we compute $t'
 = F(t \cat x_i)$, we add a node $t'$, and an edge $x_i$ from $t$ to
 $t'$. The `bad' event occurs whenever we add an edge to a previously
 existing node. We must show, firstly, that the
 adversary cannot distinguish $H$ from a random function unless the bad
 event occurs; and, secondly, that the bad event doesn't occur very
 often.
+
+ As the game with $A$ progresses, we can construct a directed \emph{graph}
+ of the query results so far. We start with a node labelled $I$. When
+ processing an $H$query, each time we compute $t' = F(t \cat x_i)$, we add
+ a node $t'$, and an edge $x_i$ from $t$ to $t'$. The `bad' event occurs
+ whenever we add an edge to a previously existing node. We must show,
+ firstly, that the adversary cannot distinguish $H$ from a random function
+ unless the bad event occurs; and, secondly, that the bad event doesn't
+ occur very often.
The latter is easier: our standard collision bound shows that the bad
 event occurs during the game with probability at most $q'(q'  1)/2$.

+ event occurs during the game with probability at most $q'(q'  1)/2^{t+1}$.
+
The former is trickier. This needs a lot more work to make it really
rigorous, but we show the idea. Assume that the bad event has not
 occurred. Consider a query $x_0, x_1, \ldots, x_{n1}$. If it's the
 same as an earlier query, then $A$ learns nothing (because it could
 have remembered the answer from last time). If it's \emph{not} a
 prefix of some previous query, then we must add a new edge to our
 graph; then either the bad event occurs or we create a new node for
 the result, and because $F$ is a random function, the answer is
 uniformly random. Finally, we consider the case where the query is a
 prefix of some earlier query, or queries. But these were computed at
 random at the time.
+ occurred. Consider a query $x_0, x_1, \ldots, x_{n1}$. If it's the same
+ as an earlier query, then $A$ learns nothing (because it could have
+ remembered the answer from last time). If it's a \emph{prefix} of some
+ earlier query, then the answer is the value of some internal node which
+ hasn't been revealed before; however, the value of that internal node was
+ chosen uniformly at random (we claim). Finally, if the query is not a
+ prefix of any previous query, then we add a new edge to our graph. If the
+ bad event doesn't occur, we must add a new node for the result, and the
+ value at that node will be uniformly random, because $F$ is a random
+ function being evaluated at a new point  this is the only time we add new
+ nodes to the graph, justifying the claim made earlier.
At the end of all of this, we see that
\[ \InSec{prf}(T^0; t, q) \le
 \InSec{prf}(F; t, q') + \frac{q'(q'  1)}{2} \]%
+ \InSec{prf}(F; t, q') + \frac{q'(q'  1)}{2^{t+1}} \]%
and hence
\[ \InSec{sufcma}(\mathcal{M}^0; t, q) \le
 \InSec{prf}(F; t, q') + \frac{q'(q'  1)}{2} + \frac{1}{2^t}. \]%
+ \InSec{prf}(F; t, q') + \frac{2 q'(q'  1) + 1}{2^{t+1}}. \]%
Now we turn our attention to $T^1$. It's clear that we can't simulate
$T^1$ very easily using an oracle for $F$, since we don't know $K$
diff git a/basics.tex b/basics.tex
index 9c7401f..3874d3c 100644
 a/basics.tex
+++ b/basics.tex
@@ 780,8 +780,9 @@ But if your cryptography is no good, you may never know.
Let $A$ be an adversary which distinguishes~$F$ from a pseudorandom
function in time~$t$, after making $q$ oracle queries. We consider a
 sequence of games $\G{i}$ played with the adversary. In each, let $S_i$ be
 the event that the adversary returns~$1$ at the end of the game.
+ sequence of games $\G{i}$ played with the adversary. In each game $\G{i}$,
+ let $S_i$ be the event that the adversary returns~$1$ at the end of the
+ game.
Game~$\G0$ is the `random function' game. We given $A$ an oracle
containing a random function $R \inr \Func{L}{L}$.

2.11.0