Matt Borland wrote: ...
Note that while finding shortest vectors in a lattice is a very hard problem as the dimension grows, here we don't really have to find exceedingly short vectors; they must instead have either -1 (removal) or positive coefficients. For collision-finding, where we control both inputs, we can start with many repetitions of the same element to make the problem easier and allow reasonably small negative coefficients as well. See also [2, Appendix B].
For larger sets, the generalized birthday attacks from Wagner [1, Section 4] also should apply here with minimal modifications, and reduces the security of an n-bit sum to O(2^{2sqrt(n)}).
As far as I can tell the only successful multiset hashes either require enormous moduli or use elliptic curves.
[1] https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf [2] https://arxiv.org/pdf/1601.06502
Thanks Samuel, very informative.
This is the correct answer. See also section 5.1 of NIST SP 800-107[1].
Matt
[1] https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-107r1....
I'm not sure why hash truncation applies here; what Samuel is saying is that this scheme for multiset hashing is insecure even if the original hash is not truncated. A 256 bit hash, for instance, would only provide (at most) 32 bit security. For 64 bit security one would need a 1024 bit source hash, which seems like an overkill to me.