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.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ You need $H: \{0,1\}^N \to \{0,1\}^P$ where $P < N$, otherwise the answer is 0, since the identity function is universal. $\endgroup$– jbappleCommented Jan 31, 2021 at 17:13
-
1$\begingroup$ 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}$? $\endgroup$– jbappleCommented Jan 31, 2021 at 21:29
-
$\begingroup$ yes sorry, corrected now. $\endgroup$– AmeerJCommented Jan 31, 2021 at 21:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ 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 $\endgroup$– AmeerJCommented Jan 31, 2021 at 20:41
-
$\begingroup$ 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. $\endgroup$– jbappleCommented Feb 1, 2021 at 0:31