Binary collusion-secure codes: Comparison and improvements

With a digital fingerprinting scheme a vendor of digital copies of copyrighted material marks each individual copy with a unique fingerprint. If an illegal copy appears, it can be traced back to one or more guilty pirates, due to this fingerprint. To work against a coalition of several pirates the fingerprinting scheme must be based on a collusion-secure code. Quite a few collusion-secure codes have been proposed over the past few years, but since the authors have addressed different settings, it is hard to compare the schemes. In this paper we study and compare how existing schemes behave both asymptotically in the number of users, asymptotically in the number of pirates, and for practical parameters with from a thousand to a billion users. For the Boneh and Shaw scheme, we make a new error analysis, proving that their scheme is in fact much better than originally assumed. We also point out a problem of adverse selection to which schemes by Tardos, and by Le, Burmester, and Hu appears to be vulnerable