Compression-function PRF ⇒ MAC (NMAC, uniform proof)

Standard model · GPR14 · security loss: additive: NMAC is (ε + (ℓ+1)qδ + q²/2^c)-secure against q queries of at most ℓ blocks, for f ε-secure against q adaptive and δ-secure against q non-adaptive queries (Theorem 1)

Statement

Let with and , let , with and , be its cascade on , and let

whose outer call takes the -bit cascade output padded to one -bit block. If the family , under a uniform key , is an -secure compression-function PRF against queries and a -secure one against non-adaptive queries, then NMAC is an -secure PRF against queries of at most blocks each, by a uniform reduction — GPR14 (Theorem 1). A non-adaptive distinguisher is an adaptive one, and is negligible for polynomial since , so for polynomial and NMAC is a PRF whenever is one, and by PRF ⇒ MAC, with canonical verification is a UF-CMA-secure MAC on — standard.

Notes

  • For the bound is essentially tight: there is an for which NMAC has an attack with advantage — GPR14.
  • The earlier proof from the same assumption uses a non-uniform reduction, and so needs to be a compression-function PRF against non-uniform adversaries (Non-uniform compression-function PRF ⇒ MAC (NMAC)) — Bel06, GPR14.