What is Metadata Privacy?

Metadata vs. content: what’s the difference?

In messaging, content is the payload of a message — the words, images, or files you send. Metadata is everything else: the sender and recipient identifiers, the timestamp, the message size, the frequency and duration of exchanges, the device fingerprint, and the network path the message took. Two people can have a perfectly encrypted conversation and still leak, to any observer, the fact that they spoke, for how long, at what cadence, and from which networks.

A useful analogy: content is the letter inside the envelope; metadata is the address on the outside, the postmark, the envelope’s thickness, and the fact that you and your correspondent have exchanged a letter every Tuesday for the past three years. Encrypting the letter does not hide the envelope.

Why metadata is sensitive

Metadata reveals social graphs, relationships, and behavioural patterns that content often does not. Knowing who you talk to is frequently more revealing than knowing what you say. A call to a suicide hotline at 3 a.m., a message to a divorce lawyer, repeated contact with a journalist — each is a single metadata event whose content is irrelevant to the harm it could cause.

Aggregated, metadata becomes a behavioural fingerprint. Researchers have shown that as few as four spatio-temporal points are enough to uniquely identify 95% of individuals in a mobility dataset. Communication metadata is similarly identifying: the pattern of who, when, how often is hard to forge and easy to exploit for surveillance, discrimination, or targeting.

The NSA “metadata is not content” argument — and why it’s wrong

In defending the bulk collection of US telephone call records, government officials repeatedly argued that “metadata is not content” — that collecting the who-called-whom records was qualitatively different from wiretapping calls. The implication was that metadata collection is a minor intrusion.

This argument is empirically false. The Stanford Metadata Study (Mayer, Mutchler & Mitchell, 2016) had volunteers install a logging app that captured only call and SMS metadata — exactly the kind of record the NSA collected in bulk. From metadata alone, the researchers could infer medical conditions (e.g. someone who called a cardiologist and then a pharmacy), financial relationships, firearm ownership, and romantic affiliations. They concluded that telephone metadata is “plainly not anonymous” and that it “sensitive enough to be protected”.

“We find that telephone metadata is densely interconnected, can identify individuals with high accuracy, and has high sensitivity to social and medical information.” — Mayer, Mutchler & Mitchell, Proceedings of the ACM on Human-Computer Interaction, 2016.

The “metadata is not content” framing therefore collapses on contact with data: metadata alone is enough to profile, target, and deanonymize. Metadata privacy is not a luxury layered on top of content encryption — it is a distinct and necessary property.

How existing systems leak metadata

Signal

Signal’s sealed envelopes protect message content with the Signal Protocol, but the Signal server must still route messages between two identified accounts. It sees, for each message, the sender and recipient identifiers, the timestamp, and the message size. From this it reconstructs the full social graph of its users. Signal’ssealed sender feature hides the sender from the server, but the recipient is still visible and the server still learns thatsome message was delivered to a given account at a given time.

WhatsApp

WhatsApp uses phone numbers as account identifiers. The routing server sees phone-number-to-phone-number edges, delivery status, and online presence. Even with end-to-end encryption, the graph of who messages whom — by real phone number — is exposed to the operator and to anyone the operator shares data with.

Email (SMTP)

Email is the worst case. Each message carries a plaintextFrom, To, Cc, aReceived: header chain revealing every mail server it traversed and when, plus optional Message-ID andX-Mailer fingerprints. Content is frequently unencrypted in transit (STARTTLS opportunistic) and the entire header set is visible to every relay. Email metadata is, for most users, fully public.

Tor

Tor anonymizes the source of TCP connections through onion routing, but it does not by itself protect messaging metadata: an adversary observing both ends can perform traffic-correlation attacks, the exit node sees cleartext (unless the application uses TLS), and Tor does not provide authenticated delivery or hide who is talking to a hidden service if the service is observable.

Approaches to metadata privacy

Cryptographers have proposed several families of solutions, each with different trust, latency, and scalability tradeoffs.

• Mixnets (Chaum 1981; Vuvuzela, Nym): messages pass through a cascade of mix servers that shuffle and re-encrypt batches, breaking the link between input and output. Strong anonymity but high latency (round-based batching) and reliance on at least one honest mix in the cascade.
• DC-nets (dining cryptographers, Chaum 1988): participants jointly produce a shared random pad so that any one participant can transmit a bit without revealing which. Information- theoretically anonymous but bandwidth grows with the square of the group size and denial-of-service resistance is weak.
• Private information retrieval (PIR): a client retrieves a record from a server without revealing which record. PIR protects retrieval, not delivery, and typically has high server-side computation.
• Bucketed broadcast (Tessera’s approach): every proof is sent to a small number of buckets; recipients subscribe to their bucket and filter for their own deliveries. There is no per- message recipient routing decision for the network to observe, and (ε,δ)-differentially-private cover traffic hides the real per-bucket counts. Anonymity set = bucket occupancy; no trusted mixes required.

Tessera’s specific mechanism

Tessera combines four primitives to achieve metadata-private, authenticated, one-to-one delivery:

1. Per-recipient blinded pseudonyms. Each delivery uses a fresh pseudonym Y′ = Y + t·G wheret = H(seed ‖ session_id) mod q. The sender proves knowledge of x′ = x + t, not x, so the proof is unlinkable across deliveries and recipients.
2. Schnorr / Fiat–Shamir zero-knowledge proofs.Authentication is a non-interactive ZK proof of knowledge of the secret key, encrypted under AES-GCM so only the recipient can read it.
3. Bucketed broadcast routing. Proofs are routed by a commitment hash into one of 64 buckets; relays gossip proofs over a P2P mesh; recipients subscribe via Bloom filters.
4. (ε,δ)-differentially-private cover traffic. Each bucket is padded with a load-independent, Laplace-noised number of dummy proofs so that a global observer cannot tell whether a real delivery happened. Empirically the adversary linking AUC is 0.526 atε = 0.1 (the information-theoretic ceiling for this mechanism is 0.548).

What each scheme leaks — a comparison

Signal, WhatsApp, and email all leak the social graph to the operator. Tor anonymizes the source of TCP streams but is vulnerable to timing correlation and does not provide authenticated delivery. Tessera hides sender, recipient, timing, and graph from a global passive observer within the (ε,δ)-DP bound.

Frequently asked questions