ML-KEM: Future of Key Encapsulation

Cryptography

Understanding ML-KEM: The Future of Key Encapsulation

14 min read

What Problem Does ML-KEM Solve?

Every time you buy something online, log into your email, or send a private message, your computer needs to do something tricky: it needs to agree on a secret code with another computer, over an open connection that anyone could be watching.

Think about it like this. You and a friend are standing on opposite sides of a crowded room. You need to agree on a secret word that only the two of you will know. But everyone in the room can hear everything you say. How do you do it?

This is the "key agreement" problem, and it is one of the most important problems in all of computer security. For the past 30 years, we have solved it using mathematical tricks based on the difficulty of factoring very large numbers (RSA) or computing discrete logarithms on elliptic curves (ECDH). These tricks work because regular computers simply cannot do those calculations fast enough to break them in any reasonable time.

ML-KEM is a new solution to this problem. It stands for Module-Lattice Key Encapsulation Mechanism, and it was standardized by NIST as FIPS 203 in August 2024. The reason we need it is simple: quantum computers can solve those old mathematical problems very quickly. ML-KEM uses different math that quantum computers cannot crack.

Key Encapsulation vs. Key Exchange: A Subtle but Important Difference

You might hear the terms "key exchange" and "key encapsulation" used interchangeably, but they are actually different operations. Understanding the difference helps you understand what ML-KEM actually does.

In a traditional key exchange (like Diffie-Hellman or ECDH), both parties contribute equally. Each side generates a value, they swap those values, and then both sides independently calculate the same shared secret. Neither party alone chose the secret; it emerged from the combination of both contributions.

In a key encapsulation mechanism (KEM), the process is asymmetric. One party (let us call them Alice) publishes a public key. The other party (Bob) uses that public key to generate a random shared secret and produce a "ciphertext" that only Alice can open. Bob sends the ciphertext to Alice. Alice uses her private key to "decapsulate" it and recover the same shared secret. The secret was chosen by Bob's side of the process, and the ciphertext acts like a locked box that only Alice's private key can open.

The practical result is the same: both parties end up with the same shared secret that nobody else knows. But the KEM approach turns out to be much easier to build securely from lattice mathematics, which is why NIST chose it for the post-quantum standard.

Why Current Encryption Will Break

To understand why we need ML-KEM, you need to understand what quantum computers change. Today, virtually all key agreement on the internet relies on one of two mathematical problems:

• Integer factorization (used by RSA): Given two very large prime numbers multiplied together, find the original primes. A 2048-bit RSA key means the product is roughly 617 digits long. Classical computers cannot factor numbers this large in any practical timeframe.
• Elliptic curve discrete logarithm (used by ECDH and X25519): Given a point on a mathematical curve that was reached by "walking" some number of steps from a starting point, figure out how many steps were taken. With 256-bit curves, the number of possible answers is astronomically large.

In 1994, mathematician Peter Shor published an algorithm showing that a quantum computer could solve both of these problems exponentially faster than any classical computer. For RSA-2048, a classical supercomputer would need roughly 300 trillion years. A sufficiently powerful quantum computer running Shor's algorithm could do it in hours.

The key phrase is "sufficiently powerful." Today's quantum computers have a few thousand noisy qubits. Breaking RSA-2048 would require roughly 4,000 error-corrected logical qubits, which translates to millions of physical qubits with current error correction technology. We are not there yet. But quantum hardware is improving rapidly, and the consensus among researchers is that cryptographically relevant quantum computers will arrive within 10 to 20 years. NIST began the standardization process in 2016 specifically because cryptographic transitions take many years, and waiting until quantum computers exist would be far too late.

The Lattice Problem: Why ML-KEM Is Hard to Break

ML-KEM is built on a mathematical structure called a lattice. A lattice, in mathematical terms, is a regular grid of points in space. Think of tiles on a bathroom floor: a perfectly repeating grid in two dimensions. Now imagine that grid extended into three dimensions, like a crystal structure. Now imagine it in 256 dimensions, or 512, or 1024. You cannot visualize this, and that is exactly the point.

The specific hard problem ML-KEM relies on is called the Module Learning With Errors (Module-LWE) problem. Here is a simplified version of how it works:

Imagine you have a system of equations like this: you know a matrix A (public), and you are given a result b that equals A times some secret vector s, plus a small amount of random noise e. Your goal is to figure out the secret s. Without the noise, this would be basic linear algebra, solvable by any college freshman. But the noise makes it brutally hard. With enough dimensions (hundreds or thousands), no known algorithm, classical or quantum, can efficiently separate the signal from the noise.

An analogy: imagine someone tells you the result of a calculation, but they have rounded every intermediate step slightly and randomly. From the rounded result, you need to work backwards to find the exact original inputs. In two or three dimensions, you might manage it. In 768 dimensions, even the most powerful computer we can imagine cannot do it.

Grover's algorithm, which gives quantum computers a general speedup for search problems, does apply here, but only as a square-root speedup. That means a lattice problem with 256-bit security against classical computers still has roughly 128-bit security against quantum computers. ML-KEM's parameter sets are designed to account for this, so all three security levels remain robust even against quantum attackers.

