Lune

CRYPTO2026Top-tier venue

An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

Lynn Engelberts, Yanlin Chen, Amin Shiraz Gilani, Maya-Iggy van Hoof, Stacey Jeffery, Ronald de Wolf

Abstract

The assumed hardness of the Shortest Vector Problem (SVP) in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension d, they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. k-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of k of the input vectors. Iterating these "sieving steps" sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for k = 2, but taking larger k reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from 2 0.3098d to 2 0.2846d , using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby "center points" to focus the search on the neighborhoods of these center points. Our algorithm uses 2 0.1887d classical bits and QCRAM bits, and 2 o(d) qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to 2 0.1887d .

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Solving the Shortest Vector Problem in 20.63269n+o(n) Time on Random LatticesAmaury Pouly, Yixin ShenEUROCRYPT 2026 · 9 citations
  2. Lower Bounds on Lattice Sieving and Information Set DecodingElena Kirshanova, Thijs LaarhovenCRYPTO 2021 · 9 citations
  3. Finding Many Collisions via Reusable Quantum Walks - Application to Lattice SievingXavier Bonnetain, André Chailloux, André Schrottenloher, Yixin ShenEUROCRYPT 2023 · 22 citations
  4. Just How Hard Are Rotations of Zn\mathbb {Z}^n? Algorithms and Cryptography with the Simplest LatticeHuck Bennett, Atul Ganju, Pura Peetathawatchai, Noah Stephens-DavidowitzEUROCRYPT 2023 · 26 citations
  5. Slide Reduction, Revisited - Filling the Gaps in SVP ApproximationDivesh Aggarwal, Jianwei Li, Phong Q. Nguyen, Noah Stephens-DavidowitzCRYPTO 2020 · 33 citations
Dusk over the sea between two cliffs drawn in fine vertical lines