Skip to main content
Cryptography

Return to Question

Tweeted twitter.com/StackCrypto/status/1338453706854060034
edited title
Link
OuttaSpaceTime
OuttaSpaceTime
  • 195
  • 1
  • 6

Why does the hashfamily of all functions with $\{h \in H_0 | h:U \rightarrow V\}$ would satisfy universal hashing?

added 22 characters in body
Source Link
OuttaSpaceTime
OuttaSpaceTime
  • 195
  • 1
  • 6

I read in our scriptuniversity lecture on hashing that it would be good (even though it is way to space intensive) if we could take the set of all function from $U \rightarrow V$ to satisfy the following universal hashing condition: for all $\forall x,y\in U$ so that $x≠y$, we have $Pr[h(x)=h(y)]≤\frac{1}{|V|}$

I actually don´t understand why the set of all functions would satisfy our condition. I can definitively see that there are some function which fit this condition, but I can think of other functions which dont meet the condition. So I would have to make a statement about average probabilty over the set of all functions, but how could something like this be defined precisely?

Or am I taking something wrong here and the Set of all functions wouldn´t meet the condition, but would actually be better that the condition taking the case that h is taking randomly from H? Even if so it seems to come down to the same problem.

I read in our script that it would be good (even though it is way to space intensive) if we could take the set of all function from $U \rightarrow V$ to satisfy the following universal hashing condition: for all $\forall x,y\in U$ so that $x≠y$, we have $Pr[h(x)=h(y)]≤\frac{1}{|V|}$

I actually don´t understand why the set of all functions would satisfy our condition. I can definitively see that there are some function which fit this condition, but I can think of other functions which dont meet the condition. So I would have to make a statement about average probabilty over the set of all functions, but how could something like this be defined precisely?

Or am I taking something wrong here and the Set of all functions wouldn´t meet the condition, but would actually be better that the condition taking the case that h is taking randomly from H? Even if so it seems to come down to the same problem.

I read in our university lecture on hashing that it would be good (even though it is way to space intensive) if we could take the set of all function from $U \rightarrow V$ to satisfy the following universal hashing condition: for all $\forall x,y\in U$ so that $x≠y$, we have $Pr[h(x)=h(y)]≤\frac{1}{|V|}$

I actually don´t understand why the set of all functions would satisfy our condition. I can definitively see that there are some function which fit this condition, but I can think of other functions which dont meet the condition. So I would have to make a statement about average probabilty over the set of all functions, but how could something like this be defined precisely?

Or am I taking something wrong here and the Set of all functions wouldn´t meet the condition, but would actually be better that the condition taking the case that h is taking randomly from H? Even if so it seems to come down to the same problem.

Source Link
OuttaSpaceTime
OuttaSpaceTime
  • 195
  • 1
  • 6

Why does the hashfamily of all functions with $\{h \in H_0 | h:U \rightarrow V\}$ would satisfy universal hashing?

I read in our script that it would be good (even though it is way to space intensive) if we could take the set of all function from $U \rightarrow V$ to satisfy the following universal hashing condition: for all $\forall x,y\in U$ so that $x≠y$, we have $Pr[h(x)=h(y)]≤\frac{1}{|V|}$

I actually don´t understand why the set of all functions would satisfy our condition. I can definitively see that there are some function which fit this condition, but I can think of other functions which dont meet the condition. So I would have to make a statement about average probabilty over the set of all functions, but how could something like this be defined precisely?

Or am I taking something wrong here and the Set of all functions wouldn´t meet the condition, but would actually be better that the condition taking the case that h is taking randomly from H? Even if so it seems to come down to the same problem.