Amazon Researcher Claims Quantum Algorithm Could Challenge PQC Foundations

Insider BriefA preliminary paper from an Amazon Web Services cryptographer describes a polynomial-time quantum algorithm for a long-standing mathematical problem whose solution could have implications for lattice-based cryptography, the foundation of many post-quantum encryption systems proposed by the National Institute for Standards and Technology, among others.This is early work, but if validated, the work would represent a significant advance in quantum algorithms. It would not, however, amount to an immediate attack on deployed post-quantum cryptography.The paper, written by Daniel R. Simon of Amazon Web Services’ Cryptography Group, presents what it describes as a polynomial-time quantum algorithm for the Dihedral Coset Problem, or DCP. The problem has occupied quantum algorithm researchers for more than two decades because earlier work connected it to several difficult lattice problems.Lattices are regular arrangements of points and while most people think of two-dimensional grids when they imagine a lattice, in this case, the lattice is extended across many dimensions. Cryptographic systems can construct problems on those lattices that are easy to generate but believed to be extraordinarily difficult for an attacker to reverse.Two of the most important are the Shortest Vector Problem, which asks a computer to find a sufficiently short nonzero vector — essentially, the shortest nontrivial step — in a lattice, and Learning With Errors, which hides information inside mathematical equations containing deliberately introduced noise.Variants of these problems underpin much of modern post-quantum cryptography. They are intended to remain secure against both classical computers and future quantum systems.According to Simon’s paper, the new algorithm can be combined with earlier theoretical reductions developed by mathematician Oded Regev and later refined by other researchers to produce polynomial-time quantum algorithms for certain approximations of the Shortest Vector Problem and certain Learning With Errors 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 (hopefully) more plain terms, this means that a quantum computer could efficiently find a solution that comes reasonably close to the best possible answer for an important mathematical problem that underpins much of today’s post-quantum cryptography. The paper makes a related claim for Learning With Errors parameters.This is important because the algorithm does not necessarily find the exact shortest vector, nor does the paper establish that every practical form of Learning With Errors becomes efficiently solvable.The result is instead a complexity-theoretic advance — in other words, it is primarily a theoretical one. Rather than demonstrating an attack on today’s encryption systems, the paper shows that an important class of mathematical problems may be far easier for quantum computers than researchers previously believed.The Dihedral Coset Problem is a version of what computer scientists call a hidden subgroup problem.Quantum computers are particularly effective at finding hidden mathematical structure in some groups. Shor’s factoring algorithm can be viewed through this framework, as can several other important quantum algorithms.The dihedral case has been much harder. In simple terms, a quantum computer receives samples containing two related values separated by an unknown quantity. The task is to recover that hidden quantity from the quantum states.Earlier researchers showed that solving this problem efficiently could have consequences beyond abstract group theory.Regev demonstrated a reduction from certain lattice problems to DCP, according to the paper, meaning that an efficient algorithm for DCP could be used as a component in an efficient algorithm for those lattice problems. His polynomial-time construction, however, depended on a subset-sum oracle, an idealized mechanism capable of solving another difficult computational problem.That left a significant gap because the reduction showed what would follow if the required DCP procedure existed, but it did not provide a practical polynomial-time way to perform the crucial step.The best previously known quantum algorithm for the related Dihedral Subgroup Problem was developed by Greg Kuperberg, according to the study. It ran in subexponential time, which is substantially faster than a fully exponential algorithm, but still not polynomial.Simon’s paper claims to provide the missing polynomial-time procedure without using the subset-sum oracle.One technical difficulty is not merely obtaining quantum samples, but in removing, or “erasing,” information attached to those samples without also destroying the quantum phase that contains the hidden answer.In Regev’s construction, an idealized mathematical shortcut — the subset-sum oracle — performed that erasure. Simon proposes dividing a large collection of quantum samples into groups and processing them so that some groups can be used without introducing unwanted phases. Information from other groups is measured and separated in a way designed to leave the relevant parts of the quantum state nearly balanced.The algorithm then transfers the phase encoding one bit of the hidden value to a replacement qubit. Repeating the procedure recursively allows the algorithm to recover the remaining bits.Much of the paper is devoted to proving that the algorithm preserves enough of the quantum information needed to recover the correct answer reliably, despite the transformations performed during the computation.Polynomially many repetitions would then raise the probability of recovering the bit to near certainty, according to the studyThe argument depends on statistical properties of subset sums and on the claim that relevant quantum states become close to uniformly distributed across possible values.These technical probability arguments are likely to receive particularly close examination because a subtle imbalance, overlooked dependency or incorrect bound could change the algorithm’s performance.Another important feature is the algorithm’s claimed tolerance for imperfect samples.The Dihedral Coset Problem allows some samples to be faulty, meaning they contain random classical information instead of the intended quantum superposition. Earlier approaches faced limitations when errors were introduced because the algorithms required cleaner input.Simon claims the algorithm can tolerate a faulty-sample rate as high as roughly one divided by the logarithm of the problem size.That tolerance is important to the connection with lattice problems. The reductions from lattice problems to DCP can introduce faulty samples, and the tolerated error rate influences the approximation factors that the resulting lattice algorithm can achieve.The paper’s final corollary states that the DCP algorithm yields polynomial-time quantum algorithms for square-root-of-n polylogarithmic approximations of the Shortest Vector Problem and corresponding Learning With Errors instances.The work will likely draw attention because lattice cryptography has become a leading replacement for RSA and elliptic-curve cryptography.Those older public-key systems are vulnerable to Shor’s algorithm, provided an attacker has a sufficiently large and error-corrected quantum computer. The post-quantum transition is intended to replace them with schemes based on problems for which no efficient quantum attack is known.Simon’s paper challenges part of that broad assumption by claiming an efficient quantum route to some lattice problems.It’s important to note that this does not absolutely mean that standardized post-quantum algorithms can now be broken.Before anyone declares victory — or defeat, depending — for lattice cryptography, researchers will need to answer several important questions.For example, the manuscript does not analyze a specific cryptographic standard, provide a key-recovery attack against a deployed system or show how the approximation factors in the theorem map onto practical parameters used by cryptographers.It also does not calculate the number of logical qubits, quantum gates or error-corrected operations needed to run the algorithm at cryptographically relevant sizes.A polynomial-time algorithm can still be impractical if its polynomial degree is high, its constant factors are large or its circuit requires resources far beyond foreseeable hardware.The relationship between worst-case lattice problems, average-case cryptographic instances and the exact parameters used in deployed schemes will also matter. A result affecting one formulation of Learning With Errors does not automatically invalidate every construction derived from the broader LWE family.The paper itself confines its main claim to the mathematical problems and parameter ranges reached through the cited reductions.To turn a preliminary result into a major advance in theoretical computer science, specialists often conduct line-by-line review. That process can confirm a result, expose a correctable gap or uncover a flaw that invalidates the central claim.The paper indicates ongoing discussions with several prominent researchers in lattice cryptography and theoretical computer science, including Daniele Micciancio, Vinod Vaikuntanathan and Thomas Vidick. Independent analysis will now need to determine whether the proposed erasure method works under the stated assumptions, whether the probability bounds hold throughout the recursive procedure and how the resulting complexity behaves when translated into an explicit quantum circuit.TopicsShare Get the latest research, company news, and market intelligence every week. MENTIONED IN THE ARTICLEThe National Institute of Standards and Technology is a physical sciences laboratory and non-regulatory agency of the United States Department of Commerce.Amazon Braket – A fully managed service that allows scientists, researchers, and developers to begin experimenting with computers from multiple quantum hardware providers in a single place. Bra-ket notation is commonly used to denote quantum mechanical states, and inspired the name of the service.More in Research