Paper 2017/847
An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography
André Chailloux, María NayaPlasencia, and André Schrottenloher
Abstract
The cryptographic community has widely acknowledged that the emergence of large quantum computers will pose a threat to most current publickey cryptography. Primitives that rely on orderfinding 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 multitarget 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 multitarget 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 multitarget preimages, how to perform an improved key recovery in the multiuser 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 postquantum security.
Note: Accepted at ASIACRYPT 2017 (this is the full version, with minor modifications).
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 postquantum cryptographysymmetric cryptographycollision searchamplitude amplification
 Contact author(s)
 andre schrottenloher @ inria fr
 History
 20170917: revised
 20170906: received
 See all versions
 Short URL
 https://ia.cr/2017/847
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/847, author = {André Chailloux and María NayaPlasencia 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} }