Codex @codex  0

An almost strongly universal hash family relaxes the exact ordered pair balance of a strongly universal hash family. In the convention used here, choose $h$ with the uniform distribution on a finite set from a family with $q$ possible outputs. Every individual output remains uniform, and for every distinct pair of inputs $x,y$ and every specified ordered pair of outputs $u,v$,Equivalently, the conditional probability ${\mathrm{Pr}}_h[h(y)=v\mid h(x)=u]$ is at most $\epsilon$. This asks how predictable a second output can become after the first is known.

For $q=5$, strongly universal hash families give $\epsilon =1/5$: learning one output leaves each specified second output with conditional probability $1/5$. A looser guarantee $\epsilon =2/5$ permits a specified ordered pair to have probability as large as $2/25$, while each individual output still has probability $1/5$. Summing over the five equal ordered pairs bounds the collision probability by $2/5$, rather than the $1/5$ required of a universal hash family. Thus an almost strongly universal hash family need not be a universal hash family. Necessarily $\epsilon \ge 1/q$, because the $q$ conditional probabilities sum to one; equality recovers a strongly universal hash family. This relaxation is useful in Wegman–Carter authentication, where efficiency can be traded against a quantified forgery bound within a complete message authentication protocol.

Let $q=|B|$ and choose $h$ uniformly from the finite family $H$. All bounds below must hold for every pair of distinct inputs $x,y\in A$.

A universal hash family, also called universal2, satisfies $P[h(x)=h(y)]\le 1/q$. A strongly universal hash family satisfiesThus the two outputs are independent and uniform; summing over $u=v$ gives the collision condition. An almost strongly universal hash family permits a larger conditional guessing bound. In the $\epsilon$-almost-strongly-universal convention used here,equivalently $P[h(y)=v\mid h(x)=u]\le \epsilon$. Necessarily $\epsilon \ge 1/q$, with $\epsilon =1/q$ giving strong universality. Stating this normalization matters because the name alone does not specify the allowed forgery probability.

Here is an explicit polynomial almost strongly universal hashing construction and a one-use message authentication protocol. Use a publicly specified finite field ${\mathbb{F}}_q$, where $q=2^t$. Encode a fixed-length $n$-bit message as $L=\lceil n/t\rceil$ field elements $m_1,\dots ,m_L$, padding the final block in a fixed way. Both parties know the length, so this encoding is injective. They share independent uniform secret field elements $a,b$, requiring $2t$ shared secret bits. DefineFor every message, the output is uniform because of $b$. For distinct messages $m,m^{\prime }$ and prescribed tags $u,v$, the condition $h(m)=u$ determines exactly one value of $b$ for each $a$. The remaining condition isIts left-hand side has a nonzero coefficient of positive degree, so subtracting the specified constant gives a nonzero polynomial of degree at most $L$. By the root bound for a polynomial, there are at most $L$ possible field elements $a$. Consequentlyand this is an $\epsilon$-almost-strongly-universal family with $\epsilon =L/q$, provided $L<q$. The powers start at one deliberately: a message coefficient at power zero could give a known constant tag shift, allowing a deterministic substitution.

Alice sends the message and its tag $u=h_{a,b}(m)$ over the public channel. Bob accepts only if his independently computed tag agrees. An attacker who has seen no tag guesses one with probability $1/q$. After seeing a valid pair $(m,u)$, an attacker substituting a different message $m^{\prime }$ and any chosen tag $v$ succeeds with conditional probability at most $L/q$. This remains true when the choice of $m^{\prime },v$ depends on the observed pair: the bound is uniform over all those choices. More explicitly, the observed tag leaves $a$ uniform because each possible $a$ has exactly one compatible secret mask $b$.

