Communication optimal tardos-based asymmetric fingerprinting

Asymmetric fingerprinting schemes — introduced by Pfitzmann and Schunter in Eurocrypt 1996 — enable the transmission of a file stored in a server to a set of users so that each user obtains a variation of the file. The security considerations of these schemes are as follows: if any (appropriately bounded) subset of users collude to produce a “pirate” copy of the file, it is always possible for the server to prove to a third party judge the implication of at least one of them, while a malicious server can never implicate innocent users. Given that asymmetric fingerprinting is supposed to distribute files of substantial size (e.g., media files including video and audio) any communication rate (defined as the size of the file over the total transmission length) less than 1 would render them practically useless. The existence of such schemes is currently open. Building on a rate close to 1 oblivious transfer (constructed from recently proposed rate optimal homomorphic encryption), we present the first asymmetric fingerprinting scheme that is communication optimal, i.e., its communication rate is arbitrarily close to 1 (for sufficiently large files) thus resolving this open question. Our scheme is based on Tardos codes, and we prove our scheme secure in an extended formal security model where we also deal with the important but previously unnoticed (in the context of asymmetric fingerprinting) security considerations of accusation withdrawal and adversarial aborts.