Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2205.14023 · Lecture notes in computer science

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

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

Published Jan 1, 2023• 29 citations
arXivHTMLPDF
DOI
10.1007/978-3-031-30589-4_8

Related papers

Lattice Sieving via Quantum Random Walks

André Chailloux, Johanna Loyer

arXiv:2105.05608•Lecture notes in computer science•Jan 1, 2021•46 citations

Quantum Algorithms for the Approximate k-List Problem and Their Application to Lattice Sieving

Elena Kirshanova, Erik Mårtensson, Eamonn W. Postlethwaite +1 more

Lecture notes in computer science•Jan 1, 2019•21 citations

An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

Lynn Engelberts, Yanlin Chen, Amin Shiraz Gilani +3 more

arXiv:2510.08473•Lecture notes in computer science•Jan 1, 2026•1 citation

Estimating Quantum Speedups for Lattice Sieves

Martin R. Albrecht, Vlad Gheorghiu, Eamonn W. Postlethwaite +1 more

Lecture notes in computer science•Jan 1, 2020•46 citations

A Tight Quantum Algorithm for Multiple Collision Search

Xavier Bonnetain, Johanna Loyer, André Schrottenloher +1 more

Searching for collisions in random functions is a fundamental computational problem, with many applications in symmetric and asymmetric cryptanalysis. When one searches for a single collision, the known quantum algorithms match the query lower bound. This is not the case for the problem of finding multiple collisions, despite its regular appearance as a sub-component in sieving-type algorithms. At EUROCRYPT 2019, Liu and Zhandry gave a query lower bound $Ω(2^{m/3 + 2k/3})$ for finding $2^k$ collisions in a random function with m-bit output. At EUROCRYPT 2023, Bonnetain et al. gave a quantum algorithm matching this bound for a large range of $m$ and $k$, but not all admissible values. Like many previous collision-finding algorithms, theirs is based on the MNRS quantum walk framework, but it chains the walks by reusing the state after outputting a collision. In this paper, we give a new algorithm that tackles the remaining non-optimal range, closing the problem. Our algorithm is tight (up to a polynomial factor) in queries, and also in time under a quantum RAM assumption. The idea is to extend the chained walk to a regime in which several collisions are returned at each step, and the ``walks'' themselves only perform a single diffusion layer.

arXiv:2509.13909•Sep 17, 2025•0 citations

Quantum Walks and Search Algorithms

Renato Portugal

Quantum science and technology•Jan 1, 2013•501 citations
Searching for collisions in random functions is a fundamental computational problem, with many applications in symmetric and asymmetric cryptanalysis. When one searches for a single collision, the known quantum algorithms match the query lower bound. This is not the case for the problem of finding multiple collisions, despite its regular appearance as a sub-component in sieving-type algorithms. At EUROCRYPT 2019, Liu and Zhandry gave a query lower bound Ω(2m/3+2k/3)Ω(2^{m/3 + 2k/3})Ω(2m/3+2k/3) for finding 2k2^k2k collisions in a random function with m-bit output. At EUROCRYPT 2023, Bonnetain et al. gave a quantum algorithm matching this bound for a large range of mmm and kkk, but not all admissible values. Like many previous collision-finding algorithms, theirs is based on the MNRS quantum walk framework, but it chains the walks by reusing the state after outputting a collision. In this paper, we give a new algorithm that tackles the remaining non-optimal range, closing the problem. Our algorithm is tight (up to a polynomial factor) in queries, and also in time under a quantum RAM assumption. The idea is to extend the chained walk to a regime in which several collisions are returned at each step, and the ``walks'' themselves only perform a single diffusion layer.