| 12 |
Toward secure cryptography against quantum attacksQuantum algorithm for finding collisions of hash functions 
|
|---|
Recently, the security analysis of ciphers against quantum attacks is rapidly growing in importance, since quantum computers could make strong attacks on them in the future. For such a security analysis, it is crucial to evaluate how fast quantum computers can solve the problems used to break ciphers. Among others, it is one of the major problems to find a multi-collision of random hash functions, essential primitives used ubiquitously in cryptosystems. In this work, we provide a novel quantum algorithm that solves this problem. This algorithm is the fastest among all possible ones in the sense that it achieves the theoretical limit. Our result would contribute to enhancing the security of hash-based ciphers in the quantum-computer era.
[1] A. Hosoyamada, Y. Sasaki, S. Tani, K. Xagawa, “Improved quantum multicollision-finding algorithm,” in Proc. 10th International Conference on Post-Quantum Cryptography (PQCrypto 2019), pp. 350–367, vol. 11505, 2019.
[2] A. Hosoyamada, Y. Sasaki, S. Tani, K. Xagawa, “Quantum algorithm for the multicollision problem,” Theoretical Computer Science, vol. 842, pp. 100–117, 2020.
Seiichiro Tani / Computing Theory Research Group, Media Information Laboratory
Email: cs-openhouse-ml@hco.ntt.co.jp