A Family of Asymptotically Good Binary Fingerprinting Codes
Josep Cotrina‐Navau, Marcel Fernández · IEEE Transactions on Information Theory · 2010
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.