International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On Finding Quantum Multi-collisions

Authors:
Qipeng Liu
Mark Zhandry
Download:
DOI: 10.1007/978-3-030-17659-4_7 (login may be required)
Search ePrint
Search Google
Abstract: 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, $$\varTheta \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.
Video from EUROCRYPT 2019
BibTeX
@article{eurocrypt-2019-29385,
  title={On Finding Quantum Multi-collisions},
  booktitle={Advances in Cryptology – EUROCRYPT 2019},
  series={Advances in Cryptology – EUROCRYPT 2019},
  publisher={Springer},
  volume={11478},
  pages={189-218},
  doi={10.1007/978-3-030-17659-4_7},
  author={Qipeng Liu and Mark Zhandry},
  year=2019
}