"For those who don't yet know from their other social media: a week ago the cryptographer Yilei Chen posted a preprint, eprint.iacr.org/2024/555, claiming to give a polynomial-time quantum algorithm to solve lattice problems. For example, it claims to solve the GapSVP problem, which asks to approximate the length of the shortest nonzero vector in a given n-dimensional lattice, to within an approximation ratio of ~n4.5. The best approximation ratio previously known to be achievable in classical or quantum polynomial time was exponential in n."
"If it's correct, this is an extremely big deal. It doesn't quite break the main lattice-based cryptosystems, but it would put those cryptosystems into a precarious position, vulnerable to a mere further polynomial improvement in the approximation factor. And, as we learned from the recent NIST competition, if the lattice-based and LWE-based systems were to fall, then we really don't have many great candidates left for post-quantum public-key cryptography! On top of that, a full quantum break of LWE (which, again, Chen is not claiming) would lay waste (in a world with scalable QCs, of course) to a large fraction of the beautiful sandcastles that classical and quantum cryptographers have built up over the last couple decades--everything from Fully Homomorphic Encryption schemes, to Mahadev's protocol for proving the output of any quantum computation to a classical skeptic."
Wow, that's quite a lot. Let's see if we can figure out what's going on here.
First of all, I hadn't heard of these "lattice" problems, but doing some digging, I found they've been of great interest to people working on quantum computers, because they're thought to be resistant to attacks from quantum computers. Quantum computers have this magical ability to use the superposition of wavefunctions to test "all combinations at once" for a mathematical problem, which could be finding a key that decrypts an encrypted message. This magical ability is harder to tap into than it sounds because, first of all, you need enough qubits (quantum bits -- the superposition bits that quantum computers use instead of the regular 0 or 1 bits of regular computers), and that's really hard because all the qubits have to be entangled, and maintaining a boatload of entangled qubits usually involves freezing atoms to near absolute zero and other such difficult things. And second of all, you have to find an algorithm -- quantum computers are not straightforward to program, and can only "run" "programs" written specifically for quantum computers, with algorithms that have been invented to solve a particular mathematical problem using quantum physics.
What supposedly makes "lattice" problems harder to solve than RSA, Elliptic Curve Cryptography, and so on, is that with lattices, you can have any number of dimensions. This increase in dimensionality cranks up the number of qubits required much faster than traditional algorithms such as RSA, Elliptic Curve Cryptography, and so on. So they stand a much better chance of outpacing the advancement of quantum computers. Also, nobody has ever come up with an algorithm for cracking lattice problems...
...until now, maybe. That's what this post is about. Possibly this Yilei Chen cryptographer has found an algorithm. The specific encryption algorithm that he may have found a way to crack with a quantum computer algorithm is called GapSVP. SVP stands for "shortest vector problem" and clicking through on the link will take you to a Wikipedia page that explains the mathematics behind it. However if you scroll down in the original post you'll see there is discussion of a bug in cryptographer Yilei Chen's algorithm. It is not known whether the algorithm can be fixed or whether this means GapSVP and LWE remain unbroken.
Speaking of LWE, the post also mentions LWE without giving a clue what "LWE" means. LWE stands for "Learning With Errors". In fact if you clicked through on GapSVP to the Wikipedia page, you can find a handy link to the Learning With Errors page at the bottom in the "See also" section. With LWE, you have an n-dimensional "ring" of integers -- called a "ring" instead of a "vector" because they are all modulo some prime number (remember we make this hard by making the number of dimensions and the size of the prime number huge) -- which you run through some secret linear transformation function and then perturb with some error, perhaps drawn from a Gaussian distribution. To crack the system you have to recover the secret linear transformation function. Mathematicians have proven LWE is equivalent to lattice problems and therefore is a lattice problem.
The mention of Mahadev's protocol, which you can find out all about by clicking through on that link, refers to a method of verifying that a quantum algorithm works using a classical computer. The protocol works by forcing the qubits into states that are predetermined ahead of time, and then verifying those states are achieved. Of course a classical computer cannot verify the output of a quantum computer for any given input.
There are no comments yet.