In landmark for post-quantum encryption, NIST releases three algorithms

Three encryption tools designed to protect information against a quantum computer were publicly released on Tuesday by the U.S. National Institute of Standards and Technology (NIST) — a milestone for computer science and cryptography.

The new standards are “ready for immediate use,” the Department of Commerce said, and are launched following an eight-year consultation into how to protect the privacy of information against the threat posed by a functioning quantum computer.

The finalized standards include not only the three algorithms but also “instructions for incorporating them into products and encryption systems,” said NIST mathematician Dustin Moody, encouraging “system administrators to start integrating them into their systems immediately, because full integration will take time.”

Technically known as a cryptographically relevant quantum computer (CRQC), the looming existence of this device is a threat officials have taken extremely seriously.

A CRQC would be theoretically capable of breaking the encryption “at the root of protecting both corporate and national security secrets,” as Anne Neuberger, the White House’s top cyber advisor, said earlier this year.

Although such a device may not exist for another decade or so — incidentally, experts have been expecting a CRQC to be available “in a decade” for several decades now, as Conrad Prince, the former deputy director of GCHQ, quipped while speaking to Neuberger — the risk such a device poses isn't limited to the future.

Neuberger said the U.S. intelligence community’s more conservative estimate is “the early 2030s,” for when a CRQC would be operational. But the time-frame is relevant, said the White House advisor, because “there is national security data that is collected today and even if decrypted eight years from now, can still be damaging.”

Britain’s National Cyber Security Centre has warned that contemporary threat actors could be collecting and storing intelligence data today for decryption “at some point in the future.”

“Given the cost of storing vast amounts of old data for decades, such an attack is only likely to be worthwhile for very high-value information,” they said. As such, the possibility of a CRQC existing at some point in the next decade is a very relevant threat right now.

Publishing the algorithms is just the second step in moving to a quantum-resistant computing world, which the NCSC has warned will be “a very complicated undertaking.”

Even if any one of the algorithms proposed by NIST achieves universal acceptance as something that is unbreakable by a quantum computer, it would not be a simple matter of just swapping those algorithms in for the old-fashioned ones.

Part of the challenge is that most systems that currently depend on public-key cryptography for their security are not necessarily capable of running the resource-heavy software used in post-quantum cryptography.

Ultimately, the security of traditional public key cryptographic systems relies on the mathematical difficulty of factoring very large prime numbers — something that traditional computers find exhaustingly difficult.

However, research by American mathematician Peter Shor, published in 1994, proposed an algorithm that could be run on a quantum computer for finding these prime factors with far more ease, potentially undermining some of the key assumptions about what makes public-key cryptography secure.

The good news, according to NCSC, is that while advances in quantum computing continue to be made, the machines that exist today “are still limited, and suffer from relatively high error rates in each operation they perform.”

But the NCSC warned that “in the future, it is possible that error rates can be lowered such that a large, general-purpose quantum computer could exist,” but it is “impossible to predict when this may happen.”