Paper 2022/676

Finding many Collisions via Reusable Quantum Walks

Xavier Bonnetain, Université de Lorraine, CNRS, Inria
André Chailloux, Inria
André Schrottenloher, Inria, Univ Rennes, IRISA
Yixin Shen, Royal Holloway University of London
Abstract

Given a random function $f$ with domain $[2^n]$ and codomain $[2^m]$, with $m \geq 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 $\Theta(2^{m/3})$, and matching algorithms are known for any value of $m$. The situation becomes different when one is looking for multiple collision pairs. Here, for $2^k$ collisions, a query lower bound of $\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 $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 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 $2^{0.2563d + o(d)}$ instead of the previous $2^{0.2570d + o(d)}$.

Note: Full version of the paper.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Keywords
Quantum algorithmsquantum walkscollision searchlattice sieving
Contact author(s)
xavier bonnetain @ inria fr
andre chailloux @ inria fr
andre schrottenloher @ inria fr
yixin shen @ rhul ac uk
History
2023-02-23: revised
2022-05-30: received
See all versions
Short URL
https://ia.cr/2022/676
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/676,
      author = {Xavier Bonnetain and André Chailloux and André Schrottenloher and Yixin Shen},
      title = {Finding many Collisions via Reusable Quantum Walks},
      howpublished = {Cryptology ePrint Archive, Paper 2022/676},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/676}},
      url = {https://eprint.iacr.org/2022/676}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.