3
$\begingroup$

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.

$\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$ – jbapple Jan 31 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$ – jbapple Jan 31 at 21:29
  • $\begingroup$ yes sorry, corrected now. $\endgroup$ – AmeerJ Jan 31 at 21:52
2
$\begingroup$

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.

$\endgroup$
2
  • $\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$ – AmeerJ Jan 31 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$ – jbapple Feb 1 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.