How ML-KEM Works Step by Step

The ML-KEM process has three operations: key generation, encapsulation, and decapsulation.

1. Key Generation

Alice's computer generates a random secret (the private key) and uses it along with a public matrix A to create a public key. The public key contains A and a value t that is computed as A*s + e, where s is the secret and e is random noise. Alice publishes the public key and keeps the private key hidden.

2. Encapsulation

Bob wants to establish a shared secret with Alice. His computer takes Alice's public key and generates a fresh random value. Using that random value plus Alice's public key, his computer produces two things: a ciphertext c (which is safe to send publicly), and a shared secret key K (which Bob keeps). The ciphertext is essentially the random value encrypted in a way that only Alice's private key can reverse.

3. Decapsulation

Alice receives the ciphertext c and uses her private key to recover the same shared secret K. At this point, both Alice and Bob have the same key K. They can now use K as the key for a symmetric cipher like AES-256-GCM to encrypt their actual messages.

ML-KEM also includes an important safety feature called an "implicit rejection" mechanism. If someone sends Alice a malformed ciphertext (either by accident or as an attack), instead of producing an error message that might leak information, the decapsulation produces a random-looking output derived from the private key and the ciphertext. This prevents a class of attacks called "chosen ciphertext attacks" where an attacker tries to learn about the private key by observing how the system responds to bad inputs.

The Three Security Levels

FIPS 203 defines three parameter sets for ML-KEM. Each one represents a different trade-off between security strength and performance. The numbers in the names (512, 768, 1024) refer to the dimension of the lattice used.

Parameter Set	NIST Security Level	Equivalent Strength	Public Key Size	Ciphertext Size
ML-KEM-512	Level 1	At least as hard to break as AES-128	800 bytes	768 bytes
ML-KEM-768	Level 3	At least as hard to break as AES-192	1,184 bytes	1,088 bytes
ML-KEM-1024	Level 5	At least as hard to break as AES-256	1,568 bytes	1,568 bytes

To put "128-bit security" in perspective: it means an attacker would need to perform approximately 2^128 operations to break the encryption. That number, 340 undecillion (340 followed by 36 zeros), exceeds the estimated number of atoms in the observable universe. Even a quantum computer running Grover's algorithm against a 128-bit target would need 2^64 operations, which is still computationally infeasible.

Notice that these key sizes are significantly larger than classical alternatives. An X25519 public key is only 32 bytes. An ML-KEM-768 public key is 1,184 bytes, roughly 37 times larger. This is one of the practical trade-offs of post-quantum cryptography. The math that resists quantum attacks requires bigger numbers, which means bigger keys. For data encryption, this overhead is negligible. For protocols like TLS that perform many key exchanges per second, it matters more, which is one reason Google's Chrome team worked hard to optimize their ML-KEM deployment.

How Fast Is ML-KEM?

Despite the larger key sizes, ML-KEM is remarkably fast. On modern hardware, the three operations take approximately:

• Key generation: approximately 30 microseconds for ML-KEM-768
• Encapsulation: approximately 40 microseconds for ML-KEM-768
• Decapsulation: approximately 40 microseconds for ML-KEM-768

For comparison, RSA-2048 key generation takes tens of milliseconds (hundreds of times slower), and even X25519, which is considered very fast, takes about 120 microseconds per key exchange operation. ML-KEM is actually faster than most classical key agreement algorithms at the computational step itself. The only real overhead is the additional bytes transmitted for the larger keys and ciphertexts.

In a data encryption context, the KEM operation happens once per file. The actual data encryption (using AES-256-GCM) dominates the total time. Whether you encrypt a 1 MB document or a 25 GB video, the ML-KEM step adds well under a millisecond.

The NIST Standardization Process

ML-KEM did not appear out of nowhere. It is the result of an eight-year public process that is one of the most thorough algorithm evaluations in cryptographic history.

In December 2016, NIST issued a call for proposals for post-quantum cryptographic algorithms. They received 82 submissions from research teams around the world. Over three rounds of evaluation (2017-2020, 2020-2022, and 2022-2024), NIST and the global cryptography community analyzed each submission for security, performance, and implementation characteristics.

The algorithm that became ML-KEM was originally submitted as "CRYSTALS-Kyber" by a team of researchers from Europe. It survived every round, was selected as a finalist, and was published as FIPS 203 on August 13, 2024. During the evaluation, hundreds of published papers analyzed Kyber's security. Multiple research teams attempted to find weaknesses. The algorithm was also tested against side-channel attacks (where an attacker tries to learn secrets by measuring how long operations take or how much power the computer uses).

The fact that ML-KEM survived eight years of concentrated attack by the world's best cryptanalysts is the strongest evidence for its security. No algorithm can be mathematically proven secure in an absolute sense (this is true of all public-key cryptography, classical or post-quantum). But ML-KEM has passed the most rigorous public evaluation process ever conducted for a cryptographic standard.

Why Hybrid: ML-KEM + X25519 Together