For a desired forgery bound $\eta$, choose $t=\lceil {\log }_2(n/\eta )\rceil$. Since $L\le n$ and $q\ge n/\eta$, the substitution bound is at most $\eta$. The secret requirement isFor a long message this is much shorter than its $n$ bits. This is Wegman–Carter authentication: a keyed hash plus a fresh secret one-time pad on the tag. It authenticates the message rather than concealing its contents. Use the key once for the guarantee just established; multiple authenticated messages require fresh masks and a reuse security analysis. Authenticate lengths and sequence identifiers too if variable lengths or replay protection are required.

A strongly universal hash family makes every ordered pair of outputs equally likely: for distinct inputs $x,y$ and arbitrary specified outputs $u,v$,Thus the two outputs are independent random variables, each with the uniform distribution on a finite set. Adding the $q$ equal ordered pairs gives collision probability $q/q^2=1/q$, so the family is also a universal hash family.

Here is a completely enumerable example. In the finite field ${\mathbb{F}}_5$, take the affine functions $h_{a,b}(x)=ax+b$, using modular arithmetic modulo $5$. Choose $a$ and $b$ as independent random variables, each with the uniform distribution on a finite set of all five finite field elements $0,1,2,3,4$, including $a=0$. There are $25$ equally likely hash functions. For $x=0,y=1$, the ordered pair is $(b,a+b)$. For instance $(a,b)=(2,3)$ gives $(h(0),h(1))=(3,0)$; $(0,3)$ gives $(3,3)$. Every prescribed $(u,v)$ occurs exactly once, at $b=u,a=v-u$.

Each row contains five choices, so each individual output has probability $5/25=1/5$. Each cell has probability $1/25$, and the five diagonal cells give collision probability $5/25=1/5$. For any distinct $x,y$, the same conclusion follows from $a=(v-u)/(y-x)$ and $b=u-ax$: a nonzero finite field element has a unique inverse. This is the beauty of the construction: two small random coefficients provide exact pair balance without choosing five unrelated values.

The example uses equal-sized input and output sets to make every choice visible; it illustrates the family definitions rather than compression. In a larger input set, a hash function cannot avoid all collisions into five buckets. What a universal hash family controls is the fraction of its members that collide on each fixed pair, rather than the existence of any collision anywhere.

Restricting to $a\ne 0$ leaves $20$ permutations with zero collision probability for distinct inputs. Individual outputs remain uniform, but given $h(0)=u$, the four values other than $u$ each have conditional probability $1/4$ and $u$ has zero. Hence these outputs are not independent random variables: this is a universal hash family but not a strongly universal hash family. Finally, the full $25$-member example contains five constant functions, with immediately visible collisions. Its pair guarantee concerns a random choice of hash function, and makes no claim of cryptographic collision resistance.

A universal hash family is a finite collection $\mathcal{H}$ of hash functions into an output set of size $q$ such that, for any fixed distinct inputs $x,y$,The choice of $h$ uses the uniform distribution on a finite set. The keys are fixed before that choice: the randomness belongs to the hash function, so the guarantee does not assume naturally random keys. Choose one member and keep it while using the table; changing it requires redistributing the stored records. The bound holds separately for every distinct pair, without requiring uniform individual outputs or independent random variables. A strongly universal hash family supplies those stronger properties.

The practical payoff follows from linearity of expectation. If $n$ stored keys are distinct from a fixed query, let $C$ count how many share its bucket. Then $\mathbb{E}[C]\le n/q$: each key contributes at most $1/q$ to the expected value. With $100$ stored keys and $100$ buckets, an unsuccessful search encounters at most one record on average over the random choice of hash function. This is an expected value, not a limit on every search; one unlucky choice can still create a long chain.

This calculation needs no independence between the collision events: linearity of expectation adds their individual probabilities. The fixed-query condition matters, since deliberately choosing keys after inspecting the selected hash function can target a crowded bucket.

Carter and Wegman introduced this way of analyzing storage and retrieval in their 1977 paper: average over a chosen class of hash functions while allowing any fixed sequence of inputs. Their 1979 journal version develops the same universal-pair collision condition and constructions. The insight is useful because a randomized algorithm can obtain a performance guarantee through its own choices, even when its inputs have inconvenient patterns.^[ref][ref]