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$, $\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.

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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2018/1096}},
      url = {https://eprint.iacr.org/2018/1096}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.