# Almost universal string hashing in $Z_{2^n}$ and sublinear space

Here are two families of hash functions on strings $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$:

1. For $p$ prime and $x_i \in \mathbb{Z_p}$, $h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$ for $a \in \mathbb{Z}_p$. Dietzfelbinger et al. showed in "Polynomial Hash Functions Are Reliable" that $\forall x \neq y, P_a(h^1_a(x) = h^1_a(y)) \leq m/p$.

2. For $x_i \in \mathbb{Z}_{2^b}$, $h^2_{\vec{a} = \langle a_0 a_1 a_2 \dots a_{m+1}\rangle}(\vec{x}) = (a_0 + \sum a_{i+1} x_i \bmod 2^{2b}) \div 2^b$ for $a_i \in \mathbb{Z}_{2^{2b}}$. Lemire and Kaser showed in "Strongly universal string hashing is fast" that this family is 2-independent. This implies that $\forall x \neq y, P_\vec{a}(h^2_\vec{a}(x) = h^2_\vec{a}(y)) = 2^{-b}$

$h^1$ uses only $\lg p$ bits of space and bits of randomness, while $h^2$ uses $2 b m + 2 b$ bits of space and bits of randomness. On the other hand, $h^2$ operates over $\mathbb{Z}_{2^{2b}}$, which is fast on actual computers.

I'd like to know what other hash families are almost-universal (like $h^1$), but operate over $\mathbb{Z}_{2^b}$ (like $h^2$), and use $o(m)$ space and randomness.

Does such a hash family exist? Can its members be evaluated in $O(m)$ time?

Yes. Wegman and Carter's "New hash functions and their use in authentication and set equality" (mirror) shows a scheme meeting the requirements stated (almost universal, over $\mathbb{Z}_{2^b}$, sublinear space and randomness, linear evaluation time) based on a small number of hash functions drawn from a strongly universal family.

This is sometimes called "tree hashing", and it is used in "Badger - A Fast and Provably Secure MAC" by Boesgaard et al.

If you want something fast and that you can use in practice, you might look at the cryptographic literature. For instance, poly1305 and UMAC are fast, and there are many others. Because 2-universal hashes are useful for cryptography, cryptographers have studied many constructions and found ones that are extremely efficient.

Poly1305 works like your first type of hash (called a polynomial evaluation hash), working modulo $2^{130}-5$. The scheme shows clever tricks to make this run very fast on a modern computer. The amount of randomness is small: 128 bits.

If you want to reduce the amount of randomness and don't care so much about practicality, you might look at the following research paper:

• LFSR-based Hashing and Authentication. Hugo Krawczyk. CRYPTO 1994.

Krawczyk describes a scheme to reduce the amount of randomness basically by letting $a_i$ be the $i$th row of a Toeplitz matrix. However, the Krawczyk scheme works over $GF(2^b)$, not arithmetic modulo $2^b$.

• I appreciate your references, but this answer does not address the question. – jbapple Oct 29 '13 at 13:35