How I would create an unscrubbable watermark…
When Hollywood release ‘screener’ copies of films to be reviewed for Oscar contention, they know that some copies are going to be leaked on to torrent sites. To prevent this, they digitally watermark each copy so they can trace down who sent it, this is known as a ‘Canary trap’ or a ‘Barium Meal’. Pirates have different methods at their disposal to attempt to scrub these watermarks off, but I propose a method here for watermarking that can survive any scrubbing and correctly identify multiple guilty parties.
Suppose Hollywood release 1000 watermarked screener copies, each only has to contain a number between 0 and 1000, hidden in the stream somewhere. A naive approach would be to take the first frame of the movie, and to encode the number 703, you’d pick the 703rd pixel and make it one unit darker. You could pick the 703rd bit, but pixels are easier to picture. Then when the torrent leaks, then Hollywood simply compare the torrented copy with their master copy, and see which pixel on frame one is different. Then look up the 703rd person on the list and arrest them.
If the scrubber only has one copy of the film it would be absolutely impossible, even with a mighty super-computer, to identify if there is a watermark and what value it represents. A scrubber could just add lots of visual noise to movie, but that could create a noticable deterioration in quality, and would only get rid of differences encoded at the level of single pixels, not large regions.
A better way of scrubbing would be to compare two copies, then if you find that pixel 413 and pixel 703 are different, you could assume that this is where the data is being stored. You wouldn’t know what the correct value for pixel 703 was supposed to be though, and guessing it wrong would leave evidence of both guilty parties. Instead you would need to get 3 copies, and for every difference take a vote. If two copies say that pixel 703 is green, but one copy says it is blue, then we can assume that the blue one deviates from the master copy and should be corrected to green.
This three-copy-voting method uses the same logic used when a computer is trying to correct errors that have crept into saved data, or when geneticists try to discover at what point in a family tree a mutation appeared in DNA. We can think of the Watermarker as adding mutations, and the Scrubber as trying to identify and correct those mutations. This is a pretty good method, even if the watermarker has tagged hundreds or even thousands of frames, and used different watermarking techniques, then you would still just need three copies to purge all these differences. However it is not foolproof.
It is possible to create a water mark that survives three-copy-voting. This would have to be done by deliberately creating parts of your watermark that were the same for some pairs of numbers. You can encode data, such that even with three copies, some part of your information carrying signal would be the same on those three copies. The scrubber would not know those identical pixels contained information unless they had access to a greater and greater number of watermarked copies.
To do this, suppose we encode our screener id as ten bits, as this is all we would need to represent a number up to 1000. Imagine that frame 1, being all black, has master copy values of ten zeroes in a row. Suppose the Scrubber gets a hold of copies with id’s of 6, 7 and 8. These would be represented in binary as 0000000110, 0000000111 and 0000001000 By three-copy-voting you would end up with a string: 0000000110. 7 and 8 escape, but poor old 6 gets left in the torrent. Does this mean the scrub has failed? No, because Hollywood have to legally prove that the watermark of person 6 must have been the leaked copy. But the combination of 6,7,8 isn’t the only combination that would get three-copy-voted to leave a 6. Suppose the following strings were three-copy-voted: 1000000110, 0100000110, 0010000110. This too would leave 6, a fact which the lawyers of person 6 would be keen to point out.
But a torrent with 0000000110 does tell us something about our list of 1000 screeners. It tells us that most of the 3 parties who leaked it had 1’s in those two positions. By exploiting this fact, we can create a watermark that even after being scrubbed, still reveals the identity of the three guilty parties.
Remember that we only chose the first ten bits of frame one as a simple example. In reality these ten digits could be in any position, in any order, in the gigabyte of data that stores the film. They can be represented multiple times, and they can be encoded as a brightening or darkening of a square of 100 pixels, such that a noise filter applied on top would not destroy them. In our example we had 0’s in the master copy, and 1’s in the watermark, but if the master was 00110101000 then we could watermark the value of 1111111111 by the string 11001010111. There is no method a scrubber could use to identify the presense or absense of one of these bits, if the three copies they have all happen to store the same piece of data.
So how do we construct our unscrubbable watermark then?
The torrented copy featuring 0000000110 tells us that most of the 3 offenders have 1’s in those two positions. Every digit in this string is essentially halving the 1000 people, so we know 500 people have 1’s in the second from left digit. Those two 1’s in the scrubbed watermark are very weak fingers of suspicion pointing at the subset of 500 people who have an id like this ???????1?? and like this ????????1?. Not exactly damning evidence, but it is a start. We can take our 1000 suspects, and add a tiny flag of suspicion next to both those subsets. And there should be about 250 people who get two flags. On average, for 10 bits of data, we should get about 5 flag markers, each which we use to apply 500 flags to our 100 people. The more flags you get, the more guilty you look.
But why stop there? Lets call our first watermark we have added watermark A. Why not take our list of 1000 people, put it in a different order, create a new id for each person, and add that watermark B into each screener copy. Now each person has two ids. A screener copy might have id A = 703, and id B = 229. Now we analyse the scrubbed torrent and instead of just one round of adding around 5 x 500 flags, we can have a second round of 5 x 500. But why stop at two ids? We could re-order our list a huge number of times, add a huge number of id’s, get a huge number of rounds of adding flags. With a thousand watermark id’s you would end up with a huge number of guilty flags being added to the 3 guilty people. Statistically their copies would stand out like a spike, against the background noise of innocent people who only get an average number of flags.
This would correctly identify any number of offenders who had their copies blended in a three-copy-voting or any-number-copy-voting scrubbing method. A scrubber can not scrub out the bits in a watermark which are identical on all three of the copies they are blending. On average 5 out of 10 bits will be identical between 2 copies, and 3 out of 10 identical between 3 copies. With 1000 watermarks applied to a each copy, that means that a scrubber with only 3 copies will end up leaving on average 333 bits of invisible incriminating evidence behind. Each of those 333 bits puts a flag in 500 peoples boxes, which is more than enough to identify the three guilty parties.
Even if some of the watermarks are lost due to randomising noise added by the scrubber, there only have to be enough flags that slip through to add enough votes to the guilty parties for them to stand out from the background noise. The number of 10 bit flags that can be added to a gigabyte of data without losing quality is huge. Scrubbing exhaustively enough to remove all the invisible watermarks would introduce so much entropy into the source that data would be lost.
I believe this watermarking system is efficient, unscrubbable, and can detect multiple, combined watermarks.
Stuart Bray 