Abstract:
We construct binary codes for fingerprinting. Our codes for n users that are ε-secure against c pirates have length O(c2 log(n/ε)).This improves the codes proposed by Boneh and Shaw whose length is approximately the square of this length. Our codes use the full power of randomization. This improvement carries over to works using the Boneh- Shaw code as a primitive, e.g. to the dynamic traitor tracing scheme of Tassa.
By proving matching lower bounds we establish that the length of our codes is best within a constant factor for reasonable error probabilities. This lower bound generalizes the bound found independently by Peikert, Shelat, and Smith that applies to a limited class of codes. Our results also imply that randomized fingerprint codes over a binary alphabet are as powerful as over an arbitrary alphabet and the equal strength of two distinct models for fingerprinting.