Differential Privacy for Messaging Metadata

What is differential privacy?

Differential privacy (Dwork, McSherry, Nissim & Smith, 2006) is a formal guarantee that the output of a randomized mechanism does not change much whether or not any single individual’s record is present in the input. Intuitively: an adversary seeing the output learns almost nothing about any one record. For messaging, the “record” is whether a given delivery occurred; the “output” is the per-bucket message count observed by the network.

The formal definition: a randomized mechanism M is(ε,δ)-differentially private if for all neighbouring databases D and D′ (differing in one record) and all measurable output sets S:

Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D′) ∈ S] + δ

ε is the privacy-loss budget: smaller is more private. The additive δ is a small slack — the probability that the guarantee fails outright. When δ = 0 the mechanism is “pure” ε-DP; when δ > 0 it is “(ε,δ)-DP” and tolerates rare large-δ events, which is what allows Tessera to truncate noise at zero.

Why DP for messaging?

In Tessera’s bucketed broadcast, every relay (and every global passive network observer) can count the number of real proofs that enter each bucket in a routing round. Without cover traffic, that count is a direct signal: a bucket that receives one extra proof when Alice is known to be sending did carry Alice’s delivery. The adversary’s linking AUC in this case is essentially 1.0 — perfect classification.

Differential privacy gives a quantitative answer: if the per-bucket count is (ε,δ)-DP in the presence/absence of any one delivery, then no adversary — no matter how sophisticated — can use the count to distinguish those two worlds with advantage greater thanε (plus δ slack). This is the strongest privacy guarantee available for a count observable, and it holds compositionally across rounds.

Tessera’s mechanism: the shifted-Laplace cover

For each bucket b and routing round, Tessera injectsD_b dummy proofs, where:

D_b = max(0, round(μ + L)),   L ~ Laplace(0, 1/ε)
μ  ≥ (1/ε) · ln(1 / (2δ))

Here μ is a fixed load-independent target — it does not depend on the real number of deliveries — and L is Laplace noise calibrated to the privacy budget ε. The total number of proofs in bucket b isreal_b + D_b, and because D_b is drawn from a shifted-Laplace distribution with the right scale, the total count is (ε,δ)-DP in the presence/absence of any single delivery.

The truncation max(0, ·) is the source of the additiveδ: when the noise L is more negative than−μ, the dummy count would be negative and is clipped to zero. The probability of that event is bounded by δthrough the choice μ ≥ (1/ε)·ln(1/(2δ)). Increaseμ for smaller δ (stricter guarantee) at the cost of more bandwidth.

Why load-independent, not proportional?

A natural but wrong idea is to make the dummy count proportionalto the real load — pad each bucket to k times its real occupancy. This provides zero privacy: the dummy count becomes a deterministic function of the real count, so the total count reveals the real count up to a known multiplier. A deterministic function of the secret is not private.

Tessera’s target μ is a fixed constant chosen fromε and δ alone — it does not move with the real load. The real load affects only how many real proofs are in the bucket; the noise distribution over the total count is the same whether the real count is 0, 1, or 100 (up to the (ε,δ) bound). That is what makes the mechanism differentially private.

Tuning ε and δ

The privacy budget is a dial. Smaller ε means stronger indistinguishability but more noise (higher μ, more dummy bandwidth). Smaller δ means rarer truncation events and a stricter guarantee, again at higher bandwidth cost. Tessera ships with sensible defaults and exposes the parameters:

At ε = 0.1 the empirical adversary linking AUC is 0.526, essentially at the information-theoretic ceiling of 0.548 for this mechanism — the adversary gains almost nothing from observing the bucket counts.

Empirical validation

Tessera’s privacy is not just argued, it is measured. Thescripts/analysis/linkability_sim.py harness simulates a global passive adversary that observes per-bucket counts and tries to link deliveries to senders. With DP cover traffic atε = 0.1, the adversary’s linking AUC is 0.526— barely above random (0.5) and at the theoretical ceiling of 0.548 for the shifted-Laplace mechanism. For comparison, without cover traffic the same adversary achieves AUC 1.0, and with proportional cover traffic AUC is still 1.0 because the count is a deterministic function of the load.

Bandwidth cost

The DP cover adds B · μ dummy proofs per routing round across B buckets, independent of the real load. That is the price of load-independence: the network carries a fixed noise budget whether or not any real deliveries occur. For a deployment with 64 buckets and μ ≈ 70 (suitable forε = 0.1, δ = 10⁻⁶), that is roughly 4,500 dummy proofs per round — a known, budgetable cost, and far cheaper than the per-message overhead of a mixnet cascade for the same anonymity set.

Code example: DPCoverTraffic API

from tessera.sdk.traffic_manager import DPCoverTraffic

# Configure a (0.1, 1e-6)-DP cover-traffic generator
dp = DPCoverTraffic(epsilon=0.1, delta=1e-6, num_buckets=64)

# For each routing round, get the dummy count per bucket
dummy_counts = dp.sample()           # list[int] of length 64

# Inject `dummy_counts[b]` dummy proofs into bucket b
# (real proofs ride alongside; the relay cannot tell them apart)
for b, n in enumerate(dummy_counts):
    for _ in range(n):
        relay.publish(bucket=b, proof=dp.make_dummy_proof(b))

The same DPCoverTraffic instance is used by every relay; because the mechanism is load-independent, relays need not coordinate on the real load to produce the right noise distribution.

Frequently asked questions