What is metadata privacy in messaging?

Content privacy hides what was said; metadata privacy hides the facts around it — who sent it, who received it, when, how often, and how large it was. End-to-end encryption delivers the first and not the second. A server that can see nothing of a message body can still reconstruct a complete social graph from delivery records, which for many threat models is the more sensitive artefact.

Why do authentication and anonymity normally conflict?

Authentication means proving a message came from a specific identity, which usually means attaching something that identifies that party. Anonymity means removing exactly that. Systems generally pick one: signed messaging authenticates and leaks a stable identifier, while anonymity networks hide the sender and cannot tell an authorised participant from an intruder. Closing the gap requires a proof that convinces the intended recipient and nobody else.

What is a blinded pseudonym?

A per-recipient re-randomisation of a public key. Starting from a long-term key Y, a sender derives Y' = Y + tG where the blinding scalar t comes from a secret shared only with that recipient. Every recipient therefore sees a different pseudonym for the same sender, and two recipients who compare notes cannot tell they are talking to the same person. The sender can still prove knowledge of the corresponding secret.

What does differentially private cover traffic protect against?

A global passive observer who cannot read any message but can count them. Real traffic volumes correlate with real events, so counts alone leak. Adding cover traffic drawn from a calibrated noise distribution bounds by (epsilon, delta) how much any observed count sequence can shift the observer's belief about whether a particular real message was sent. The guarantee is quantified rather than heuristic, which is the point.

What does this design not protect?

It assumes the endpoint is intact. An adversary who owns the device holds the secret key and sees plaintext before it is encrypted, and no protocol-level property survives that. It also does not protect message content on its own — payloads are separately encrypted — and it does not defend against a user voluntarily disclosing what they received. The honest scope is a network adversary and curious or colluding recipients, not a compromised operating system.

Proving Who Sent a Message Without Revealing To Whom

Encrypting a message hides its contents from everyone except the recipient. It does not hide the fact that you sent it, to whom, at what time, or how often — and for a large class of adversaries that pattern is the thing worth having. A service provider who can read nothing can still produce a complete edge list of who talks to whom, which is the artefact subpoenas, acquisitions and breaches actually surface.

Metadata-private systems exist, but they have historically bought their privacy by giving up authentication: if the network cannot tell who sent a message, neither can the recipient. Tessera is our attempt to hold both properties at once — a protocol in which a recipient can verify that a message came from a specific enrolled contact while a network observer learns nothing about the pairing. This note explains the construction and, more importantly, where it stops.

Two properties that are usually traded

It helps to separate the guarantees before discussing mechanisms.

Content confidentiality is the property that nobody but the recipient learns the message body. Modern end-to-end encryption delivers this well, and it is the property most people mean when they say a messenger is private.

Metadata privacy is the property that nobody learns the communication pattern: sender, recipient, time, frequency, size. This is the property almost no widely-deployed messenger delivers, because the server must know where to route a message.

Sender authentication is the property that the recipient can verify who sent the message. A signature provides this, and a signature is a stable identifier — which is precisely what metadata privacy is trying to withhold.

The conflict is structural. Authentication wants a persistent, linkable credential. Metadata privacy wants no linkable anything. Signal-style messengers resolve it in favour of authentication and accept that the server sees the graph. Anonymity networks resolve it in favour of unlinkability and accept that any participant may be an intruder.

Proving identity to exactly one party

The way out is a proof whose verifier is fixed in advance. Tessera composes two standard pieces.

The first is a Schnorr proof of knowledge, made non-interactive by the Fiat–Shamir transform. The sender proves knowledge of the secret scalar behind a public point without revealing it, and the challenge is bound to the message so the proof cannot be lifted onto different content. Unforgeability rests on the discrete-logarithm assumption in the underlying group, by the standard forking-lemma argument; the zero-knowledge property holds in the random-oracle model. Neither is novel, and that is a feature — the security argument is one a reviewer can check against textbook results rather than a new assumption.

The second is per-recipient key blinding. Rather than proving knowledge against a global public key, the sender proves it against a blinded pseudonym Y' = Y + tG, where the blinding scalar t is derived from a seed shared only with that one recipient during enrolment. Alice presents a different Y' to Bob than she presents to Carol. Bob can verify that whoever produced the proof knows Alice’s secret; Bob cannot compute Carol’s view, and Bob and Carol comparing their records cannot establish that they are talking to the same person.

Enrolment is pairwise and local. There is no directory server, no key transparency log, no central authority that could be compelled to produce the mapping — because the mapping does not exist in one place to be produced.

Hiding the traffic pattern, quantifiably

