A Family of Asymptotically Good Binary Fingerprinting Codes

作者：Cotrina Navau Josep^*; Fernandez Marcel

来源：IEEE Transactions on Information Theory, 2010, 56(10): 5335-5343.

DOI：10.1109/TIT.2010.2059470

• Boneh-Shaw codes
• digital fingerprinting
• list decoding

A fingerprinting code is a set of codewords that are embedded in each copy of a digital object with the purpose of making each copy unique. If the fingerprinting code is c-secure with epsilon error, then the decoding of a pirate word created by a coalition of at most c dishonest users, will expose at least one of the guilty parties with probability 1 - epsilon. The Boneh-Shaw fingerprinting codes are n-secure codes with epsilon(B) error, where n also denotes the number of authorized users. Unfortunately, the length the Boneh-Shaw codes should be of order O(n(3) log(n/epsilon(B))), which is prohibitive for practical applications. In this paper, we prove that the Boneh-Shaw codes are (c < n)- secure for lengths of order O(nc(2) log(n/epsilon(B))). Moreover, in this paper it is also shown how to use these codes to construct binary fingerprinting codes of length L = O(c(6) log(c/epsilon)log n), with probability of error epsilon < epsilon(B) and an identification algorithm of complexity poly(log n) = poly(L). These results improve in some aspects the best known schemes and with a much more simple construction.

• 出版日期2010-10