According to the definition, an $\varepsilon$-universal linear hash function family, given a field $\mathbb{F}$, is a set of linear transformations $\mathcal{H} \subseteq \mathbb{F}^{m,n}$ such that for any $\mathbf{v} \in \mathbb{F}^n \setminus \{0 \}$ if $H \sim U(\mathcal{H})$ $$ \Pr[ H \mathbf{v} = 0 ] \leq \varepsilon. $$ My question is whether it is possible to have an $\varepsilon$-universal linear hash function family with low Hamming weight (over small order field, say $\mathbb{F}_2$), that is, calling $w( \cdot )$ the hamming weight of a vector over $\mathbb{F}^n$, we want to have a constant $M$ such that for "almost any" $H \in \mathcal{H}$ $$ w(H \mathbf{v}) \leq M \cdot w(\mathbf{v}) $$

Now, I've ruled out the possibility to have $M = 1$ as this implies that the column of $M$ need to be vectors of the kind $\alpha \cdot e_i = (0, \ldots, \alpha, \ldots, 0)$ in the $i$-th position and one of the vectors $e_1$, $e_2$ or $e_1 - e_2$ is going to be mapped to zero with non negligible probability. Can one do better? For instance can $M = \Theta(\log(n))$ or $M = \Theta(\sqrt{n})$ be achieveable? Is there any result in the positive direction?

  • 1
    $\begingroup$ Do you mean any $\mathbf{v}\in\mathbb{F}^n\setminus \{0\}$? $\endgroup$
    – Mark Schultz-Wu
    Commented Jul 22, 2020 at 23:00
  • 1
    $\begingroup$ Rogaway's bucket hash seems like something that could be modified to accomplish this. It is pretty much multiplication by a random sparse matrix. $\endgroup$ Commented Jul 23, 2020 at 21:22


Your Answer

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

Browse other questions tagged or ask your own question.