# Is this a correct understanding of Universal Hash Functions?

I'm studying universal hash functions and have been reading several papers but now i'm focusing on Wegman and Carters original paper from 1979 (Universal classes of hash functions) and the H1 class.

1. Choose a prime $p$ that is $p >= a$
2. Let $g$ be residue modulus $b$ ($g(x) = x \pmod b$)
3. Then the $H1$ class is the set of:

$$\left\{ f_m,n \middle| m,n \in \mathbb Z_p \text{ and }m \neq 0\right\}$$

Formal Definitions:

Let $A=\{0,1,\dots,πβ1\}$ and $B={0,1,\dots,bβ1}$, with $|A|=a>b=|B|$. Define $h_{m,n}:A\to\mathbb Z_p$ and $f_{m,n}:A\to B$ such that $$h_{m,n}(x)=(mx+n\pmod p ) \quad\text{and}\quad f_{m,n}(x)=g(h_{m,n}(x))$$

For the scheme to work, we also require that $p$ is sufficiently large, which we quantify by requiring that:

$$\forall i \in B, \quad |\{ y\in \mathbb Z_p | g(y)=i \}| \leq \lceil \frac{p}{b} \rceil$$

I have been trying to work through the following example:

π΄={0,1,2,3,4,5,6,7,8,9}βπ=9

π΅={0,1,2,3,4,5}βπ=4

πβ₯πβπ=11

Then we need to fulfill the requirement:

The number of y that would be mapped by g to i must be less then βπ/πβ = β11/4β = β2.75β = 3 ?

I understand that $h_{m,n}:A\to\mathbb Z_p$ maps from $A$ to $\mathbb Z_p$ and $g$ map from Z_p to B but what elements are in Z_p if A and B is like in my example ?

And i not sure how to continue my example, do i need to do g(x) for all elements in Z_p and check how many map to i ?

-
I've tried to clean up the first half of your question, hope it worked. The first thing I notice is the definitions you give in the first section do not coincide with the values you give them in the second section - surely a=10 in your example? – figlesquidge Apr 9 '14 at 22:58
according to the defintion it is A = {0,1, ... , a-1} so maybe a is 8 then? – user12949 Apr 10 '14 at 2:35
erm... $a-1=9\implies a=9+1=10$ – figlesquidge Apr 10 '14 at 7:58
Ok then. What about my questions? – user12949 Apr 10 '14 at 13:03