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}
&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}I'm interested in constructive answers, where $f$ can explicitly designed.
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 $M = N + \lfloor (N - P)/2 \rfloor - 1$, where $P$ is the number of bits in the codomain.