Lower bounds for collusion-secure fingerprinting

Chris Peikert, Abhi Shelat, Adam D. SmithSODA 2003 · OpenReview

Abstract

Collusion-secure fingerprinting codes are an important primitive used by many digital watermarking schemes [1, 10, 9]. Boneh and Shaw [3] define a model for these types of codes and present an explicit construction. Their code has length O(c3 log(l/ε)) and attains security against coalitions of size c with ε error. Boneh and Shaw also present a lower bound of Ω (c3log(1/cε)) on the length of any collusion-secure code.We give new lower bounds on the length of collusion-secure codes by analyzing a weighted coinflipping strategy for the coalition. As an illustration of our methods, we give a simple proof that the Boneh-Shaw construction cannot be asymptotically improved. Next, we prove a general lower bound: no secure code can have length O(c21og(1/cε)), which improves the previous known bound by a factor of c. In particular, we show that any secure code will have length Ω(c2 log(1/cε)) as long as log(l/ε) ≥ K k log c, where K is a constant and k is the number of columns in the code (in some sense, a measure of the code's complexity). Finally, we describe a general paradigm for constructing fingerprinting codes which encompasses the construction of [3], and show that no secure code that follows this paradigm can have length O((c3/log c) log(1/cε)) follows this (again, by showing a lower bound for large values of ln(1/ε)). This suggests that any attempts at improvement should be directed toward techniques that lie outside our paradigm.
BibTeX
@inproceedings{peikert2003lower,
  author = {Chris Peikert and Abhi Shelat and Adam D. Smith},
  title = {{Lower bounds for collusion-secure fingerprinting}},
  booktitle = {SODA},
  year = {2003},
  url = {https://openreview.net/forum?id=Rf8QH7Uqwul},
}

Loading related content...

Figure