HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Relay

Deniability: Messages No One Can Prove You Sent

7 min read

When you say something out loud to a friend, you can always deny it later — there is no recording, no receipt, nothing a third party can wave around as proof you said those exact words. Digital messages, done the obvious way, are the opposite: every signature is a permanent, transferable confession. This article is about giving a conversation back its plausible deniability, even against a judge who shows up in fifteen years with a quantum computer.

This is the last property in the series, and the most philosophically interesting. It is why several places you would expect a signature have a shared-key MAC instead.

1. Authentication that proves too much

Bob needs to know a message really came from Alice and wasn't forged. The textbook tool is a digital signature: Alice signs each message with her private key, and anyone with her public key can verify it. Done — except it does far more than Bob needed.

A signature is transferable, non-repudiable proof. It doesn't just convince Bob; it convinces anyone, forever, that Alice — the unique holder of that private key — signed those exact bytes. Bob can show the signature to a journalist, a court, a blackmailer, and they can verify it themselves without trusting Bob at all. Alice cannot deny it, because the mathematics says only she could have produced it.

That is the correct property for a legal contract and a terrible property for a private conversation. Real-world talk is repudiable: you can always say "I never said that," and the other person cannot mathematically prove otherwise. A messenger that signs every message quietly strips that away, turning every chat into a stack of notarized affidavits its own users didn't ask for.

And it is worse than it first appears, because it is a harvest-now, judge-later threat. A signature recorded today stays a valid proof forever. An adversary can archive your signed messages now and produce them as court-admissible evidence decades later — including in front of a future "quantum judge" who can break the classical parts but doesn't even need to, because the signature was designed to convince third parties in the first place. Recent work (ePrint 2025/1090) drives exactly this point: transferable authentication is a long-lived liability, not just a convenience.

We want Bob to believe his messages, and no one else to be able to prove anything.

2. The trick: authenticate with something Bob could have faked

The resolution is one of the oldest ideas in secure messaging, from Off-the-Record Messaging (OTR) in 2004: replace the signature with a Message Authentication Code (MAC) under a key that both parties share.

Here is the sleight of hand, and it is worth slowing down for because it feels paradoxical at first. A MAC is computed with a secret key. Alice and Bob both hold the shared key for their conversation. So:

  • To Bob, the MAC authenticates the message. Bob reasons: "Only Alice and I have this key. I know I didn't compute this tag. Therefore Alice did — this message is genuinely hers." He is convinced.
  • To a third party, the MAC proves nothing. A judge reasons: "This tag could have been computed by anyone holding the shared key — and Bob holds it. Bob could have forged this entire transcript himself to frame Alice." The tag is perfectly consistent with Alice never having sent anything. It is not evidence.

The single fact that makes authentication work for Bob — he knows he didn't fake it — is a fact only Bob has. He cannot transfer it. Anyone else looking at the same bytes sees a tag Bob was fully capable of manufacturing. So the message is authentic to its recipient and deniable to the world at the same time, with no contradiction. You believe what you know you didn't fake; everyone else sees something you could have faked.

This is why, back in Sealed Sender, we noted the per-message inner authenticator is a MAC under the pairwise channel key, not a signature. That is deniability by construction: the per-message proof of "Alice sent this" is one Bob himself could have produced, so it convinces Bob and indicts no one.

3. But the first message has no shared key yet

The MAC trick assumes Alice and Bob already share a conversation key. At first contact they don't — establishing one is the whole point of the handshake — and that is exactly where a naive design leaks a transferable proof.

The obvious way to authenticate a first message is for Alice to prove she holds the private key behind her certificate — a proof of possession, which is, once again, a signature- like object a third party can check. So the very act of starting a conversation would emit a permanent "Alice initiated contact with Bob" certificate, undoing the whole property before the conversation even begins.

The fix is a deniable handshake: a key-agreement whose transcript any party could have simulated on their own. Concretely, first-contact authenticity is carried by a symmetric MAC that the verifier can itself compute from the shared secrets it helped establish — so, just like the per-message MAC, it convinces the intended party and is forgeable-by-the- recipient to everyone else. Because the whole transcript is simulatable, it proves nothing to a judge. The construction — a post-quantum (X-Wing) key-and-MAC exchange over three shared secrets — is its own article: The Deniable Handshake (CDH).

4. Deniable and post-quantum: the strongest form

There is a spectrum of deniability, and it matters which end you are on:

  • Computational deniability says a judge cannot feasibly distinguish a real transcript from a simulated one — assuming some problem stays hard. A future quantum computer might break the assumption and, retroactively, the deniability.
  • Perfect / information-theoretic deniability says the real and simulated transcripts are identically distributed — there is no statistical difference, so no amount of computing power, quantum or otherwise, can tell them apart. Deniability that never expires.

Our handshake and MACs are designed for the second kind. The deniability rests on the symmetric, simulatable structure of the authenticators — not on a hardness assumption — so it is immune even to a quantum judge. And the simulator is not an abstraction: it is Bob. The recipient's own half of the exchange is enough to manufacture a transcript identically distributed to a real one — which is exactly why a transcript convinces Bob and no one else. This is the deniability analogue of the whole series' post-quantum stance: don't just make it hard to break today, make it nothing to break, ever. And, fittingly, it is machine-checked — the deniability (a simulator exists whose output is indistinguishable from real transcripts) is proved in both the symbolic (ProVerif) and computational (EasyCrypt / CryptoVerif) models in the formal corpus.

5. The honest residual

Deniability is a subtle property and it is easy to overclaim, so let us be precise about what it does and does not give:

  • It is deniability against a third party, not against Bob. Bob is personally convinced the message is Alice's — that is the point. What Bob cannot do is transfer that conviction to anyone else. If your threat model is "I don't want my own correspondent to believe me," this is not that (and no authenticated system could be).
  • The certificate still binds identity to a key, not to a message. Alice's sender certificate is signed (it is an identity credential), but it attests "this key belongs to a registered user" — it never signs any particular message. So it proves Alice exists on the system, never that she said any specific thing. The message-level proof is the deniable MAC.
  • Interactive/online deniability has caveats. The strong statement is about a judge examining a transcript after the fact. A judge who participates live — coercing one party in real time — is a different, harder model; the design targets the offline-judge case, which is the one that matches "harvest a transcript now, wave it in court later."

Within those honest bounds, the guarantee is strong and unusual: your messages authenticate to the person you sent them to, and to everyone else — breach, subpoena, hostile recipient, future quantum judge — they are bytes you could deny ever having written. That is what a private conversation is supposed to be.

References & further reading