alt Hacker NewsWould this be applicable to fast hashes like WyHash and xxh3 or are those not using polynomials? Is this mainly for faster cryptographic hashes?
Replies
orlp • today at 5:03 AM
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.
➕ show 1 reply
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