Comment by thomasahle
9 hours ago
> This method requires additional preprocessing of the coefficients, before starting to evaluate the polynomial. That preprocessing would slow the hashing algorithm more than what is gained during evaluation.
There is no preprocessing at hash time in either use.
Universal hashing: the message words are the parameters of the chain, a_i and b_i in P_i = a_i + (b_i + y)(P_{i−1} + u), not coefficients of a target polynomial. Distinct messages give distinct polynomials, which is all a universal hash needs; the decoder never runs. Same as Bernstein's BRW.
k-independent hashing: the key should be a uniformly random monic polynomial of degree k. Our parameterisation is a bijection onto those polynomials, with the rational preprocessing as its inverse, so uniformly random gate constants give a uniformly random polynomial. You draw the ⌊k/2⌋+1 constants and evaluate; the coefficients are never computed. That is why the paper needs bijective rather than just injective constructions, and the Section 5 speedups are for the whole hash.
Preprocessing only appears when a fixed polynomial (a Taylor approximation, a secret-sharing polynomial) is evaluated at many points, and then it runs once.
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, patent filed on 2000-04-14; many other patents were filed on variants of this, but now they are expired or invalid; in this method, the input text is partitioned in blocks with the length equal to the hash length, 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; an LFSR, i.e. linear-feedback shift register, is used to generate a non-repeating sequence that is added to each block, both before and after applying the mixing transformation, to make the hash depend on the order of the input blocks, i.e. this is equivalent with using a different mixing function for each block; 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).
Another example is the HighwayHash, developed at Google in 2016, and optimized for SIMD instructions of AVX2 or SSE4.1 or IBM POWER VSX or Arm Aarch64.
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.
1 reply →