You are looking at a specific version 20181130:115207 of this paper. See the latest version.

Paper 2018/1122

Improved Quantum Multicollision-Finding Algorithm

Akinori Hosoyamada and Yu Sasaki and Seiichiro Tani and Keita Xagawa

Abstract

The current paper improves the number of queries of the previous quantum multi-collision finding algorithms presented by Hosoyamada et al.~at Asiacrypt 2017. Let an $l$-collision be a tuple of $l$ distinct inputs that result in the same output of a target function. The previous algorithm finds $l$-collisions by recursively calling the algorithm for finding $(l-1)$-collisions, and it achieves the query complexity of $O(N^{(3^{l-1}-1) / (2 \cdot 3^{l-1})})$. The new algorithm removes the redundancy of the previous recursive algorithm so that different recursive calls can share a part of computations. The new algorithm achieves the query complexity of $O(N^{(2^{l-1}-1) / (2^{l}-1)})$. Moreover, it finds multiclaws for random functions, which are harder to find than multicollisions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
post-quantum cryptographyquantum algorithmmulticlawmulticollision
Contact author(s)
hosoyamada akinori @ lab ntt co jp
History
2019-01-28: last of 6 revisions
2018-11-20: received
See all versions
Short URL
https://ia.cr/2018/1122
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.