[ivmaykov]

I can think of hash functions that are homomorphic, but are not secure. A simple example is something like “sha256 each element separately and XOR all the resulting hashes together.” This would not be collusion resistant.

We offer a proof that LtHash with our choice of parameters provides over 200 bits of security. You would have to read the paper for the details.

[Scaevolus]

I can see how you might lose collision resistance with a normal 256-bit hash function, but it's not clear why a "stretched" hash with 2048 bytes of output wouldn't work.

E: Ah, there it is, in the paper:

> However, Wagner [Wag02] later showed an attack on the generalized birthday problem which could be used to find collisions > for AdHash on an n-bit modulus in time O(2^(2√n)), and that the AdHash modulus needs to be greater > than 1600 bits long to provide 80-bit security. Lyubashevsky [Lyu05] and Shallue [Sha08] showed > how to solve the Random Modular Subset Sum problem (essentially equivalent to finding collisions > in AdHash) in time O(2^(n^ε)) for any ε < 1, which indicates that AdHash requires several more orders > of magnitude larger of a modulus just to provide 80-bit security.

[_urga]

Assuming a trusted system, could you go into more detail on the qualities or guarantees a Merkle tree using XOR would or would not give you and partial mitigations for any of these disadvantages? i.e. How does the entropy of a leaf node's 256-bit signature disperse into the tree up to the root? How does the birthday paradox come into play with regards to collisions at the root of the tree?

For synchronization purposes in a trusted system, a Merkle tree based on XOR seems elegant and efficient, but I can't seem to find accessible papers on this.