[Tar08] Optimal probabilistic fingerprint codes

Authors: Gábor Tardos | Venue: Journal of the ACM 2008 | Source

Abstract

We construct binary codes for fingerprinting digital documents. Our codes for $n$ users that are $ϵ$-secure against $c$ pirates have length $O(c^2\log (n/ϵ))$. This improves the codes proposed by Boneh and Shaw BS98 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.

BibTeX

Copy

@Inproceedings{STOC:Tardos03,
  author = {G{\'a}bor Tardos},
  title = {Optimal probabilistic fingerprint codes},
  pages = {116--125},
  booktitle = {35th Annual {ACM} Symposium on Theory of Computing},
  address = {San Diego, CA, USA},
  month = {jun~9--11},
  publisher = {{ACM} Press},
  year = {2003},
  doi = {10.1145/780542.780561},
}