Binary Codes for Collusion-Secure Fingerprinting

摘要

We examine the problem of Collusion-Secure Fingerprinting in the case when marks are binary and coalitions are of size 2. We are motivated by two considerations, the pirates' probablity of success (which must be non-zero, as was shown by Boneh and Shaw) on one hand, and decoding complexity on the other. We show how to minimize the pirates' probability of success: but the associated decoding complexity is O(M~2), where M is the number of users. Next we analyze the Boneh and Shaw replication strategy which features a higher probability of success for the pirates but a lower decoding complexity. There are two variations. In the case when the fingerprinting code is linear we show that the best codes are linear intersecting codes and that the decoding complexity drops to O(log~2 M). In the case when the fingerprinting code is allowed to be nonlinear, finding the best code amounts to finding the largest B_2-sequence of binary vectors, an old code amounts to finding the largest B_2-sequence of binary vectors, and old combinatorial problem. In that case decoding complexity is intermediate, namely O(M).