Optimal random bits complexity for universal hashing
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.