What does "4-universal hash function" mean?

Question

I encountered the notion of 4-universal hash function and I cannot understand what exactly it means. This article https://en.wikipedia.org/wiki/Universal_hashing did not really help to clarify it.

Thanks!

Answer 1

Unfortunately, the jargon around this is not consistent. 4-universal hashing is 4-independent hashing.

Note that there is no such thing as a 4-universal hash function - k-independence and k-universality are a function of families of hash functions.

Answer 2

Actually, there is a pretty standard definition of a k-universal hashing, as stating here.

What is says is that if you pick any K elements in the first set, choosing uniformly a hash function from the reference K-universal family will imply a uniform distribution over all combinations of K elements in the second set.

From an informational-bayesian perspective, this means that observing any k-1 hash results won't give you any information about the k'th value: $P(h(x_k) | h(x_{k-1})...h(x_1)) = P(h(x_k))$.