Finding many Collisions via Reusable Quantum Walks

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

Eurocrypt 2023

Time bound

2^{0.2563 n + o(n)}

Space bound

—

Source / version date

27 May 2022

Comparison variant

Quantum · heuristic

Cost scale

2^{c n + o(n)}

QRAM / random access

Quantum random access; see algorithm model

Quantum memory

Time-memory trade-off; see source

Operation model

Quantum sieving, random-list heuristic

reference

BCSS23

Assumptions and source notes

EUROCRYPT 2023. Reuses a quantum-walk state to find many collisions. The SVP application retains the lattice-sieving heuristic. Date tracks first arXiv availability, arXiv:2205.14023.

Source location

Version 1 abstract gives the 0.2563 SVP bound; arXiv submission history records 27 May 2022, 14:50:45 UTC
Version: arXiv:2205.14023v1, 27 May 2022; earlier than the 30 May ePrint receipt

Primary source ↗

@misc{paper-8837c0491680,
  author = {Xavier Bonnetain and André Chailloux and André Schrottenloher and Yixin Shen},
  title = {{Finding many Collisions via Reusable Quantum Walks}},
  year = {2023},
  url = {https://eprint.iacr.org/2022/676},
  cr_date = {2022-05-27},
  cr_status = {published},
  cr_venue = {EUROCRYPT 2023},
  cr_author_ids = {xavier-bonnetain; andre-chailloux; andre-schrottenloher; yixin-shen},
  howpublished = {EUROCRYPT 2023; full version Cryptology ePrint Archive, Paper 2022/676}
}