Posted by thomasahle 1 day ago
I made this website to make it easy for anyone how has polynomials to evaluate to see how it would be done using our method, as well as a number of previous approaches by Knuth and others.
Do you think this can be used to speed up the algebraic method for k-path?
If so, you should enter next years PACE challenge.
One small change I'd recommend is for the graph visualization, have a separate source node for each x, x^2, x^4 used. A single x source clutters the graph and hides the structure.
> have a separate source node for each x, x^2, x^4 used
Do you mean a graph like this R&W? https://thomasahle.com/fast-polynomials/#ex=bessel&mode=Q&me... there are nodes labeled x2, x4, x8; but it's the output of multiplications, and we want to make the number of mults visually clear.
Also I am curious, in your version vs. horner , how do both algorithms map onto number of fmadd operations?
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
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.
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.
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.
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.)
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.
However, in section "5.9 Injective Polynomial Hashing" we actually study the problem of universal hashing, which is a lot more like CRC8.
> We also give an injective polynomial construction for universal hashing that uses N multiplications to hash 2N values with a single random key. This improves the best previous construction by Daniel J. Bernstein (this http URL).
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})
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)