$H$ is a family of weakly universal hash functions if for two elements $x,y$:

$$ P(h(x) = h(y)) \le \frac1m, $$

where $m$ is the size of the domain, and $h$ is chosen at random from $H$.

Given a hash family, how could one prove that it is weakly universal. I understand how to prove it isn't (proof by counter-example) but I cannot find any examples for when it is.

I apologise if this is a duplicate of another question. I was not able to find any examples online specifically for weakly universal hash functions.

  • $\begingroup$ See here: iuuk.mff.cuni.cz/~vesely/vyuka/1718/apx-06-en.pdf. $\endgroup$ – Yuval Filmus May 13 '18 at 12:36
  • 1
    $\begingroup$ You prove it by proving that the inequality above holds. Without knowing any specifics about what particular hash function you are dealing with, it's hard to say much more. $\endgroup$ – D.W. May 13 '18 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.