Update: Scientists Spot Mistake in Proposed PQC-Cracking Algorithm

Insider Brief

• Scientists have spotted a bug in a polynomial-time quantum algorithm developed to solve the Learning with Errors (LWE) problem.
• The bug renders the algorithm, which theoretically solved a critical post-quantum computing protection methods, inoperative.
• Yilei Chen, assistant professor at Tsinghua University Institute for Interdisciplinary Information Science (IIIS), reported Hongxun Wu and (independently) Thomas Vidick spotted the bug during informal peer-review.

In a good showing of science at its best — and with a huge sigh of relief — Yilei Chen, assistant professor at Tsinghua University Institute for Interdisciplinary Information Science (IIIS), reported that fellow scientists have spotted a bug in his polynomial-time quantum algorithm that was developed to solve the Learning with Errors (LWE) problem and an approach that’s relied on in cryptographic security and computational mathematics.

Ultimately, Chen said his approach does not hold and, at least it would follow, that this approach to PQC protection is currently safe. LWE is often referred to as a lattice problem because it is derived from the mathematical structure of lattices. Lattice problems are known for their complexity and computational hardness.

Chen posted the following message on the study, “Quantum Algorithms for Lattice Problems,”  posted on the pre-print server Cryptology ePrint Archive: “Step 9 of the algorithm contains a bug, which I don’t know how to fix. See Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.”

LWE is a foundational problem in modern cryptography, serving as the basis for various encryption schemes, including those that are considered resistant to attack by quantum computers.

Chen’s study also looked at other complex lattice problems, such as the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP), within polynomial approximation factors. There were no known algorithms capable of solving these problems in polynomial or even subexponential time.

News of Chen’s algorithm caused a stir among the quantum science community and quantum computing industry. Fault-tolerant quantum computers could crack most of the current schemes to protect data.  Many consider fault-tolerant quantum computing as a technology that is years away from maturity, which would give scientists and policymakers time to devise new methods to thwart quantum attacks, called Post-Quantum Cryptography. However, recent work done by Microsoft, Quantinuum and QuEra — to name a few — have dented those timelines — significantly. If fault-tolerant quantum computers are nearing, methods that are critical to securing data and computer systems must hold up.

If anything, Chen’s work — and those scientists who peer-reviewed his paper — is a sign that science works and that peer review is critical. It may also serve as a wake-up call for those dismissive of the progress of quantum computing and the need to redouble efforts to ensure a safe landing of what might be the most disruptive form of technology the world has produced.