Some time ago, a new “quantum algorithm for cracking lattice ciphers” 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, the critical step 9 was found to have an irreparable bug, causing the algorithm to fail to hold.
Solving the approximate shortest vector problem (Lattice Problems) on the lattice and the learning with error problem (LWE) have always been classic algorithmic problems in the computer field.
Advertisement
Especially in the eyes of the scientific community, they are well beyond the capabilities of traditional computers. So, are quantum computers expected to be able to crack Lattice Problems and LWE?
Some time ago, Assistant Professor Chen Yilei from the Institute of Cross-Information at Tsinghua University proposed a new “quantum algorithm for cracking lattice ciphers” to address these problems.
Once the preprint paper was published, it caused a huge sensation in the entire computer community.
For example, the famous cryptographer NP Smart immediately published a blog post discussing the impact of the paper in detail.
Advertisement
Specifically, the polynomial-time quantum algorithm proposed by Professor Chen is mainly used to solve the “Learning with Error Problem” (LWE) with a specific polynomial modulus-to-noise ratio.
By combining the reduction from the grid problem to LWE proposed by Regev, a polynomial time quantum algorithm can be obtained, and can be
Solve the decision shortest vector problem (GapSVP) and shortest independent vector problem (SIVP) for all n-dimensional grids within the approximation factor.
Previously, there were no known polynomial or even sub-exponential time quantum algorithms that could solve GapSVP or SIVP for all meshes within any polynomial approximation factor.
In order to develop quantum algorithms for solving LWE, the authors propose two new techniques:
First, the Gaussian function with complex variance is introduced in the design of quantum algorithms. In particular, the Custer wave characteristics in the discrete Fourier transform of complex Gaussian functions are exploited.
Second, a windowed quantum Fourier transform with a complex Gaussian window is used, enabling the combination of information in the time and frequency domains.
Based on this, the LWE instance can be first converted into a quantum state with pure virtual Gaussian amplitude, then the pure virtual Gaussian state can be converted into a classical linear equation of LWE secret and error terms, and finally the system of linear equations can be solved using the Gaussian elimination method.
But unfortunately, Hongxun Wu (a second-year Ph.D. student at UC Berkeley) and Thomas Vidick (an expert in the quantum field) discovered that step 9 of the algorithm actually has a bug that cannot be fixed.
In other words, this polynomial-time quantum algorithm for solving LWE through polynomial modulus-to-noise ratio cannot be established.
The author expressed the hope that ideas like Complex Gaussian and windowed QFT will find other applications in quantum computing, and the LWE problem may have other solutions.
9 key steps
First, the parameters are set, and then a quantum subroutine consisting of nine steps needs to be run, a total of O (n) times.
The most critical thing in the paper is a quantum subroutine consisting of nine steps that needs to be called O (n) times.
Among them, each call will get a classical linear equation whose random coefficients are
The shortest vector in (related to the LWE secret vector and error vector).
After O (n) calls, a full-rank linear system of equations can be obtained, and the LWE secret and error terms can be calculated by Gaussian elimination.
Step 1: Overlay on and apply a complex Gaussian window
Step 2: Apply on |φ1
Step 3: Apply a complex Gaussian window on |φ2 to get |φ3 and z′
Step 4: Apply on |φ3
Step 5: Split |φ4 into high-order | h′ and low-order | h′′ , and then measure | h′′
Step 6: Apply on |φ5
Step 7: Extract the center of |φ6 to obtain the pure virtual Gaussian state |φ7
Step 8: Extract and retain |φ8 =|φ7
In step 8, the author first performs four operations (reversible), then performs partial measurements, and finally inverts the four operations.In other words, it is necessary to learn without folding or modifying |φ7
.
Step 9: Extract the secret linear equation from and |φ8
The goal of step 9 is to convert |φ8 into a secret classical linear equation, and finally obtain the proof of Master Lemma (3.8).
Among them, step 9 uses the value obtained in step 8
information, and the κ-1 coordinates of the known items inserted into the LWE secret.
Here, the bug comes: |φ8.fThe amplitude of does not satisfy the M2 periodicity.
Or, another explanation is: |φ8.fContains p1…pκ vectors. After domain expansion, the p1p2…pκ-p2…pκ vector should be obtained, but according to |φ8.g, it only contains p1…pκ vectors. Therefore |φ8.gThe expression for is wrong.
about the author
Chen Yilei is an assistant professor at the Institute of Interdisciplinary Information (IIIS), Tsinghua University.
Previously, he received his PhD from Boston University, under the supervision of Professor Ran Canetti and Professor Leonid Reyzin. and received a bachelor's degree from Shanghai Jiao Tong University. There, an interesting question led him onto the path of scientific research.
His research interests are cryptography, especially in the areas of pseudorandom, lattice cryptography, number theory, and quantum computing.
The main achievements include: designing a quantum algorithm for lattice problems, establishing the basis for the safe implementation of multilinear mapping and code obfuscation on lattice problems, proposing a method to prove the Fiat-Shamir hypothesis, and proposing the construction of an irreversible group.
References:
https://www.zhihu.com/question/652567682
https://sqz.ac.cn/password-50
http://www.chenyilei.net/
2024/555