4 ms·

In addition to the things others have pointed out, note that "universality" is a well-defined concept w.r.t. hash functions: https://en.wikipedia.org/wiki/Unive

In addition to the things others have pointed out, note that "universality" is a well-defined concept w.r.t. hash functions: https://en.wikipedia.org/wiki/Universal_hashing https://en.wikipedia.org/wiki/Universal_hashing - you should probably not use it to describe your hash function if you can't show universality.

19eightyfour 9y ago
I think it is probably universal, but I have to show it to know for sure. I'm going to keep calling it universal until I know more. I think I note it in the README, but some reasons I think it is probably universal are because tifuhash can be parameterized, and it has good independence properties ( passes PractRand ). Showing it is universal or not is another step. I suppose I could experiment, to see if the collision probabilities match the criteria for universal or k-universal. Or maybe I could show it. For showing it, my next step is to read over this paper[1] to see if I can use its methods to show universality. I think it is using properties of the bits under multiplication. And I believe one avenue would be to show it using properties of the bits under division. I don't know how to approach the bits under division right now. [1]: https://arxiv.org/abs/1504.06804 https://arxiv.org/abs/1504.06804
- lorenzhs 9y ago
  I admire your confidence but I don't share it - showing universality for a complex construct like yours is rather nontrivial. You should really start by testing with SMHasher, though. Best of luck.
  - 19eightyfour 9y ago
    Okay, I'll start with that next time, thanks
  - 19eightyfour 9y ago
    Maybe i ought to have just said that the title includes the qualifier, " - that's the aim anyway," reinforcing the notion that even if we don't know if tifuhash is universal, it aims to be. So work is ongoing in that area, and you're welcome to contribute code or work on an approach to prove it is universal at some point. If you have more you'd like to contribute, you could become co author potentially. Please try to see it like that. That's the idea I'm going for here. Thanks
  - 19eightyfour 9y ago
    Thanks for encouraging me to use SMHahser. I posted the SMHasher results here: https://github.com/dosaygo-coder-0/smhasher/blob/master/tifuhash.results.txt https://github.com/dosaygo-coder-0/smhasher/blob/master/tifu... And my SMHasher fork testing tifuhash is here: https://github.com/dosaygo-coder-0/smhasher https://github.com/dosaygo-coder-0/smhasher
19eightyfour 9y ago
I realize my other comment might have come across as: "i called it universal because it hashes both strings and numbers, then someone pointed out the technical term universal and i decided i would just turn it into a 'universal hash' as well, because that would be easy." From that point of view it makes sense to point out what universal hashing means, and how showing universality is non trivial, and not something i can just trivially track on. However, i didn't communicate this following point before, but the genesis of tifuhash was: yesterday i read the paper i linked in the other comment and wanted to write a universal hash family. There's an open problem at the end of the paper that directly motivated me to try to come up with this. * from that paper:* > "Major Open Problem: Can we get something simple and fast like multiply-shift to work directly for strings, so that we do not need to compute polynomials over prime fields?" Actually i wrote tifuhash to be universal and work on strings, in other words to be a family of parameterized hash functions with the 2^-64 collision probability. I imposed a bunch of other constraints I myself as well, such as only using arithmetic operations ( no bitwise ops ), making it as simple as possible, and trying to avoid opaque magic constants. I tried a bunch of things related to traditional multiply shift but nothing really clicked for me. Then I had the idea of using ratios of successive message values and from there just went into continued fractions. I was blown away with something so simple and using only arithmetic passed practrand. One reason i think passing practrand is important to universality is reflected in this quote from the wiki page on universal hashing: > "This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key. " Anyway, tl;dr is I designed it from the start to be universal.

19eightyfour 9y ago

I think it is probably universal, but I have to show it to know for sure. I'm going to keep calling it universal until I know more. I think I note it in the README, but some reasons I think it is probably universal are because tifuhash can be parameterized, and it has good independence properties ( passes PractRand ). Showing it is universal or not is another step. I suppose I could experiment, to see if the collision probabilities match the criteria for universal or k-universal. Or maybe I could show it. For showing it, my next step is to read over this paper[1] to see if I can use its methods to show universality. I think it is using properties of the bits under multiplication. And I believe one avenue would be to show it using properties of the bits under division. I don't know how to approach the bits under division right now. [1]: https://arxiv.org/abs/1504.06804 https://arxiv.org/abs/1504.06804

lorenzhs 9y ago
I admire your confidence but I don't share it - showing universality for a complex construct like yours is rather nontrivial. You should really start by testing with SMHasher, though. Best of luck.
- 19eightyfour 9y ago
  Okay, I'll start with that next time, thanks
- 19eightyfour 9y ago
  Maybe i ought to have just said that the title includes the qualifier, " - that's the aim anyway," reinforcing the notion that even if we don't know if tifuhash is universal, it aims to be. So work is ongoing in that area, and you're welcome to contribute code or work on an approach to prove it is universal at some point. If you have more you'd like to contribute, you could become co author potentially. Please try to see it like that. That's the idea I'm going for here. Thanks
- 19eightyfour 9y ago
  Thanks for encouraging me to use SMHahser. I posted the SMHasher results here: https://github.com/dosaygo-coder-0/smhasher/blob/master/tifuhash.results.txt https://github.com/dosaygo-coder-0/smhasher/blob/master/tifu... And my SMHasher fork testing tifuhash is here: https://github.com/dosaygo-coder-0/smhasher https://github.com/dosaygo-coder-0/smhasher

19eightyfour 9y ago

I realize my other comment might have come across as: "i called it universal because it hashes both strings and numbers, then someone pointed out the technical term universal and i decided i would just turn it into a 'universal hash' as well, because that would be easy." From that point of view it makes sense to point out what universal hashing means, and how showing universality is non trivial, and not something i can just trivially track on. However, i didn't communicate this following point before, but the genesis of tifuhash was: yesterday i read the paper i linked in the other comment and wanted to write a universal hash family. There's an open problem at the end of the paper that directly motivated me to try to come up with this. * from that paper:* > "Major Open Problem: Can we get something simple and fast like multiply-shift to work directly for strings, so that we do not need to compute polynomials over prime fields?" Actually i wrote tifuhash to be universal and work on strings, in other words to be a family of parameterized hash functions with the 2^-64 collision probability. I imposed a bunch of other constraints I myself as well, such as only using arithmetic operations ( no bitwise ops ), making it as simple as possible, and trying to avoid opaque magic constants. I tried a bunch of things related to traditional multiply shift but nothing really clicked for me. Then I had the idea of using ratios of successive message values and from there just went into continued fractions. I was blown away with something so simple and using only arithmetic passed practrand. One reason i think passing practrand is important to universality is reflected in this quote from the wiki page on universal hashing: > "This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key. " Anyway, tl;dr is I designed it from the start to be universal.