Obtaining Asymptotic Fingerprint Codes Through a New Analysis of the Boneh-Shaw Codes

  • Marcel Fernandez
  • Josep Cotrina
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4318)


A fingerprinting code is a set of codewords that are embedded in each copy of a digital object with the purpose of making each copy unique. If the fingerprinting code is c-secure with ε error, then the decoding of a pirate word created by a coalition of at most c dishonest users, will expose at least one of the guilty parties with probability 1–ε.

The Boneh-Shaw fingerprinting codes are n-secure codes with ε error, where n also denotes the number of authorized users. Unfortunately, the length the Boneh-Shaw codes should be of order O(n 3log(n/ε)), which is prohibitive for practical applications. In this paper, we prove that the Boneh-Shaw codes are (c< n)-secure for lengths of order O(nc 2log(n/ε)).

Moreover we show how to use these codes to construct binary fingerprinting codes with length L=O(c 6logc logn), with probability of error O(1/n)=exp(–Ω(L)), and identification algorithm of complexity poly(logn)=poly(L). These results improve in some aspects the best known schemes and with a much more simple construction.


Fingerprinting Intellectual Property Protection Electronic Commerce Security Information Hiding and Watermarking 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Barg, A., Blakey, G.R., Kabatiansky, G.A.: Digital fingerprinting codes: Problem statements, constructions, identification of traitors. IEEE Trans. Inform. Theory 49(4), 852–865 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Boneh, D., Shaw, J.: Collusion-secure fingerprinting for digital data. IEEE Trans. Inform. Theory 44(95), 1897–1905 (1998)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Forney, G.: Concatenated codes. MIT Press, Cambridge (1966)Google Scholar
  4. 4.
    Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon codes and algebraic geometry codes. IEEE Trans. Inform. Theory 45(6), 1757–1767 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301), 13–30 (1963)zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Tardos, G.: Optimal probabilistic fingerprint codes. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 116–125 (2003)Google Scholar
  7. 7.
    Tsfasman, M., Vlăduţ, S.: Algebraic-geometric codes. Kluwer, Dordrecht (1991)zbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Marcel Fernandez
    • 1
  • Josep Cotrina
    • 1
  1. 1.Departament of Telematics Engineering.Universitat Politècnica de CatalunyaBarcelonaSpain

Personalised recommendations