Saddle-point solution of the fingerprinting capacity game under the marking assumption

Yen Wei Huang, Pierre Moulin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study a fingerprinting game in which the collusion channel is unknown. The encoder embeds fingerprints into a host sequence and provides the decoder with the capability to trace back pirated copies to the colluders. Fingerprinting capacity has recently been derived as the limit value of a sequence of maxmin games with mutual information as the payoff function. However, these games generally do not admit saddle-point solutions and are very hard to solve numerically. Here under the so-called Boneh-Shaw marking assumption, we reformulate the capacity as the value of a single two-person zerosum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is k and the fingerprint alphabet is binary, we derive equations that can numerically solve the capacity game for arbitrary k. We also provide tight upper and lower bounds on the capacity. Finally, we discuss the asymptotic behavior of the fingerprinting game for large k and practical implementation issues.

Original languageEnglish (US)
Title of host publication2009 IEEE International Symposium on Information Theory, ISIT 2009
Pages2256-2260
Number of pages5
DOIs
StatePublished - 2009
Event2009 IEEE International Symposium on Information Theory, ISIT 2009 - Seoul, Korea, Republic of
Duration: Jun 28 2009Jul 3 2009

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8102

Other

Other2009 IEEE International Symposium on Information Theory, ISIT 2009
Country/TerritoryKorea, Republic of
CitySeoul
Period6/28/097/3/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Saddle-point solution of the fingerprinting capacity game under the marking assumption'. Together they form a unique fingerprint.

Cite this