Reversible database watermarking with consistent virtual primary key synchronization

Existing reversible database watermarking schemes face watermark synchronization issues. These issues arise from inconsistencies in the virtual primary key (VPK) before and after watermark embedding. To address this issue, a synchronization-preserving reversible watermarking scheme for relational databases is proposed. Specifically, a hash function-based grouping mechanism is adopted to partition tuples, thereby improving resistance to VPK disruption caused by deletion attacks. In addition, a genetic algorithm is employed to optimize the secret key, aiming to reduce VPK duplication and improve group uniformity. Novel binary arrangement rules are further introduced to mitigate VPK redundancy. Moreover, a histogram shifting-based reversible embedding method is designed, together with a most significant bit preservation strategy, to ensure VPK consistency before and after watermark embedding. Experimental evaluations on a benchmark database containing 581,012 tuples demonstrate that the proposed scheme improves the VPK consistency rate from 91% to 100%, thereby eliminating synchronization issues caused by reversible embedding. In addition, the proposed method reduces VPK duplication by approximately 10% compared with state-of-the-art approaches, while achieving lower distortion and stronger robustness. Furthermore, it achieves a 0% bit error rate (BER) under insertion attacks, and maintains BERs below 40% even under 90% deletion or modification attacks.