PRF ⇒ nonce-based MAC (Wegman–Carter)
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.