# Optimal probabilistic fingerprint codes URL: https://dl.acm.org/doi/abs/10.1145/1346330.1346335 Authors: Gábor Tardos ## Abstract We construct binary codes for fingerprinting digital documents. Our codes for $n$ users that are $\epsilon$-secure against $c$ pirates have length $O(c^2\log(n/\epsilon))$. This improves the codes proposed by Boneh and Shaw [[BS98 - Collusion-secure fingerprinting for digital data|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.