Skip to content

Traitor Trace

Broadcast encryption · subset-cover revocation · traitor tracing

One ciphertext readable by any authorized subscriber and no one else, a revoked member locked out without rekeying anyone, and a leaked decoder traced back to whoever built it.

What is this?

Broadcast encryption solves a one-to-many problem: a sender publishes a single encrypted message, and every authorized subscriber — but no one else — can open it. The two hard parts are revocation (kick one subscriber out without re-issuing anyone else's keys) and tracing (when a bootleg decoder turns up, work out whose keys are inside it just by feeding it ciphertexts). This lab runs the real thing at a small scale: sixteen subscribers on a binary tree, real AES-256-GCM, real key derivation — and a pirate decoder you build yourself and then hunt down.

What's real here, what's scaled down, and what this does not prove
  • Real: every encryption and decryption on this page is WebCrypto AES-256-GCM; tree keys are derived with HKDF-SHA-256 and GGM-style HMAC-SHA-256 walks; covers are computed live by the actual Naor–Naor–Lotspiech algorithms; every lockout you see is a genuine GCM authentication failure.
  • Scaled down: 16 subscribers instead of millions, so you can watch the tree. The pirate decoder is a transparent software box built from real subscriber keys — a deployed system would face opaque hardware.
  • Not proven here: nothing about endpoint security (a paying subscriber can always re-share content it legitimately decrypted), nothing about watermarking media, and no claims about production parameter sizes. This is a teaching demo, not production crypto.

Exhibit 1 The naive corner — why this problem is hard

Encrypting to a group is easy if you don't mind paying for it. There are two obvious designs, and each is bad at exactly the thing the other is good at. Both run below with real AES-256-GCM key wraps — count the work.

Exhibit 2 The subset cover — revoke by clicking

The Naor–Naor–Lotspiech idea: give each subscriber keys tied to subtrees of a binary tree, and to broadcast, cover exactly the non-revoked leaves with a few subtrees and wrap the session key once per cover set. Click subscribers below to revoke them and watch the cover recompute, the header shrink, and the revoked decoders fail against real GCM — while nobody else's keys change.

Exhibit 3 The tracing — name the leaker

A pirate decoder has appeared. You built it, but the tracer doesn't know that — it sees only a black box that either decrypts a ciphertext or doesn't. The trick: craft probe ciphertexts that only some subscribers' keys can open, and binary-search the subscriber line by watching where the box goes silent. The keys inside the box give its owner away.

Exhibit 4 Collusion — the honest limit

Two traitors pool their keys. The encryption itself doesn't care — pooled revoked keys still open nothing, no matter how many collude. Tracing is the delicate part: this page's tracer provably catches any lone traitor, and catches a coalition member when the box always decrypts what it can. But a coalition box that notices it's being probed and answers by coin flip can drag the binary search onto an innocent subscriber. Run it and watch the guarantee end.

Same math, different building: the licensed database

A vendor licenses a database to two hundred institutions and gives each one a leaf on a tree like Exhibit 2's. Every content batch is encrypted under a subset cover, and three problems this page demonstrates become routine operations. A campus whose subscription lapses mid-year is revoked by recomputing the cover — the other 199 institutions' keys never change and nobody re-enrolls. A credential that turns up on a proxy site is a pirate decoder, and Exhibit 3's procedure — feed it crafted batches, watch what it can and cannot open — points back to the institution whose keys it carries. And the vendor needs no live connection to any subscriber to do either: receivers are stateless. This isn't an analogy; it is the same construction at a different scale.

Real world: AACS and the leaked device keys

AACS, the content-protection system on Blu-ray discs, uses the subset-difference scheme demonstrated here: player devices hold key sets from a large tree, and each disc carries a Media Key Block — a subset-cover header — that every unrevoked player can process. When keys were extracted from software players (most famously the processing key that spread across the internet in 2007), the licensing authority did what Exhibit 2 does: newly pressed discs carried covers excluding the compromised keys. Revocation worked as designed — for discs pressed afterward. It could not undo discs already on shelves, and keys kept being extracted from new player versions. The primitive held; the endpoints kept leaking. That is the honest lesson of this whole page: subset cover makes revocation cheap and tracing possible — it does not make decoders leak-proof.

What this isn't