Research
Formal foundations, security proofs, and experiment harnesses behind the Tessera protocol. This page summarises the protocol's academic framing for citation and reproduction.
Protocol summary
Tessera is an authenticated, metadata-private, one-to-one delivery protocol. A sender proves identity to a recipient using aSchnorr / Fiat–Shamir zero-knowledge proof under a per-recipient blinded pseudonymY' = Y + tG(t = H(seed ‖ session_id) mod q). The proof is AES-GCM encrypted and routed over abucketed broadcast network whose cover traffic is calibrated to provide (ε,δ)-differentially-privatesender↔recipient metadata.
Three independent privacy mechanisms compose: sender authentication without witness leak, per-recipient pseudonyms for cross-recipient unlinkability, and (ε,δ)-DP cover traffic for network metadata privacy. No central authority; pairwise local enrolment.
Security properties
| Property | Mechanism | Formal proof |
|---|---|---|
| Unforgeability | Schnorr binds (R, s, Y, m); EUF-CMA ⇐ DLog | Forking lemma |
| HVZK / NIZK | Fiat–Shamir transform in the ROM | Standard Schnorr ZK |
| Cross-recipient unlinkability | Per-recipient blinded pseudonym Y' | Blinding lemma |
| Replay resistance | Per-delivery commitment + dedup | Freshness theorem |
| Metadata privacy | (ε,δ)-DP cover traffic, load-independent | Laplace mechanism |
Threat model
| Adversary | Defence |
|---|---|
| Malicious sender (impersonation) | Unforgeability ⇐ DLog |
| Honest-but-curious recipient | Per-recipient blinding — Y' uniform per delivery |
| Colluding recipients | Distinct shared_seed → distinct Y' distributions |
| Global passive network observer | (ε,δ)-DP cover traffic |
| Replay attacker | Per-delivery commitment freshness + dedup |
Out of scope: compromised endpoint (secret key assumed intact on sender's device; recipient runs verifier honestly).
Headline numbers
Single-laptop, single node.
| Metric | Value |
|---|---|
| ZK proof generation | ~0.85 ms |
| ZK proof verification | ~13 ms |
| Subscribe throughput | 326 ops/s4.5× naive |
| Route throughput (~75 subs/bucket) | 440 ops/s |
| FAR / FRR (tamper, swap-key, forge, replay) | 0 / 0 |
| Adversary linking AUC (DP cover, ε=0.1) | 0.526≤ 0.548 |
| Churn delivery (mesh, 50% offline) | 100% |
Experiment harnesses
Each experiment is regenerated by a harness inscripts/; outputs land inresults/.
| ID | Harness | What it measures |
|---|---|---|
| E1 | bench_crypto.py | ZK proof gen/verify/AES latency + sizes |
| E2 | anonymity_sim.py | Bucket k-anonymity + bloom FPR |
| E3 | linkability_sim.py | DP cover-traffic privacy/overhead |
| E4 | bench_throughput.py | Persistent-connection node throughput |
| E5 | churn_sim.py | Mesh vs ring delivery under churn |
| E6 | bench_security.py | Verifier FAR/FRR |
| E7 | leakage_compare.py | Comparative leakage matrix |
uv run python scripts/bench_crypto.py # E1
uv run python scripts/bench_security.py --trials 5000 # E6
uv run python scripts/analysis/anonymity_sim.py # E2
uv run python scripts/analysis/linkability_sim.py # E3
uv run python scripts/analysis/churn_sim.py --nodes 8 # E5
uv run python scripts/analysis/leakage_compare.py # E7Comparative leakage
| Scheme | Routing | Network | Recipient | Colluding | Auth |
|---|---|---|---|---|---|
| Signed messaging | 5 leaks | timing | intended | none | yes |
| Metadata-private messaging | none | none | none | none | missing |
| Tessera | none | none | intended | none | yes |
Open research directions
- Distributed DP-noise generation across relays without a coordinator
- Adaptive bucket count for low-deployment-scale k-anonymity
- Reputation overlay for relay discovery (Kademlia DHT scaffold exists)
- Verifiable AI-agent identity with cross-service unlinkability