Optimal probabilistic fingerprint codes
G Tardos - Journal of the ACM (JACM), 2008 - dl.acm.org
G Tardos
Journal of the ACM (JACM), 2008•dl.acm.orgWe construct binary codes for fingerprinting digital documents. Our codes for n users that are
ε-secure against c pirates have length O (c 2log (n/ε)). This improves the codes proposed by
Boneh and Shaw [1998] whose length is approximately the square of this length. The
improvement carries over to works using the Boneh--Shaw code as a primitive, for example,
to the dynamic traitor tracing scheme of Tassa [2005]. By proving matching lower bounds we
establish that the length of our codes is best within a constant factor for reasonable error …
ε-secure against c pirates have length O (c 2log (n/ε)). This improves the codes proposed by
Boneh and Shaw [1998] whose length is approximately the square of this length. The
improvement carries over to works using the Boneh--Shaw code as a primitive, for example,
to the dynamic traitor tracing scheme of Tassa [2005]. By proving matching lower bounds we
establish that the length of our codes is best within a constant factor for reasonable error …
We construct binary codes for fingerprinting digital documents. Our codes for n users that are ε-secure against c pirates have length O(c2log(n/ε)). This improves the codes proposed by Boneh and Shaw [1998] whose length is approximately the square of this length. The improvement carries over to works using the Boneh--Shaw code as a primitive, for example, to the dynamic traitor tracing scheme of Tassa [2005].
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 et al. [2003] 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.
ACM Digital Library