Nearest neighbor decoding for Tardos fingerprinting codes

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

Over the past decade, various improvements have been made to Tardos' collusion-resistant fingerprinting scheme [Tardos, STOC 2003], ultimately resulting in a good understanding of what is the minimum code length required to achieve collusion-resistance. In contrast, decreasing the cost of the actual decoding algorithm for identifying the potential colluders has received less attention, even though previous results have shown that using joint decoding strategies, deemed too expensive for decoding, may lead to better code lengths. Moreover, in dynamic settings a fast decoder may be required to provide answers in real-time, further raising the question whether the decoding costs of score-based fingerprinting schemes can be decreased with a smarter decoding algorithm. In this paper we show how to model the decoding step of scorebased fingerprinting as a nearest neighbor search problem, and how this relation allows us to apply techniques from the field of (approximate) nearest neighbor searching to obtain decoding times which are sublinear in the total number of users. As this does not affect the encoding and embedding steps, this decoding mechanism can easily be deployed within existing fingerprinting schemes, and this may bring a truly efficient joint decoder closer to reality. Besides the application to fingerprinting, similar techniques can potentially be used to decrease the decoding costs of group testing methods, which may be of independent interest.

Originele taal-2Engels
TitelIH and MMSec 2019 - Proceedings of the ACM Workshop on Information Hiding and Multimedia Security
Plaats van productieNew York
UitgeverijAssociation for Computing Machinery, Inc
Pagina's182-187
Aantal pagina's6
ISBN van elektronische versie978-1-4503-6821-6
DOI's
StatusGepubliceerd - 2 jul 2019
Evenement7th ACM Workshop on Information Hiding and Multimedia Security, IH and MMSec 2019 - Paris, Frankrijk
Duur: 3 jul 20195 jul 2019

Congres

Congres7th ACM Workshop on Information Hiding and Multimedia Security, IH and MMSec 2019
LandFrankrijk
StadParis
Periode3/07/195/07/19

Vingerafdruk Duik in de onderzoeksthema's van 'Nearest neighbor decoding for Tardos fingerprinting codes'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Laarhoven, T. M. M. (2019). Nearest neighbor decoding for Tardos fingerprinting codes. In IH and MMSec 2019 - Proceedings of the ACM Workshop on Information Hiding and Multimedia Security (blz. 182-187). Association for Computing Machinery, Inc. https://doi.org/10.1145/3335203.3335732