On finding quantum multi-collisions

Qipeng Liu, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Scopus citations

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, (Formula presented) 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsVincent Rijmen, Yuval Ishai
PublisherSpringer Verlag
Pages189-218
Number of pages30
ISBN (Print)9783030176587
DOIs
StatePublished - 2019
Event38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 - Darmstadt, Germany
Duration: May 19 2019May 23 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11478 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019
Country/TerritoryGermany
CityDarmstadt
Period5/19/195/23/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On finding quantum multi-collisions'. Together they form a unique fingerprint.

Cite this