Post-quantum security: ML-KEM, PQXDH, and the hybrid Triple Envelope

The cryptography community has a name for the most insidious threat in modern messaging: harvest now, decrypt later. Every ciphertext currently crossing the internet — every session that has ever been established — can be recorded today and stored at trivial cost. The files will still be there when a cryptographically relevant quantum computer arrives, and Shor's algorithm will unlock them all in one afternoon. Classical messaging does not defend against this, because classical messaging was not designed to.

Enchant's answer is not a promise. It is a series of post-quantum primitives wired into both ends of the session lifecycle: the key exchange that starts a session, and the Envelope that runs every message inside it. This post is the technical tour of those primitives, as implemented in the LibEnchant cryptographic library — ML-KEM, PQXDH, and a hybrid Envelope that refuses to trust any single algorithm with your secrets.

The threat: what Shor's algorithm actually breaks

Shor's algorithm solves the discrete logarithm problem in polynomial time on a quantum computer. That single result demolishes the two families of classical public-key cryptography still in use today:

• Finite-field DH / DSA / RSA. The math of modular exponentiation collapses. RSA-2048, once a 112-bit-work-factor fortress, becomes a polynomial-time exercise.
• Elliptic-curve DH. X25519, P-256, all of them — the hardness of EC discrete logarithms is exactly what Shor breaks.

