Keys - Disappearing Cryptography - page 247

subset of values with each skeptic as long as the prover knows one
value of x i for the values in the subset. Of course, multiple copies

and multiple blocks and help reduce this danger but they do not
eliminate it. Eventually, all of the marks will be revealed.

12.6 Collusion Control

Another technique for “keying” watermarks is occasionally called
“collusion control” for lack of a better term. Imagine that you cre-
ate two documents, w 2 encod-

ing the true owner's identity. Watermarking is an imperfect science,
so despite your best efforts someone trying to cheat the system com-
pares the files and finds where they are different. The cheater injects
random noise into these locations, effectively changing half of the
bits. What happens to the watermarks?
Basic systems would fail here.

d 1 and d 2 ,withwatermarkbits w 1 and

w 2 =
001010100 , then only the last two bits are different. A newwatermark,
00101010101 would implicate someone else.
Collusion control systems that can combat this were first intro-
duced by Dan Boneh and James Shaw.[BS95] Their mechanism acts
like an extension of error-correcting codes.

If w 1 = 001010111 and

Error-correcting codes
are described in Chapter
3.

Here's a example. Let S be the set of n -bit code words with only

a single bit set to 1 . f .

Let one code word be assigned to each document. If two document
holders collude, they will only find that their watermarks differ by
two bits. Boneh and Shaw call this a frameproof code and note that
any code that is frameproof for

n =4 ,then S = { 1000 , 0100 , 0010 , 0001 }

n users must come with n bits. So this

construction is optimal.
For example, let Alice's watermark be 0100 and Bob's be 0001 .
Someone tries to erase the watermark by creating a synthetic one
blending the two files. After identifying all bits that are different, the
attacker chooses half from Alice's file and half from Bob's. What hap-
pens if someone compares a file fromAlice and a file fromBob to find
differences? If someone creates a new file with the watermark 0101 ,
then both Alice and Bob will be implicated. Anyone examining the
file can trace it back to both of them. Changing 50 percent of the bits
will produce one of the two watermarks. One will remain implicated.
Of course, a clever attacker may flip both to zero to produce the
watermark 0000 . Thiswillimplicatenoone,butitisnoteasyto
generate. Anyone trusting the watermark will not choose bit vectors
like this example. They may XOR them with a secret password and
the attacker won't know what is up and down, so to speak. A zero in