PRF ⇒ nonce-based MAC (Wegman–Carter)

Fully-black-box reduction · standard model · folklore · security loss: for a forger making tag queries, with making queries

Statement

Let be a PRF with range whose domain has size superpolynomial in , as the nonce space of a nonce-based MAC does, write , and let be an efficiently sampleable and computable -almost XOR-universal family of functions . The Wegman–Carter MAC has key with and , nonce space , and

For every efficient making queries in the UF-CMA game for nonce-based MACs there is an efficient making queries with

so for negligible the Wegman–Carter MAC is a UF-CMA-secure nonce-based MAC — folklore.

Sketch

samples , answers each query of with , and outputs iff ‘s output has unqueried and . With a uniformly random function as , the tags under distinct nonces are independent uniform values that carry no information about . A forgery under an unused nonce succeeds with probability , since is uniform given ‘s view, and for every -almost XOR-universal family into . One under a used nonce needs for , which has probability at most .

Notes

  • With a block cipher, a PRP on in place of , the switching lemma applied to ‘s queries adds at most to the bound — standard.