g^{(i+1)}(x) = g_0(x) \cat g^{(i)}(g_1(x)). \]%
Relate the security of $g^{(i)}$ to that of $g$.
\answer%
+ The description of the function $g^{(i)}$ is deliberately terse and
+ unhelpful. It probably helps understanding if you make a diagram.
+
Let $A$ be an adversary running in time $t$ and attacking $g^{(i+1)}$.
Firstly, we attack $g$: consider adversary $B(y)$: \{ \PARSE $y$ \AS $y_0,
k\colon y_1$; $z \gets g^{(i)}$; $b \gets A(y_0 \cat z)$; \RETURN $b$;~\}.
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}$.
\end{proof}
\begin{slide}
+ \head{Hash functions, \seq: Merkle-Damg\aa{}rd iterated hashing (cont.)}
+
+ \vfil
+ \[ \begin{graph}
+ []!{0; <2cm, 0cm>: <0cm, 0.9cm>::}
+ *+=(1, 0)+[F]{\mathstrut I_0 = I} :[d] *+[F]{F}="f"
+ [urrr] *+=(3, 0)+[F]{\mathstrut x_0} :`d"f" "f" :[d]
+ *+=(1, 0)+[F]{\mathstrut I_1} :[d] *+[F]{F}="f"
+ [urrr] *+=(3, 0)+[F]{\mathstrut x_1} :`d"f" "f" :@{-->}[dd]
+ *+=(1, 0)+[F]{\mathstrut I_{n-1}} :[d] *+[F]{F}="f"
+ [urrr] *+=(3, 0)+[F]{\mathstrut x_{n-1}} :`d"f" "f" :[d]
+ *+=(1, 0)+[F:thicker]{\mathstrut H(x) = I_n}
+ \end{graph} \]
+ \vfil
+\end{slide}
+
+\begin{slide}
\head{Hash functions, \seq: any-collision resistance}
The statement usually made about a `good' hash function $h$ is that it