The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
author：New Zhiyuan
Edit: So sleepy Aeneas
Some time ago, the new "quantum algorithm for cracking lattice codes" proposed by Chen Yilei, an assistant professor at Tsinghua University, caused a sensation in the industry as soon as it was published. However, just recently, critical step 9 was found to have an unfixable bug that prevented the algorithm from working.
For a long time, solving the Lattice Problems and Learning with Errors (LWE) on lattice have been classical algorithmic problems in the field of computing.
Especially in the eyes of the scientific community, they are far beyond the capabilities of traditional computers.
So, is it possible for quantum computers to solve the Lattice Problems and LWE?
Some time ago, Chen Yilei, an assistant professor from the Institute for Interdisciplinary Information Sciences of Tsinghua University, proposed a new "quantum algorithm for cracking lattice codes" to solve these problems.
As soon as the preprint paper was published, it caused a huge sensation in the entire computer world.
For example, the famous cryptographer N. P. Smart, right now, posted a blog post detailing the impact of the paper.
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Specifically, the polynomial time quantum algorithm proposed by Professor Chen is mainly used to solve "learning problems with errors" (LWE) with specific polynomial analog-to-noise ratios.
By combining the reduction from the grid problem to the LWE proposed by Regev, the polynomial time quantum algorithm can be obtained, and can be used in
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The decision shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all n-dimensional grids are solved within the approximation factor.
Prior to this, there was no known polynomial or even subexponential time quantum algorithm that could solve for GapSVP or SIVP for all meshes within any polynomial approximation factor.
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Address: https://eprint.iacr.org/2024/555.pdf
In order to develop a quantum algorithm to solve LWE, the authors propose two new techniques:
Firstly, the Gaussian function with complex variance is introduced into the design of quantum algorithms. In particular, the complex Gaussian function is used to discrete the Castellar wave features in the Fourier transform.
Secondly, a window quantum Fourier transform with a complex Gaussian window is used, which enables the combination of information in the time and frequency domains.
Based on this, the LWE instance can be converted into a quantum state with a pure virtual Gaussian amplitude, then the pure virtual Gaussian state can be converted into a classical linear equation with LWE secrets and error terms, and finally the Gaussian elimination method can be used to solve the linear equations.
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Unfortunately, Hongxun Wu (UC Berkeley Bo2 student) and Thomas Vidick (quantum domain expert) found that step 9 of the algorithm actually had a bug that could not be fixed.
In other words, this polynomial time quantum algorithm that solves LWE by using the polynomial analog-to-noise ratio cannot be established.
In response, the authors say that ideas like Complex Gaussian and windowed QFT will find other applications in quantum computing, and that there may be other solutions to the LWE problem.
9 key steps
First, the parameters are set, and then a quantum subroutine consisting of nine steps needs to be run, and a total of O(n) runs are run.
The most critical thing in the paper is a quantum subroutine consisting of nine steps that needs to be called O(n) times.
where each call results in a classical linear equation with random coefficients of
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The shortest vector (related to the LWE secret vector and the error vector).
After O(n) calls, a system of full-rank linear equations can be obtained, and the LWE secret and error terms can be calculated by Gaussian elimination method.
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Step 1: In
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
and apply a complex Gaussian window
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Step 2: Apply on |φ1⟩
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Step 3: Apply the complex Gaussian window on |φ2⟩ to get |φ3⟩ and z′
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Step 4: Apply on |φ3⟩
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Step 5: Divide |φ4⟩ into higher-order |h′⟩ and lower-order |h′′⟩, and then measure the |h′′⟩
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Step 6: Apply on |φ5⟩
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Step 7: Extract the center of |φ6⟩ to obtain the pure virtual Gaussian state |φ7⟩
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Step 8: Extract
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
and keep |φ8⟩=|φ7⟩
In step 8, the authors first perform four operations (reversible), then partial measurements, and finally invert the four operations. In other words, you need to learn without folding or modifying |φ7⟩
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
。
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Step 9: From
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
and |φ8⟩ to extract the secret linear equations
The goal of step 9 is to convert |φ8⟩ into a secret classical linear equation and finally get the proof of the main Lemma(3.8).
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Where, step 9 uses the one obtained in step 8
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
information, as well as κ-1 coordinates of known terms inserted in the LWE secret.
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Here, here comes the bug: the amplitude of |φ8.f⟩ does not satisfy the periodicity of M2.
Alternatively, another explanation is: |φ8.f⟩ contains p1... pκ vector. After domain extension, you should have got p1p2... pκ-p2... pκ vector, but according to the |φ8.g⟩ it only contains p1... pκ vector. Therefore, the expression of |φ8.g⟩ is wrong.
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
About the Author:
The professor of Tsinghua University dropped a quantum cryptography paper bomb! The industry caused a sensation, but the algorithm was found to be buggy
Yilei Chen is an assistant professor at the School for Interdisciplinary Information Sciences (IIIS) at Tsinghua University.
Previously, he received his Ph.D. from Boston University under the supervision of Prof. Ran Canetti and Prof. Leonid Reyzin. He received his bachelor's degree from Shanghai Jiao Tong University. There, an interesting question led him to the path of scientific research.
His research interests are in cryptography, especially in the fields of pseudorandom, lattice cryptography, number theory, and quantum computing.
The main achievements are: the quantum algorithm for lattice problems is designed, the basis for the safe implementation of multilinear mapping and code obfuscation on lattice problems is established, the method of proving the Fiat-Shamir hypothesis is proposed, and the construction of an irreversible group is proposed.
