<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2014-01-23T23:29:31.927Z
2014-01-23T23:29:31.927Z
D.W.
<p>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$.</p>

<p>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?</p>

CC BY-SA 3.0
2014-01-21T19:13:13.173Z
You might get a quicker response for this question on StackExchange Cryptography.
William Hird
CC BY-SA 3.0
2014-01-23T23:27:24.543Z
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$.
D.W.
CC BY-SA 3.0
2014-01-23T23:28:35.203Z
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?
D.W.
CC BY-SA 3.0
2014-01-24T01:17:09.877Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-01-24T19:41:10.640Z
@D.W. oh sorry for the notation, it is a careless mistake, the way I ask it might not be very informative and clear, sorry about that too.
Boyu Fang
CC BY-SA 3.0
2014-01-24T19:42:25.570Z
@SashoNikolov, sorry, did not know that before, thought this site is like stackoverflow where people ask all level of questions about theoretical computer science. I might try cs.stackexchange next time.
Boyu Fang
CC BY-SA 3.0
2014-01-24T19:44:09.593Z
@SashoNikolov why it is $1/m^2$? I don't get it.
Boyu Fang
CC BY-SA 3.0
2014-01-24T20:46:00.870Z
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.
Sasho Nikolov
<ds.algorithms><ds.data-structures><hash-function>
Isn't weakly universal hashing even a stronger than truly random?
Boyu Fang
# Isn't weakly universal hashing even a stronger than truly random?

(Asked by: username_0 on 2014-01-20)

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?

**Tags:** ds.algorithms, ds.data-structures, hash-function
> **Comments:**
> **username_1**: You might get a quicker response for this question on StackExchange Cryptography.  
> **username_2**: 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$.  
> **username_2**: 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?  
> **username_3**: 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.  
> **username_0**: @D.W. oh sorry for the notation, it is a careless mistake, the way I ask it might not be very informative and clear, sorry about that too.  
> **username_0**: @SashoNikolov, sorry, did not know that before, thought this site is like stackoverflow where people ask all level of questions about theoretical computer science. I might try cs.stackexchange next time.  
> **username_0**: @SashoNikolov why it is $1/m^2$? I don't get it.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-01-23. Score: 3

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?


---

