3 ms·
An associative / non-commutative hash function over lists. This would mean that the hash of a list, H(list1), could be "concatenated" with another hash, H(list2
by infogulch 5y ago
An associative / non-commutative hash function over lists. This would mean that the hash of a list, H(list1), could be "concatenated" with another hash, H(list2), to find the hash of the concatenation and be equivalent to H(list1+list2). I think such a construction could be huge for cryptographic verification of data in data structures while avoiding baking in incidental details about the data structure itself.
I hesitate to link to it because I already know of a potential attack, but I played around with an implementation that does this with matrix multiplication over galois field elements of reinterpreted hash digests [1]. I mean, the associative / non-commutative part works nicely, but I expect that factoring the matrix is possible which makes it utterly useless as a cryptographic primitive [2]. "don't roll your own crypto" would apply, but I'm obviously not using such an academic exercise in production.
[1]: https://blog.infogulch.com/2021/07/15/Merklist-GF.html https://blog.infogulch.com/2021/07/15/Merklist-GF.html
[2]: https://math.stackexchange.com/questions/4200988/using-random-invertible-matrices-over-finite-fields-to-define-the-hash-of-a-list?noredirect=1#comment8720609_4200988 https://math.stackexchange.com/questions/4200988/using-rando...
- andyferris 5y agoI agree - such a thing would be really, really useful!
- kragen 5y agoThis is super interesting, thanks! I just wrote a related note in http://canonical.org/~kragen/dernocua.git http://canonical.org/~kragen/dernocua.git in text/hash-consing-ropes.md, linking to those two notes; my interest is using it for hash consing, like symbol interning but for all your strings.
- infogulch 5y agoSomething that might interest you even more is the related questions by Jason Hise that I linked to. They explored using 8x8 bit-element matrices as an associative hash of a string and apparently it works pretty good as a hash for string keys in a hashmap. Both questions, answers, and comments all have some interesting context, and Jason answers some questions I had about their usage in comments on the second question. Using 8x8 Binary Matrices as a hash - https://math.stackexchange.com/questions/1902462/using-8x8-binary-matrices-as-a-hash https://math.stackexchange.com/questions/1902462/using-8x8-b... Finding Prime Binary Matrices - https://math.stackexchange.com/questions/1914853/finding-prime-binary-matrices https://math.stackexchange.com/questions/1914853/finding-pri...
- kragen 5y agoIt's a pretty interesting idea! If you were implementing it in hardware, it would probably be faster. In software, I suspect that my suggestion of composition of linear forms in the ring ℤ/nℤ would be more efficient.