Post-quantum without a prekey server

Correction, 2026-08-23. This post originally described deriving the starting ML-KEM keypair from the X25519 secret two contacts already share, and argued that a passive recorder is protected from the first message because that secret never crosses the wire. That argument was wrong, and we have changed the design rather than the wording. The secret is a function of both parties’ long-term X25519 public keys — and two of our own flows put those keys on channels an adversary can record, so breaking X25519 later hands over both halves of the hybrid for the first chain. Each identity now carries its own long-term ML-KEM key instead. The sections below have been updated; what was originally claimed, and why it failed, is spelled out in where it ends and in the whitepaper changelog.

The attack does not begin when a quantum computer exists. It begins now, with a hard drive.

An adversary who cannot read your traffic today can simply keep it — every block, every timestamp — and wait. If the key exchange that protected it was X25519 alone, then whatever opens that key exchange in 2041 also opens everything recorded in 2026. The industry calls this harvest now, decrypt later, and it is the one attack where doing nothing today is a decision you cannot revisit later.

So the answer is not controversial: mix a quantum-resistant key exchange into the handshake. Signal shipped PQXDH in 2023 and a post-quantum ratchet in 2025, to billions of devices, reviewed by outside cryptographers. That is the bar, and we are not pretending to have cleared it.

But when we went to do the same thing, we hit a wall that Signal does not have.

The dependency nobody mentions

A post-quantum handshake has an awkward requirement: the person you are writing to is offline. You need something of theirs to encapsulate against — a public key that exists before they ever hear from you. The standard solution is a prekey server: each user uploads a batch of one-time keys, the server hands one out when someone wants to start a conversation, and the key is burned.

It works. It is also a server that holds material on your behalf, knows which keys were requested, and knows roughly when. Signal’s is a well-run instance of exactly that, and for their model it is the right call.

Our relay is deaf — it stores opaque blocks and timestamps and nothing else. No accounts, no user table, no key store. That is not a configuration we could relax for this; it is the property the whole design exists to protect. A prekey server would hand back, in one component, the thing we removed everywhere else.

Carry it, don’t deposit it

A prekey server exists to solve one problem: you need a public key belonging to someone who is offline. But there is already a moment when two people exchange public keys, and it does not involve a server at all — it is when they become contacts, face to face over a QR code or an NFC tap, or by passing a code through some other channel.

So the post-quantum key goes there. Your identity is one 32-byte seed, and everything else comes out of it deterministically — your Ed25519 signing key, your X25519 key-exchange key, and a long-term ML-KEM-768 keypair:

(d, z)         = HKDF-SHA3-256(salt="…/identity/v1", ikm=seed,
                               info="mlkem768-identity/" ‖ gen, L=64)
(ek_id, dk_id) = ML-KEM.KeyGen(d, z)

ML-KEM key generation is fully deterministic from that 64-byte input, which means the key needs no storage and no separate backup: whoever can restore the identity seed can recompute the post-quantum key with it. The gen counter is there so the post-quantum key can be rotated later without throwing away the identity.

The encapsulation key rides in the contact bundle you already hand over — the same 66 bytes as before, plus 1184 for ek_id. The initiator encapsulates to it in the very first message; the recipient decapsulates with the private half that never left their phone. Nothing was uploaded, nothing was requested, nothing was burned — and the relay, as always, carried a block it cannot read and cannot attribute.

The honest cost is size: a contact code that used to be a small QR is now 1254 bytes. Measured against the same library the app draws with, that is a 137×137-module monster as a single code — so the bundle travels as NFC, as a link, or as two QR codes instead of one, each back down to a comfortable 97×97.

There was an earlier version of this section. It derived the starting ML-KEM keypair from sk — the X25519 secret two contacts already share — on the grounds that this secret is never transmitted, so a passive recorder could not reconstruct it. That reasoning does not survive contact with our own feature list, and the next section is where it broke.

A hybrid, because new cryptography is new

ML-KEM does not replace X25519 here. Both run, and both results go into one key:

ss_hybrid = HKDF-SHA3-256(salt=<context>,
                          ikm = ss_x25519 ‖ ss_mlkem ‖ ct_mlkem,
                          info="…/pqhybrid/v1")

