Welcome to the resource topic for 2017/847
Title:
An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography
Authors: André Chailloux, María Naya-Plasencia, 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.
ePrint: https://eprint.iacr.org/2017/847
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .