Paper 2017/847

An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography

André Chailloux, María Naya-Plasencia, and André Schrottenloher

Abstract

The cryptographic community has widely acknowledged that the emergence of large quantum computers will pose a threat to most current public-key cryptography. Primitives that rely on order-finding problems, such as factoring and computing Discrete Logarithms, can be broken by Shor's algorithm (Shor, 1994). Symmetric primitives, at first sight, seem less impacted by the arrival of quantum computers: Grover's algorithm (Grover, 1996) for searching in an unstructured database finds a marked element among $2^{n}$ in time $\widetilde{O}(2^{n / 2})$, providing a quadratic speedup compared to the classical exhaustive search, essentially optimal. Cryptographers then commonly consider that doubling the length of the keys used will be enough to maintain the same level of security. From similar techniques, quantum collision search is known to attain $\widetilde{O}(2^{n / 3})$ query complexity (Brassard et al., 1998), compared to the classical $O(2^{n / 2})$. However this quantum speedup is illusory: the actual quantum computation performed is actually more expensive than in the classical algorithm. In this paper, we investigate quantum collision and multi-target preimage search and present a new algorithm, that uses the amplitude amplification technique. As such, it relies on the same principle as Grover's search. Our algorithm is the first to propose a time complexity that improves upon $O(2^{n/2})$, in a simple setting with a single processor. This time complexity is $\widetilde{O}(2^{2n/5})$ (equal to its query complexity), with a polynomial quantum memory needed ($O(n)$), and a small classical memory complexity of $\widetilde{O}(2^{n/5})$. For multi-target preimage attacks, these complexities become $\widetilde{O}(2^{3n/7})$, $O(n)$ and $\widetilde{O}(2^{n/7})$ respectively. To the best of our knowledge, this is the first proof of an actual quantum time speedup for collision search. We also propose a parallelization of these algorithms. This result has an impact on several symmetric cryptography scenarios: we detail how to improve upon previous attacks for hash function collisions and multi-target preimages, how to perform an improved key recovery in the multi-user setting, how to improve the collision attacks on operation modes, and point out that these improved algorithms can serve as basic tools for some families of cryptanalytic techniques. In the end, we discuss the implications of these new attacks on post-quantum security.

Note: Accepted at ASIACRYPT 2017 (this is the full version, with minor modifications).