A note on the limits of collusion-resistant watermarks

In one proposed use of digital watermarks, the owner of a document D sells slightly different documents, D-1,D-2,... to each buyer; if a buyer posts his/her document D-i to the web, the owner can identify the source of the leak. More general attacks are however possible in which k buyers create some composite document D*; the goal of the owner is to identify at least one of the conspirators. We show, for a reasonable model of digital watermarks, fundamental limits on their efficacy against collusive attacks. In particular, if the effective document length is n, then at most O(rootn/lnn) adversaries can defeat any watermarking scheme. Our attack is, in the theoretical model, oblivious to the watermarking scheme being used; in practice, it uses very little information about the watermarking scheme. Thus, using a proprietary system seems to give only a very weak defense.