Lune

CRYPTO2026顶会

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

摘要

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 .

问 Lune

几分钟读透这篇 Paper,不用再花一下午。

Lune 能读完全文,也能读引用它的顶会 Paper,讲清它的结论、证据和局限,每一点都注明出自哪篇 Paper。不用硬啃,也不靠猜。

可以从这些问题问起

Lune 可以查阅

全文 · 相关的 Paper

获取答案

免费开始,无需绑卡

相关 Paper

  1. Solving the Shortest Vector Problem in 20.63269n+o(n) Time on Random LatticesAmaury Pouly, Yixin ShenEUROCRYPT 2026 · 9 次引用
  2. Lower Bounds on Lattice Sieving and Information Set DecodingElena Kirshanova, Thijs LaarhovenCRYPTO 2021 · 9 次引用
  3. Finding Many Collisions via Reusable Quantum Walks - Application to Lattice SievingXavier Bonnetain, André Chailloux, André Schrottenloher, Yixin ShenEUROCRYPT 2023 · 22 次引用
  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 次引用
  5. Slide Reduction, Revisited - Filling the Gaps in SVP ApproximationDivesh Aggarwal, Jianwei Li, Phong Q. Nguyen, Noah Stephens-DavidowitzCRYPTO 2020 · 33 次引用
黄昏的海面,两侧是细线勾勒的悬崖