Capacities and capacity-achieving decoders for various fingerprinting games

Onderzoeksoutput: Boek/rapportRapportAcademic

12 Citaten (Scopus)
83 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Uitgeverijs.n.
Aantal pagina's13
StatusGepubliceerd - 2014

Publicatie series

NaamarXiv.org
Volume1401.5688 [cs.IT]

Vingerafdruk Duik in de onderzoeksthema's van 'Capacities and capacity-achieving decoders for various fingerprinting games'. Samen vormen ze een unieke vingerafdruk.

Citeer dit