# What is the definition of security of universal hashing

As a cryptographic primitive, universal hashing should have somewhat a criterion on its security. How is its (computational) security defined? Or, in other words, what "breaks" a universal hashing?

There's a variety of formal definitions, let me illustrate by giving the three most common definitions. Let $$\Pr_{h\in \mathcal{H}}[X]$$ denote the probability of event $$X$$ if $$h$$ is chosen independently and uniformly at random from set $$\mathcal{H}$$. A hash function family $$\mathcal{H}$$ is $$\epsilon$$-almost universal ($$\epsilon$$-AU) if for any $$m \neq m'$$ we have

$$\Pr_{h\in\mathcal{H}}\left[h(m) = h(m ')\right] \leq \epsilon.$$

A hash function family $$\mathcal{H}$$ is $$\epsilon$$-almost delta universal ($$\epsilon$$-ADU) if for any $$m \neq m'$$ and any $$\delta$$ we have

$$\Pr_{h\in\mathcal{H}}\left[h(m) \ominus h(m') = \delta\right] \leq \epsilon,$$ where $$\ominus$$ is subtraction in some group (e.g. subtraction mod $$n$$ or XOR).

A hash function family $$\mathcal{H}$$ is $$\epsilon$$-almost strongly universal ($$\epsilon$$-ASU) if for any $$m \neq m'$$ and any $$d, d'$$ we have

$$\Pr_{h\in\mathcal{H}}\left[h(m) = d \wedge h(m') = d'\right] \leq \epsilon.$$

If $$D$$ is the set of hash digests, we find that $$\epsilon/|D|$$-ASU implies $$\epsilon$$-ADU which in turn implies $$\epsilon$$-AU.

Or, in other words, what "breaks" a universal hashing?

All three of the above three formal definitions area bound some probability. You break a universal hash by showing that the respective event $$X$$ happens more often than the bound claims.