On the Fingerprinting Capacity Under the Marking Assumption

DOI10.1109/TIT.2008.921859zbMATH Open1308.94096arXivcs/0612073OpenAlexW2118032825MaRDI QIDQ3604735FDOQ3604735

Authors: N. Prasanth Anthapadmanabhan, Alexander Barg, I. I. Dumer 

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We address the maximum attainable rate of fingerprinting codes under the marking assumption, studying lower and upper bounds on the value of the rate for various sizes of the attacker coalition. Lower bounds are obtained by considering typical coalitions, which represents a new idea in the area of fingerprinting and enables us to improve the previously known lower bounds for coalitions of size two and three. For upper bounds, the fingerprinting problem is modelled as a communications problem. It is shown that the maximum code rate is bounded above by the capacity of a certain class of channels, which are similar to the multiple-access channel. Converse coding theorems proved in the paper provide new upper bounds on fingerprinting capacity. It is proved that capacity for fingerprinting against coalitions of size two and three over the binary alphabet satisfies $0.25leq{C}_{2,2}leq0.322$ and $0.083leq{C}_{3,2}leq0.199$ respectively. For coalitions of an arbitrary fixed size $t,$ we derive an upper bound $(tln2{)}^{-1}$ on fingerprinting capacity in the binary case. Finally, for general alphabets, we establish upper bounds on the fingerprinting capacity involving only single-letter mutual information quantities.

Full work available at URL: https://arxiv.org/abs/cs/0612073

Recommendations

• scientific article; zbMATH DE number 7051201
• On the Capacity Game of Private Fingerprinting Systems Under Collusion Attacks
• Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes
• Achievable Error Exponents for the Private Fingerprinting Game
• Digital fingerprinting codes: problem statements, constructions, identification of traitors

zbMATH Keywords

digital fingerprintingstrong converse theoremChannel capacitymultiple-access channel (MAC)

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Authentication, digital signatures and secret sharing (94A62)

Cited In (4)

• Equal-Weight Fingerprinting Codes
• Digital fingerprinting under and (somewhat) beyond the marking assumption. (Invited talk)
• Achievable Error Exponents for the Private Fingerprinting Game
• On the Capacity Game of Private Fingerprinting Systems Under Collusion Attacks

This page was built for publication: On the Fingerprinting Capacity Under the Marking Assumption

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604735)