Universal hash function
From CRYPTUTOR
A universal hash function (UHF) is a hash function which achieves a very primitive notion of collision-resistance. Universal hash functions are also known as pairwise-independent hash functions.
[edit]
Definition
Let m and h be polynomials, and let 
be a collection of functions from m(n) bits to h(n) bits, indexed by seeds k. We say that 
is a universal hash function if it has the following properties:
- Efficiency: Hk(m) can be computed in polynomial time in the security parameter n.
- Compression: h(n) < m(n) for all n.
- 2-universality: For all
and all 
:
![\Pr_{k \gets \{0,1\}^n} [ H_k(x) = a \land H_k(y) = b ] = 1/2^{2h(n)}](/wiki/images/uploaded/math/a/a/1/aa1c49fbf5b910546ef177d837517032.png)
In other words, x and y are mapped uniformly and independently across the range of , when the seed k is chosen at random.
[edit]
Existence
The definition of UHFs is purely combinatorial -- there are no computational restrictions. Thus, many unconditional constructions of UHFs are known.