Unlinkable identities do not help if an observer can simply count. Message volume correlates with events; a spike after a news story, or a silence during a holiday, tells a patient adversary a great deal.

The usual defence is cover traffic — send decoys so real messages are hidden among them. The usual weakness is that cover traffic is calibrated by intuition, and its guarantee is described qualitatively. Tessera instead draws cover traffic from a shifted-Laplace distribution calibrated to give an (ε, δ) differential-privacy bound on the per-bucket counts an observer can see. The claim is then of a familiar shape: observing the counts shifts an adversary’s belief about whether any particular real message was sent by at most a bounded factor, except with probability δ.

Two consequences follow from making the guarantee quantitative. It is tunable — ε trades bandwidth against privacy explicitly, and an operator can state which point on that curve they chose. And it is load-independent: the bound does not degrade when traffic is light, which is exactly when naive cover-traffic schemes leak most.

Delivery itself uses a bucketed broadcast network rather than a mix network. Each delivery’s commitment maps to one of a fixed set of buckets; a recipient scans its bucket and matches entries against a Bloom fingerprint, and gossip propagates buckets between relays. A mix network hides the path by shuffling through successive hops and pays for it in latency and in the assumption that at least one hop is honest. Bucketed broadcast hides the pairing by giving the observer only counts, and pays for it in bandwidth. Neither is universally better; they fail differently, which is the more useful thing to know.

The adversaries, and which are in scope

Adversary	What they observe	Defence	In scope
Malicious sender attempting impersonation	Public parameters, the recipient’s key	Schnorr unforgeability under the discrete-log assumption	Yes
Honest-but-curious recipient	Its own deliveries, all public traffic	Zero-knowledge: learns nothing beyond the sender’s identity	Yes
Colluding recipients	Their combined deliveries	Distinct shared seeds give distinct pseudonym distributions	Yes
Global passive network observer	All per-bucket counts over time	(ε, δ)-differentially-private cover traffic	Yes
Coalition of compromised relays	Proofs and Bloom filters	Same bound — relays see counts only — plus blinding	Yes
Replay attacker	Previously recorded proofs	Per-delivery commitment freshness and deduplication	Yes
Compromised endpoint	The secret key and all local state	None	No

The last row is the honest one. Every protocol-level guarantee here assumes the device and its key material are intact. An adversary with the endpoint reads plaintext before encryption and can produce valid proofs at will. Claiming otherwise would be the kind of overreach that makes security marketing untrustworthy.

Two further limits are worth stating plainly. The construction is for one-to-one messaging; group semantics introduce linkability questions that it does not answer. And the payload is encrypted separately with AES-GCM — the zero-knowledge machinery authenticates the sender and hides the pairing, it does not by itself protect content.

Where the comparison actually lands

Signal protects content extremely well and is designed for a threat model in which the server is trusted not to abuse routing metadata. Tor anonymises the network path of a TCP stream and assumes at least one honest hop in a circuit; it says nothing about whether the party at the other end is who they claim to be. Mix networks provide strong transport-level unlinkability at a latency cost, and again leave authentication to a layer above.

Tessera sits in a different place: it authenticates at the protocol layer and hides the pairing, while explicitly delegating content encryption and endpoint security elsewhere. That is a narrower claim than “private messaging”, and narrower claims are the only kind worth making about cryptographic systems.

Open Questions

Group messaging. A conversation with five participants has a pairing structure that per-recipient blinding does not obviously generalise to without either leaking membership or multiplying bandwidth.

Parameter selection in practice. Choosing ε for a messaging system is not a mathematical question. What does a deployment consider acceptable, and how is that choice communicated to a user who will never read the definition?

Bandwidth at scale. Bucketed broadcast trades bandwidth for unlinkability. The regime in which that trade stays acceptable on a mobile connection is an empirical question we have not answered.

Enrolment usability. Pairwise local enrolment removes the central authority and moves the burden to the user. Every deployed system that has tried this has struggled with it, and we should expect to as well.

Conclusion

The authentication-versus-metadata gap is not a gap in engineering effort; it is a genuine tension between two properties that pull in opposite directions. Closing it requires a proof that is convincing to one party and meaningless to everyone else, plus a traffic-shaping layer whose guarantee is stated as a number rather than an assurance.

Tessera is experimental, and the questions above are not rhetorical. What we are confident about is the framing: content privacy and metadata privacy are different properties, both are negotiable, and a system that claims both should say exactly which adversary it is claiming them against. The project page has the scope and licensing, our comparison index places it against Signal and Tor, and the safe computing pillar collects the rest of our work on verifiable systems.