Lune

EUROCRYPT2023Top-tier venue

Finding Many Collisions via Reusable Quantum Walks - Application to Lattice Sieving

Xavier Bonnetain, André Chailloux, André Schrottenloher, Yixin Shen

Abstract

Given a random function ff with domain [2n][2^n] and codomain [2m][2^m], with m≥nm \geq n, a collision of ff 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 Θ(2m/3)\Theta(2^{m/3}), and matching algorithms are known for any value of mm. The situation becomes different when one is looking for multiple collision pairs. Here, for 2k2^k collisions, a query lower bound of Θ(2(2k+m)/3)\Theta(2^{(2k+m)/3}) was shown by Liu and Zhandry (EUROCRYPT 2019). A matching algorithm is known, but only for relatively small values of mm, 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 20.2563d+o(d)2^{0.2563d + o(d)} instead of the previous 20.2570d+o(d)2^{0.2570d + o(d)}.

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers4

  1. Quantum Lattice Enumeration in Limited DepthNina Bindel, Xavier Bonnetain, Marcel Tiepelt, Fernando VirdiaCRYPTO 2024 · 7 citations
  2. Improving Generic Attacks Using Exceptional FunctionsXavier Bonnetain, Rachelle Heim Boissier, Gaëtan Leurent, André SchrottenloherCRYPTO 2024 · 1 citation
  3. Quantum Algorithms for Triangle Cut SparsificationShan Jiang, Pan PengICML 2026
  4. 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

  1. Tight Time-Space Lower Bounds for Finding Multiple Collision Pairs and Their ApplicationsItai DinurEUROCRYPT 2020 · 16 citations

Related papers

  1. Communication Lower Bounds for Collision Problems via Density Increment ArgumentsGuangxu Yang, Jiapeng ZhangSTOC 2024 · 1 citation
  2. Quantum Collision Attacks on Reduced SHA-256 and SHA-512Akinori Hosoyamada, Yu SasakiCRYPTO 2021 · 52 citations
  3. The NISQ Complexity of Collision FindingYassine Hamoudi, Qipeng Liu, Makrand SinhaEUROCRYPT 2024 · 2 citations
  4. An Improved Quantum Algorithm for 3-Tuple Lattice SievingLynn Engelberts, Yanlin Chen, Amin Shiraz Gilani, Maya-Iggy van Hoof et al.CRYPTO 2026
  5. 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
Dusk over the sea between two cliffs drawn in fine vertical lines