Cookie Consent by Free Privacy Policy Generator
Search
Close this search box.

Scientist Says New Quantum Algorithm Can Crack Key PQC Method

PQC advance

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.

Responsive Image

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.

 

For more market insights, check out our latest quantum computing news here.

The Future of Materials Discovery: Reducing R&D Costs significantly with GenMat’s AI and Machine Learning Tools

When: July 13, 2023 at 11:30am

What: GenMat Webinar

Picture of Jake Vikoren

Jake Vikoren

Company Speaker

Picture of Deep Prasad

Deep Prasad

Company Speaker

Picture of Araceli Venegas

Araceli Venegas

Company Speaker

Matt Swayne

With a several-decades long background in journalism and communications, Matt Swayne has worked as a science communicator for an R1 university for more than 12 years, specializing in translating high tech and deep tech for the general audience. He has served as a writer, editor and analyst at The Quantum Insider since its inception. In addition to his service as a science communicator, Matt also develops courses to improve the media and communications skills of scientists and has taught courses. [email protected]

Share this article:

Relevant

The Future of Materials Discovery: Reducing R&D Costs significantly with GenMat’s AI and Machine Learning Tools

When: July 13, 2023 at 11:30am

What: GenMat Webinar

Picture of Jake Vikoren

Jake Vikoren

Company Speaker

Picture of Deep Prasad

Deep Prasad

Company Speaker

Picture of Araceli Venegas

Araceli Venegas

Company Speaker

Keep track of everything going on in the Quantum Technology Market.

In one place.

Join Our Newsletter