Deletion Attacks on Database Watermarking for Tracing Partial Data Breach

In the digital era, data breaches and unauthorized data sharing pose significant security risks to organizations. A critical challenge lies in identifying the source of data leaks once they occur. Database watermarking, which embeds hidden own-ership information within datasets, has emerged as a promising solution for data leak tracing and ownership verification. While existing research has introduced various watermarking algorithms, there remains a significant gap in understanding how the size of the database influences these algorithms' effectiveness and resilience. This study specifically investigates the relationship between dataset size and watermark robustness under deletion attacks. Through comprehensive experiments across datasets ranging from 2,270 to 581,012 records, we evaluated watermark accuracy under systematic deletion attacks of up to 99% of the data. Our findings reveal that while the watermarking algorithm maintains perfect accuracy for datasets over 500,000 records even under extreme deletion attacks, its performance varies significantly with dataset size. Datasets around 145,000 records maintain high accuracy until 96% deletion, while smaller datasets of approximately 9,000 records show sharp accuracy decline after 60% deletion. These results provide crucial insights for practical watermarking implementation, establishing clear minimum dataset size requirements and highlighting the need for enhanced techniques for smaller datasets.