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

1 Answer 1

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, 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$
    – jbapple
    Feb 1, 2021 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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