Name
Abstract | ||
|---|---|---|
Including a unique code in each copy of a distributed document is an effective way of fighting intellectual piracy. Codes designed for this purpose that are secure against collusion attacks are called fingerprinting codes. In this paper we consider fingerprinting with the marking assumption and design codes that achieve much higher rates than previous constructions. We conjecture that these codes attain the maximum possible rate (the fingerprinting capacity) for any fixed number of pirates. We prove new upper bounds for the fingerprinting capacity that are not far from the rate of our codes. On the downside the accusation algorithm of our codes are much slower than those of earlier codes. We introduce the novel model of weak fingerprinting codes where one pirate should be caught only if the identity of all other pirates are revealed. We construct fingerprinting codes in this model with improved rates but our upper bound on the rate still applies. In fact, these improved codes achieve the fingerprinting capacity of the weak model by a recent upper bound. Using analytic techniques we compare the rates of our codes in the standard model and the rates of the optimal codes in the weak model. To our surprise these rates asymptotically agree, that is, their ratio tends to 1 as t goes to infinity. Although we cannot prove that each one of our codes in the standard model achieves the fingerprinting capacity, this proves that asymptotically they do. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.5555/1496770.1496808 | SODA |
Keywords | Field | DocType |
high rate,fingerprinting capacity,new upper bound,novel model,fingerprinting code,maximum possible rate,improved rate,higher rate,weak fingerprinting code,weak model,standard model,upper bound | Discrete mathematics,Fountain code,Computer science,Upper and lower bounds,Block code,Algorithm,Conjecture | Conference |
ISBN | Citations | PageRank |
978-0-89871-698-6 | 48 | 1.79 |
References | Authors | |
4 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ehsan Amiri | 1 | 57 | 2.73 |
| Gábor Tardos | 2 | 1261 | 140.58 |