On the saddle-point solution and the large-coalition asymptotics of fingerprinting games

Yen Wei Huang, Pierre Moulin

Research output: Contribution to journalArticlepeer-review


We study a fingerprinting game in which the number of colluders and the collusion channel are 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 maximin games with mutual information as their payoff functions. 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 zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is kand the fingerprinting alphabet is binary, we show that capacity decays quadratically with k. Furthermore, we prove rigorously that the asymptotic capacity is 1/(k 22 ln 2)and we confirm our earlier conjecture that Tardos' choice of the arcsine distribution asymptotically maximizes the mutual information payoff function while the interleaving attack minimizes it. Along with the asymptotics, numerical solutions to the game for small kare also presented.

Original languageEnglish (US)
Article number6020789
Pages (from-to)160-175
Number of pages16
JournalIEEE Transactions on Information Forensics and Security
Issue number1 PART 2
StatePublished - Feb 2012


  • Asymptotic analysis
  • capacity
  • collusion attacks
  • fingerprinting
  • game theory
  • minimax analysis
  • traitor tracing

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications

Cite this