Vector databases support machine learning tasks using Approximate Nearest Neighbour (ANN) query functionality, making them highly valuable digital assets. However, they also face security threats like unauthorized replication. By embedding stealth information, watermarking technology can be used for ownership authentication. This paper introduces a watermarking scheme specifically designed for vector databases. The scheme consists of four steps: generating identifiers, grouping, cryptographic mapping, and modification. Since watermark embedding requires modification of certain vectors, it may negatively affect the ANN query results. Further investigation reveals that in the widely used Hierarchical Navigable Small World (HNSW) indexing structure for vector databases, heuristic edge selection and pruning strategies result in some vectors having fewer edges or even none at all. These vectors exhibit significantly lower query frequencies than others, which means that modifying these vectors incurs less impact on query results. Based on this observation, we propose the Transparent Vector Priority (TVP) watermarking scheme, which prioritizes embedding the watermark in these low-query-frequency “transparent” vectors to minimize the impact of watermark embedding on query results. Experimental results show that compared to the current most effective and relevant watermarking schemes, the TVP scheme can significantly reduce the number of missed and false queries by approximately 75\%.

Database watermarking can be used for copyright verification and leakage traceability, effectively protecting the security of the database. However, the existing watermarking schemes commonly embed watermarks by modifying the original data, which changes the statistical characteristics and affects the statistical analysis of the database. Therefore, this paper proposes SCPW, aStatisticalCharacteristicsPreserving robust databaseWatermarking framework. First, we perform a theoretical analysis and propose a data modification scheme maintaining the statistical characteristics unchanged. Then, we establish the correspondence between the data and the watermarks that need to be embedded in it by grouping. Finally, the watermark message is embedded into the database through data verification and modification. Specifically, for data that needs to be watermarked, we first verify whether the potential watermark bits extracted from the data are the same as bits that need to be embedded. If they are the same, we regard this original data, usually a floating point number, as a “good number” and do not modify it. Otherwise, we modify the data until it becomes a “good number” using a data modification scheme that preserves the statistical characteristics proposed by the theoretical analysis. In addition, we also use the genetic algorithm to optimize the grouping results and increase the proportion of “good number”, thereby reducing the proportion of data that needs to be modified and further reducing distortion. To our best knowledge, SCPW is the first watermarking scheme that ensures the preservation of statistical characteristics, and the experimental results also prove its excellent ability to preserve statistical characteristics compared to existing schemes. Moreover, experiments also illustrate that our method is robust against a wide range of attacks. When under deletion attack (deletion rate = 90%), the bit error rate of watermark extraction is only 0.8%, which is more than 12% lower than the current best method.

Databases play a crucial role in storing and managing vast amounts of data in various organizations and industries. Yet the risk of database leakage poses a significant threat to data privacy and security. To trace the source of database leakage, researchers have proposed many database watermarking schemes. Among them, fake-tuples-based database watermarking shows great potential as it does not modify the original data of the database, ensuring the seamless usability of the watermarked database. However, the existing fake-tuple-based database watermarking schemes need to insert a large number of fake tuples for the embedding of each watermark bit, resulting in low watermark transparency. Therefore, we propose a novel database watermarking scheme based on fake tuples and sparse priority strategy, named SPSW, which achieves the same watermark capacity with a lower number of inserted fake tuples compared to the existing embedding strategy. Specifically, for a database about to be watermarked, we prioritize embedding the sparsest watermark sequence, i.e., the sequence containing the most ‘0’ bits among the currently available watermark sequences. For each bit in the sparse watermark sequence, when it is set to ‘1’, SPSW will embed the corresponding set of fake tuples into the database. Otherwise, no modifications will be made to the database. Through theoretical analysis, the proposed sparse priority strategy not only improves transparency but also enhances the robustness of the watermark. The comparative experimental results with other database watermarking schemes further validate the superior performance of the proposed SPSW, aligning with the theoretical analysis.