Multi-collision resistance: a paradigm for keyless hash functions
Nir Bitansky, Yael Tauman Kalai, Omer Paneth · 2018
We introduce a new notion of multi-collision resistance for keyless hash functions. This is a natural relaxation of collision resistance where it is hard to find multiple inputs with the same hash in the following sense. The number of colliding inputs that a polynomial-time non-uniform adversary can find is not much larger than its advice. We discuss potential candidates for this notion and study its applications.