-3
$\begingroup$

So as far as I know the weakly universal hashing is defined as: for any $x, y \subset U, Pr(h(x) = h(y)) \le \frac{1}{m}$ where m is a smaller number than the cardinality of $U$, and h are chosen randomly from a set of all possible hash function $H$.

I am just wondering if we choose the hash of an item randomly from the set $Z_m$, then the probability of having a hash collision is $\frac{1}{m}$ for x and y. So the weakly universal hashing is a quite strong requirement on how to choose hash function isn't it? Why?

$\endgroup$
  • $\begingroup$ You might get a quicker response for this question on StackExchange Cryptography. $\endgroup$ – William Hird Jan 21 '14 at 19:13
  • 1
    $\begingroup$ I think you mean $x,y \in U$, not $x,y \subset U$. In the standard definition, $x,y$ range over elements of $U$, not subsets of $U$. $\endgroup$ – D.W. Jan 23 '14 at 23:27
  • 1
    $\begingroup$ It's not clear what you are asking. The title asks one question. The last paragraph of your question asks another (super-vague) question. So what do you want answered? What research have you done on your own? $\endgroup$ – D.W. Jan 23 '14 at 23:28
  • 1
    $\begingroup$ universal hashing makes gives the strongest possible guarantee for pairwise collisions, but the probability of a fixed triple of elements colliding can be as high as $1/m$, while for a truly random hash it would be $1/m^2$. there are many other properties that a universal hash may not satisfy. also, this site is for research level questions, and your question is not at that level. $\endgroup$ – Sasho Nikolov Jan 24 '14 at 1:17
  • 1
    $\begingroup$ cs@SE will be more appropriate. for $1/m^2$, fix any $i \in \mathbb{Z}_m$ and let $x, y, z \in U$, $h$ a uniform random function from $U$ to $\mathbb{Z}_m$. $\Pr[h(x) = h(y) = h(z) = i] = 1/m^3$ because $h(x), h(y), h(z)$ are independent random variables. sum over all $i \in \mathbb{Z}_m$ and you are done. $\endgroup$ – Sasho Nikolov Jan 24 '14 at 20:46
3
$\begingroup$

No, "weakly universal" is not a stronger requirement than "truly random". There are hash functions that satisfy the former but not the latter, e.g., $h(x) = ax+b$ over a finite field.

As far as whether "weakly universal" is a "quite strong" requirement, I guess that depends on your definition of "quite strong", now, doesn't it?

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.