On the Fingerprinting Capacity Games for Arbitrary Alphabets and Their Asymptotics

Yen Wei Huang, Pierre Moulin

Research output: Contribution to journalArticlepeer-review


The fingerprinting capacity has recently been derived as the value of a two-person zero-sum game. In this paper, we study the fingerprinting capacity games with k pirates in a new collusion model called the mixed digit model, which is inspired by the combined digit model of Škorić et al. For small k, the capacities along with optimal strategies for both players of the game are obtained explicitly. For large k, we extend our earlier asymptotic analysis for the binary alphabet with the marking assumption to q-ary alphabets with this general model and show that the capacity is asymptotic to (A/(2k2 ln q)) where the constant (A) is specified as the maximin value of a functional game. Saddle-point solutions to the game are obtained using methods of variational calculus. For the special case of (q)-ary fingerprinting in the restricted digit model, we show that the interleaving attack is asymptotically optimal, a property that has motivated the design of optimized practical codes.

Original languageEnglish (US)
Article number6853368
Pages (from-to)1477-1490
Number of pages14
JournalIEEE Transactions on Information Forensics and Security
Issue number9
StatePublished - Sep 2014
Externally publishedYes


  • Decoding
  • Fingerprint recognition
  • Forgery
  • Games
  • Joints
  • Numerical models
  • Vectors

ASJC Scopus subject areas

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


Dive into the research topics of 'On the Fingerprinting Capacity Games for Arbitrary Alphabets and Their Asymptotics'. Together they form a unique fingerprint.

Cite this