Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:




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 ?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.