To refer to this page use:
http://arks.princeton.edu/ark:/88435/pr16g2x| 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, 𝛩(𝑁12(1−12𝑘−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. |
| Publication Date: | 2019 |
| Citation: | Liu, Qipeng, and Mark Zhandry. "On Finding Quantum Multi-collisions." In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2019): pp. 189-218. doi:10.1007/978-3-030-17659-4_7 |
| DOI: | 10.1007/978-3-030-17659-4_7 |
| ISSN: | 0302-9743 |
| EISSN: | 1611-3349 |
| Pages: | 189 - 218 |
| Type of Material: | Conference Article |
| Journal/Proceeding Title: | Annual International Conference on the Theory and Applications of Cryptographic Techniques |
| Version: | Author's manuscript |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.