On the Fingerprinting Capacity Games for Arbitrary Alphabets and Their Asymptotics

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/(2k² 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.