Universal hashing
A family of hash functions indexed by a secret or random key, chosen so that for any two distinct inputs, the probability of a collision is bounded above by a small, provable constant. That probability is taken over the random choice of key, not over the inputs. Carter and Wegman's original formulation is the family this spoke's one instance, polyxor128, traces its lineage to. The guarantee is unconditional; it needs no hardness assumption, unlike this spoke's SNARK corpus. But it is also keyed, and the bound holds only while the key is secret and independent of the input, which is a different security model from a public, unkeyed hash like SHA-256.
Lineage this spoke now holds an instance of
polyxor128 names NH (Krovetz and Rogaway's construction, the core of the UMAC MAC) and CLHASH (Lemire and Kaser's carryless-multiplication variant of NH) as its direct ancestors, and credits the broader technique to Thorup, Bernstein, Dietzfelbinger, Appleby (MurmurHash/CityHash-adjacent work) and others. The move all of these share is to hash fixed-size chunks with cheap key-mixed arithmetic, combine chunk hashes with a stronger structure (a polynomial hash, in PolyXOR128's case), and prove a collision bound as a function of input length. CLHASH's contribution, using hardware carryless multiplication instead of ordinary integer multiplication for the per-chunk step, is the one polyxor128 inherits directly. It is also the same primitive operation this spoke's proof-system corpus uses for a different purpose: multiplication in GF(2)[x], the polynomial ring behind binary-fields.
From hash to MAC
A universal hash alone is not safe to publish. Because the bound is a probability over the key, seeing
hash outputs can leak information about the key over many queries, and an adversary who learns the key
can construct guaranteed collisions. The standard fix, and the one polyxor128 implements as
finalize_mac, is to encrypt or otherwise re-key the hash output (there, with AES) before it leaves the
system, turning a keyed integrity check into a message authentication code safe to expose on an
untrusted channel. UMAC follows the same pattern: an NH hash, then a keyed pseudorandom function over
the result.
Where this sits in the spoke
Every other source held here is about proving a computation ran correctly (SNARKs) or hiding a program's logic (indistinguishability-obfuscation). Universal hashing is neither. It is a much older, unconditionally-secure symmetric-key primitive for detecting corruption or forgery, and polyxor128 is this spoke's first source in that family. It also gives binary-fields a second, independent example of the same field-size argument, carryless multiplication over GF(2)[x] making bit-heavy work cheap, arising outside proof systems entirely.
Related
polyxor128 · binary-fields · orson-peters · concrete-efficiency