HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Relay

Algorithm: The Deniable Handshake (CDH)

5 min read

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.

1. The first-contact trap

Once Alice and Bob share a conversation key, deniability is easy: authenticate with a shared-key MAC that either could have forged. 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 a third party can later check to 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) with 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.

2. Keys and the three shared secrets

Each party has a long-term identity key and generates a fresh ephemeral key for this handshake. All keys here are KEM keys, using X-Wing (the hybrid of the lattice KEM ML-KEM-768 and classical X25519 — the same seal primitive from article 13). Recall a KEM encapsulates: run it against a public key to jointly produce a fresh shared secret and a ciphertext that lets the private- key holder recover that secret.

Following the shape of PQXDH — which mixes several key agreements so the result depends on both identities and fresh randomness — the handshake derives three shared secrets by encapsulating across different key pairings:

  • ss_H — from the two parties' long-term identity keys. This is the secret that binds identities into the session: only the real Alice and real Bob can derive it.
  • ss_R — mixing one party's ephemeral key with the other's long-term key. This ties the fresh session to a specific identity while keeping it forward-secret.
  • ss_E — from the two ephemeral keys. Pure per-session randomness, so even the same two people get an independent session every time.

All three are fed into a key-derivation function (HKDF) to produce the outputs: a session key k_session (which seeds the ongoing ratchet) 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 mixed three Diffie–Hellmans. The difference here is that every mix is a post-quantum KEM, and the purpose of the combination is tuned for deniability.

3. Confirmation: authenticate with a tag either side could make

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: Alice sends tau_A, Bob sends tau_B.

This is the deniability move, exactly as in article 09, now at the handshake level:

  • To Bob, tau_A authenticates Alice. Deriving the confirmation key required ss_H, which required Alice's long-term private key. Bob didn't fabricate tau_A, so the real Alice must have taken part.
  • To a third party, tau_A proves nothing. The confirmation key is symmetric — Bob holds it too. Bob could have computed tau_A himself. The tag is perfectly consistent with a Bob who invented the entire exchange.

No signatures anywhere. Authentication rides entirely on shared secrets confirmed by MACs, and a MAC the verifier could have produced is not evidence against the sender.

4. Why the transcript is a perfect fake

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. 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 because that indistinguishability is statistical, not "hard to break," 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.

5. Proved, not just argued

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 — 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 — are proved in both a symbolic model (ProVerif) and a computational model (CryptoVerif / EasyCrypt) in the formal corpus. The deniability is not a story we tell about the protocol; it is a theorem the tools check.

6. Where it sits

The CDH handshake runs at first contact, carried on the relay's separate first-contact frame path (the 0x02 frame from Sealing the Envelope, which has no certificate yet). Its output k_session becomes the seed for the end-to-end ratchet, and the same shared-secret-and-MAC discipline carries forward 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.

References & further reading