Group actions and hashing unordered multisets (2021)

Interesting, not often you see a non-associative variant of commutativity. It confused me for a bit that 'h' itself is not commutative, but summing arbitrary sequences is order independent provided you start with the same seed and sum from left to right.

Edit: Not sure the definition of phi is right though, once you have h(a, h*(T + S)) you're pretty much stuck since the commutativity doesn't allow you to rearrange things from that point. I think I understand the gist, you want to start accumulating from a different seed, except that h(a, h*(T)) is not the hash of T if you replace the seed with a. You'd need something like:

    h_s*({}) = s
    h_s*(T + {x}) = h_s*(h_s(T), h(x))
    phi(T) = (a => h_a*(T))

then commutativity could be written

    h_(h_s*({a}))({b}) = h_(h_s*({b}))({a})

which is slightly more symmetric, but maybe not better.

There’s a nice writeup on group hashes here: https://cronokirby.com/posts/2021/07/on_multi_set_hashing/

In particular, if you choose a group where discrete log is hard (such as prime order elliptic curves), multiset hashing falls out for free

I think there are a few errors here. First there is afaict no reason the image of phi has to break up into power-of-two cyclic groups.

Second and more importantly, it seems very difficult to start with the decomposition into cyclic groups and then choose a map from the multiset group into the permutation group that corresponds to the given decomposition in a good way.

Relatedly, the isomorphism between the image of phi (i.e., the action of accumulating hashes) and the decomposition into cyclic groups may be difficult to compute, which can make finding collisions infeasible for an attacker when they could do it easily if given the explicit representation.

So overall the conclusion that “you might as well make this forced structure explicit, and just pick the block structure you want to use in advance” seems incorrect.

The blog post someone linked on multiset hashing with elliptic curves proves the foregoing points. The cyclic groups do not have power-of-two orders and the group action is very complicated even though the description in terms of elliptic curve addition is quite simple.