Constructing a virtual primary key for fingerprinting relational data

ABSTRACT

Agrawal and Kiernan's watermarking technique for database relations [1] and Li et al's fingerprinting extension [6] both depend critically on primary key attributes. Hence, those techniques cannot embed marks in database relations without primary key attributes. Further, the techniques are vulnerable to simple attacks that alter or delete the primary key attribute.This paper proposes a new fingerprinting scheme that does not depend on a primary key attribute. The scheme constructs virtual primary keys from the most significant bits of some of each tuple's attributes. The actual attributes that are used to construct then virtual primary key differ from tuple to tuple. Attribute selection is based on a secret key that is known to the merchant only. Further, the selection does not depend on an apriori ordering over the attributes, or on knowledge of the original relation or fingerprint codeword.The virtual primary keys are then used in fingerprinting as in previous work [6]. Rigorous analysis shows that, with high probability, only embedded fingerprints can be detected and embedded fingerprints cannot be modified or erased by a variety of attacks. Attacks include adding, deleting, shuffling, or modifying tuples or attributes (including a primary key attribute if one exists), guessing secret keys, and colluding with other recipients of a relation.

REFERENCES

• 1: R. Agrawal and J. Kiernan. Watermarking relational databases. In Proceedings of VLDB, 2002.
• 2: D. Boneh and J. Shaw. Collusion secure fingerprinting for digital data. IEEE Transactions on Information Theory, 44(5):1897--1905, 1998.
• 3: S. Craver, N. Memon, B.-L. Yeo, and M. M. Yeung. Resolving rightful ownerships with invisible watermarking techniques: Limitations, attacks and implications. IEEE Journal on Selected Areas of Communications, 16(4):573--586, May 1998.
• 4: David Gross-Amblard, Query-preserving watermarking of relational databases and XML documents, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.191-201, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773172]
• 5: Hans-Jürgen Guth , Birgit Pfitzmann, Error- and Collusion-Secure Fingerprinting for Digital Data, Proceedings of the Third International Workshop on Information Hiding, p.134-145, September 29-October 01, 1999
• 6: Y. Li, V. Swarup, and S. Jajodia. Fingerprinting relational databases. Technical report, Center for Secure Information Systems, George Mason University, Fairfax, VA, May 2003.
• 7: Birgit Pfitzmann , Michael Waidner, Asymmetric fingerprinting for larger collusions, Proceedings of the 4th ACM conference on Computer and communications security, p.151-160, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266453]
• 8: Radu Sion , Mikhail Atallah , Sunil Prabhakar, Rights protection for relational data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872772]
• 9: Nicholas Tran, Hiding Functions and Computational Security of Image Watermarking Systems, Proceedings of the 15th IEEE Computer Security Foundations Workshop (CSFW'02), p.295, June 24-26, 2002

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Performance, Security

Keywords:
fingerprinting, primary keys, relational databases, robustness