Comment by adrian_b
3 hours ago
There are many kinds of universal hashing, many of which are not based on polynomial evaluation.
However, the most common kinds of universal hashing, i.e. those which are used for computing message authentication codes (MAC) in the TLS and SSH protocols (using poly1305 or GCM), are based on polynomial evaluation, where the message is the sequence of coefficients of the polynomial and the secret key of the MAC is the value at which the polynomial is evaluated.
The polynomial corresponding to a MAC is evaluated only once at the sender and once at the receiver, usually in a single pass over the data, simultaneously with its encryption or decryption. Frequently the reading or writing of the data from/to the main memory limits the throughput of the MAC computation (caches do not help, because the data is not reused), in which case a better algorithm than Horner cannot provide significant speed-ups.
Besides their application in MACs, which is ubiquitous now in Internet communication, I consider the other applications of universal hashing as minor, because the "universality" property of such hashes seldom provides any substantial benefit over alternative hash functions that do not have this property, but which guarantee other more useful properties. (The "universality" property is just a statistical property of a family of hash functions, while instantiated universal hashes may happen to be quite bad hash functions. For instance, in AES-GCM it is possible to choose by bad luck a secret key for which some reordered messages have the same hash value with the original message, so tampering with the message remains undetected. Fortunately, the adversary cannot guess when the sender has chosen a bad secret key, in order to try to alter the message.)
> the "universality" property of such hashes seldom provides any substantial benefit over alternative hash functions that do not have this property
Do you mean hashes like xxh3? We have a section in the paper showing for a bunch of these that they collide much more often than universal hashes on bad inputs.
No, though even a hash like xxh3 can be useful when speed is more important than collision resistance.
There are many hashes that use more thorough mixing functions than can be achieved with one or a few arithmetic operations (like in universal hashes), thus for them the collision probability reaches the limit imposed by the length of the hash value. Modern CPUs have various instructions that can be exploited in mixing functions that have about the same speed as simpler arithmetic operations, but which achieve a better mixing.
An example is the Alred construction (Joan Daemen & Vincent Rijmen, in 2005-02), which was inspired by the old CBC-MAC algorithm, but it is much more efficient (in this construction, the hash mixing function is derived from the internal mixing function used in some block cipher function, for example the AES block cipher function, so it can be implemented with the AES round function instructions of x86-64 and Aarch64, which are very fast in modern processors; this hash function uses the AES instructions but it is several times faster than the AES encryption/decryption algorithms, which are already very fast).
Another example is any hash function that has the structure used in the Jutla authentication method (Charanjit Singh Jutla @ IBM, 2000-04-14; in this method, the input text is partitioned in blocks with the length equal to the hash length, an LFSR, i.e. linear-feedback shift register, generates a sequence that is added to each block, to make the hash depend on the order of the input blocks, then a parallel mixing function transforms each input text block into a scrambled text, in a different space of values, then in the transformed space a simple additive function, even the simplest, which is bitwise addition modulo 2, can be used to reduce the transformed message to a single intermediate hash value, and finally the inverse of the mixing function is applied to the intermediate hash value to produce the final hash value by going back to the original space of values; this makes the computation of the hash parallelizable, thus very fast; there are universal hashes based on scalar products which have the same structure like this, but the difference is that they use a simple multiplication instead of a complex mixing function).
Such hash functions were developed first in cryptographic contexts, i.e. as keyed hash functions, a.k.a. message-authentication codes.
Nonetheless, because modern CPUs now include a lot of instructions for the acceleration of cryptographic algorithms, such hash functions can be used now for any other hashing applications, because on modern CPUs they can be as fast or even faster than traditional hash functions with simple arithmetic operations.