The very first message between two strangers is where deniability is hardest to keep and easiest to lose. This is the construction that establishes a shared key at first contact while leaving a transcript that proves, to any outside observer, absolutely nothing about who took part.
This is the algorithm under Deniability, and it is the deepest crypto in the series. We will build it up from the problem rather than drop the final scheme on you. We refer to it internally as the CDH handshake: an internal codename, not the textbook "CDH" (computational Diffie–Hellman) assumption.
Once Alice and Bob share a conversation key, deniability is easy: authenticate each message with a shared-key MAC (a message authentication code, a keyed checksum that anyone holding the key can create as well as verify), so either of them could have forged it. But establishing that shared key the first time is exactly where a transferable proof tends to sneak in.
The natural first move is for Alice to prove she controls the private key behind her identity: a proof of possession. Almost every obvious way to do that (sign a challenge, run a classic authenticated key exchange) produces a transcript: the record of every byte the two sides exchanged, which anyone watching the wire can keep a copy of. A third party can later check that transcript and conclude "Alice's key was here."
That is a permanent, transferable record that Alice contacted Bob: the deniability broken before the conversation even starts.
We need an authenticated key agreement (an AKE): a protocol that leaves both sides holding the same fresh secret, each one sure of who the other is. And ours needs a peculiar extra property: anyone should be able to fabricate a transcript that looks exactly like a real run. If a convincing fake is trivial to make, then a real transcript proves nothing: it might be a fake. That property is deniability via simulation, and it is the design target.
Each party has a published discovery key. It belongs to the account, rotates on a routine cadence, and is held by every device on the account, so what this handshake authenticates is an account rather than a handset (Rotating the Key Strangers Seal To covers that lifecycle). The caller additionally generates one fresh ephemeral key: a key made for this one handshake and discarded afterward. The callee generates none.
All keys here are KEM keys: keys for a key-encapsulation mechanism, the modern shape of public-key encryption. The KEM is X-Wing: a hybrid of the lattice KEM ML-KEM-768, built to resist quantum computers, and classical X25519, run together so an attacker has to break both. It is the same seal primitive as in The Attested Push Seal. A KEM encapsulates: run it against a public key and it produces two things at once, a fresh shared secret and a ciphertext that lets the private-key holder recover that secret.
Following the spirit of PQXDH (Signal's post-quantum handshake, whose core idea is to mix several agreements so the result depends on both identities and fresh randomness), this handshake derives three shared secrets. Each is an encapsulation to one key, and the useful way to read each one is "whose private key is required to recover it":
ss_H: the secret of the sealed hello, encapsulated to Bob's discovery key. Only
Bob's private key recovers it. Alice knows it because she is the one who encapsulated.ss_R: the secret of the sealed reply, encapsulated to Alice's discovery key. Only
Alice's private key recovers it. There is no ephemeral input here, so this leg is not the
forward-secret one.ss_E: encapsulated to Alice's fresh ephemeral key. This is the only leg that
supplies forward secrecy: the ephemeral private key is
discarded after the handshake, so a later compromise of either long-term key does not
reconstruct it.All three are fed into a key-derivation function (HKDF), which blends them and stretches the
result into as many independent output keys as we ask for: a session key k_session and
separate confirmation keys used only for the next step.
Mixing three secrets (rather than one) is what lets the scheme achieve strong properties (mutual authentication, forward secrecy, session independence) simultaneously. It is the same reason X3DH, Signal's earlier handshake, mixed three Diffie–Hellman exchanges: the classic technique where each side combines its own private key with the other's public key and both land on the same shared secret. The difference here is that every mix is a post-quantum KEM, and the purpose of the combination is tuned for deniability.
With the secrets derived, each party proves it really computed them by sending a confirmation
MAC over the transcript, keyed by a confirmation key from the HKDF. The exchange is three
messages, and the order is worth following. The hello carries no authenticator at all. The
reply carries ct_E (the ciphertext of the ephemeral encapsulation) and the callee's
tag tau_B. And the caller's tag tau_A rides a third
message, the ack, on a fresh subject (routing address).
So the caller authenticates the callee one message before the callee can authenticate the
caller. That asymmetry is load-bearing: until tau_A verifies, the callee treats the binding as
provisional and commits nothing about who the caller is. A forged or unconsented hello
therefore leaves no trace on the callee's side.
This is the deniability move, exactly as in Deniability, now at the handshake level:
tau_A authenticates Alice. Deriving the confirmation key required ss_R, and
only Alice's private key recovers ss_R from the reply's ciphertext. Bob didn't fabricate
tau_A, so the real Alice must have taken part.tau_B authenticates Bob, by the mirror argument: it required ss_H, and only
Bob's private key opens the hello.tau_A himself. The tag is perfectly consistent with
a Bob who invented the entire exchange.No signature authenticates the exchange. Authentication rides entirely on shared secrets confirmed by MACs, and a MAC the verifier could have produced is not evidence against the sender.
The frame is not signature-free, and the distinction matters. Both the sealed hello and the sealed reply carry the sender's hybrid certificate (hybrid in the same sense as the KEMs, a classical and a post-quantum signature together), verified fail-closed (any doubt means reject) before anything else happens. But that certificate is a static, reusable credential: it attests "this key belongs to this account", never "this account talked to that one", and it is not bound to this handshake. A forger assembling a fake transcript simply pastes in the target's already-public certificate. It authenticates a key, not a conversation, which is exactly why it costs nothing in deniability.
Here is the property that makes the whole thing deniable, stated as a cryptographer would: a simulator (a program given only the public keys and one party's secrets) can produce a transcript identically distributed to a real handshake's. Identically distributed means the fake and the real are, statistically, the same random object; no test can separate them, even in principle.
The confirmation tags can be recomputed by anyone holding the shared secrets (which the intended party does), and the KEM ciphertexts and ephemeral keys look like fresh random values whether they came from a real run or a fabricated one. So a judge holding a transcript cannot tell a genuine Alice–Bob handshake from one Bob (or an accuser) cooked up alone.
Since the fake is indistinguishable from the real thing, the real thing is not proof of anything.
And that indistinguishability is statistical, not "hard to break." Most cryptographic guarantees hold because breaking them would take an infeasible amount of computation; this one does not lean on that at all. The deniability is information-theoretic: it survives any amount of computing power, including a future quantum judge. Combined with the X-Wing KEMs (which make the confidentiality post-quantum too), the handshake is post-quantum on both axes: what it hides stays hidden, and what it denies stays deniable, forever.
Deniability-by-simulation is precisely the kind of claim that is easy to state and subtle to get right: the history of authenticated key exchange is littered with schemes that were "obviously deniable" until they weren't. So this one is machine-checked.
The handshake's properties are proved in both a symbolic model (ProVerif) and a computational model (CryptoVerif / EasyCrypt), the two flavours of machine-checked proof, in the formal corpus: mutual authentication and key secrecy on one side, and the existence of a simulator whose output is indistinguishable from real transcripts (the deniability) on the other. The symbolic tool treats each primitive as a perfect black box and searches for logical attacks; the computational tools bound a real attacker's probability of success against the actual math. The deniability is not a story we tell about the protocol; it is a theorem the tools check.
The CDH handshake runs at first contact, carried on the relay's separate first-contact frame
path (the 0x02 frame from Sealing the Envelope, whose outside
carries no cert ticket: the certificate itself travels sealed inside the hello). Its output k_session is retained as the pair's channel key. That
key does two jobs for the rest of the relationship: it is the key under which every later message's
deniable inner MAC is computed, and it is the key from which the pair's rotating routing address is
derived: the opaque to value of The Envelope.
The end-to-end ratchet (the machinery that steps the
message keys forward as a conversation runs) is seeded from this same handshake: its opening root and chain keys are derived from
k_session. And what carries forward beyond the keys is the
shared-secret-and-MAC discipline itself, into the per-message
deniable MACs. First contact establishes a key deniably; every message
after inherits the property. From the first byte to the last, the conversation authenticates to
its participants and denies itself to everyone else.