[Resource Topic] 2018/1096: On Finding Quantum Multi-collisions

Welcome to the resource topic for 2018/1096

On Finding Quantum Multi-collisions

Authors: Qipeng Liu, Mark Zhandry


A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, \Theta\left(N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right) quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.

ePrint: https://eprint.iacr.org/2018/1096

Talk: https://www.youtube.com/watch?v=tpS_JuQWG-4

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .