On the Fingerprinting Capacity Under the Marking Assumption
N. Anthapadmanabhan, A. Barg, und I. Dumer. (2006)cite arxiv:cs/0612073
Comment: final version, 12 pages, 2 figures, to appear in IEEE Trans. on
Inform. Theory - Special Issue on Information-theoretic Security, Jun 2008,
simplified proofs in Sections II and III, changes in Theorem 4.1.
Zusammenfassung
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.25 C_2,2 0.322$ and
$0.083 C_3,2 0.199$ respectively. For coalitions of an arbitrary
fixed size $t,$ we derive an upper bound $(tłn2)^-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.
Beschreibung
[cs/0612073] On the Fingerprinting Capacity Under the Marking Assumption
cite arxiv:cs/0612073
Comment: final version, 12 pages, 2 figures, to appear in IEEE Trans. on
Inform. Theory - Special Issue on Information-theoretic Security, Jun 2008,
simplified proofs in Sections II and III, changes in Theorem 4.1
%0 Generic
%1 Anthapadmanabhan2006
%A Anthapadmanabhan, N. Prasanth
%A Barg, Alexander
%A Dumer, Ilya
%D 2006
%K capacity fingerprinting
%T On the Fingerprinting Capacity Under the Marking Assumption
%U http://arxiv.org/abs/cs/0612073
%X 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.25 C_2,2 0.322$ and
$0.083 C_3,2 0.199$ respectively. For coalitions of an arbitrary
fixed size $t,$ we derive an upper bound $(tłn2)^-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.
@misc{Anthapadmanabhan2006,
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.25 \leq C_{2,2} \leq 0.322$ and
$0.083 \leq C_{3,2} \leq 0.199$ respectively. For coalitions of an arbitrary
fixed size $t,$ we derive an upper bound $(t\ln2)^{-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.
},
added-at = {2009-02-27T23:05:23.000+0100},
author = {Anthapadmanabhan, N. Prasanth and Barg, Alexander and Dumer, Ilya},
biburl = {https://www.bibsonomy.org/bibtex/2dcc9b724e24ac825661459f8bcfca952/ywhuang},
description = {[cs/0612073] On the Fingerprinting Capacity Under the Marking Assumption},
interhash = {01d329a01a9b70f95a393db940a804bb},
intrahash = {dcc9b724e24ac825661459f8bcfca952},
keywords = {capacity fingerprinting},
note = {cite arxiv:cs/0612073
Comment: final version, 12 pages, 2 figures, to appear in IEEE Trans. on
Inform. Theory - Special Issue on Information-theoretic Security, Jun 2008,
simplified proofs in Sections II and III, changes in Theorem 4.1},
timestamp = {2009-02-27T23:13:25.000+0100},
title = {On the Fingerprinting Capacity Under the Marking Assumption},
url = {http://arxiv.org/abs/cs/0612073},
year = 2006
}