What IND-CCA Does Not Promise: KEM Binding, Re-Encapsulation and the Shared Secret ML-KEM Hands You

Picture two agents that have just run ML-KEM and now hold the same thirty-two bytes. They know an eavesdropper cannot learn those bytes, even one who can feed the decapsulating side forged ciphertexts and watch the results; that is what indistinguishability under chosen-ciphertext attack, IND-CCA, guarantees. What they do not know, from that guarantee alone, is whether those bytes could also have come out of a different ciphertext, or been encapsulated to a different public key. For most uses the difference never matters. For a protocol that treats the shared secret as proof of who it is talking to, it is the whole question. The cryptographic literature now has a name for it, binding, and a growing list of protocols whose security turned out to rest on it.

Two questions a shared secret can answer

A key-encapsulation mechanism, or KEM, has three algorithms. Key generation produces a public encapsulation key and a private decapsulation key. Encapsulation takes the public key and returns a ciphertext together with a fresh shared secret. Decapsulation takes the private key and the ciphertext and recovers the same secret. ML-KEM, standardized by NIST as FIPS 203, is the lattice-based KEM now being deployed to protect key exchange against future quantum computers. Its security target is IND-CCA: an attacker who sees the public key and a challenge ciphertext, and who may ask for the decapsulation of any other ciphertext, still cannot tell the real shared secret from random bytes.

That definition answers a confidentiality question: can anyone else learn the secret? It does not answer an attribution question: given a particular shared secret, how many different public keys, ciphertexts or key pairs could have produced it? An analogy helps. A tamper-proof envelope guarantees nobody read the letter inside. It does not, by itself, tell you which address it was mailed to. If two different envelopes, addressed to two different people, could contain the identical letter, a recipient who reasons 'only someone writing to me could have produced this letter' is wrong, even though no envelope was ever opened.

Binding is the name for that attribution property. A KEM binds a value if equal shared secrets force that value to be equal too. Binding is not implied by IND-CCA, and it is not implied by the older robustness notions, which ask only whether one ciphertext can decapsulate validly under two keys. Whether a protocol needs it depends on what the protocol does with the secret. If the secret is fed into a key schedule together with a hash of every message exchanged, the transcript supplies the attribution and the KEM need not. If the secret is used more or less directly as the session key, or as evidence of a peer's identity, the KEM's own binding is what holds the protocol together.

The binding lattice: what binds what, and against whom

Cremers, Dax and Medinger, in work published at ACM CCS 2024, gave the first systematic family of binding notions for KEMs. They consider three values visible in any run: the public key, the ciphertext and the output key. A property is written as a set of values P that binds a set Q: whenever two runs agree on everything in P, they must also agree on everything in Q. The public key alone is excluded from P because one public key is meant to serve many encapsulations. That leaves six core properties, among them 'the output key binds the ciphertext' and 'the output key binds the public key', usually shortened to BIND-K-CT and BIND-K-PK.

Each property comes in three strengths, distinguished by how much power the adversary has over the key pairs. In the honest variant, HON, the key pairs come from honest key generation and the adversary never sees the private keys. In the leakage variant, LEAK, the key pairs are honestly generated but then handed to the adversary, which models a compromised key that was once legitimate. In the malicious variant, MAL, the adversary may construct key material however it likes, which models a party that generates its own keys dishonestly. Each strength implies the weaker ones, so a KEM that is MAL-BIND-K-PK is automatically LEAK- and HON-BIND-K-PK.

Two consequences are worth stating plainly. First, the strengths matter more in practice than the letters. A protocol in which keys can be stolen needs at least LEAK binding; a protocol in which an untrusted party supplies its own key needs MAL binding. Second, some properties are unreachable by design. Cremers and colleagues show that an implicitly rejecting KEM, one that answers an invalid ciphertext with a pseudorandom key rather than an error, can never make the ciphertext bind the output key. The same ciphertext submitted under two different private keys yields two unrelated rejection keys, which is exactly what implicit rejection is for. ML-KEM rejects implicitly, so the only binding properties worth asking of it are the ones in which the output key, alone or with something else, binds the rest.

