TY - GEN
T1 - On finding quantum multi-collisions
AU - Liu, Qipeng
AU - Zhandry, Mark
N1 - Funding Information:
Acknowledgements. This work is supported in part by NSF. Opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of NSF.
Publisher Copyright:
© International Association for Cryptologic Research 2019.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85065920946&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85065920946&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-17659-4_7
DO - 10.1007/978-3-030-17659-4_7
M3 - Conference contribution
AN - SCOPUS:85065920946
SN - 9783030176587
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 189
EP - 218
BT - Advances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Rijmen, Vincent
A2 - Ishai, Yuval
PB - Springer Verlag
T2 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019
Y2 - 19 May 2019 through 23 May 2019
ER -