-\begin{slide}
- \topic{a MAC}
- \head{Universal hashing, 6: a MAC}
-
- Suppse that $H\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^l$ is an
- almost universal hash fucntion, and $F\colon \{0, 1\}^{k'} \times \{0,
- 1\}^l \to \{0, 1\}^L$ is a PRF\@. Define a MAC $\Xid{\mathcal{M}}{UH}^{H,
- F} = (\Xid{T}{UH}^{H, F}, \Xid{V}{UH}^{H, F})$ where:
- \begin{eqnarray*}[rl]
- \Xid{T}{UH}^{H, F}_{K, K'}(m) &= F_{K'}(H_K(m)) \\
- \Xid{V}{UH}^{H, F}_{K, K'}(m, \tau) &= \begin{cases}
- 1 & if $\tau = F_{K'}(H_K(m))$ \\
- 0 & otherwise
- \end{cases}.
- \end{eqnarray*}
- We have
- \begin{eqnarray*}[Ll]
- \InSec{suf-cma}(\Xid{\mathcal{M}}{UH}^{H, F}; t, q_T, q_V) \\
- & \le
- (q_V + 1) \biggl(\InSec{prf}(F; t, q_T + 1) + \frac{1}{2^L} +
- \frac{q_T(q_T - 1)}{2} \cdot \InSec{uh}(H)\biggr).
- \end{eqnarray*}
-\end{slide}
-
-\begin{proof}
- We shall prove the result for $q_V = 0$ and $q_T = q$, and appeal to the
- earlier result on verification oracles.
-
- Suppose $A$ attacks the scheme $\Xid{\mathcal{M}}{UH}^{H, F}$ in time $t$,
- issuing $q$ tagging queries. Consider a distinguisher $D$, constructed
- from a forger $A$:
- \begin{program}
- Distinguisher $D^{F(\cdot)}$: \+ \\
- $K \getsr \{0, 1\}^k$; \\
- $\Xid{T}{list} \gets \emptyset$; \\
- $(m, \tau) \gets A^{\id{tag}(K, \cdot)}$; \\
- \IF $m \notin \Xid{T}{list} \land \tau = F(H_K(m))$
- \THEN \RETURN $1$; \\
- \ELSE \RETURN $0$; \- \\[\smallskipamount]
- Oracle $\id{tag}(K, m)$: \+ \\
- $\Xid{T}{list} \gets \Xid{T}{list} \cup \{m\}$; \\
- \RETURN $F(H_K(m))$; \- \\[\smallskipamount]
- \end{program}
- Note that $A$ isn't provided with a verification oracle: that's because we
- didn't allow it any verification queries.
-
- We can see immediately that
- \[ \Pr[K \getsr \{0, 1\}^{k'} : D^{F_K(\cdot)} = 1] =
- \Succ{suf-cma}{\Xid{\mathcal{M}}{UH}^{H, F}}(A). \]%
-
- We must now find an upper bound for $\Pr[F \getsr \Func{l}{L} :
- D^{F(\cdot)}]$. Suppose that the adversary returns the pair $(m^*,
- \tau^*)$, and that its tagging oracle queries and their answers are $(m_i,
- \tau_i)$ for $0 \le i < q$. Consider the event $C$ that $H_K(m) =
- H_K(m')$ for some $m \ne m'$, with $m, m' \in \{m^*\} \cup \{\,m_i \mid 0
- \le i < q\,\}$.
-
- If $C$ doesn't occur, then $F$ has not been queried before at $H_K(m)$, but
- there's a $2^{-L}$ probability that the adversary guesses right anyway. If
- $C$ does occur, then we just assume that the adversary wins, even though it
- might not have guessed the right tag.
-
- By our result on the collision game, $\Pr[C] \le q \cdot \InSec{uh}(H)$.
- Then
- \[ \Succ{prf}{F}(D) \ge
- \Succ{suf-cma}{\Xid{\mathcal{M}}{UH}^{H, F}}(A) -
- \frac{1}{2^L} - \frac{q(q - 1)}{2} \cdot \InSec{uh}(H). \]%
- The result follows.
-\end{proof}
+\begin{exercise}
+ Show how to extend the \emph{range} of a PRF. Specifically, suppose you're
+ given a PRF $F\colon \keys{F} \times \{0, 1\}^L \to \{0, 1\}^t$, but want
+ an $l$-bit output. Show how to achieve this.
+\answer
+ There are two obvious techniques.
+ \begin{enumerate}
+ \item Suppose we have a PRG $G\colon \{0, 1\}^t \to \{0, 1\}^l$. Then we
+ can easily use $G \compose F$; it's easy to see how this is secure.
+ Indeed, we can use $F$ itself as a PRG, by defining $G(x) = F_x(0) \cat
+ F_x(1) \cat \cdots$.
+ \item Let $m = \lceil \log_2 (l/t) \rceil$. Use the construction from the
+ slide to build a PRF $F'$ with domain $\{0, 1\}^{L+m}$. Then we define
+ $F''_K(x) = F'_K(x \cat 0) \cat F'_K(x \cat 1) \cat \cdots \cat F'_K(x
+ \cat m - 1)$.
+ \end{enumerate}
+\end{exercise}
~mdw / doc / ips / blobdiff