On Finding Quantum Multi-collisions

Qipeng Liu; Mark Zhandry

Paper 2018/1096

On Finding Quantum Multi-collisions

Qipeng Liu and Mark Zhandry

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$ , $Θ (N^{\frac{1}{2} (1 - \frac{1}{2^{k} - 1})})$ 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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A minor revision of an IACR publication in EUROCRYPT 2019
Keywords: quantum cryptography
Contact author(s): qipengl @ cs princeton edu
History: 2019-02-27: revised; 2018-11-15: received; See all versions
Short URL: https://ia.cr/2018/1096
License: CC BY

BibTeX

@misc{cryptoeprint:2018/1096,
      author = {Qipeng Liu and Mark Zhandry},
      title = {On Finding Quantum Multi-collisions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/1096},
      year = {2018},
      url = {https://eprint.iacr.org/2018/1096}
}