Metadata-Private Secure Messaging

Modern messaging apps encrypt message bodies but leak metadata — who talks to whom, when, and how often — to the central server that routes them. This metadata is sufficient to reconstruct social graphs, identify sensitive relationships, and deanonymize users. Tessera gives messaging developers a protocol that authenticates senders with zero-knowledge proofs while hiding the sender↔recipient relationship from the network.

The problem: messaging metadata leaks

End-to-end encryption (E2EE) is now table stakes, but it protects only the content of a message. The routing infrastructure still sees who sent a message to whom, when it was sent, its size, and the frequency of communication. A 2016 Stanford study showed that metadata alone is enough to infer relationships, routines, and even health conditions. The server operator — and any party they share data with, lawfully or not — learns the full communication graph.

For messaging app developers this is a structural problem: the very service you run is the surveillance surface. You cannot honestly claim "private" messaging while holding a perfect log of every conversation partner your users have.

How Tessera solves it

Tessera composes three independent privacy mechanisms so that the network — including relay operators — cannot learn sender↔recipient relationships, while the recipient can still cryptographically verify who sent the message.

• Blinded pseudonyms. Each delivery uses a per-recipient pseudonym Y' = Y + tG where t = H(seed ‖ session_id) mod q. The recipient can verify the proof but cannot link deliveries across sessions or to other recipients.
• (ε,δ)-DP cover traffic. The bucketed broadcast network injects cover traffic calibrated to a formal differential-privacy budget. An adversary's ability to distinguish real from cover messages is bounded by ε and δ.
• Bucketed broadcast. Messages are addressed to a bucket, not a recipient. The recipient subscribes to their bucket and pulls; routing reveals only bucket-level k-anonymity.
• ZK authentication. A Schnorr / Fiat–Shamir proof under the blinded pseudonym authenticates the sender without revealing the long-term public key to the network.

Architecture flow

The delivery path is designed so that no single party — sender, recipient, or relay — can reconstruct the full message graph.

Sender (holds long-term key Y, shared_seed with recipient)
  │
  1. BlindedSender.prepare(seed, session_id)
       → blinded pseudonym Y' = Y + tG
  │
  2. ZKProver.prove(Y', message)  → Schnorr FS proof π
       π binds (R, s, Y', m); reveals nothing about Y
  │
  3. SecureEncryption.encrypt(π, payload, recipient_key)  → AES-GCM ciphertext
  │
  4. make_routing_fields(recipient) → bucket, fingerprint
  │
  5. broadcast to bucket over relay overlay (with DP cover traffic)
  │
Recipient (holds shared_seed, verifier key)
  │
  6. subscribes to own bucket, pulls ciphertext
  │
  7. SecureEncryption.decrypt → recover π, payload
  │
  8. BlindedVerifier.verify(π, Y', message) → accept / reject

Code example

Minimal sender/recipient flow using the Tessera SDK. Enrolment (out-of-band exchange of shared_seed) happens once per sender↔recipient pair.

from tessera.sdk import Sender, Verifier
from tessera.crypto.blinding import BlindedSender, BlindedVerifier

# --- one-time enrolment (out of band) ---
shared_seed = b"\x9a" * 32   # both parties hold this

# --- sender side ---
sender = Sender(secret_key=b"...long-term sk...")
blinded = BlindedSender(sender.public_key, shared_seed, session_id="sess-42")
y_prime = blinded.pseudonym()                     # Y' = Y + tG
proof = blinded.prove(b"hi — meet at 7")           # Schnorr FS proof

# --- recipient side ---
ver = Verifier(expected_pubkey=sender.public_key)
bver = BlindedVerifier(ver, shared_seed, session_id="sess-42")
ok = bver.verify(proof, y_prime, b"hi — meet at 7")
assert ok is True   # authenticated, network saw no Y, no recipient address

Relevant benchmarks

Single-node measurements from the Tessera experiment harnesses.

At ~0.85 ms proof generation and 326 ops/s subscribe throughput, Tessera is fast enough for interactive messaging at realistic fan-out. Zero forgery across tamper, swap-key, forge, and replay trials means the authentication layer holds under active attack.

Frequently asked questions