Capacities and capacity-achieving decoders for various fingerprinting games

Combining the information-theoretic approach to fingerprinting with a more constructive, probabilistic approach, we derive new results on the fingerprinting capacities for various informed settings, as well as new log-likelihood decoders with provable code lengths that asymptotically match these capacities. The simple decoder built against the interleaving attack is further shown to achieve the simple capacity for unknown attacks, and is argued to be an improved and more natural choice than the recently proposed decoder of Oosterwijk et al. With this new simple decoder, cut-offs on the bias distribution function can finally be dismissed. Besides the application of these results to fingerprinting, a direct consequence of our results to group testing is that (i) a simple decoder asymptotically requires a factor 1.44 more tests to find all defectives than a joint decoder, and (ii) the simple decoder presented in this paper achieves this bound.