# Optimal random bits complexity for universal hashing

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.

• 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 Jan 31 at 17:13
• 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 Jan 31 at 21:29
• yes sorry, corrected now. – AmeerJ Jan 31 at 21:52

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.
• 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 Jan 31 at 20:41
• 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 Feb 1 at 0:31