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).

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
post-quantum cryptographysymmetric cryptographycollision searchamplitude amplification
Contact author(s)
andre schrottenloher @ inria fr
History
2017-09-17: revised
2017-09-06: received
See all versions
Short URL
https://ia.cr/2017/847
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/847,
      author = {André Chailloux and María Naya-Plasencia and André Schrottenloher},
      title = {An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2017/847},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/847}},
      url = {https://eprint.iacr.org/2017/847}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.