The U.S. Department of Commerce’s National Institute of Standards and Technology (NIST) has selected four quantum-resistant cryptographic algorithms for general encryption and digital signatures.
NIST, a US standards setting body and research organization within the Department of Commerce, announced the four algorithms after a six-year period assessing potential quantum-resistant (QR) alternatives to today’s cryptographic algorithms for public key encryption, digital signatures, and key exchange.
In 2016, NIST asked the world’s cryptographers to devise and then vet potential quantum-resistant methods to secure communications for everything from websites to email.
SEE: What is quantum computing? Everything you need to know about the strange world of quantum computers
Today’s key algorithms include AES-256 for symmetric key encryption, SHA-256 and SHA-3 for hashing functions, RSA public key encryption for digital signatures and key establishment, Elliptic Curve Cryptography (ECDSA, ECDH) and DSA public key encryption for digital signatures and key exchange.
NIST has currently selected only the CRYSTALS-Kyber algorithm for general encryption in a post-quantum world. However, it is still considering four others.
The Kyber algorithm is already used by internet firm Cloudflare in its post-quantum CIRCL (Cloudflare Interoperable, Reusable Cryptographic Library) library of cryptographic primitives written in Go. Amazon since 2020 has supported Kyber as one of its post-quantum key exchange algorithms for Transport Layer Security (TLS) 1.2, the encryption protocol behind HTTPS websites. And IBM used Kyber for its first quantum-resistant tape drive.
NIST has also nominated CRYSTALS-Dilithium, FALCON and SPHINCS+ for post-quantum digital signatures.
The four selected encryption algorithms will become part of NIST’s post-quantum cryptographic standard, expected to be finalized around 2024. This selection marks the beginning of NIST’s post-quantum cryptography standardization project.
NIST kicked off the search for new post-quantum encryption algorithms in 2016 after assessing that a sufficiently large quantum computer would render all major public key encryption algorithms insecure, while AES-256 would only require larger key sizes, and SHA-256 and SHA-3 would require larger hash outputs.
Its position was based on AT&T Bell Labs researcher Peter Shor’s algorithm that showed a powerful enough quantum computer would endanger many modern communications systems protected by these types of encryption.
And while such a quantum computer is still years away, NIST noted it has historically taken almost 20 years to deploy modern public key cryptography infrastructure. On top of this, a sophisticated adversary could collect a ton data with today’s algorithms and decrypt it once they acquire a sufficiently powerful quantum computer.
How big would that encryption-busting computer need to be?
The Department of Homeland Security (DHS) and NIST noted in its 2021 FAQ about post-quantum cryptography that a quantum computer capable of running Shor’s Algorithm to break a public key will need an estimated 6,000 stable qubits. But qubits are notoriously fragile.
DHS notes that today’s cryptographic algorithms are still very safe from a computer like Google’s 54-qubit quantum Sycamore chip, which the firm claimed had achieved “quantum supremacy” – although this is disputed. Last year IBM said it was targeting a 4,000-qubit computer by 2025.
“The point at which a given quantum computer is built with sufficient qubit capacity to break public key cryptography sometimes called “cryptographically relevant”, when a quantum machine now can break our current cryptographic algorithms. This is still significantly larger in size and power than a quantum machine that achieves “quantum supremacy”,” DHS notes.
SEE: These are the biggest cybersecurity threats. Make sure you aren’t ignoring them
Still, the the White House in May recognized the impending threat to national security and outlined several proposals to accelerate US R&D in quantum computing and a rough timeline for federal agencies to deploy quantum-resistant cryptography – to keep it ahead of and safe from rivals like China and Russia. Other governments including those in Australia, France, the UK and elsewhere have acknowledged post-quantum risks to their organizations’ networks and communications.
The White House wants key federal agencies to migrate existing cryptographic systems to ones that are resistant to a ‘cryptanalytically’-relevant quantum computer (CRQC) in order to mitigate “as much of the quantum risk as is feasible” by 2035.
NIST recommends CRYSTALS-Dilithium as the primary algorithm for digital signatures, while FALCON is suitable for applications that need signatures smaller than Dilithium can provide.
NIST picked SPHINCS+ as a backup despite it being comparatively larger and slower than the other two because it was based on a different math approach to the other three algorithms it selected.
“Three of the selected algorithms are based on a family of math problems called structured lattices, while SPHINCS+ uses hash functions. The additional four algorithms still under consideration are designed for general encryption and do not use structured lattices or hash functions in their approaches,” NIST said.
SEE: These are the cybersecurity threats of tomorrow that you should be thinking about today
“Our post-quantum cryptography program has leveraged the top minds in cryptography – worldwide – to produce this first group of quantum-resistant algorithms that will lead to a standard and significantly increase the security of our digital information.” NIST director Laurie E. Locascio said in a statement.
NIST intends for the new public-key cryptography standards to specify “one or more additional unclassified, publicly disclosed digital signature, public-key encryption, and key-establishment algorithms that are available worldwide” that can protect sensitive government information beyond the advent of powerful quantum computers.
