Asymptotics of Fingerprinting and Group Testing: Tight Bounds from Channel Capacities
arXiv:1404.2576 · doi:10.1109/TIFS.2015.2440190
Abstract
In this work we consider the large-coalition asymptotics of various fingerprinting and group testing games, and derive explicit expressions for the capacities for each of these models. We do this both for simple decoders (fast but suboptimal) and for joint decoders (slow but optimal). For fingerprinting, we show that if the pirate strategy is known, the capacity often decreases linearly with the number of colluders, instead of quadratically as in the uninformed fingerprinting game. For many attacks the joint capacity is further shown to be strictly higher than the simple capacity. For group testing, we improve upon known results about the joint capacities, and derive new explicit asymptotics for the simple capacities. These show that existing simple group testing algorithms are suboptimal, and that simple decoders cannot asymptotically be as efficient as joint decoders. For the traditional group testing model, we show that the gap between the simple and joint capacities is a factor 1.44 for large numbers of defectives.
arXiv comment14 pages, 6 figures
References in corpus (9)
- Boolean Compressed Sensing and Noisy Group Testing
- Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction
- Group Testing with Probabilistic Tests: Theory, Design and Application
- Towards joint decoding of binary Tardos fingerprinting codes
- On the Saddle-point Solution and the Large-Coalition Asymptotics of Fingerprinting Games
- Capacities and Capacity-Achieving Decoders for Various Fingerprinting Games
- Dynamic Traitor Tracing for Arbitrary Alphabets: Divide and Conquer
- Efficient Probabilistic Group Testing Based on Traitor Tracing
- Dynamic Traitor Tracing Schemes, Revisited