An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

Technical Summary: An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

Problem Statement
The Shortest Vector Problem (SVP) in high-dimensional lattices is a foundational problem in lattice-based cryptography, underpinning the security of post-quantum cryptosystems. While the fastest provable algorithms for SVP have exponential runtime, the fastest known heuristic attacks utilize "sieving" methods. These methods iteratively combine lattice vectors to produce shorter vectors. The efficiency of these attacks is often measured by the trade-off between time complexity and memory usage.

Specifically, $k$-tuple sieving generalizes the basic 2-tuple approach by searching for $k$ vectors whose signed sum has a smaller norm. Increasing $k$ reduces the required memory (list size) but increases the time complexity of finding valid $k$-tuples. For $k=3$, the minimal memory requirement is approximately $2^{0.1887d}$, but the best known quantum time complexity prior to this work was $2^{0.3098d}$. The goal is to reduce this quantum time complexity while maintaining the minimal memory footprint.

Methodology
The authors propose a new quantum algorithm for finding $m$ solutions to the "3-list problem" (finding $m$ distinct 3-tuples $(x, y, z)$ from a list $L$ of size $m \approx 2^{0.1887d}$ such that $\|x - y - z\| \le 1$). The algorithm, named 3List, improves upon previous approaches by combining two key techniques:

1. Nested Amplitude Amplification (Two-Oracle Search):
   Instead of a single search over all possible triples, the algorithm employs a nested structure inspired by two-oracle search. The search is decomposed into two stages:

   • Stage 1: Find pairs $(x, y)$ such that their inner product $\langle x, y \rangle \ge 1/3$.
   • Stage 2: Given such a pair, find a vector $z$ such that $\langle \frac{x-y}{\|x-y\|}, z \rangle \ge 2/3$.
     The algorithm uses amplitude amplification to boost the probability of finding solutions in these nested steps.

2. Locality-Sensitive Filtering via Random Product Codes (RPCs):
   To optimize the cost of the nested search, the authors introduce a preprocessing step using Random Product Codes (RPCs).

   • Preprocessing: The algorithm samples two sets of "center points" (RPCs), $C$ and $C'$, and constructs data structures (stored in QCRAM) that map each lattice vector $x \in L$ to the center points $c \in C$ (and $c' \in C'$) that are "close" to it (i.e., have a large inner product).
   • Search Restriction: During the search, instead of checking all possible $y$ for a given $x$, the algorithm restricts the search to $y$ that share a close center point with $x$. Similarly, for a pair $(x, y)$, the search for $z$ is restricted to vectors sharing a center point with the normalized difference $\frac{x-y}{\|x-y\|}$.
   • Balancing Costs: This locality filtering allows the algorithm to balance the computational costs of the two stages of amplitude amplification. By focusing the search on "neighborhoods" of center points, the algorithm avoids the unbalanced costs that plagued previous naive two-oracle approaches.

Key Contributions

• Improved Time Complexity: The paper presents a quantum algorithm that solves the 3-tuple sieving problem with list size $m \approx 2^{0.1887d}$ in time $2^{0.2846d + o(d)}$. This improves upon the previous best quantum time complexity of $2^{0.3098d}$ for the same memory regime.
• Memory Efficiency: The algorithm maintains the minimal memory requirement for 3-tuple sieving ($2^{0.1887d}$ classical bits and QCRAM bits) while using only $2^{o(d)}$ qubits. This contrasts with some other quantum sieving approaches that require exponential qubits or Quantum Read-Write Memory (QQRAM).
• Algorithmic Structure: The work demonstrates that a sophisticated nested amplitude amplification strategy, aided by a preprocessing step using RPCs, can outperform previous quantum walk-based or naive amplitude amplification approaches for this specific problem.

Results

• Theoretical Bound: The main result (Theorem 3.1) establishes that the algorithm finds $m$ solutions in time $2^{0.284551d + o(d)}$ with high probability.
• SVP Application: Under the "uniform heuristic" (which assumes lattice vectors in sieving iterations behave like independent uniform samples on a sphere), this algorithm yields a heuristic quantum algorithm for $\gamma$-SVP with time complexity $2^{0.2846d + o(d)}$ and memory $2^{0.1887d}$.
• Comparison:
  • This is the fastest known quantum algorithm for SVP when total memory is limited to $2^{0.1887d}$.
  • It is faster than the best known classical 2-tuple sieving algorithm ($2^{0.2925d}$).
  • However, the authors note that the time-memory product of their 3-tuple approach ($2^{0.4733d}$) is slightly worse than the best known 2-tuple quantum approach ($2^{0.4638d}$), though the latter requires significantly more memory and more demanding quantum hardware (QQRAM).

Significance and Claims
The authors modestly frame the significance of their work:

• Incremental Improvement: They acknowledge that the improvement in the exponent (from 0.3098 to 0.2846) is relatively small and unlikely to immediately threaten current cryptographic key sizes, as cryptographers already account for quadratic quantum speedups (Grover's algorithm) which are often larger than the specific speedups achieved here.
• Toolbox Expansion: The primary contribution is demonstrating that the "toolbox" of techniques for lattice sieving is not exhausted. Specifically, they show that combining standard amplitude amplification with a well-chosen preprocessing step (RPCs) can yield improvements without resorting to more complex quantum walk structures.
• Hardware Feasibility: The algorithm is significant for its low qubit count ($2^{o(d)}$) and reliance on QCRAM rather than the more speculative QQRAM, making it a more realistic candidate for near-term theoretical analysis of quantum attacks on lattice cryptography.
• Future Directions: The authors suggest that while their current approach uses basic amplitude amplification, it remains an open question whether quantum walks could further improve 2-tuple or 4-tuple sieving, or if the current nested approach is optimal for the "many solutions" setting of 3-tuple sieving.