Re-encapsulation: two ciphertexts, one secret

The binding notions earned attention because of a concrete attack class. Cremers and colleagues encoded their notions as symbolic models in the Tamarin protocol prover, then asked Tamarin which binding properties a given protocol needed. One of their case studies was the authenticated key exchange described in the original Kyber paper, in which the initiator encapsulates to the responder's long-term key, the responder encapsulates back to the initiator's long-term key and to a fresh ephemeral key, and all three shared secrets feed a key-derivation function. With Kyber plugged in, the protocol appears sound. With a different, still IND-CCA secure, KEM plugged in, Tamarin found an attack. The protocol's security had silently depended on a property of Kyber that its proof never used.

The mechanism is easy to state. Most post-quantum KEMs are built with a Fujisaki-Okamoto style transform: encapsulation picks a random message, derives its encryption coins deterministically, and encrypts. Whoever decapsulates necessarily recovers that message. Now suppose the KEM's output key depends only on the message. A malicious party C receives a ciphertext from A, decapsulates it with its own key, learns the message, and encapsulates the same message to B's public key. The two ciphertexts differ, the two public keys differ, and the shared secret is identical. C can then relay the conversation so that A believes it shares a key with C while B believes it shares the key with A: an unknown key-share attack, in which two honest parties agree on a key but disagree about who they are talking to.

Nothing here breaks IND-CCA, because C legitimately holds a private key and learns a secret that was encapsulated to it. Nothing here breaks robustness either, because robustness asks about one ciphertext under two keys, whereas re-encapsulation produces two ciphertexts. The attack is excluded precisely by the output key binding the public key: if the secret had depended on the recipient's public key, re-encapsulating to B would have produced a different secret. That is the sense in which binding is a separate design obligation, not a corollary of the familiar ones.

The case that reached a deployed protocol design

Signal's PQXDH handshake added a post-quantum KEM to the Diffie-Hellman combinations of its earlier X3DH design. Bhargavan, Jacomme, Kiefer and Schmidt analysed it with the ProVerif and CryptoVerif tools and reported, at USENIX Security 2024, a re-encapsulation variant against the first revision of the specification. In their scenario an attacker has compromised one of Bob's signed post-quantum prekeys while another remains secure. The attacker lets Alice encapsulate to the compromised prekey, learns the shared secret, crafts a new ciphertext that carries the same secret to the uncompromised prekey, and swaps the key identifier. Bob completes the handshake with the secure prekey, yet the attacker knows the session's post-quantum input.

The consequence they describe is a loss of session independence: compromise of a single prekey could expose sessions that should have relied on a different, uncompromised one, even after the compromised key had been deleted. The authors then checked whether Kyber, the KEM Signal actually used, permitted such re-encapsulation. It did not, because Kyber's key derivation includes the public key. The deployed implementation was therefore not exposed, but the specification as written had depended on an unstated KEM property. The revised specification made the dependency explicit, requiring either that the KEM bind its secret to the public key or that the public key be included in the associated data of the message encryption.

Fiedler and Gunther, in a concurrent game-based analysis later published at PKC 2025, reached a matching conclusion from a different direction: PQXDH's design choices make a KEM binding property necessary, and both Kyber and ML-KEM satisfy the notion their proof relies on. The lesson is not that PQXDH was broken. It is that a carefully designed, heavily reviewed protocol carried an implicit assumption about its KEM for long enough to need two independent formal analyses to surface it, and that the assumption held only because of a detail of one particular KEM.

Where ML-KEM's binding comes from, and what FIPS 203 changed

Kyber's third-round specification derived the final key by hashing an intermediate key together with a hash of the ciphertext. That ciphertext hash made the key bind the ciphertext in the most direct way possible. FIPS 203 removed it. Its Appendix C lists the change explicitly: encapsulation no longer includes a hash of the ciphertext in the derivation of the shared secret, and decapsulation was adjusted to match. A reader who learned that the ML-KEM secret is tied to the ciphertext through a final hashing step learned a property of the submission, not of the standard.

