Homomorphic and non-commutative hash function?

96 views Asked by At

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.

1

There are 1 answers

0
Matt Timmermans On BEST ANSWER

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 be sum([ 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)