A high-rate fingerprinting code

In fingerprinting, a signature, unique to each user, is embedded in each distributed copy of a multimedia content, in order to identify potential illegal redistributors. As an alternative to the vast majority of fingerprinting codes built upon error-correcting codes with a high minimum distance, we propose the construction of a random-like fingerprinting code, intended to operate at rates close to fingerprinting capacity. For such codes, the notion of minimum distance has little relevance. As an example, we present results for a length 288,000 code that can accommodate 33 millions of users and 50 colluders against the averaging attack. The encoding is done by interleaving the users' identifying bitstrings and encoding them multiple times with recursive systematic convolutional codes. The decoding is done in two stages. The first outputs a small set of possible colluders using a bank of list Viterbi decoders. The second stage prunes this set using correlation decoding. We study this scheme and assess its performance through Monte-Carlo simulations. The results show that at rates ranging from 30% to 50% of capacity, we still have a low error probability (e.g. 1%).