Asymptotics of fingerprinting and group testing: tight bounds from channel capacities

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

16 Citaten (Scopus)
86 Downloads (Pure)


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 (fast but suboptimal) and arbitrary, 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 all considered attacks the joint capacity is shown to be strictly higher than the simple capacity, including the interleaving attack. This last result contradicts results of Huang and Moulin regarding the joint fingerprinting capacity, which implies that finding the fingerprinting capacity without restrictions on the tracer’s capabilities remains an open problem. For group testing, we improve upon previous work about the joint capacities, and derive new explicit asymptotics for the simple capacities of various models. These show that existing simple group testing algorithms of Chan et al. 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 log_2(e) ˜ 1:44 for large numbers of defectives. Keywords: Fingerprinting; channel capacities; compressive sensing; group testing; search problems; traitor tracing
Originele taal-2Engels
Pagina's (van-tot)1967-1980
Aantal pagina's14
TijdschriftIEEE Transactions on Information Forensics and Security
Nummer van het tijdschrift9
StatusGepubliceerd - 2015

Vingerafdruk Duik in de onderzoeksthema's van 'Asymptotics of fingerprinting and group testing: tight bounds from channel capacities'. Samen vormen ze een unieke vingerafdruk.

Citeer dit