Watermill: An Optimized Fingerprinting System for Databases under Constraints
Authors:
- David Gross-AmblardDGDavid Gross-Amblard
- Camelia ConstantinCCCamelia Constantin
- 26 February 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 20 (4) , 532-546
Abstract
This paper presents a walermarking/fingerprinting system for relational databases. It features a built-in declarative language to specify usability constraints that watermarked data sets must comply with. For a subset of these constraints, namely, weight-independent constraints, we propose a novel watermarking strategy that consists of translating them into an integer linear program. We show two watermarking strategies: an exhaustive one based on integer linear programming constraint solving and a scalable pairing heuristic. Fingerprinting applications, for which several distinct watermarks need to be computed, benefit from the reduced computation time of our method that precomputes the watermarks only once. Moreover, we show that our method enables practical collusion-secure fingerprinting since the precomputed watermarks are based on binary alterations located at exactly the same positions. The paper includes an in-depth analysis of false-hit and false-miss occurrence probabilities for the detection algorithm. Experiments performed on our open source software WATERMILL assess the watermark robustness against common attacks and show that our method outperforms the existing ones concerning the watermark embedding speed.Keywords
This publication has 21 references indexed in Scilit:
- Watermarking Relational Databases Using Optimization-Based TechniquesIEEE Transactions on Knowledge and Data Engineering, 2007
- Rights protection for relational dataIEEE Transactions on Knowledge and Data Engineering, 2004
- Constructing a virtual primary key for fingerprinting relational data2003
- Query-preserving watermarking of relational databases and XML documents2003
- Rights protection for relational data2003
- Optimal probabilistic fingerprint codes2003
- The fingerprinted database2002
- Information Hiding Techniques for Steganography and Digital WatermakingEDPACS, 2000
- Integrity constraints for XML2000
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963