# Low weight linear $\varepsilon$-universal hash function

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?

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