Note what Shor does not break: symmetric cryptography. AES-256 and SHA-256 survive quantum attacks with only a square-root speedup (Grover's algorithm), which is precisely why quantum-resistant designs pair a lattice KEM with a classical DH and rely on symmetric key renewal for the message layer. Quantum computers attack the key exchange, not the message cipher.

The NIST competition that selected ML-KEM (then called Kyber) in 2024 evaluated candidates precisely on this scale, assigning security categories by comparison to AES: category 3 means "as hard to break as a 192-bit key," category 5 means "as hard to break as a 256-bit key." Those categories matter, because Enchant ships both — ML-KEM-768 at the message layer and ML-KEM-1024 at the handshake.

ML-KEM: the building block

ML-KEM is a key encapsulation mechanism (KEM) standardized in FIPS-203, built on the Module-LWE problem: recovering the private key from the public key is as hard as solving a noisy linear system in modules over a polynomial ring. Unlike DH, its hardness is believed to survive quantum computers because there is no known quantum shortcut for lattice problems — the best quantum algorithms achieve only polynomial-factor improvements over classical ones.

A KEM has three operations, and LibEnchant exposes all three directly as enchant_kem_keypair, enchant_kem_encapsulate, and enchant_kem_decapsulate:

$$\begin{aligned} \mathrm{KeyGen}() &\rightarrow (\mathit{ek}, \mathit{dk}) &&\text{encapsulation key, decapsulation key}\ \mathrm{Encap}(\mathit{ek}) &\rightarrow (K, c) &&\text{random session key, ciphertext}\ \mathrm{Decap}(\mathit{dk}, c) &\rightarrow K &&\text{recovered session key} \end{aligned}$$

The flow mirrors DH perfectly — Alice sends Bob a ciphertext, Bob recovers the same key — which is why ML-KEM drops into the handshake and the Envelope where X25519 used to sit alone. The sizes are the price of post-quantum security, and they are worth quoting exactly:

The shared secret is 32 bytes in both cases — exactly the size X25519 produces, which means the two can be concatenated into a single HKDF input without padding gymnastics. In the wire format the parameter set is tagged explicitly: KEM_TYPE_ML_KEM_768 = 0x07, KEM_TYPE_ML_KEM_1024 = 0x0A, so keys are self-describing and the decapsulator knows exactly which algorithm produced each ciphertext.

PQXDH: the post-quantum handshake

Classical X3DH derives its session secret from four X25519 outputs (see our X3DH post for the full treatment). PQXDH — the handshake every new Enchant session actually runs, under envelope protocol version 4 — does not replace those four DH terms. It appends an ML-KEM-1024 encapsulation to them and mixes everything in a single domain-separated HKDF call:

$$\mathrm{IKM} = \underbrace{\mathrm{FF}^{32}}_{\text{discontinuity marker}} \parallel \mathrm{DH}_1 \parallel \mathrm{DH}_2 \parallel \mathrm{DH}$$3 , [,\parallel \mathrm{DH}4,] \parallel \underbrace{\mathit{SS}{\mathrm{KEM}}}{32\ \mathrm{bytes}}

$$K = \mathrm{HKDF\text{-}SHA256}(\mathrm{IKM},\ \mathrm{salt}=0^{32},\ \mathrm{info}=\text{``EnvelopeText_X25519_SHA-256_ML-KEM-1024"},\ L=96)$$

$$\rightarrow RK \parallel CK_{\mathrm{send}} \parallel pqk$$

Three design decisions in this one equation are deliberate:

1. The discontinuity marker. The 32-byte 0xFF prefix is a protocol separator. Even if identical DH material were ever reused across protocol generations, a classical X3DH session and a PQXDH session can never derive the same keys — the HKDF inputs are structurally different. (The constant is literally named PQXDH_DISCONTINUITY_BYTES in the source.)
2. Hybrid composition. The session is secure if either the classical DH half or the KEM half is secure. A flaw found in ML-KEM tomorrow does not retroactively decrypt today's sessions; a quantum computer today does not see past the X25519 layer. The classic "if one primitive breaks, the other still stands" argument — here it is not an argument, it is the construction.
3. Domain separation. The info string "EnvelopeText_X25519_SHA-256_ML-KEM-1024" names the exact composition of the input. HKDF outputs from this handshake cannot be confused with outputs from any other Enchant protocol, because no other protocol uses this label.

The result is a 96-byte master key split into the root key $RK$, the initial chain key, and a post-quantum key $pqk$ that seeds the Envelope. The handshake is only run once per session; everything after it is the Envelope's job.

The hybrid Envelope: ML-KEM-768 on every turn

The handshake protects one key exchange. A session is thousands of messages long, and the session Envelope is what turns that single secret into a fresh key per message — while remaining forward-secret. Enchant's Triple Envelope carries the post-quantum guarantee into the Envelope itself:

At every key turn, both sides generate a fresh ephemeral key pair and run an ML-KEM-768 encapsulation in parallel. The two shared secrets are concatenated and mixed through HKDF with a labeled combine step:

$$ec_{ss} = \mathrm{X25519}(\text{our new ephemeral},\ \text{their ephemeral})$$

$$pq_{ss} = \mathrm{ML\text{-}KEM\text{-}768}\ \mathrm{Encap/Decap}$$

$$(RK' \parallel CK'$${\mathrm{send}} \parallel CK'{\mathrm{recv}}) = \mathrm{HKDF\text{-}SHA256}(ec_{ss} \parallel pq_{ss},\ \mathrm{salt}=0^{32},\ \mathrm{info}=\text{``enchant_TripleRatchet_Combine_20240101"},\ L=96)

Why ML-KEM-768 in the Envelope and ML-KEM-1024 in the handshake? The handshake is the highest-value target — it establishes the session's identity and is the only place an eavesdropper can attempt a harvest — so it gets the category-5 parameter set. Envelope turns happen often, and category-3 ML-KEM-768 is still substantially harder to break than the X25519 classical half it rides alongside; the pair's combined security is the maximum of the two, not the minimum.

There is also a graceful degradation path for the Envelope: if PQ keys are unavailable (an old peer, a partial directory response), the quantum half is derived from the classical half through a dedicated HKDF call with its own label ("enchant_TripleRatchet_PQ_Derive_20240101"), keeping the Envelope's mechanics identical. The post-quantum layer is additive — it never breaks the classical session path, it just seals it further.

SPQR: post-quantum forward secrecy for every message

The Envelope guarantees forward secrecy within a chain: steal a chain key and you see only messages after the last turn, not before it. But a single decrypted chain key still exposes a run of messages until the next key turn. SPQR — the sealed post-quantum turn used in the current envelope protocol — tightens this to per-message post-quantum forward secrecy.

The construction replaces the key turn with a KEM-based one. Instead of exchanging ephemeral DH keys every $n$ messages, every message carries a fresh ML-KEM-1024 encapsulation:

   Sender                                       Recipient
 
   Envelope key R (or fresh ephemeral)           decapsulation key dk
        │                                             │
        ├─ Encap(ek) ──→ (pqk, capsule)               │
        │                                              │
        │   capsule ────────────────────────────────►  │
        │                                              ├─ Decap(dk, capsule) → pqk
        │                                              │
   chain key CK' = H(pqk ‖ CK)                  CK' = H(pqk ‖ CK)  (same!)
        │                                              │
   message key MK = H'(CK')                      MK = H'(CK')      (same!)

The chain step is a single HMAC-labeled KDF:

$$CK' = \mathrm{HMAC\text{-}SHA256}(\mathrm{state}, pqk)$$

with the domain label "SPQR_SymmetricChain" — the same state → same output, so both sides turn in lockstep without any additional handshake. Because the KEM key is fresh per message, each message is under a key that no longer exists for the next message: compromise at time $T$ reveals exactly one message. The per-message encapsulation replaces the batch key turn's granularity of "a run of messages" with a granularity of "one message."

SPQR enforces the same resource bounds as the classical Envelope — a maximum forward jump of 25,000 (SPQR_MAX_JUMP), at most 2,000 skipped-key entries (SPQR_MAX_OOO_KEYS), and at most 5 concurrent receiver chains (SPQR_MAX_RECEIVER_CHAINS) — so a hostile peer cannot inflate the skipped-key table into a memory bomb.

What the full stack achieves

Nothing here is speculative. Every primitive named above is implemented, tested, and exposed through the C API of LibEnchant — enchant_prekey_generate_kyber_batch, enchant_kem_encapsulate, enchant_kem_decapsulate, enchant_session_manager_establish_pqxdh, and enchant_session_cipher_encrypt / enchant_session_cipher_decrypt — with the parameter sets and labels quoted in this post appearing verbatim in the source. When a quantum computer finally boots, the interesting question will not be "were Enchant messages encrypted?" It will be "did the attacker record an Enchant session before 2026?" The answer to that one is a message you can read today, and the math says it stays that way.