QNSQY never uses ML-KEM alone. Every encryption operation combines ML-KEM with X25519, a classical elliptic curve algorithm. This approach is called "hybrid" cryptography, and major security organizations including NIST, NSA, ENISA (the EU cybersecurity agency), and BSI (Germany's Federal Office for Information Security) all recommend it.

The reasoning is straightforward. ML-KEM has been publicly studied for about nine years. X25519 has been publicly studied for about fifteen years and has been deployed in billions of devices. ML-KEM is believed to be secure against quantum computers but is relatively new. X25519 is thoroughly proven against classical computers but will fall to quantum attacks.

By combining both, QNSQY runs two independent key encapsulation operations and feeds both results into a key derivation function (HKDF-SHA3-256) to produce the final encryption key. An attacker must break both ML-KEM and X25519 to recover the key. If ML-KEM were somehow broken by a classical attack nobody anticipated, X25519 still protects the data. If a quantum computer breaks X25519, ML-KEM still protects the data. You need to defeat both locks to get in.

NIST published guidance on hybrid approaches in SP 800-227, specifically addressing how to safely combine post-quantum and classical algorithms during the transition period. The hybrid approach adds minimal computational overhead (both key operations complete in well under a millisecond combined) and provides meaningful insurance against unexpected cryptanalytic breakthroughs in either family of algorithms.

Common Misconceptions About ML-KEM

Several misunderstandings about ML-KEM circulate online. Clearing these up helps you make informed decisions.

"ML-KEM is unproven and experimental"

ML-KEM is a published NIST Federal Information Processing Standard (FIPS 203). It went through an eight-year public evaluation that is more rigorous than the process that standardized AES. The underlying mathematics (lattice problems, Learning With Errors) have been studied in academic cryptography since the 1990s. Oded Regev's foundational work on LWE was published in 2005, giving the core mathematical problem over 20 years of scrutiny. ML-KEM is not experimental. It is a vetted, standardized algorithm.

"Post-quantum algorithms are too slow for practical use"

This was partially true for early candidates, but ML-KEM is one of the fastest public-key cryptographic algorithms ever standardized. Its key generation, encapsulation, and decapsulation are faster than RSA operations at comparable security levels and comparable to X25519. The only trade-off is key size, not speed.

"We can wait until quantum computers are closer"

This ignores two facts. First, cryptographic transitions take years. Moving the entire internet from DES to AES took over a decade. Organizations with large deployed systems need time to plan, test, and migrate. Second, the "harvest now, decrypt later" attack means that data encrypted today with vulnerable algorithms is already at risk from future quantum computers. If your data needs to remain secret for 10 or more years, the time to act was yesterday.

"AES-256 is already quantum-safe, so we do not need ML-KEM"

AES-256 is quantum-safe for the encryption step, but AES is a symmetric cipher. It requires both parties to already share the same key. ML-KEM solves the key agreement problem: how two parties who have never communicated establish a shared AES key in the first place. Without quantum-safe key agreement, AES-256 cannot protect data because the key exchange itself is vulnerable. ML-KEM and AES-256 solve different parts of the encryption problem and are used together.

What ML-KEM Means for Your Files

When you encrypt a file with QNSQY, here is what happens at the ML-KEM level:

1. QNSQY generates a fresh ML-KEM keypair and a fresh X25519 keypair for this encryption.
2. The encapsulation step produces two shared secrets: one from ML-KEM and one from X25519.
3. Your password is processed through Argon2id (a memory-hard key derivation function) to produce a third key component.
4. All three components are combined via HKDF-SHA3-256 to produce the final AES-256-GCM encryption key.
5. The file content is encrypted with AES-256-GCM using that key.
6. The ML-KEM ciphertext, X25519 public key, Argon2id salt, and encrypted data are packaged into a .qs file.

When you decrypt, the reverse happens: your password regenerates the Argon2id component, the KEM ciphertexts are decapsulated with the private keys (which are themselves derived from the password), and all three are recombined to produce the same AES-256-GCM key.

The result is a file that is protected by three independent factors: the strength of ML-KEM against quantum computers, the proven strength of X25519 against classical computers, and the strength of your password processed through memory-hard Argon2id. All three would need to fail simultaneously for the encryption to be broken.

Sources

1. NIST FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard (August 2024)
2. NIST Post-Quantum Cryptography Standardization Project
3. NIST SP 800-227: Recommendations for Key-Encapsulation Mechanisms (Hybrid Guidance)
4. CRYSTALS-Kyber Algorithm Specification (original submission)
5. Alkim, Ducas, Poppelmann, Schwabe: Post-Quantum Key Exchange from Module-LWE (Kyber Foundations)
6. Cloudflare: The State of the Post-Quantum Internet (2024 Deployment Analysis)
7. Chromium Blog: Advancing Our Amazing Bet on Quantum-Resistant Encryption (X25519MLKEM768 Rollout)

Related Articles

• Lattice-Based Cryptography: Foundation of PQC
• Why Hybrid Encryption Matters
• What is Post-Quantum Cryptography?
• NIST FIPS 203/204/205: The Complete Guide

Ready to Protect Your Data?

QNSQY uses ML-KEM + X25519 hybrid encryption in all tiers, including the free version.

---

Originally published at quantumsequrity.com.