The quest for quantum-proof encryption just made a leap forwardon August 3, 2020 at 9:00 am

Many of the things you do online every day are protected by encryption so that no one else can spy on it. Your online banking and messages to your friends are likely encrypted, for example–as are government secrets. But that protection is under threat from the development of quantum computers, which threaten to render modern encryption methods useless.

Quantum machines work in a fundamentally different way from the classical computers we use today. Instead of using traditional binary code, which represents information with 0s and 1s, they use quantum bits, or qubits. The unusual properties of qubits make quantum computers far more powerful for some kinds of calculations, including the mathematical problems that underpin much of modern encryption.

“Researchers have known for decades that if a large-scale quantum computer could be built, it could do some pretty big calculations that would threaten the cryptosystem that we rely on today for security,” says Dustin Moody, a mathematician at NIST, the US National Institute of Standards and Technology.

While quantum machines are still a long way from being able to break modern encryption, NIST launched a competition in 2016 to develop new standards for cryptography that will be more quantum-proof. The race is long, with the winners set to be announced in 2022, but last week the organization announced that it had narrowed the initial field of 69 contenders down to just 15.

And so far a single approach to “post-quantum cryptography” accounts for the majority of the finalists: lattice-based cryptography.

How it works

Public-key encryption uses traditional math to encode data, unlocking it only for those who have the key–or can figure it out. Lattice-based cryptography instead uses enormous grids with billions of individual points across thousands of dimensions. Breaking the code means getting from one specific point to another–which is essentially impossible unless you know the route.

Even the National Security Agency, the US spy agency that has long sounded alarms over the threat posed by quantum computers, recently expressed confidence in lattice-based approaches.

However, it’s not just how impenetrable or complex the math is that counts. Post-quantum approaches will only work if they can be used in all the places that high-level cryptography will be needed. For example, the size of the key required to decrypt data is important: imagine what will be possible inside a piece of medical equipment that has little memory and severely limited bandwidth. If the math is so complex that opening the lock requires a massive key, the solution may not pass the usability test.

Five of the shortlisted candidates announced last week use lattice approaches that have no known quantum solution, and NIST’s new status report says they are “the most promising general-purpose algorithms” in the list.

But that list includes alternative approaches that could also break through–particularly if lattice systems prove insufficient. These other options are generally less mature, less well-studied, and much further away from being used in the real world, leading most observers to believe that lattice systems will win out when two winners are chosen in 2022.

“What NIST thinks is that lattice problems are really hard,” says Elena Kirshanova, a mathematician and cryptanalysis researcher at I.Kant Baltic Federal University in Russia. “Although these problems are hard, they seem quite efficient in terms of time to generate keys, time to construct signatures, and also efficient in terms of memory.”

When will quantum arrive?

If so much time and effort is being put into heading off a security disaster, when will we see a quantum computer that can do all this?

Last year Google famously boasted it had achieved “quantum supremacy” by finding a task a quantum computer could do that was essentially impossible for a classical computer. The company announced that it had used its 53-bit quantum computer Sycamore to solve a math problem in 200 seconds that would take a classical computer 10,000 years.

It was an important milestone, but it didn’t usher in a new era of quantum computing, and experts from industry and academia were quick to criticize it for a range of reasons.

In reality, we’re likely a decade or more away from a quantum computer that can solve useful problems–which gives NIST time to make a decision so the transition to quantum-safe cryptography can begin.

“It takes a long time to standardize and get cryptographic algorithms implemented and into products,” says NIST’s Moody. “It can take 10 or 20 years. We need this process done before a quantum computer is done so we’re ahead of the game.”

Not everybody is convinced that the time will be well spent, however.

“The next step is quantum computers solving a useful problem, which they haven’t done yet,” says Vadim Lyubashevsky, a cryptographer at IBM who worked on the CRYSTALS algorithm that is now a finalist with NIST. “If that doesn’t happen for a long time, I think companies will forget the hype and implement the weakest thing that comes out of NIST until they are suddenly reminded of the problem in 30 years.”

Read More