Gábor Tardos
Abstract
We construct binary codes for fingerprinting digital documents. Our codes for n users that are ϵ-secure against c pirates have length O(c2log(n/ϵ)). This improves the codes proposed by Boneh and Shaw [1998] whose length is approximately the square of this length. The improvement carries over to works using the Boneh--Shaw code as a primitive, for example, to the dynamic traitor tracing scheme of Tassa [2005].
By proving matching lower bounds we establish that the length of our codes is best within a constant factor for reasonable error probabilities. This lower bound generalizes the bound found independently by Peikert et al. [2003] that applies to a limited class of codes. Our results also imply that randomized fingerprint codes over a binary alphabet are as powerful as over an arbitrary alphabet and the equal strength of two distinct models for fingerprinting.
- Anthapadmanabhan, N. P., Barg, A., and Dumer, I. 2008. On the fingerprinting capacity under the marking assumption. IEEE Trans. Inf. Theory 54 (Feb.). Google Scholar
Digital Library
- Blakley, G. R., Meadows, C., and Purdy, G. B. 1985. Fingerprinting long forgiving messages. In Proceedings of Crypto '85. Springer-Verlag Berlin, Heidelberg, Germany, 180--189. Google ScholarDigital Library
- Boneh, D., and Franklin, M. 1999. An efficient public key traitor tracing scheme. In Proceedings of Crypto '99. Springer-Verlag, Berlin, Heidelberg, Germany, 338--353. Google ScholarDigital Library
- Boneh, D., and Shaw, J. 1998. Collusion-secure fingerprinting for digital data. IEEE Trans. Inf. Theory 44, 480--491. Google ScholarDigital Library
- Chor, B., Fiat, A., and Naor, M. 1994. Tracing traitors. In Proceedings of Crypto '94. Lecture Notes in Computer Science, vol. 839. Springer-Verlag, Berlin, Heidelberg, Germany, 257--270. Google ScholarDigital Library
- Chung, F., Graham, R., and Leighton, T. 2001. Guessing secrets. Electron. J. Combinat. 8.Google Scholar
- Fiat, A., and Tassa, T. 2001. Dynamic traitor tracing. J. Crypt. 14, 3, 211--223.Google ScholarDigital Library
- Guth, J., and Pfitzmann, B. 2000. Error- and collusion-secure fingerprinting for digital data. In Proceedings of the Symposium on Information Hiding '99. Springer-Verlag, Berlin, 134--145. LNCS 1768. Google ScholarDigital Library
- Kilian, J., Leighton, T., Matheson, L., Shamoon, T., Tarjan, R., and Zane, F. 1998. Resistance of digital watermarks to collusive attacks. In Proceedings of the IEEE International Symposium on Information Theory. IEEE Computer Society Press, Los Alamitos, CA, 71.Google Scholar
- Kurosawa, K., and Desmedt, Y. 1998. Optimum traitor tracing and asymmetric schemes. In Advances in Cryptology—EUROCRYPT'98. Lecture Notes in Computer Science, vol. 1403. Springer, Berlin, Germany, 145--157.Google Scholar
- Lindkvist, T. 1999. Fingerprinting digital documents. Ph.D. dissertation. Linköping Studies in Science and Technology. Thesis No. 798.Google Scholar
- Peikert, C., Shelat, A., and Smith, A. 2003. Lower bounds for collusion-secure fingerprinting. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 472--479. Google ScholarDigital Library
- Rényi, A. 1970. Probability theory. North-Holland Series in Applied Mathematics and Mechanics, vol. 10. North-Holland Publishing Co., Amsterdam, London; American Elsevier Publishing Co., Inc., New York.Google Scholar
- Safavi-Naini, R., and Wang, Y. 2000. Sequential traitor tracing. In Proceedings of Crypto '2000. Lecture Notes in Computer Science, vol. 1880. Springer-Verlag Berlin, Heidelberg, Germany, 316--332. Google ScholarDigital Library
- Staddon, J. N., Stinson, D. R., and Wei, R. 2001. Combinatorial properties of frameproof and traceability codes. IEEE Trans. Inf. Theory 47, 1042--1049. Google ScholarDigital Library
- Tardos, G. 2003. Optimal probabilistic fingerprint codes. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 116--125. Google ScholarDigital Library
- Tassa, T. 2005. Low bandwidth dynamic traitor tracing schemes. J. Crypt. 18, 167--183. Google ScholarDigital Library
- Wagner, N. 1983. Fingerprinting. In Proceedings of the 1983 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, Los Alamitos, CA, 18--22. Google ScholarDigital Library
- Yacobi, Y. 2001. Improved Boneh--Shaw content fingerprinting. In Topics in Cryptology—CT-RSA 2001. Lecture Notes in Computer Science, vol. 2020. Springer-Verlag Berlin, Germany, 378--391. Google ScholarDigital Library
Index Terms
- Optimal probabilistic fingerprint codes
Recommendations
Optimal probabilistic fingerprint codes
STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computingWe construct binary codes for fingerprinting. Our codes for n users that are ε-secure against c pirates have length O(c2 log(n/ε)). This improves the codes proposed by Boneh and Shaw [3] whose length is approximately the square of this length. Our codes ...
Probabilistic Existence Results for Separable Codes
Separable codes were defined by Cheng and Miao in 2011, motivated by applications to the identification of pirates in a multimedia setting. Combinatorially, t̅-separable codes lie somewhere between t-frameproof and (t - 1)-frameproof codes: all t-...
A general conversion method of fingerprint codes to (more) robust fingerprint codes against bit erasure
ICITS'09: Proceedings of the 4th international conference on Information theoretic securityA c-secure fingerprint code is called robust if it is secure against a limited number of bit erasure in undetectable positions in addition to usual collusion attacks. In this article, we propose the first general conversion method of (non-robust) c-...
Reviews
J Wolper
A fingerprint is a serial number embedded in a digital entity that enables tracing the source of a pirated version. A historical example is the introduction of small errors in low-order digits of tables of logarithms [1]. Pirates with multiple copies can identify where differences occur and, thus, alter part of the serial number. More pirates can alter the serial number even more, but information about the original serial numbers remains. This paper improves on previous results [1] that used a random matrix, by a clever choice of probability distribution of the bits in the matrix of serial numbers. The statistics of the distribution allow for a detailed analysis of the probability of accusing a pirate, which is high, and of the probability of accusing an innocent user, which is low. An accusation of piracy occurs when a score exceeds a certain threshold. The score is increased substantially when a bit is inconsistent with the distribution, and decreased when the bit is consistent. In other words, if 0 is expected but 1 is seen, add a lot to the score; if 0 is both expected and seen, subtract a little. Such results are seldom seen in the fingerprinting literature. In this paper, the codes constructed are shorter than those of Boneh and Shaw [1]. The probabilistic analysis is much more detailed and sophisticated than what is typically found in a computer science journal. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments