Lattice sieving via quantum random walks

André Chailloux · Johanna Loyer

Asiacrypt 2021

Time bound

2^{0.2570 n + o(n)}

Space bound

—

Source / version date

12 May 2021

Comparison variant

Quantum · heuristic

Cost scale

2^{c n + o(n)}

QRAM / random access

Quantum random-access assumptions; see paper trade-offs

Quantum memory

Time-memory trade-off; see source

Operation model

Quantum sieving, random-list heuristic

reference

CL21

Assumptions and source notes

ASIACRYPT 2021. Heuristic sieving time; the paper supplies memory trade-offs. A single total-space coefficient is intentionally not inferred from its abstract.

Primary source ↗

@misc{paper-3219d85db441,
  author = {André Chailloux and Johanna Loyer},
  title = {{Lattice sieving via quantum random walks}},
  year = {2021},
  doi = {10.1007/978-3-030-92068-5_3},
  url = {https://arxiv.org/abs/2105.05608},
  cr_date = {2021-05-12},
  cr_status = {published},
  cr_venue = {ASIACRYPT 2021},
  cr_author_ids = {andre-chailloux; johanna-loyer},
  howpublished = {ASIACRYPT 2021; arXiv:2105.05608}
}