Redirecting you to
Blog Post Sep 12, 2022

Who Are NIST’s Post-Quantum Algorithm Winners?

Quantum computing’s arrival will cause a ripple effect touching every corner of the technological landscape. In general terms, quantum computers lean on quantum physics to run multiple processes simultaneously, making them able to solve certain complex problems much more quickly than traditional computers can today.

In many ways this is good news, because stable quantum computing will introduce exciting technological possibilities. Quantum computing’s greater ability to solve complex problems promises potential breakthroughs in fields like artificial intelligence, financial modeling, and many others. However, there’s also a very significant and dangerous downside in regards to cybersecurity: quantum computers will be able to crack the existing cryptographic schemes protecting nearly all of the world’s digital operations.

When the first quantum computer becomes powerful enough, virtually all data using existing technology will become easily decrypted by whoever has access to one of these computers. This includes the most sensitive data we have, such as high-value industrial secrets or military and state secrets. In fact, it’s widely believed that today’s threat actors are even saving encrypted content so they can break it later using quantum computers.

This anticipated impact of quantum computing is so severe that it’s sometimes referred to as the Quantum Apocalypse. This “apocalypse” will not occur on a single, discrete date. Rather, over time the difficulty and time required to break encrypted files and communications will continue to decrease, and the risk of using pre-quantum algorithms will keep increasing.

This “apocalypse” may be years away, but governments and enterprises across the globe must begin preparing for the new age of quantum computing. To remain secure, the world must adopt new families of quantum-resistant cryptography.

The US National Institute of Standards and Technology (NIST) is driving a joint effort involving academics, government, and industry to arrive at a new set of cryptographic “primitives” that are secure against cracking by quantum computers. In July 2022, after a six-year effort, it made monumental progress in the journey to quantum-safe computing systems. NIST announced its winning selections for post-quantum encryption algorithms.

What Are the Winning Post-Quantum Algorithms?

The four winning algorithms include:

  • CRYSTALS-Kyber for general encryption to access secure websites. According to NIST, Kyber’s advantages include “comparatively small encryption keys that two parties can exchange easily, as well as its speed of operation.”
  • CRYSTALS-Dilithium, FALCON, and SPHINCS+ for digital signature algorithms or to sign documents remotely. NIST recommends Dilithium as the primary algorithm, while FALCON is best for uses requiring smaller signatures than Dilithium’s capabilities. SPHINCS+ is a larger and slower algorithm than the others, but its value lies in the fact that it’s based on a different mathematical approach (a stateless hash-based signature scheme) than the other three cryptographic algorithms. This makes SPHINCS+ a good backup option. Dilithium is expected to be used 99.9 percent of the time.

Understanding the Cryptography

To understand what this quantum future looks like, it’s important to understand cryptography today. For nearly 50 years public key infrastructure (PKI) has provided the cryptographic foundation to secure human and machine identities. PKI relies primarily on two standardized algorithms, Rivest-Shamir-Adleman (RSA) and elliptic-curve cryptography (ECC).

In 1994, mathematician Peter Shor discovered a new algorithm capable of breaking conventional public-key cryptography, but it required a then-theoretical quantum computer. This algorithm became known as Shor’s Algorithm and demonstrates that a quantum computer can factor integers much more efficiently than a classical computer. Therefore, this makes quantum computers more efficient at cracking RSA and ECC.

Now, consider just how integral encryption is today. It has fundamental uses in government, defense, finance, commerce, communication, transportation, and healthcare, just to name a few industries it touches. PKI secures everything from email accounts and Internet of Things (IoT) devices to financial transactions and healthcare data. Quantum computing threatens this digital trust.

The winning post-quantum algorithms are capable of withstanding the expected encryption-cracking capabilities of quantum computers. Why? They are based on entirely different mathematical principles that do not benefit from the extreme performance boost described by Peter Shor.

The new primitives use fundamentally different mathematical techniques than the related math problems that underlie RSA and ECC. RSA takes advantage of the difficulty in factorizing numbers down to very large primes. ECC relies on the difficulty in solving for two points on an elliptical curve. These related computational tasks are both reduced vastly due to Shor’s Algorithm.

But the new algorithms are different. Aside from SPHINCS+, they focus on lattice-based encryption, which uses not algebraic formulas but rather matrices.

Think of it as a geometric problem. A two-dimensional matrix (like a chess board with rows and columns) includes a set of integer points along these rows and columns, and solving problems about these integer points is a fundamentally different technique from solving the problems defined by RSA and ECC. To give our potential key space sufficient scope, the very large matrices involved will be not two-dimensional or even three-dimensional but rather will have upwards of 10,000 dimensions. All this complexity makes the brute force computation required to crack these keys prohibitively difficult for both traditional and quantum computing architectures.

Next Steps

While NIST’s announcement marks the end of one chapter, another is only beginning. Now, standards bodies, hardware and software manufacturers, and ultimately enterprises worldwide will need to implement new cryptography across all aspects of their computing systems. Standardization is expected by 2024. Until there is upgraded post-quantum cryptography everywhere, the world’s digital systems remain insecure. The preparation for this change must begin now.

Read the blog post, 5 Ways to Prepare Now for Quantum Computer.