Fingerprinting codes: higher rates, quick accusations

Leakage of a document distributed among a set of authorized recipients may result in violation of copyright or secrecy of a document. A hidden serial number in the document can be used for finding the source of the leak. A coalition attack is collusion of a set of users to generate copies of the document with a serial number (now called fingerprint) that is different from their original ones. To trace such a forged fingerprint back to one of its producers, reasonable assumptions are necessary. The marking assumption is one such assumption. It says if the i-th bits of the fingerprints of all colluders are the same, it will have the same value in the forged copy. Our first result in this thesis is a construction that achieves the highest known rate of fingerprinting codes, which we conjecture to be optimal. This construction combines two ideas from two earlier constructions. We use bias based code generation that was introduced by Tardos for his well-known fingerprinting code. Our accusation algorithm is based on an earlier algorithm by Anthapadmanabhan, Barg and Dumer that uses the information theoretic notion of typicality. The drawback of this construction is its slow accusation algorithm. Building upon our first construction, we construct another fingerprinting code in which the distributor may choose to have a faster accusation algorithm by sacrificing a little of the rate. A different accusation algorithm for our first code allows us to generalize it to a family of codes that show a tradeoff between rate and efficiency. This tradeoff suggests new ways to construct more efficient algorithms without losing the rate. For the case of two pirates this tradeoff can be made simpler by using Hamming distance instead of a mutual information. This allows improving quadratic running time of our first accusation algorithm to linear without lowering the rate at all. We also look at weak fingerprinting, a variant of fingerprinting for which the capacity is known. We construct a capacity-achieving weak fingerprinting code.