It’s very early, but a preliminary paper from an Amazon Web Services cryptographer suggests a polynomial-time quantum algorithm for a long-standing mathematical problem linked to lattice-based cryptography could challenge assumptions about the difficulty of some problems used to secure post-quantum systems.
The paper, written by Daniel R. Simon of Amazon Web Services’ Cryptography Group, presents an algorithm for the Dihedral Coset Problem, or DCP, a problem that has interested quantum computing researchers for more than two decades because of its connections to lattice mathematics.
If the result withstands scrutiny, it would represent a theoretical advance in quantum algorithms. It does not, however, demonstrate that deployed post-quantum encryption can be broken, and the paper leaves open major questions about whether the method could ever be practical on a real quantum computer.
Lattices are repeating geometric grids of points, somewhat like an infinitely large street grid but extended into hundreds or thousands of mathematical dimensions. Cryptographers use difficult problems built on these structures because they are believed to resist attacks by both classical and quantum computers.
Two important examples are the Shortest Vector Problem, or SVP, and Learning With Errors, or LWE. Variants of these problems form part of the mathematical foundation for widely studied post-quantum cryptographic systems.
Simon’s paper argues that his DCP algorithm can be combined with earlier work by mathematician Oded Regev and later refinements by other researchers to produce polynomial-time quantum algorithms for certain approximations of SVP and certain LWE instances.
The paper specifically claims a polynomial-time method for obtaining roughly a square-root-of-n times polylogarithmic approximation to the shortest vector in an n-dimensional lattice. In more plain terms, it argues that a quantum computer could efficiently get close to solving an important mathematical problem that researchers have generally treated as difficult even for quantum machines.
The result is primarily theoretical. Rather than demonstrating an attack on today’s encryption systems, the paper argues that an important class of mathematical problems may be easier for quantum computers than researchers previously believed.
Removing a Previous Roadblock
Earlier work by Regev established a theoretical connection between DCP and lattice problems, showing how solving one could help solve the other.
In a key limitation, Regev’s construction relied on a subset-sum oracle, essentially an idealized mathematical shortcut capable of solving another difficult problem. Simon proposes a different method that avoids that assumption.
The best previously known quantum approach to the related Dihedral Subgroup Problem, developed by Greg Kuperberg, ran in subexponential rather than polynomial time, but Simon’s paper claims to cross that threshold.
The new method works by processing groups of quantum samples while attempting to remove unwanted information without destroying the quantum information needed to recover the hidden mathematical value.
Much of the paper is devoted to proving that enough of that information survives the procedure to recover the answer reliably after repeated measurements.
The algorithm also claims to tolerate a limited fraction of faulty samples, an important feature because the reductions connecting DCP with lattice problems introduce imperfect inputs. Simon writes that the method can tolerate a faulty-sample rate as high as roughly one divided by the logarithm of the problem size.
From Mathematical Result to Practical Attack
There are several questions that need to be answered before it spells the end for lattice cryptography with one of the largest being quantum hardware.
The paper proves an asymptotic result but does not provide detailed estimates for the number of logical qubits required to execute the algorithm at cryptographically relevant problem sizes.
Logical qubits are the error-corrected qubits that a quantum algorithm effectively uses. Creating even one reliable logical qubit can require many physical qubits, depending on the hardware and error-correction scheme. An algorithm requiring thousands, millions or more logical qubits could remain impractical even if its mathematical running time is classified as efficient.
Circuit depth and gate count would matter as well. A polynomial-time algorithm can still require an enormous number of operations, and every logical quantum operation ultimately adds demands on error correction, control electronics and physical hardware.
Simon’s paper does not provide those resource estimates.
The approximation factor presents another challenge. The paper does not claim to solve every lattice problem exactly or show an attack against a specific standardized cryptographic implementation. Whether the mathematical approximations produced by the algorithm are strong enough to compromise practical cryptographic parameters would require further analysis.
The same caution applies to LWE. The paper establishes results for particular parameter ranges reached through earlier mathematical reductions; it does not demonstrate a key-recovery attack on a deployed post-quantum encryption system.
There is also the question of verification. Many of claims depend on detailed probability arguments showing that the quantum states used by the algorithm behave as required through successive stages of computation. Researchers will need to examine those arguments, the assumptions behind them and the reductions connecting the algorithm to lattice problems.
