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

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)
87 Downloads (Pure)

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 (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
Original languageEnglish
Pages (from-to)1967-1980
Number of pages14
JournalIEEE Transactions on Information Forensics and Security
Volume10
Issue number9
DOIs
Publication statusPublished - 2015

Fingerprint Dive into the research topics of 'Asymptotics of fingerprinting and group testing: tight bounds from channel capacities'. Together they form a unique fingerprint.

Cite this