Would this be applicable to fast hashes like WyHash and xxh3 or are those not using polynomials? Is this mainly for faster cryptographic hashes?
Would this be applicable to fast hashes like WyHash and xxh3 or are those not using polynomials? Is this mainly for faster cryptographic hashes?
WyHash and xxh3 are not polynomial, in fact this is one of the issues we try to solve in the paper.
Many "practical" hashes use heuristics instead of real field multiplications to be faster. But it means they are vulnerable to adversarial inputs. That means, it's possible to design a set of keys that have much higher probability (under random hash seeds/keys) to collide than you'd expect under a correct hash function.
We actually analyze both WyHash and xxh3 in this setting in section "Adversarial inputs for heuristic hashes" - https://arxiv.org/pdf/2609.06022#page=165
It is applicable to fast universal hashes like Poly1305 and Polymur (the latter of which I'm the author). However it's not clear to me whether this work improves over the state of the art for that purpose, see some questions here: https://www.reddit.com/r/programming/comments/1wbgcke/comput....
This purpose is however much easier/flexible than actual polynomial equivalence since the requirement here is only that the polynomial is injective, not identical.
WyHash and xxh3 do not have polynomial structures.
It is applicable, but it is not useful.
Universal hashes use the input text as the set of coefficients.
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.
This method is useful only when with a given polynomial, i.e. set of polynomial coefficients, you want to evaluate that polynomial many times, so the cost of the preprocessing is amortized.
However, this application is very important because most functions are approximated either with polynomials or with rational functions, so this method can accelerate the evaluation of all such approximated functions.
> 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; 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.