Paper Info
Title
Optimal probabilistic fingerprint codes
Abstract
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.
Year
DOI
Venue
2008
10.1145/1346330.1346335
J. ACM
Keywords
Field
DocType
constant factor,collusion attack,binary code,arbitrary alphabet,lower bound generalizes,digital document,length O,lower bound,fingerprint codes,optimal probabilistic fingerprint code,c pirate,binary alphabet,Shaw code
Discrete mathematics,Computer science,Binary code,Fingerprint,Probabilistic logic
Journal
Volume
Issue
ISSN
55
2
0004-5411
Citations 
PageRank 
References 
40
1.59
9
Authors
1
Name
Order
Citations
PageRank
Gábor Tardos11261140.58