All four of my friends texed me Thursday morning: “Did you see THE paper?” I told them all to go away, I was ankle-deep into Turgenev and wanted to watch the second part of Dune in the evening. But, this paper was special. It spread like wildfire and I did finally get around to reading it. Well, I have been using the term ‘reading’ liberally these days. What I mean is I opened a browser tab, read the first few pages and the last few paragraphs, highlighted a few words here and there, and I followed some Twitter reactions to it.

Here are some frequently and infrequently asked questions.

UPDATE (April 25): A paper made a huge claim but it turned out there was a major irreparable hole in the paper. The author has withdrawn the claims and Post-Quantum Crypto is still safe.

What lesson can one learn retrospectively from this episode?

What this paper has revealed to me is that people do not seem to have strong confidence on LWE being difficult. For example, Dan Simon of Simon’s algorithm fame comments on Scott Aaronson’s blog “FWIW, I’ve believed for years that this was coming.”. I would not be too surprised if another paper were to drop in a few months that circumvents the bug in the current paper.

Why do people care about this work?

By now, it is common knowledge that quantum algorithms can break cyptography algorithms whose hardness derives from prime factoring or calculating discrete log. In response, cryptographers have been working towards “post-quantum” cryptography (PQC), supposedly robust against quantum attacks. For example, NIST (National Institute of Standard and Technology) has been working for a while to come up with federally approved standards on post-quantum cryptography. These new crypto algorithms are often built around a family of problems called ’lattice problems’ – over the next few months, you might hear terms like GapSVP, and SIVP, which are all examples of lattice problems. I won’t get into the details because life is better without knowing all these things.

What does this paper do to such post-quantum cryptography?

The paper specifically solves a problem called Learning with Errors (LWE), which can then be used to solve certain lattice problems, which in turn make up the backbone of post-quantum algorithms like CRYSTALKyber. The paper claimed to solve the LWE problem in polynomial time, which, if the paper is true (UPDATE: it’s not), would open up new vulnerabilities in post-quantum cryptography.

Is it good news or bad news?

For me and other researchers, it’s great news! It adds to the urgency and relevance of the kinds of things we study. But, if you are in the business which depends on LWE being exponentially difficult to solve, then probably not so great news for you. (UPDATE: if you are in the business which depends on LWE being exponentially difficult to solve, you are gooood. For now.)

That sounds like a big deal?

Yes, but only if the paper is true and correct, and the jury is still out on that, or so I hear. I don’t understand the field well enough to have a reliable knee-jerk reaction to this paper, plus the paper is sixty four pages long and uses words like “Karst waves” and “Gaussians.” (UPDATE: As it turns out, the mistak appeared in a rather significant part of the paper, in the ‘algorithm’ itself. Still, it is remarkable that multiple people found this bug. )

I heard NIST has some candidate post-quantum crypto algoritms? Are they vulnerable too?

Interestingly, even if the paper is true, it doesn’t quite break NIST Post-Quantum candidates; the paper just barely falls short. But, this increases the likelihood that more follow-up work on the subject will eventually take us there. (UPDATE: nothing is vulnerable now.)

Is there a business angle here? Can I maybe do a startup based on this paper?

There is always a business angle, my friend.

What about cryptocurrencies? Are they vulnerable?

Unless I am mistaken, both Bitcoin and Ethereum use some form of elliptic curve cryptography, which was known to be vulerable to quantum computers long before this work. There has been ongoing discussions of the quantum threat in Ethereum communities, but I am not very up to date.

Will I be personally affected by it?

Even if the paper was true, no one currently has a working quantum computer, and a device that can solve LWE is very very far away. So I would say, you are good. Unless you are the type to be driven into existential despair by cryptographic falliabilities.

April 13, 2024