Most current encryption methods are computationally secure. While we know how to break them, the good news is that it would take a computer around 300 trillion years to break RSA-2048-bit encryption. So, we are good, right?

Well, perhaps we were, until Peter Shor discovered a new algorithm that would bring this down to around 10 seconds! The algorithm would however need a hypothetical device called a “Quantum Computer”. Such a device didn’t exist back then and still doesn’t exist today, but experts believe that a “cryptographic relevant quantum computer” (CRQC) will exist within the next decade.

This is why NIST started a project on upgrading vulnerable encryption methods back in 2015 and after working on this for more than eight years, they have just released three finalized standards:

• FIPS 203 enables quantum-safe encryption (a lattice-based key-exchange enables two parties to establish a shared key which then can be used for encryption/decryption with a symmetrical algorithm). The algorithm used is CRYSTALS-Kyber (ML-KEM).
• FIPS 204 and FIPS 205 are algorithms for protecting digital signatures. FIPS 204 defines the primary algorithm (CRYSTALS-Dilithium or ML-DSA) while FIPS 205 defines a backup algorithm (Sphincs+ or SLH-DSA).
  
  

So What Exactly is Broken and What is Safe?

Most asymmetric encryption methods (public-key crypto, such as RSA encryption or Elliptic Curve Cryptography (ECC)) are vulnerable to quantum attacks. Symmetric encryption (such as AES) is considered safe assuming the key size is appropriate.

Public key cryptography works by encrypting a message with a public key (that is well known and can be published) in a way that only the person who knows the private key (which is private) can decrypt it. Post-quantum cryptography (PQC) introduces new algorithms intended to replace these vulnerable asymmetric encryption methods.

Symmetric Encryption

One interesting fact is that FIPS 203 doesn’t replace asymmetric encryption but rather provides a quantum-safe method for establishing a shared key that can then be used in symmetric encryption. This means that symmetric encryption, with appropriate key sizes, remains a strong and viable option in a post-quantum world.

Randomness is Key

The initiator of an encrypted connection needs access to high-entropy randomness. To generate a 256-bit encryption key, it needs 512-bits of randomness. FIPS 203 relies on NIST-approved randomness generators to guarantee sufficient randomness without additional processing. The recipient of the encrypted shared key does not need access to high-entropy randomness.

Key Sizes are Much Bigger

The FIPS 203 standard defines three types of parameters of various strengths that fit into security strength categories. More specifically, ML-KEM-512 fits into security category 1, ML-KEM-768 fits into security category 3 and ML-KEM-1024 fits into security category 5. However, the key sizes are considerably larger than existing schemes.

For example, ML-KEM-768 has a public key size of 1184 bytes and a private key size of 2400 bytes. Compare this with ECC-256 has a key size of 32 bytes (256 bits). That private key is 75 times bigger!

See below for further examples (where the encapsulation key is effectively the public key and the decapsulation key is the private key):

Digital Signature Algorithm

The new Digital Signature Algorithm (FIPS 204) is a lattice based digital signature algorithm previously known as Dilithium. Its key sizes are also considerably larger. ML-DSA-65 requires 1,952 bytes for the public key and 3,309 bytes for a signature – compared to Ed2559 (EC) which uses 32 bytes for the public key and 64 bytes for the signature.

Word of Caution

While NIST has finalized the three new standards for quantum-safe algorithms (FIPS 203, 204 and 205), these algorithms are still new. While they have undergone extensive review over the last eight years, it's essential to recognize that implementation vulnerabilities, such as side-channel attacks, can still arise. For example, a 2022 side-channel attack on CRYSTALS-Kyber exploited power consumption variations, highlighting the need for secure implementations. Although the attack did not break the algorithm itself, it emphasized the importance of robust implementation practices.

Additionally, another candidate algorithm, SIKE, was withdrawn from the standardization process in 2022 after being successfully attacked. These examples illustrate the importance of proceeding cautiously and not assuming that the adoption of new algorithms will eliminate all security concerns.

So Are These New Algorithms Guaranteed to be Quantum-safe?

The only answer to this question is: No. There is no mathematical proof that guarantees that quantum computers (or any other computer) cannot break these algorithms. We just know that Shor’s algorithm cannot be applied to them. We also know that they are secure under the assumption that the well-studied computational lattice problem cannot be solved efficiently. However, there is no proof.

That said, these new algorithms have undergone a lengthy diligence and currently no algorithm even with quantum computers are known to break them. This is why NIST released FIPS 203, 204 and 205.

What Happens Now?

We expect that adoption of these new standards will be quite fast. The strategy for the US is already outlined in the Quantum Computing Preparedness Act with a budget of $7.1 billion USD to migrate just the federal government. This number doesn’t include the critical national security systems, so this number will probably double. Other security bodies in Europe (like Germany’s BSI, France’s ANSSI and UK’s NCSC) will most likely follow.

What About QKD?

Quantum Key Distribution (QKD) is a protocol that uses quantum effects to enable two parties to agree on a shared key. However, due to current limitations, QKD is only practical for certain niche use cases and is not yet mature or widely applicable. The focus should therefore remain on the migration to post-quantum cryptography and the adoption of symmetric keying methods for most use cases.

Next Steps – Quantum Safe Strategy

With the release of NIST’s candidate standards, every organization should start developing a quantum-safe strategy. This involves more than just adopting new algorithms—it requires a thorough review of key management practices, infrastructure readiness for larger key sizes, and the potential performance impact. It's also essential to consider hybrid encryption approaches that combine existing security methods with new quantum-safe algorithms.

In summary, while the move to quantum-safe algorithms is a critical step, it must be part of a broader, well-considered strategy to ensure robust security in the quantum era.