TransWikia.com

Low weight linear $varepsilon$-universal hash function

Cryptography Asked by JayTuma on December 2, 2021

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?

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP