Scientist Says New Quantum Algorithm Can Crack Key PQC Method

Insider Brief

• A quantum algorithm has been developed that could make some post-quantum cryptological protection methods vulnerable to quantum computers.
• Yilei Chen reports that he developed a polynomial-time quantum algorithm capable of solving the Learning with Errors (LWE) problem.
• 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.

We may have entered Post-Post-Quantum Cryptology.

Scientists have begun to digest a study recently posted on Cryptology ePrint Archive that purports to show a method that will make some — allegedly — post-quantum cryptological protection methods vulnerable to quantum computers.

In the study, Quantum Algorithms for Lattice Problems, Yilei Chen, assistant professor at Tsinghua University Institute for Interdisciplinary Information Science (IIIS). reports that he developed a polynomial-time quantum algorithm capable of solving the Learning with Errors (LWE) problem, which has implications for both cryptographic security and computational mathematics. 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.

If it bears peer-review, the quantum algorithm would be a leap forward in addressing problems that were previously believed to be intractable for quantum computers. The research indicates that certain conditions of polynomial modulus-noise ratios make it possible to solve LWE.

LWE is a problem considered central to cryptography, particularly in constructing secure communications protocols.

The advance could also extend to other complex lattice problems, such as the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP), within polynomial approximation factors, according to the paper. Until now, the solutions to GapSVP and SIVP for n-dimensional lattices have eluded researchers, with no known algorithms capable of solving them in polynomial or even subexponential time.

Chen introduced two innovative techniques in the development of this algorithm. The first involves the use of Gaussian functions with complex variances, leveraging the properties of discrete Fourier transforms, the study shows. The second technique employs a windowed quantum Fourier transform with complex Gaussian windows, enabling the combination of information from both time and frequency domains.

By converting LWE instances into quantum states with imaginary Gaussian amplitudes and then into classical linear equations, Chen was able to apply Gaussian elimination to solve for the LWE secret and error terms. This approach culminates in a polynomial-time quantum algorithm, offering a new tool — or weapon — in quantum computing’s arsenal with potential ramifications for cryptography and beyond.

It’s important to recognize that the research is still at a nascent stage. Pre-print servers are not officially peer-reviewed. However, scientists are hotly debating the work on social media now.

The paper is highly technical that is loaded with equations and this article is a perhaps superficial summary of the study, so please read the entire paper on the pre-print site.