The Watermark That Survives a Collusion

Give every subscriber a copy with its own pattern of bits and a leaked film names the leaker. A group who pool their copies can see where they differ and choose what to put there. Set how many of them there are, how long the string is, and how many subscribers you must not accuse by mistake.

Worked example — The Watermark That Survives a Collusion

Length this coalition and audience need	2,490 bits · 311 B
Length actually carried	3,200 bits · 400 B
Colluders over the threshold	3 of 4
Score of the weakest colluder	230.9
Columns they cannot touch	52.3%
Score of an average colluder	262.4
Spread of an innocent score	42.8
Accusation threshold	239.9

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — The Watermark That Survives a Collusion

A fingerprinting code gives every subscriber a copy of the same film carrying a different string of m bits, so a leaked copy names whoever it was issued to. The bits are not chosen evenly: each position j gets its own bias p_j, drawn so that most positions are nearly all ones or nearly all zeros across the whole subscriber base. A group who pool their copies can see a position only where their own bits differ, and the accusation score adds up, over the positions where the forgery says one, how surprising each subscriber's bit was.

What each symbol means

m: the length of the code in bits, which is what the whole lesson is about
c: how many subscribers pool their copies
Z: the accusation threshold: a score above it names somebody

Assumes: The marking assumption: where every copy in the coalition carries the same bit, they cannot tell that position is there and cannot change it. Everything on this page rests on it. In a real system it is a claim about the embedding — that a mark you cannot see by comparing copies is a mark you cannot remove — and it is the part of the design that gets attacked rather than the arithmetic.
Breaks when: When the number of colluders is larger than the code was sized for. There is no graceful degradation: the scores of the guilty fall as 1/c while the bar stays where the innocent population puts it, so a code long enough for four and facing eight does not name somebody a little less often, it names nobody.

Twice the colluders, four times the watermark 🖖

Drag the coalition slider and watch the first card. Two colluders need 623 bits, four need 2,490, eight need 9,959, sixteen need 39,833. Every doubling multiplies the length by four, three times over, and the ratio to c² lands between 155.60 and 155.75 at all four. It is not exactly four only because a length is a whole number of bits: the ratios are 3.9968, 3.9996 and 3.9997. The reason is in the two cards beside it, and neither is mysterious on its own. A colluder's score is the evidence the code collects about them, and they share it: it grows like the length divided by the number of colluders. An innocent subscriber's score is a random walk of the same length, so its spread grows like the square root of the length. Evidence over noise therefore goes as m/c divided by √m, which is √m/c, and holding that constant while c doubles means m must quadruple. Everything else on this page is a consequence of those two lines.

The bar is set by the people you must not accuse 🖖

Press Four colluders, a long enough code, then Ten million subscribers. The colluders are the same four people with the same copies and the same forgery. The threshold moves from 239.9 to 254.5 and one fewer of them is named. Nothing about the crime changed; the size of the innocent population did. The threshold is not a property of the evidence at all — it is the level an innocent score exceeds by accident only once in a thousand runs across the whole subscriber base, so ten times as many subscribers means each one of them has to be held to a stricter test. That is the multiple-comparison correction that ruins careless statistics, doing something useful for once: it is the only thing standing between a watermarking scheme and a wrongly accused customer.

The code is sized to catch one, not all of them 🖖

At exactly the length the first card demands, run it forty times with different codes: at least one colluder is named in 38 runs out of 40 when four of them collude, and all four are named in none. Make the code half as long again and all four come out in 15 runs of 40. Press Sixteen colluders for the far end, where 10 of 16 are over the bar and the weakest sits 270 points short. There is a strange consolation in it for the studio. A bigger coalition makes each member harder to convict and makes it almost certain that somebody will be, because there are more of them to go wrong — at the required length, four colluders yield a name in 38 runs of 40 and sixteen colluders in 40 of 40.

Problems solved in full

Where does 2,490 come from? The tool prints it for four colluders among a million subscribers, and it is not a simulated number: it comes from two measured laws and one decision about how often you are willing to accuse an innocent person. The derivation is four lines, and the last of them is the one that produces the square.

Open this problem in the tool
1. The evidence a colluder leaves is proportional to the length of the code and shared out among them, because each column they control is one they all had a hand in. Measured across coalitions of 2 to 16 and codes of 800 to 51,200 bits: about 0.34 m/c.
  
  $E [S_{colluder}] \approx 0.34 \frac{m}{c}$
2. An innocent subscriber's score is a sum of m independent contributions with mean zero, so it is a random walk. Its spread grows like the square root of the length, not the length. Measured: about √(m/2).
  
  $sd (S_{innocent}) \approx \frac{m}{2}$
3. Choose how often you will accuse an innocent person: at most ε across a population of n. One subscriber must therefore be cleared at 1 − ε/n, which for a million subscribers and one chance in a thousand is 6.00 standard deviations out.
  
  $Z = z \frac{m}{2}, z = Φ^{- 1} (1 - \frac{ε}{n}) = Φ^{- 1} (1 - 1 0^{- 9}) = 5.9978$
4. Detection needs the evidence to clear the bar. Put the two laws in and solve for m.
  
  $0.34 \frac{m}{c} > z \frac{m}{2} ⟹ m > \frac{z c}{0 . 34 2} ⟹ m > 4.3253 z^{2} c^{2}$