What remains is subtler and, it turns out, sufficient. In ML-KEM, encapsulation hashes the random message together with a hash of the encapsulation key, and that single hash call outputs both the shared secret and the coins used to encrypt. Binding to the public key follows directly: a different public key changes the hash input and therefore the secret, unless someone finds a hash collision. Binding to the ciphertext follows from the re-encryption check. A decapsulator accepts a ciphertext only if re-encrypting the recovered message under the derived coins reproduces it exactly. Two accepted ciphertexts with the same secret would need the same message and key hash, hence the same coins, hence the same deterministic encryption, hence the same ciphertext. Hashing the encapsulation key into the derivation also gives every key pair its own domain, which Barbosa and colleagues note is a defence against multi-target attacks.

Fiedler and Gunther's analysis, as Cremers and colleagues summarize it, establishes that ML-KEM, like Kyber, is LEAK-BIND-K-PK and LEAK-BIND-K-CT. Their summary table also credits ML-KEM, citing Kraemer, Struck and Weishaupl, with the malicious-strength version of one combined property, in which the key and public key together bind the ciphertext, while the X-Wing specification states that ML-KEM lacks it; the disagreement turns on how the private key is modelled, which is itself a sign of how much rests on key formats. Schmieg, reviewing the same question, concluded that NIST's simplified derivation was the right choice: it improved performance without giving up binding against an adversary who can steal keys. The boundary is the malicious strength. When the adversary can fabricate the private key itself, ML-KEM is neither MAL-BIND-K-CT nor MAL-BIND-K-PK, because the stored key hash and the rejection secret are simply trusted. That case is a property of key formats and key provenance, and it deserves separate treatment from the honest-key protocol question addressed here.

What a protocol should bind for itself

Because binding is a property that protocols either inherit from the KEM or supply themselves, the useful engineering question is where each protocol gets it. The robust answer is to stop depending on the KEM. If the key-derivation input includes the public key and the ciphertext, or a hash of the whole transcript that contains them, then even a KEM with no binding at all cannot produce two runs with different inputs and the same session key. Cremers and colleagues give a generic wrapper of exactly this kind. The TLS 1.3 key schedule already achieves it through its transcript hash, which is why the hybrid groups used there could afford a simple concatenation of secrets.

Key confirmation is the second tool. NIST SP 800-227, the 2025 recommendation on using KEMs, says key confirmation should be used and describes a construction in which one party sends a message authentication code, computed with a key derived from the shared secret, over identifiers and the exchanged values. A successful confirmation tells each party that the other holds matching keying material for this specific exchange. The same publication requires that an encapsulating party obtain assurance of ownership before trusting another party's static encapsulation key, through a certificate authority or a proof-of-possession step, which closes the door through which re-encapsulation attacks usually enter: a peer whose key nobody vouched for.

A third rule concerns algorithm agility. A protocol that is secure with ML-KEM only because ML-KEM happens to bind the public key is not secure with an arbitrary IND-CCA KEM. Grubbs, Maram and Paterson showed that Classic McEliece, another well-studied post-quantum KEM, achieves neither form of public-key binding: one ciphertext can decrypt to the same plaintext under any private key. A design that lets operators swap the KEM, as crypto-agile systems are encouraged to do, inherits the weakest binding in its list unless the protocol binds the transcript itself.

Agent channels that use the secret alone

Mainstream transport protocols bind their transcripts, so the binding question rarely arises inside a standard TLS connection. It arises in the custom channels that agent platforms tend to build around them. An orchestrator that encapsulates a fresh key to each worker agent's published ML-KEM key and uses the resulting secret directly as a message-encryption key is relying on the KEM's binding for the claim that only the intended worker shares that key. A model-serving endpoint that accepts encapsulated request keys, so that prompts stay confidential past a load balancer, is relying on it for the claim that a response key belongs to one request. A tool server that authenticates agents by their ability to decapsulate a challenge is treating the shared secret as identity evidence, which is exactly where unknown key-share attacks bite.

