Robust fingerprinting codes: a near optimal construction

Fingerprinting codes, originally designed for embedding traceable fingerprints in digital content, have many applications in cryptography; most notably, they are used to construct traitor tracing systems. Recently there has been some interest in constructing robust fingerprinting codes: codes capable of tracing words even when the pirate adversarially destroys a δ fraction of the marks in the fingerprint. An early construction due to Boneh and Naor produces codewords whose length is proportional to c4/(1-δ)2 where c is the number of words at the adversary's disposal. Recently Nuida developed a scheme with codewords of length proportional to (c log c)2/(1-δ) 2. In this paper we introduce a new technique for constructing codes whose length is proportional to (c log c)2/(1-δ), which is asymptotically optimal up to logarithmic factors. These new codes lead to traitor tracing systems with constant size ciphertext and asymptotically shorter secret keys than previously possible.