The property that matters: this is secure if either input is. X25519 has three decades of scrutiny and no quantum resistance. ML-KEM is NIST-standardised and comparatively young. Combining them means a break of the new algorithm costs you nothing, and a quantum computer costs you nothing — an attacker needs both. Adding post-quantum cryptography should never be a bet; done this way, it isn’t one.

The ML-KEM ciphertext goes into the derivation too, not just the shared secret. It costs nothing and closes a family of re-encapsulation subtleties without having to lean on the primitive’s binding properties.

And because all of this is key exchange and hashing — no signatures anywhere — the channel stays deniable. Nothing you send can later be held up as proof that you sent it. Authentication comes from the fact that the ratchet’s root began at a secret only your two private keys can compute; an attacker who injects their own keys simply computes a different root and every message they forge fails its tag.

The 2.3 KB we decided to pay

An ML-KEM encapsulation key is 1184 bytes; a ciphertext is 1088. Carried in a message header, that is about 2.3 KB of overhead — on a messenger that runs over Tor.

The obvious optimisation is to send it only when the key actually rotates. We rejected that, and the reason is the same one behind every other decision here: that message would be a different size. A relay that cannot read a single word could still watch the size classes go by and read the rhythm of your key changes — which is a shape of your conversation, drawn without breaking anything.

So the post-quantum header rides in every message of an epoch, identical each time. There is no “this is a ratchet step” size to notice, because every message is that size. It is the same trade as padding: pay a fixed, boring cost rather than emit a secret signal.

Signal solved the same 2.3 KB differently — their post-quantum ratchet slices the key material into chunks spread across many message headers, keeping any single message small. That is a good answer to a bandwidth problem. Ours is an answer to a traffic-analysis problem. Neither is a refutation of the other; they are two projects with different things they refuse to leak.

Where it ends — because we always say so

The prekey server we refused was buying something real, and we do not get it for free:

• We got the first chain wrong, and this is what it was. The original design derived the starting ML-KEM keypair from sk. We wrote here that the passive recorder — the actual harvest-now-decrypt-later adversary — was protected from the first message, because sk never crosses the wire. The premise is true and the conclusion does not follow: sk is computed from both parties’ long-term X25519 public keys, and those do cross the wire in two flows we ship deliberately — adding a contact by passing their code through another app, and an invite carrying the sender’s identity. Record either one, break X25519 in 2041, recompute sk, derive dk₀, read the first chain. Both halves of the hybrid, gone together, in the exact window the hybrid exists for. It was not a small window either: a ratchet step happens when a message is received, so a conversation nobody replies to never leaves the first chain at all. Contacts added strictly face to face were never exposed to this, because their keys never reached a recordable channel — but a protection that quietly depends on how you added someone is not the protection we described. Since 2026-08-23 the post-quantum key is part of the identity and independent of X25519, and a channel whose contact predates that change says so instead of claiming otherwise.
• The first chain is still not post-compromise-fresh — the classical half. The responder’s starting ratchet key is derived from sk, so an attacker who already holds that root also holds the first exchange; freshness arrives after one full round-trip, once each side has contributed a key the other has never seen. That is a trade against designs with one-time prekeys on a server, and we still take it.
• Timing. These implementations exist to be checkable — runnable in a test VM in two languages so neither can drift from the other. They no longer perform any secret-dependent division; that was measured rather than assumed, and confirmed on the ARM64 phone we target, where the earlier code did leak and the same test on a desktop CPU showed nothing at all. One timing anomaly in the third-party SHA3 library remains unexplained, and we are not claiming otherwise until it is.
• The rendezvous address is out of scope. It is metadata, not content, and its derivation is load-bearing for how conversations rotate. Post-quantum protection here covers what you said, not the fact that a block arrived.
• We are not audited. Post-quantum or not, that sentence stays until it isn’t true.

Verify, don’t trust

Correctness is not a thing you should take on faith from a project that keeps its source closed. Our ML-KEM implementation is pinned against the published C2SP/CCTV accumulated vectors — ten thousand deterministic key generations, encapsulations and decapsulations, reduced to a single digest that either matches the public one or doesn’t. Both of our implementations recompute it independently, from scratch, in their own test suites. A digest that matches by accident is not a thing that happens.

The parameters, the combiner, the header layout and the honest edges are all written out in the whitepaper. The plain-language version is in learn the words.

Your key, your rules — everything else is redacted.

← Back to blog