Actual quantum computers don't exist yet. The cryptography to defeat them may already be here

NIST pushes ahead with CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, SPHINCS+ algorithms

The US National Institute of Standards and Technology (NIST) has recommended four cryptographic algorithms for standardization to ensure data can be protected as quantum computers become more capable of decryption.

Back in 2015, the NSA announced plans to transition to quantum-resistant cryptographic algorithms in preparation for the time when quantum computers make it possible to access data encrypted by current algorithms, such as AES and RSA.

No one is quite sure when that may occur but it depends on the number of qubits – quantum bits – that a quantum machine can muster, and other factors, such as error correction.

Researchers at Google and in Sweden last year suggested it should be possible to factor a 2,048-bit integer in an RSA cryptosystem in about eight hours, given a 20 million-qubit quantum computer. Researchers in France claim it should be possible to factor 2,048-bit RSA integers in 177 days with 13,436 qubits and multimode memory.

Current quantum computers have orders of magnitude fewer qubits than they need to be cryptographically relevant. IBM recently unveiled a 127-qubit quantum processor. The IT giant says it is aiming to produce a 1,000-qubit chip by the end of 2023 and its roadmap places machines of more than 1 million qubits in an unidentified time period. The Jülich Supercomputing Center (JSC) and D-Wave Systems have a 5,000-qubit machine.

Not all qubits are equal however. The JSC/D-Wave machine relies on a quantum annealing processor and is adept at solving optimization problems. IBM's machine is gate-based, which is better suited for running Shor's algorithm to break cryptography.

In any event, the expectation is that quantum computers, eventually, will be able to conduct practical attacks on data protected using current technology – forcibly decrypt data encrypted using today's algorithms, in other words. Hence, the White House issued a national security memo in May emphasizing the need to promote quantum computing and to mitigate the risks it poses to encryption.

The primary concern is that data protected with current encryption algorithms often needs to remain secure for some period of time, perhaps as much as 75 years for government secrets, banking information, and health data. Waiting to see what quantum computers can do decades hence isn't exactly a sensible security posture.

NIST has been on the case since 2017 when it started with a group of 82 cryptographic algorithms as part of its Post Quantum Cryptography (PQC) Standardization Process. Of these, 69 candidates were deemed fit enough to take part in Round One. In 2019, twenty-six advanced to Round Two. By 2020, seven went on to Round Three, with eight alternates.

Round Three has now concluded and four candidate algorithms have been recommended for standardization, meaning we're likely to see their adoption by companies and vendors that seek to be NIST compliant.

"NIST will recommend two primary algorithms to be implemented for most use cases: CRYSTALS-KYBER (key-establishment) and CRYSTALS-Dilithium (digital signatures)," NIST said in a statement. "In addition, the signature schemes FALCON and SPHINCS+ will also be standardized."

Two months ago, as NIST prepared to announce its recommendations, an official with the NSA, believed to have meddled with past encryption algorithms, insisted in a Bloomberg interview that "there are no backdoors" in these new algorithms. Nonetheless, the new algorithms may see further refinement.

The Register asked Bruce Schneier, a cryptographer and public-interest technologist, to comment and he provided a draft of an essay on the subject.

He describes the NIST cryptanalysis competition as brutal, noting that twenty-five candidate algorithms were attacked successfully enough to oust them from Round One and another eight were similarly removed from Round Two. And he says in the months leading up to NIST's announcement, cryptanalysis was published affecting at least four of the finalists.

Agility is the only way to maintain security

"One of the most popular algorithms, Rainbow, was found to be completely broken," [PDF] wrote Schneier. "Not that it could theoretically be broken with a quantum computer, but that it can be broken today – with an off-the-shelf laptop in just over two days. Three other finalists, Kyber, Saber, and Dilithium, were weakened – with new techniques that will probably work against some of the other algorithms as well."

NIST however isn't done. There will be a Round Four, in which the four above-mentioned algorithms can have their specifications tweaked and four Key-Establishment Mechanism (KEM) candidates (BIKE, Classic McEliece, HQC, and SIKE) will be studied further and likely winnowed down to two.

Schneier said the process is working as it should and emphasized the need for cryptographic resilience – to be able to switch to new algorithms if widely used ones get broken.

"We can't stop the development of quantum computing," wrote Schneier. "Maybe the engineering challenges will turn out to be impossible, but it's not the way to bet. In the face of all that uncertainty, agility is the only way to maintain security." ®

Other stories you might like

Biting the hand that feeds IT © 1998–2022