[HN Gopher] Group actions and hashing unordered multisets (2021)
       ___________________________________________________________________
        
       Group actions and hashing unordered multisets (2021)
        
       Author : KqAmJQ7
       Score  : 59 points
       Date   : 2024-06-23 13:07 UTC (3 days ago)
        
 (HTM) web link (www.jeremykun.com)
 (TXT) w3m dump (www.jeremykun.com)
        
       | contravariant wrote:
       | 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.
        
       | rjeli wrote:
       | 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
        
       | ihm wrote:
       | 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.
        
         | contravariant wrote:
         | I think they skip a few steps, but in this derivation im phi is
         | exactly Z/2^nZ so every subgroup should have cardinality 2^k
         | for some k.
        
       ___________________________________________________________________
       (page generated 2024-06-26 23:01 UTC)