Tessera Threat Model
A threat model says what you are protecting, from whom, and under what assumptions. This page enumerates the adversaries Tessera considers, the security property each is defended by, the formal basis for that defence, the cryptographic assumptions the whole edifice rests on, and — just as importantly — what Tessera does not protect.
What a threat model is, and why it matters
Security is not a scalar; it is a set of guarantees against a set of adversaries under a set of assumptions. A protocol that is “secure” without naming its threat model is underspecified. For architects evaluating Tessera, the relevant questions are: which adversaries does it defend against, which does it not, and what must be true about the deployment environment for the guarantees to hold? This page answers each in turn.
Adversaries
| Adversary | What they see | Defence | Scope |
|---|---|---|---|
| Malicious sender (impersonation) | Public parameters, recipient’s Y | Schnorr EUF-CMA ⇐ DLog (forking lemma) | In scope |
| Honest-but-curious recipient | Its own deliveries, all public traffic | ZK — learns nothing beyond identity of sender | In scope |
| Colluding recipients | Their combined deliveries | Distinct shared_seed → distinct Y′ distributions | In scope |
| Global passive network observer | All per-bucket counts over time | (ε,δ)-DP cover traffic | In scope |
| Coalition of compromised relays | All proofs + Bloom filters | Same DP bound (counts only) + blinding | In scope |
| Replay attacker | Recorded proofs | Per-delivery commitment freshness + dedup | In scope |
| Compromised endpoint (OS/keys) | Secret key, all state | — | OUT OF SCOPE (assumed secret key intact) |
The model is deliberately conservative: a coalition of compromised relays is considered in-scope and defended by the same (ε,δ)-DP bound that defends a single global observer, because the relays see only counts and blinded commitments. Endpoint compromise is out of scope — Tessera assumes the secret key is intact on the sender’s device.
Security properties
Each property maps to a mechanism and a formal result:
| Property | Mechanism | Formal basis |
|---|---|---|
| Unforgeability | Schnorr binds (R, s, Y, m) | EUF-CMA ⇐ DLog (forking lemma) |
| HVZK / NIZK | Fiat–Shamir transform in ROM | Standard Schnorr ZK |
| Cross-recipient unlinkability | Per-recipient blinded pseudonym Y′ | Blinding lemma |
| Replay resistance | Commitment freshness + dedup | Freshness theorem |
| Metadata privacy | (ε,δ)-DP cover traffic, load-independent | Laplace mechanism (Dwork et al.) |
Assumptions
Tessera’s guarantees rest on four assumptions:
- SECP256k1 discrete-logarithm hardness. No efficient adversary can compute
xfromY = x·G. This underpins unforgeability and the blinding lemma. - Random oracle model (ROM). The hash
Hused for the Fiat–Shamir challenge and the blinding scalar is modeled as a random oracle. This is the standard assumption for NIZK soundness and zero-knowledge of FS-transformed Schnorr. - Honest verifier. The recipient (verifier) follows the protocol. Tessera does not defend against a malicious verifier who deviates from the verification algorithm — but such deviation only affects whether the recipient accepts the proof, not the sender’s secrets.
- Secret-key integrity. The sender’s long-term secret key
xis not compromised. Ifxleaks, the adversary can impersonate the sender — out of scope, same as every other public-key authentication system.
What Tessera does NOT protect
A clear threat model says what is out of scope as loudly as what is in. Tessera does not protect:
- Message content. Tessera authenticates the sender and routes privately; it does not encrypt the payload. Use a content-encryption layer (Tessera ships AES-GCM for the proof envelope; end-to-end content encryption is the application’s responsibility).
- Endpoint compromise. If the sender’s device is compromised and
xis extracted, all guarantees fail. Tessera assumes key integrity, like every public-key system. - Traffic-confirmation attacks beyond the (ε,δ)-DP bound.An adversary that can correlate timing, size, or content of messages across the network boundary in ways not captured by the per-bucket count model may gain additional information up to the DP budget. The bound is statistical and compositionally holds across rounds, but exotic side channels (e.g. traffic analysis of the TCP layer, power analysis of the device) are not covered.
Comparison: Tessera vs Signal vs Tor
| Scheme | Assumes | Protects | Does not protect |
|---|---|---|---|
| Tessera | DLog, ROM, honest verifier, key integrity | Sender, recipient, timing, graph | Content (use AES-GCM), endpoint |
| Signal | Honest server, E2EE key exchange | Content | Social graph (server sees it) |
| Tor | ≥1 honest hop in circuit | Source IP of TCP stream | Exit traffic, timing correlation |
Tessera’s threat model is narrower than Signal’s on content (Tessera does not provide the content layer) but strictly stronger on metadata (Signal’s server reconstructs the social graph). Compared with Tor, Tessera provides authenticated one-to-one delivery rather than anonymous source-of-TCP-stream, and defends against a global passive observer via DP cover traffic rather than relying on hop diversity.
Frequently asked questions
Why is endpoint compromise out of scope?
Every public-key authentication system assumes the secret key is intact on the prover's device. If the device is compromised and x is extracted, the adversary can impersonate the sender indefinitely. Defending against endpoint compromise requires OS-level isolation (secure enclaves, hardware keys), which is orthogonal to the protocol layer Tessera operates at. Tessera integrates with standard key stores (EncryptedKeyStore, PBKDF2) to make extraction harder, but does not claim to prevent it.
Does Tessera defend against a coalition of all relays?
Yes, within the (ε,δ)-DP bound. A coalition of all relays sees every proof and every Bloom subscription, but it still sees only counts (padded by DP cover traffic) and blinded commitments (uniform per delivery). The blinding lemma and the DP guarantee both hold against a coalition because they are information-theoretic/statistical and do not depend on trust assumptions about relays. The only thing a full coalition gains over a single relay is more proof copies, which it already had via gossip.
What is the difference between the (ε,δ) bound and perfect privacy?
Perfect privacy (ε=0, δ=0) would require the per-bucket count to be statistically independent of the real load — achievable only with infinite dummy bandwidth. Tessera's (ε,δ)-DP bound is the standard relaxation: an adversary's ability to distinguish 'delivery happened' from 'delivery did not happen' is bounded by ε, with a δ probability of failure. At ε=0.1 the empirical linking AUC is 0.526, essentially at the information-theoretic ceiling of 0.548 — the residual information is negligible for practical purposes.