Universal Hashing and the Carter-Wegman MAC
Stub. Universal hash functions (UHFs) — families of hash functions with a bounded collision probability for any two fixed inputs — three constructions (polynomial evaluation, CBC/cascade as computational UHFs, a parallel UHF from a small PRF), composing a UHF with a PRF to build fast MACs for long messages (the PRF(UHF) paradigm and the Carter-Wegman MAC), nonce-based MACs, and unconditionally (information-theoretically) secure one-time MACs from pairwise-unpredictable functions.
Corresponds to Chapter 7, entirely new territory. A universal hash function needs no cryptographic hardness assumption at all — just a combinatorial guarantee that any two distinct inputs collide with bounded probability — which makes hashing a long message down to a short digest with a UHF extremely fast, and then applying a PRF only to that short digest (the PRF(UHF) composition) gives a MAC for arbitrarily long messages at close to the cost of hashing alone. The Carter-Wegman MAC is the resulting concrete, highly efficient construction (used in GCM and Poly1305-based schemes), with nonce-based variants for avoiding key reuse issues. Closes with unconditionally secure one-time MACs: using a pairwise-unpredictable function instead of a PRF gives MAC security against an unbounded adversary, at the cost of being usable only once per key — the finite-key analogue of the one-time pad for authentication.
Outline (TODO — flesh out each)
- Universal hash functions (UHFs); multi-query UHFs
- Construction 1: UHFs using polynomials
- Construction 2: CBC and cascade as computational UHFs
- Construction 3: a parallel UHF from a small PRF
- PRF(UHF) composition — constructing MACs using UHFs
- The Carter-Wegman MAC
- Nonce-based MACs
- Unconditionally secure one-time MACs — pairwise unpredictable functions
- Fun application: timing attacks