3
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.