5. The c is inside the square, and that is the whole answer: 2,490 bits for four colluders and 9,959 for eight, which is four times as many to within the rounding up to whole bits.
  
  $m > 155.5955 c^{2} ⌈ \cdot ⌉ c = 4 \Rightarrow 2, 490, c = 8 \Rightarrow 9, 959, c = 16 \Rightarrow 39, 833$
6. The number to design around is not the number a proof will give you. Tardos's own theorem guarantees this with 100c²⌈ln(n/ε)⌉ bits, which is 2,100c² here — thirteen times longer than the Gaussian estimate, because a proof must hold against every collusion strategy rather than against the three on this page.
  
  $m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉ = 2100 c^{2} = 13.5 \times 155.6 c^{2}$
Answer

m > (z c √(1/2) ÷ 0.34)² = 4.3253 z² c², which at z = 5.9978 is 155.60 c² before rounding up to whole bits: 623 bits for two colluders, 2,490 for four, 39,833 for sixteen. In bytes that is 78 B, 311 B and 4.98 kB of watermark payload — small enough that the length is almost never what stops you, and the reason the field argues about the marking assumption instead. The one thing the square cannot be traded against is the audience: n enters only through z, which grows like √(log n), so going from a thousand subscribers to ten million takes the length from 1,564 bits to 2,801, a rise of 79%, while doubling the coalition once costs 300%.

$m > 4.3253 z^{2} c^{2} vs m_{proved} = 100 c^{2} ⌈ ln \frac{n}{ε} ⌉$
Does a streaming service need any of this? Step one of this series covers a world where every copy is identical and there is no way to talk to a device. A subscription service is the opposite: Widevine's own documentation says a licence request goes over HTTPS to a licence server and that "the contents of the license are no longer modifiable and are individualized to the requesting device". So what is left of the mathematics?

Open this problem in the tool
1. Half of it goes away entirely. With a back channel there is no header to cover: excluding a device costs nothing in the stream, because you simply do not issue it a licence. The whole covering problem of step one is the price of having no way to talk back — a disc cannot ask who is playing it.
2. The other half does not go away, and gets more important rather than less. A licence server stops a device it knows is compromised; it cannot stop a subscriber in good standing from recording what they legitimately decrypted. That leak carries a fingerprint, and the fingerprint is the only thing that names them.
3. So the sizing question is the one on this page, at a real subscriber base. The code length grows with the square of the coalition, and with the audience only through a logarithm.
  
  $m > 155.6 c^{2} at n = 1 0^{6}, m \propto z^{2} \propto lo g \frac{n}{ε}$
4. Read the table across and then down. Sixteen colluders cost sixty-four times two colluders. Ten thousand subscribers to a hundred million — four orders of magnitude — costs 1.66 times.
  
  $n 1 0^{4} 1 0^{5} 1 0^{6} 1 0^{7} 1 0^{8} c = 2 468545623701779 c = 4 1, 871 2, 180 2, 490 2, 801 3, 113 c = 8 7, 484 8, 719 9, 959 11, 202 12, 449 c = 16 29, 933 34, 873 39, 833 44, 808 49, 795 \frac{m ( 1 0 ^{8} )}{m ( 1 0 ^{4} )} = \frac{3 , 113}{1 , 871} = 1.66 against \frac{m ( c = 16 )}{m ( c = 2 )} = 64$
5. At ten million subscribers and four colluders that is 2,801 bits: three hundred and fifty bytes of payload, for a film of several gigabytes.
  
  $n = 1 0^{7}, c = 4 : 2, 801 bits = 350 bytes$
Answer

Nothing about the code length is ever the problem. 350 bytes at a scale where the content is billions of bytes, and an audience a thousand times larger costs two thirds again rather than a thousand times. The coalition is the only term that bites, because it is the only one inside the square — and the number of people who will actually pool their copies is the one quantity in the whole calculation that nobody can measure in advance. What a real system spends its engineering on is not this arithmetic: it is making the mark survive re-encoding, cropping and a camera pointed at a screen, and holding the marking assumption up when the attacker has two copies and a difference tool.

$m \propto c^{2} lo g \frac{n}{ε} : \times 64 in c, \times 1.66 in n$

Learning path

Protecting a stream: revoke a device, then find out which one

References (4)

Worked problem 2 turns on a streaming service working the other way round from step 1 of the series, and this is the vendor's own description of the licence flow: Google, "Widevine DRM Overview", developers.google.com/widevine/drm/overview.
The code this page builds, the accusation score it computes, and the c² the whole lesson is about: G. Tardos, "Optimal probabilistic fingerprint codes." Journal of the ACM 55(2), 2008, pp. 1–24. First published in STOC 2003, pp. 116–125.
Where the marking assumption comes from, and the proof that some length is unavoidable: D. Boneh and J. Shaw, "Collusion-secure fingerprinting for digital data." IEEE Transactions on Information Theory 44(5), 1998, pp. 1897–1905.
Why a studio cares: this is the other half of the same specification as step 1 of the series, and forensic marks are what it falls back on when revocation is too slow. AACS LA, Advanced Access Content System (AACS): Introduction and Common Cryptographic Elements, Revision 0.91, 17 February 2006.