Finding Many Collisions via Reusable Quantum Walks - Application to Lattice Sieving
Xavier Bonnetain, André Chailloux, André Schrottenloher, Yixin Shen
Abstract
Given a random function with domain and codomain , with , a collision of is a pair of distinct inputs with the same image. Collision finding is an ubiquitous problem in cryptanalysis, and it has been well studied using both classical and quantum algorithms. Indeed, the quantum query complexity of the problem is well known to be , and matching algorithms are known for any value of . The situation becomes different when one is looking for multiple collision pairs. Here, for collisions, a query lower bound of was shown by Liu and Zhandry (EUROCRYPT 2019). A matching algorithm is known, but only for relatively small values of , when many collisions exist. In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters where the lower bound is met. Our new method relies on a chained quantum walk algorithm, which might be of independent interest. It allows to extract multiple solutions of an MNRS-style quantum walk, without having to recompute it entirely: after finding and outputting a solution, the current state is reused as the initial state of another walk. As an application, we improve the quantum sieving algorithms for the shortest vector problem (SVP), with a complexity of instead of the previous .
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers4
- Quantum Lattice Enumeration in Limited DepthNina Bindel, Xavier Bonnetain, Marcel Tiepelt, Fernando VirdiaCRYPTO 2024 · 7 citations
- Improving Generic Attacks Using Exceptional FunctionsXavier Bonnetain, Rachelle Heim Boissier, Gaëtan Leurent, André SchrottenloherCRYPTO 2024 · 1 citation
- Quantum Algorithms for Triangle Cut SparsificationShan Jiang, Pan PengICML 2026
- Another Look at the Quantum Security of the Vectorization Problem with Shifted InputsPaul Frixons, Valerie Gilchrist, Péter Kutas, Simon-Philipp Merz et al.EUROCRYPT 2026
Builds on1
Related papers
- Communication Lower Bounds for Collision Problems via Density Increment ArgumentsGuangxu Yang, Jiapeng ZhangSTOC 2024 · 1 citation
- Quantum Collision Attacks on Reduced SHA-256 and SHA-512Akinori Hosoyamada, Yu SasakiCRYPTO 2021 · 52 citations
- The NISQ Complexity of Collision FindingYassine Hamoudi, Qipeng Liu, Makrand SinhaEUROCRYPT 2024 · 2 citations
- An Improved Quantum Algorithm for 3-Tuple Lattice SievingLynn Engelberts, Yanlin Chen, Amin Shiraz Gilani, Maya-Iggy van Hoof et al.CRYPTO 2026
- On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential WorkKai-Min Chung, Serge Fehr, Yu-Hsuan Huang, Tai-Ning LiaoEUROCRYPT 2021 · 3 citations