In each case ML-KEM's LEAK binding helps: an attacker who steals one agent's private key cannot re-encapsulate traffic so that it appears bound to a different agent's public key. But three situations fall outside it. If the platform lets an agent or tenant supply its own key material, the relevant strength is MAL, which ML-KEM reaches only partly, and only when private keys travel as seeds rather than in expanded form. If the platform is designed to switch KEMs for agility, the binding is only as strong as the weakest KEM in the configuration. And if the channel is hybrid, combining ML-KEM with a classical exchange, the combiner rather than ML-KEM determines what is bound.

The practical response is not to avoid ML-KEM but to make the dependency visible. Derive channel keys from the shared secret together with the agent identifiers, both public keys and the ciphertext; add key confirmation before the first privileged message; and record, in the channel's design note, which binding property the protocol would need if those steps were removed. That turns a silent assumption into a reviewable one. The limits of the evidence should be stated too: the binding proofs are in the random-oracle model, the protocol findings come from symbolic and game-based analyses of specific designs, and none of them measures how often unbound agent channels occur in practice.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

Glossary

Key-encapsulation mechanism (KEM)

A public-key primitive that produces a fresh shared secret and a ciphertext that lets only the private-key holder recover it.

IND-CCA

Indistinguishability under chosen-ciphertext attack: the shared secret looks random even to an attacker who can obtain decapsulations of other ciphertexts.

Binding

A property under which equal outputs of a KEM force the equality of other values, such as the public key or ciphertext.

HON, LEAK and MAL

The three adversary strengths for binding: honest secret keys, honest keys later leaked to the attacker, and key material the attacker constructs.

Re-encapsulation attack

An attack in which a party that decapsulated a ciphertext encapsulates the same underlying message to another public key, producing one secret under two ciphertexts.

Unknown key-share attack

A failure in which two honest parties share a key but disagree about whom they share it with.

Implicit rejection

Returning a pseudorandom key, rather than an error, when a ciphertext fails validation.

Fujisaki-Okamoto transform

A construction that turns a passively secure encryption scheme into an IND-CCA KEM by deriving encryption coins from the message and re-encrypting to check ciphertexts.

Key confirmation

An exchange, typically a message authentication code over the handshake, that proves to each party that the other derived matching keys.

Transcript binding

Including a hash of every exchanged message in key derivation so that the session key depends on the exact run.

Robustness

An older notion asking whether a single ciphertext can decrypt or decapsulate validly under two different keys.

References

1. NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024)
2. Cremers, Dax and Medinger, Keeping Up with the KEMs: Stronger Security Notions for KEMs and Automated Analysis of KEM-based Protocols (ACM CCS 2024)
3. Bhargavan, Jacomme, Kiefer and Schmidt, Formal verification of the PQXDH Post-Quantum key agreement protocol for end-to-end secure messaging (USENIX Security 2024)
4. Fiedler and Gunther, Security Analysis of Signal's PQXDH Handshake (PKC 2025, IACR ePrint 2024/702)
5. Schmieg, Unbindable Kemmy Schmidt: ML-KEM is neither MAL-BIND-K-CT nor MAL-BIND-K-PK (IACR ePrint 2024/523)
6. Kraemer, Struck and Weishaupl, Binding Security of Implicitly-Rejecting KEMs and Application to BIKE and HQC (IACR ePrint 2024/1233)
7. Grubbs, Maram and Paterson, Anonymous, Robust Post-Quantum Public Key Encryption (IACR ePrint 2021/708)
8. NIST SP 800-227, Recommendations for Key-Encapsulation Mechanisms (2025)
9. Barbosa et al., X-Wing: The Hybrid KEM You've Been Looking For (IACR ePrint 2024/039)