$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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.