Comment by thomasahle

I don't know what happened to the URL, but it's supposed to link to this paper: https://www.gwizfl.org/email/cr.yp.to/antiforgery/pema-20071...

It's a very nice construction (based on Rabin & Winograd's polynomial multiplication method) for building universal hashes with n/2+O(logn) multiplications.

The annoying part is that it's a tree structure, which is not usually what you want in a fast hash that you're folding over a data stream. Some papers like https://eprint.iacr.org/2017/328.pdf try to fix this, but there are a lot of annoying trade-offs.

A famous fast hash is NH, which is just:

   H(x) = sum_i (x_{2i} + a_{2i}) * (x_{2i+1} + a_{2i+1})

where `a_i` are random keys. No modulus needed. The issue is that you need as many random keys as the length of the input.

Our construction (section 5.9 Injective Polynomial Hashing) shows that you can do something a bit similar with polynomials:

    P_0 = z
    P_i = x_{2i} + (x_{2i+1} + z^3)(x_{2i} + z^2)

this is a lot simpler than Bernstein's, and is still n/2 multiplications.