Does a non commutative homomorphic hash function exist (or been researched/published)?
LtHash
developed by Facebook and implemented on Github here is the sort of function I am looking for, but LtHash commutes and I'd like to know if there is a non commutative hashing algorithm.
I have had a look online and so far not found any hashing functions (or even better implementations) that are both homomorphic and non commutative.
LtHash only commutes if you leave out the block indexes, but that makes it also insecure. I guess you left them out, because you want to be able to concatenate hashes as in your graph example comment.
In order to do that with LtHash, you can use the first block and pairs of adjacent blocks instead of pairs of blocks with indexes.
For example, the LtHash of
[a,b,c,d,e]
would normally besum([ h([0,a]), h([1,b]), h([2,c]), h([3,d]), h([4,e]) ])
Instead, you can use
sum([ h(a), h([a,b]), h([b,c]), h([c,d]), h([d,e]) ])
.Now you can concatenate hashes if you know the starting and ending blocks:
Hash([a,b,c,d,e,f])
=Hash([a,b,c]) + Hash([d,e,f]) + h([c,d]) - h(d)