<p>Yes. <a href="http://cr.yp.to/bib/1981/wegman.html" rel="nofollow">Wegman and Carter's "New hash functions and their use in authentication and set equality"</a> (<a href="http://www.fi.muni.cz/~xbouda1/teaching/2009/IV111/Wegman_Carter_1981_New_hash_functions.pdf" rel="nofollow">mirror</a>) 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.</p>

<p>This is sometimes called "tree hashing", and it is used in <a href="https://eprint.iacr.org/2004/319.pdf" rel="nofollow">"Badger - A Fast and Provably Secure MAC" by Boesgaard et al</a>.</p>

CC BY-SA 3.0
2013-05-04T21:09:22.610Z
2015-12-14T14:36:20.253Z
2015-12-14T14:36:20.253Z
jbapple
<p>If you want something fast and that you can use in practice, you might look at the cryptographic literature.  For instance, <a href="http://cr.yp.to/mac.html" rel="nofollow">poly1305</a> and <a href="https://en.wikipedia.org/wiki/UMAC" rel="nofollow">UMAC</a> 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.</p>

<p>Poly1305 works like your first type of hash (called a <em>polynomial evaluation hash</em>), 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.</p>

<p>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:</p>

<ul>
<li>LFSR-based Hashing and Authentication. Hugo Krawczyk. CRYPTO 1994.</li>
</ul>

<p>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$.</p>

CC BY-SA 3.0
2013-10-29T13:35:02.140Z
I appreciate your references, but this answer does not address the question.
jbapple
CC BY-SA 3.0
2013-05-06T01:39:02.403Z
2013-05-06T01:53:40.367Z
2013-05-06T01:53:40.367Z
D.W.
<p>Here are two families of hash functions on strings $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$:</p>

<ol>
<li><p>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$.</p></li>
<li><p>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}$</p></li>
</ol>

<p>$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.</p>

<p>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.</p>

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

<ds.data-structures><randomness><hash-function>
Almost universal string hashing in $Z_{2^n}$ and sublinear space
jbapple
# Almost universal string hashing in $Z_{2^n}$ and sublinear space

(Asked by: username_0 on 2013-04-09)

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?

**Tags:** ds.data-structures, randomness, hash-function


---

## 2 answers

### Answer by username_0 on 2013-05-04. Score: 5 | Accepted answer

Yes. [Wegman and Carter's "New hash functions and their use in authentication and set equality"](http://cr.yp.to/bib/1981/wegman.html) ([mirror](http://www.fi.muni.cz/~xbouda1/teaching/2009/IV111/Wegman_Carter_1981_New_hash_functions.pdf)) 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](https://eprint.iacr.org/2004/319.pdf).


---

### Answer by username_1 on 2013-05-06. Score: -1

If you want something fast and that you can use in practice, you might look at the cryptographic literature. For instance, [poly1305](http://cr.yp.to/mac.html) and [UMAC](https://en.wikipedia.org/wiki/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$.

> **Comments:**
> **username_0**: I appreciate your references, but this answer does not address the question.  

---

