author mdw Wed, 31 Oct 2001 09:33:59 +0000 (09:33 +0000) committer mdw Wed, 31 Oct 2001 09:33:59 +0000 (09:33 +0000)
 auth-mac.tex patch | blob | blame | history

index 8b4eb8a..cd3defa 100644 (file)

If $F_K\colon \{0, 1\}^* \to \{0, 1\}^L$ is a $(t, q, \epsilon)$-secure
PRF, then it's also a $(t', q_T, q_V, \epsilon')$-secure MAC, with $q = q_T - + q_V + 1$, $t = t' + O(q)$, and $\epsilon \le \epsilon' + (q_V + 1) + + q_V + 1$, $t = t' + O(q)$, and $\epsilon' \le \epsilon + (q_V + 1) 2^{-L}$.  The constant hidden by the $O(\cdot)$ is small and depends on the
model of computation.

$A$ does when it's given a random function.  But we know that the
probability of it successfully guessing the MAC for a message for which it
didn't query $T$ can be at most $(q_V + 1) 2^{-L}$.  So
-  $\Adv{prf}{F}(D) \le \Succ{suf-cma}{F}(A) - (q_V + 1) 2^{-L}.$
+  $\Adv{prf}{F}(D) \ge \Succ{suf-cma}{F}(A) - (q_V + 1) 2^{-L}.$
Let $q = q_T + q_V + 1$; then counting, rearranging, maximizing yields
$\InSec{suf-cma}(F; t, q_T, q_V) \le \InSec{prf}(F; t + O(q), q) + (q_V + 1)2^{-L}.$%