International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Xavier Bonnetain , Inria
André Chailloux , Inria
André Schrottenloher , Inria
Yixin Shen , Royal Holloway, University of London
Download:
DOI: 10.1007/978-3-031-30589-4_8 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: Given a random function f with domain [2n] and codomain [2m], with m≥n, a collision of f 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), and matching algorithms are known for any value of m. The situation becomes different when one is looking for \emph{multiple} collision pairs. Here, for 2k collisions, a query lower bound of Θ(2(2k+m)/3) was shown by Liu and Zhandry (EUROCRYPT~2019). A matching algorithm is known, but only for relatively small values of m, 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 \emph{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) instead of the previous 20.2570d+o(d).
BibTeX
@inproceedings{eurocrypt-2023-32953,
  title={Finding many Collisions via Reusable Quantum Walks - Application to Lattice Sieving},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-30589-4_8},
  author={Xavier Bonnetain and André Chailloux and André Schrottenloher and Yixin Shen},
  year=2023
}