4 ms·
Where can I read what they mean by "Strong" hashing for HighwayHash? Also, is there a peer-reviewed paper on SipTreeHash? I am not a cryptographer, so I wouldn'
by jbapple 11y ago
Where can I read what they mean by "Strong" hashing for HighwayHash? Also, is there a peer-reviewed paper on SipTreeHash? I am not a cryptographer, so I wouldn't trust my own instincts in terms of evaluating its strength compared to SipHash.
For non-cryptographic applications, CLHASH produces 64 bits of result and is 2.004/2^64 almost delta universal, at a cost of 0.16 cycles per byte on Haswell and 0.10 cycles per byte on Skylake.
https://github.com/lemire/StronglyUniversalStringHashing https://github.com/lemire/StronglyUniversalStringHashing
http://arxiv.org/abs/1503.03465 http://arxiv.org/abs/1503.03465
- janwas 11y agoFor the record, S. Gueron has some papers on similar tree hashes (http://dx.doi.org/10.4236/jis.2014.53010 http://dx.doi.org/10.4236/jis.2014.53010) and there's more theory in http://sponge.noekeon.org/TreeHashing.pdf http://sponge.noekeon.org/TreeHashing.pdf .
- janwas 11y agoI hadn't seen CLHASH yet, thank you for mentioning it. Looks even faster but only XOR universal (meaning XORed hashes are uniformly distributed, not the hashes themselves). In particular, it fails smhasher's avalanche test (because bit flips have predictable effects), and their proposed fix is more expensive than a HighwayTreeHash round.
- jbapple 11y ago> their proposed fix is more expensive than a HighwayTreeHash round. For longish-strings, most of the cycles are in the preliminary rounds, so appending whatever you want onto the end should add negligible cost. This includes bitmixing (their proposed smhasher fix) or a HighwayTreeHash round.
- janwas 11y agoAgreed :) We (and SipHash developers) do care about short strings, though. Scripting language hash table inputs are typically around 10 bytes, so we can't ignore finalization overhead.