Post-quantum without a prekey server

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.

Derive it, don’t deposit it

Two people who are already contacts share something the relay has never seen: an X25519 ECDH secret, computed independently on each phone from keys exchanged in person. We already use it to derive the conversation address and the channel key.

ML-KEM key generation is fully deterministic from a 64-byte seed. So there is no need to store a starting keypair anywhere — both devices can compute the same one, at the same moment, from something they already hold:

(d, z)     = HKDF-SHA3-256(salt="…/pqhybrid/v1", ikm=sk,
                           info="pq-bootstrap/responder", L=64)
(ek₀, dk₀) = ML-KEM.KeyGen(d, z)      # identical on both phones

The initiator encapsulates to ek₀ in the very first message. The responder decapsulates with dk₀. Nothing was uploaded, nothing was requested, nothing was burned — and the relay, as always, carried a block it cannot read and cannot attribute.

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:

• The first chain is not post-compromise-fresh. The starting ML-KEM keypair is derived from sk, so an attacker who already holds that root also holds the first exchange. Freshness arrives after one full round-trip, when each side has contributed a key the other has never seen. Against the passive recorder — the actual harvest-now-decrypt-later adversary, who never had sk and never saw it cross the wire — the first message is protected. Against someone who already owns your root, the first chain is not the place you were going to be saved.
• Our reference implementations are not constant-time. They are written to be checkable — runnable in a test VM in two languages so neither can drift from the other. The production target on the device is a vetted native implementation, validated against the same vectors.
• 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