Rendered at 18:54:12 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
thomasahle 6 hours ago [-]
Non-cryptographic hashing should not mean "no guarantees". Unfortunately it's very hard to empirically test if a pseudorandom function works well on all inputs.
We analyzed 30 popular hashes and found Key-independent collisions in nearly all of them. E.g. xxh3 has pairs that collide with probability 2^{-10}, much higher than the 2^{-64} you'd expect.
However some fast hashes are good on all inputs, and we were able to verify it in Lean.
AlotOfReading 3 hours ago [-]
Most non-CS hashes should have two parts:
1. A permutation that does as much as possible of the actual bit-mixing and
2. The simplest compression rule possible, though combining can be tricky.
Good permutations are much easier to design than good hashes, and one of the main ways hash functions are used is consuming integers smaller than the state space. May as well take advantage of provably ideal behavior.
thomasahle 47 minutes ago [-]
Yes, a good example is tabulation hashes which is
h(x1, x2, ...) = T[1, x1] ^ T[2, x2] ^ ...
but most fast hashes are actually algebraic, typically using polynomials in some way. I'm not sure they fit into the same pattern?
We analyzed 30 popular hashes and found Key-independent collisions in nearly all of them. E.g. xxh3 has pairs that collide with probability 2^{-10}, much higher than the 2^{-64} you'd expect.
However some fast hashes are good on all inputs, and we were able to verify it in Lean.
1. A permutation that does as much as possible of the actual bit-mixing and
2. The simplest compression rule possible, though combining can be tricky.
Good permutations are much easier to design than good hashes, and one of the main ways hash functions are used is consuming integers smaller than the state space. May as well take advantage of provably ideal behavior.