<p>I believe the best known bound is in Woelfel's &quot;Efficient strongly universal and optimally universal hashing&quot;, Theorem 5, which presents a set with <span class="math-container">$M = N + \lfloor (N - P)/2 \rfloor - 1$</span>, where <span class="math-container">$P$</span> is the number of bits in the codomain.</p>

CC BY-SA 4.0
2021-01-31T20:41:34.357Z
I thought of adding a constraint that $P(H(a)=h)=2^{-N}$ so that the identity cannot be a solution, but thought that your suggestion makes the problem more interesting, so changed it back
AmeerJ
CC BY-SA 4.0
2021-02-01T00:31:44.283Z
As you implied, this also applied when $P = N$, in which case the hash function is just multiplication by an odd number. Since this is a bijection, its collision probability is still $0$, which also implies it is uniform.
jbapple
CC BY-SA 4.0
2021-01-31T17:42:33.713Z
2021-01-31T17:42:33.713Z
jbapple
<p>Let <span class="math-container">$Q_N:=\{0,1\}^N$</span> denote the <span class="math-container">$N$</span>-dimensional Hamming cube. Let <span class="math-container">$a\in Q^N$</span> and <span class="math-container">$X\sim\mathrm{Unif}(Q^M)$</span> be input and random bits respectively, and function <span class="math-container">$f$</span> maps the the joint space to the <span class="math-container">$P$</span>-dimensional cube <span class="math-container">$f:Q^{N+M}\to Q^P$</span>. Defining hash function as <span class="math-container">$H(a):=f(a,X)$</span>, what is the optimal <span class="math-container">$M$</span> if we require hash <span class="math-container">$H$</span> to be universal and uniform?
<span class="math-container">\begin{align}
&amp;\Pr(H(a)=H(b))\le 2^{-P} &amp;&amp;\forall a,b\in Q^N, a\neq b\\
&amp;\Pr(H(a)=c)=2^{-P} &amp;&amp;\forall c\in Q^P,a\in Q^N
\end{align}</span>I'm interested in constructive answers, where <span class="math-container">$f$</span> can explicitly designed.</p>

CC BY-SA 4.0
2021-01-31T17:13:41.527Z
You need $H: \{0,1\}^N \to \{0,1\}^P$ where $P < N$, otherwise the answer is 0, since the identity function is universal.
jbapple
CC BY-SA 4.0
2021-01-31T21:29:33.867Z
If $N > P$, it cannot be the case that $\Pr[H(a) = H(b)] \leq 2^{-N}$. The best you can get, as Woelfel shows in "Efficient strongly universal and optimally universal hashing", is $(2^N - 2^P)/(2^{N+P} - 2^P)$. Did you maybe mean $\Pr[H(a) = H(b)] \leq 2^{-P}$?
jbapple
CC BY-SA 4.0
2021-01-31T21:52:25.843Z
yes sorry, corrected now.
AmeerJ
<hash-function><pseudorandomness>
Optimal random bits complexity for universal hashing
AmeerJ
# Optimal random bits complexity for universal hashing

(Asked by: username_0 on 2021-01-31)

Let $Q\_N:=\{0,1\}^N$ denote the $N$-dimensional Hamming cube. Let $a\in Q^N$ and $X\sim\mathrm{Unif}(Q^M)$ be input and random bits respectively, and function $f$ maps the the joint space to the $P$-dimensional cube $f:Q^{N+M}\to Q^P$. Defining hash function as $H(a):=f(a,X)$, what is the optimal $M$ if we require hash $H$ to be universal and uniform?
\begin{align}
&\Pr(H(a)=H(b))\le 2^{-P} &&\forall a,b\in Q^N, a\neq b\\
&\Pr(H(a)=c)=2^{-P} &&\forall c\in Q^P,a\in Q^N
\end{align}I'm interested in constructive answers, where $f$ can explicitly designed.

**Tags:** hash-function, pseudorandomness
> **Comments:**
> **username_1**: You need $H: \{0,1\}^N \to \{0,1\}^P$ where $P < N$, otherwise the answer is 0, since the identity function is universal.  
> **username_1**: If $N > P$, it cannot be the case that $\Pr[H(a) = H(b)] \leq 2^{-N}$. The best you can get, as Woelfel shows in "Efficient strongly universal and optimally universal hashing", is $(2^N - 2^P)/(2^{N+P} - 2^P)$. Did you maybe mean $\Pr[H(a) = H(b)] \leq 2^{-P}$?  
> **username_0**: yes sorry, corrected now.  

---

## 1 answers

### Answer by username_1 on 2021-01-31. Score: 2 | Accepted answer

I believe the best known bound is in Woelfel's "Efficient strongly universal and optimally universal hashing", Theorem 5, which presents a set with $M = N + \lfloor (N - P)/2 \rfloor - 1$, where $P$ is the number of bits in the codomain.

> **Comments:**
> **username_0**: I thought of adding a constraint that $P(H(a)=h)=2^{-N}$ so that the identity cannot be a solution, but thought that your suggestion makes the problem more interesting, so changed it back  
> **username_1**: As you implied, this also applied when $P = N$, in which case the hash function is just multiplication by an odd number. Since this is a bijection, its collision probability is still $0$, which also implies it is uniform.  

---

