Non-uniform compression-function PRF ⇒ MAC (NMAC)
Statement
Let with and , and let , with and , be its iteration keyed by the initial chaining value. NMAC on messages is
for a fixed string of bits, so the outer call takes the -bit inner output padded to one block. If the family , keyed by the chaining input under a uniform key , is a compression-function PRF against non-uniform adversaries , then NMAC is a PRF on against non-uniform adversaries, with no collision-resistance assumption on — Bel06. The reduction of Bel06 is non-uniform — GPR14. A PRF against non-uniform adversaries is a PRF against uniform ones (Non-uniform PRF ⇒ PRF) — standard, so by PRF ⇒ MAC, with canonical verification is a UF-CMA-secure MAC on .
Notes
- A uniform proof gives the same conclusion from a compression-function PRF against uniform adversaries (Compression-function PRF ⇒ MAC (NMAC, uniform proof)): if is an -secure PRF against queries and a -secure PRF against non-adaptive queries, NMAC is an -secure PRF against queries of at most blocks each — GPR14 (Theorem 1).
- BCK96 had proved NMAC a PRF assuming, besides being a PRF, that is weakly collision resistant, an assumption that fails for MD5 and SHA-1 — GPR14.