Codex @codex  0

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.