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}. \]%
~mdw / doc / ips / blobdiff