Assuring Certified Database Utility in Privacy-Preserving Database Fingerprinting

Fingerprinting techniques allow a database owner (DO) to embed unique identifiers within relational databases to trace unauthorized redistribution. To protect its interests, the DO often prioritizes maximizing fingerprint robustness, resulting in extensive modifications to the databases. However, excessive modifications may significantly degrade the databases' utility, making recipients hesitant to purchase databases that seem compromised when they cannot evaluate the maximum number of modified bits made during fingerprinting process. Current database fingerprinting techniques focus only on boosting fingerprint robustness, without providing recipients any mechanism to verify the degree of modifications. This paper, for the first time, addresses the research gap in providing recipients the ability to verify the maximum number of modified bits in database fingerprinting. We introduce a fuzzy perturbation verification (FPV) protocol, which enables a verifier to assess the extent of modifications made to a bit-string by a prover while keeping the exact modification positions and original bit-string confidential. Using the FPV protocol, we propose UtiliClear, a novel database fingerprinting scheme that allows the recipient to specify and verify the modification degree within the fingerprinted database. We theoretically validate that UtiliClear enables recipients to verify the extent of modifications during the fingerprinting process while maintaining fingerprint robustness, database utility, and data privacy. To demonstrate its effectiveness, we evaluate UtiliClear's performance using large real-world datasets. The experimental results and analysis indicate that UtiliClear incurs modest overhead while preserving fingerprint robustness and database utility comparable to existing state-of-the-art schemes.