#  DREW: Towards Robust Data Provenance by Leveraging Error-Controlled
Watermarking

Mehrdad Saberi1, Vinu Sankar Sadasivan1, Arman Zarei1, Hessam Mahdavifar2,
Soheil Feizi1
1 University of Maryland 2 Northeastern University

###### Abstract

Identifying the origin of data is crucial for data provenance, with
applications including data ownership protection, media forensics, and
detecting AI-generated content. A standard approach involves embedding-based
retrieval techniques that match query data with entries in a reference
dataset. However, this method is not robust against benign and malicious
edits. To address this, we propose Data Retrieval with Error-corrected codes
and Watermarking (DREW). DREW randomly clusters the reference dataset, injects
unique error-controlled watermark keys into each cluster, and uses these keys
at query time to identify the appropriate cluster for a given sample. After
locating the relevant cluster, embedding vector similarity retrieval is
performed within the cluster to find the most accurate matches. The
integration of error control codes (ECC) ensures reliable cluster assignments,
enabling the method to perform retrieval on the entire dataset in case the ECC
algorithm cannot detect the correct cluster with high confidence. This makes
DREW maintain baseline performance, while also providing opportunities for
performance improvements due to the increased likelihood of correctly matching
queries to their origin when performing retrieval on a smaller subset of the
dataset. Depending on the watermark technique used, DREW can provide
substantial improvements in retrieval accuracy (up to 40% for some datasets
and modification types) across multiple datasets and state-of-the-art
embedding models (e.g., DinoV2, CLIP), making our method a promising solution
for secure and reliable source identification. The code is available at
https://github.com/mehrdadsaberi/DREW.

##  1 Introduction

In the era of big data, the ability to accurately trace the provenance of data
is critical for ensuring the integrity, reliability, and accountability of
information (Simmhan et al., 2005; Buneman et al., 2001). Data provenance, the
documentation of the origins and the life-cycle of data, is essential for
various applications, including the detection of AI-generated content and
deepfakes, legal compliance, data ownership protection, and copyright
protection. Some current approaches to data provenance often rely on metadata
or external logs (Coalition for Content Provenance and Authenticity, 2023),
which can be easily tampered with or lost. To overcome these limitations, this
paper introduces a novel approach that leverages error-controlled watermarking
and retrieval techniques to address source identification in data provenance.

Watermarking is a powerful technique for embedding information directly within
data, enabling tracking of data origins (Honsinger, 2002; Swanson et al.,
1998). However, recent studies (Saberi et al., 2024; Zhang et al., 2023;
Rabbani et al., 2024; Sadasivan et al., 2024) have revealed significant
limitations in watermark robustness against data augmentations. These studies
show that watermarks often fail to preserve information when subjected to
modifications such as cropping, blurring, diffusion purification (Saberi et
al., 2024; Nie et al., 2022), and adversarial attacks (Chakraborty et al.,
2018).

To mitigate information loss, some approaches (Tancik et al., 2020; Bui et
al., 2023) use error correction codes (Hamming, 1950) like BCH codes (Bose &
Ray-Chaudhuri, 1960) to recover lost information during transformations.
However, the volume of information that can be reliably embedded as a
watermark is limited (e.g., $100$-$200$ bits), restricting the inclusion of
sufficient redundant bits for effective error correction. Consequently,
existing watermarking methods are not suitable for source identification in
large-scale scenarios. As a toy example, to handle billion-scale datasets,
more than $2^{3}0$ unique watermark keys are required, and with $100$-bit
watermarks injected into the data, ECC algorithms cannot provide a highly
robust coding.

Embedding-based retrieval techniques (Chen et al., 2023) use data embedding
similarities for provenance. These methods map data into a low-dimensional
space where similar items are closer, allowing query embeddings to be compared
against a database to find matches. These techniques have been effectively
used in image retrieval (Radford et al., 2021; Oquab et al., 2024) and natural
language processing (Devlin et al., 2019; Raffel et al., 2023; Brown et al.,
2020) to infer data origins.

While embedding-based retrieval is robust against certain transformations,
challenges arise as the reference database grows (see Figure 3) or when
encountering challenging data alterations. These factors can impact retrieval
accuracy, necessitating advancements in embedding techniques for enhanced
performance and reliability. Additionally, embedding models, like other deep
learning models, often struggle with generalization to out-of-distribution or
under-represented data.

Figure 1: Overview of DREW. (Top) During the pre-processing phase, $2^{k}$
clusters are created, each associated with a unique watermark key produced by
the ECC encoder module. Instances from the dataset are randomly allocated to
these clusters, and the corresponding watermark keys are injected into them.
(Bottom) Upon receiving a query sample, the watermark decoder extracts the
injected key, and the embedding model computes an embedding vector for the
query. The ECC decoder processes this extracted key to identify the cluster
code associated with the query. If the ECC reliability module confirms the
reliability of the decoded cluster code, an embedding-based retrieval is
conducted within the corresponding cluster. If the reliability is not ensured,
the retrieval is performed across the entire dataset.
Figure 2: Source identification accuracy of DREW (with Trustmark used as the
watermarking technique) vs naive embedding-based retrieval using DinoV2
embeddings, against different types of augmentations.

This paper introduces a novel approach, DREW (Data Retrieval with Error-
corrected codes and Watermarking), that integrates watermarks, error control
codes, and embedding-based retrieval to address the challenge of source
identification. The proposed framework effectively mitigates the limitations
of watermark capacity (i.e., the constraints on the number of bits that can be
stored within content), and the scalability issues inherent in data retrieval
methods (i.e., the decreasing accuracy of retrieval in larger reference
databases). By leveraging the complementary strengths of watermarking and
retrieval techniques, DREW presents a more robust alternative for source
identification.

In DREW, data from the reference dataset is randomly clustered, with each
cluster assigned a unique $k$-bit binary cluster code. To enhance robustness,
we use an ECC encoder to add redundancy to these codes, resulting in new
$n$-bit keys for each cluster. These keys are then injected into the data
samples from the corresponding cluster using a watermark injector. The
watermarked samples, which can be any type of media and content such as
outputs of generative models, images posted on social media platforms, or
legal documents, are subsequently published to general users. If a watermarked
sample from our reference dataset is modified, we can reverse the process to
identify the corresponding cluster and perform embedding-based data retrieval
within that cluster. Additionally, the ECC module provides a reliability flag,
enabling us to perform retrieval on the entire reference dataset if the
retrieved cluster code is deemed unreliable due to excessive data
modification.

DREW offers several key advantages:

  * •

Robust Watermark Utilization: By using $k$-bit cluster codes and encoding them
using ECC to create $n$-bit watermark keys, we can adjust $k$ as a
hyperparameter to control the ECC decoder’s robustness. This flexibility is
crucial because using unique $n$-bit watermark keys for each data instance in
a large-scale dataset would make robust decoding impractical.

  * •

Improved Retrieval Accuracy: Conducting data retrieval on smaller clusters
enhances accuracy, addressing challenges associated with purely embedding-
based retrieval.

  * •

Reliability of ECC Algorithms: Our method might underperform compared to
purely embedding-based retrieval only if the ECC algorithm returns an
incorrect cluster code and falsely marks it as reliable. However, modern ECC
algorithms have near-optimal coding efficiency with very low false positive
rates, ensuring that our method maintains performance on par with the
baseline.

The following sections provide a detailed formal description of our method,
along with theoretical insights and empirical analysis on the impact of the
different modules utilized in our framework. Furthermore, we conduct
comprehensive experiments to demonstrate the effectiveness of our approach
compared to the baseline of performing embedding-based retrieval on the entire
dataset. While our framework is applicable to various data types, we focus our
experiments on the image domain.

As shown in Figure 2, in practice, DREW provides significant robustness,
especially on more challenging datasets where naive embedding-based retrieval
methods struggle. In Section 4, we show that while DREW shows substantial
performance gains against some augmentations, it does not cause performance
degradation against any modification types, when compared to the baseline.

Below, we list the main contributions of this paper:

  * •

We propose DREW, a novel framework for source identification, by combining
error correction codes (ECC), watermarking techniques, and embedding-based
data retrieval. Our framework addresses the limitations of using watermarks or
data retrieval independently, providing a robust and scalable solution by
combining their strengths.

  * •

We provide theoretical insights into the effectiveness of our framework,
followed by empirical results supporting our claims.

  * •

We conduct extensive experiments on multiple image datasets, showcasing the
improved robustness of our method compared to the baseline of embedding-based
data retrieval using state-of-the-art embedding models (e.g., DinoV2 (Oquab et
al., 2024), CLIP/ViT-L-14 (Radford et al., 2021)).

##  2 Background

Watermarking Techniques. Watermarking involves embedding information within
content so that it can be reliably decoded later, even after the content has
been modified. This technique has been applied to various types of media,
including images (Wan et al., 2022), text (Kirchenbauer et al., 2024), and
audio (Hua et al., 2016). Recent advancements in watermarking methods utilize
deep learning models for encoding and decoding, leading to improved robustness
in the face of several types of content modifications (Bui et al., 2023;
Tancik et al., 2020; Wen et al., 2023; Kirchenbauer et al., 2024). However,
numerous studies have highlighted the limitations and unreliability of these
watermarks when subjected to certain data augmentations and transformations
(Saberi et al., 2024; Sadasivan et al., 2024; Zhang et al., 2023; Rabbani et
al., 2024). As a result, relying solely on watermarking as a solution can be
challenging in many scenarios.

Error Control Codes. Error control codes (ECC) (Hamming, 1950) are fundamental
in ensuring the reliable transmission and storage of data across noisy
channels. These codes detect and correct errors without needing re-
transmission, enhancing data integrity and communication efficiency. Notable
ECCs include Reed-Solomon codes (Reed & Solomon, 1960), known for robust error
correction in digital communications and storage like CDs and DVDs. LDPC codes
(Gallager, 1962) have transformed ECC with near-capacity performance, crucial
in modern systems like 5G and satellite communications. BCH codes (Bose & Ray-
Chaudhuri, 1960), introduced in the 1950s, are versatile for error detection
and correction in applications from QR codes to digital broadcasting. Polar
codes (Arikan, 2009), a recent advancement, achieve channel capacity with low-
complexity decoding, essential for 5G technology. These advancements highlight
ECC’s evolution, driven by the need for high reliability and efficiency in
complex communication networks.

Data Retrieval. Data retrieval techniques refer to the methods and algorithms
used to efficiently search, access, and retrieve relevant information from
large data repositories or databases (Chen et al., 2023). Recent advancements
include embedding-based retrieval systems, which utilize deep learning models
to transform data into feature vectors, enabling accurate and context-aware
searches. Approximate Nearest Neighbors (ANN) (Arya et al., 1998; Simhadri et
al., 2022) is a notable technique in this field, facilitating rapid similarity
searches by approximating the nearest neighbor search in large datasets. Data
retrieval techniques are especially useful in applications such as
recommendation systems (Naumov et al., 2019), retrieval augmented generation
(Lewis et al., 2021), near-duplicate detection (Song et al., 2013), and
anomaly detection (Cohen & Hoshen, 2021).

Watermarking for Data Retrieval. Some existing works have explored the use of
watermarks in retrieval-based tasks in various ways. Certain studies (Roy et
al., 2005; Roy & Chang, 2004) propose manually shifting data (similar to
watermarking) to enhance the mutual separation of samples in feature space,
thereby improving the robustness of feature-based data retrieval. However,
these methods do not leverage recent advancements in watermarking or efficient
retrieval techniques, rendering them impractical compared to contemporary
approaches. Additionally, other works (J. & R., 2022; Lafta & Abdulsada, 2022)
have utilized watermarks in image retrieval systems for user identification
and to prevent illegal data distribution. Nonetheless, these approaches fail
to address the low robustness of watermarks when used alone and without error
correction modules, making them unreliable in practical applications.

##  3 DREW: Data Retrieval with Error-Corrected Codes and Watermarking

In the following sections, we formally define the problem and present our
approach. We note that the framework in this section is not dependent on the
type of data and can be potentially applied to data types such as images,
text, audio, etc. However, our experiments in Section 4 are performed in the
image domain.

Algorithm 1 Preprocessing for DREW

1:$X$: dataset, $k$: bit length of cluster codes, $\mathcal{C}_{E}$: error
control encoder, $\mathcal{W}_{I}$: watermark injector, $\phi$: embedding
model

2:Randomly partition $X$ into $2^{k}$ clusters $X_{0},...,X_{2^{k}-1}$

3:$\forall_{i=0}^{2^{k}-1}\ c[i]\ \leftarrow\ $ $k$-bit binary representation
of number $i$ /* Set cluster codes */

4:for $i$ : $0\rightarrow 2^{k}-1$ do

5: $w\ \leftarrow\ \mathcal{C}_{E}$($c[i]$)

6: for $x$ in $X_{i}$ do

7: $x^{\prime}\ \leftarrow\ \mathcal{W}_{I}(x,w)$

8: replace $x$ with $x^{\prime}$ in $X$

9: Store $\phi(x)$ for query phase

10: end for

11:end for

12:return $X=\bigcup\limits_{i=0}^{2^{k}-1}X_{i},\ \phi(X)$ /* return
watermarked clusters and data embeddings */

###  3.1 Problem Definition

Consider a dataset $X=\\{x_{0},x_{1},...,x_{N-1}\\}$ containing images or
other types of data. New instances, denoted by $z\in\mathbb{R}^{D}$, may be
added to this dataset. The primary objective is to detect whether $z$ is
either an exact duplicate or a modified version of any data currently existing
within $X$. The allowed modifications are a set of alterations that do not
change the semantics of the data, and the modified data is considered a copy
of the original data based on human judgment. In the case where a matching
data sample is found, the method is required to identify and report this
instance. Conversely, the method should also report if no such match exists.
For some applications, we might want to proceed to add $z$ to the dataset
after finding no matching sample for it. Typically, this problem is addressed
through the application of data retrieval techniques.

###  3.2 Preliminaries

The data modification function (i.e., attack function) is shown as
$\mathcal{A}:\mathbb{R}^{D}\rightarrow\mathbb{R}^{D}$, which can be performed
on $x_{i}\in X$ to create a query $z=\mathcal{A}(x_{i})$. A method
$\mathcal{M}:\mathbb{R}^{D}\rightarrow\mathbb{R}^{D}$ that addresses the
problem, receives a query sample $z$, and outputs a matching data instance
from $X$. Note that for simplicity of the analysis in this section, we assume
that methods always output a match for all the queries. Further analysis of
scenarios where queries do not necessarily have a corresponding match in the
dataset is provided in Appendix A.

Embedding Model. We utilize a data embedding model
$\phi:\mathbb{R}^{D}\rightarrow\mathbb{R}^{d}$, to create a normalized low-
dimensional embedding of the data. This embedding is used to measure the
similarity between two data samples $z_{1}$ and $z_{2}$, by calculating the
dot product between their embeddings (i.e., $\phi(z_{1})^{\top}\phi(z_{2})$).

Watermarking Module. The watermarking module consists of two models. The
watermark injector
$\mathcal{W}_{I}:\mathbb{R}^{D}\times\\{0,1\\}^{n}\rightarrow\mathbb{R}^{D}$
receives a data sample and a $n$-bit binary key, and outputs a data sample
which contains the key embedded inside of it. The watermark decoder
$\mathcal{W}_{D}:\mathbb{R}^{D}\rightarrow\\{0,1\\}^{n}$ receives a data
sample and retrieves the watermark key that is embedded in it.

Error Control Module. The error control module (Shannon, 1948; Hamming, 1950)
consists of multiple modules. There is an encoder
$\mathcal{C}_{E}:\\{0,1\\}^{k}\rightarrow\\{0,1\\}^{n}$ that receives a
$k$-bit binary code and outputs an $n$-bit binary code. This $n$-bit binary
code can be passed through a noisy channel (i.e., a channel that can alter the
bits), which for our case, we consider a channel that performs randomized flip
operation on the bits (i.e., changes some $0$ bits to $1$, and vice versa).

The decoder module $\mathcal{C}_{D}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{k}$
receives the $n$-bit binary code, after it has been passed through the
channel, and outputs the initial $k$-bit code from which the $n$-bit code was
created.

The last module is reliability check module
$\mathcal{C}_{R}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ that receives an $n$-bit
binary code, and outputs a reliability flag that determines whether
$\mathcal{C}_{D}$ can confidently decode this input, or if the noise that was
applied to the $n$-bit code in the channel was more than the decoder’s
capacity of correction (a value of $1$ represents a reliable output).

###  3.3 Methodology: DREW

Algorithm 2 Querying with DREW

1:$z$: query sample, $X$: watermarked dataset, $\mathcal{W}_{D}$: watermark
decoder, $\mathcal{C}_{D}$: error control decoder, $\mathcal{C}_{R}$: error
control reliability module, $\phi$: embedding model, $\tau_{r}$: retrieval
threshold

2:$w\ \leftarrow\ \mathcal{W}_{D}(z)$

3:$c\leftarrow\ \mathcal{C}_{D}(w)$

4:$r\leftarrow\ \mathcal{C}_{R}(w)$

5:if $r$ then /* if the output of error control decoder is reliable */

6: $S(z)\leftarrow X_{c}$

7:else

8: $S(z)\leftarrow X$

9:end if

10:$x^{*}\leftarrow\mathop{\arg\max}_{x\in S(z)}\phi(x)^{\top}\phi(z)$

11:if $\phi(x^{*})^{\top}\phi(z)<\tau_{r}$ then /* if similarity is low, no
match has been found */

12: return -1

13:end if

14:return $x^{*}$ /* if similarity is higher than threshold, return the match
*/

Preprocess. We randomly partition the data from $X$ into $2^{k}$ clusters and
assign a unique binary code with length $k$ to each cluster (i.e., cluster
codes). Next, we use the encoder model $\mathcal{C}_{E}$ of an error control
module to create an $n$-bit binary key for each cluster (i.e., cluster
watermark keys). These $n$-bit binary keys are injected as watermarks into the
data samples in each cluster (using the watermark injector model
$\mathcal{W}_{I}$). The watermarked dataset replaces the original dataset
(i.e., $X$ now contains watermarked data). Algorithm 1 shows the pseudocode
for DREW’s pre-processing.

Query. When a query sample $z$ (which could be a modified version of an
existing data sample in $X$), we use the watermark decoding model
$\mathcal{W}_{D}$, which gives us an $n$-bit binary watermark key as output
(i.e., $w=\mathcal{W}_{D}(z)$). Next, we use the error control decoder
$\mathcal{C}_{D}$ to retrieve the $k$-bit cluster code that corresponds to the
cluster in which the non-altered version of $z$ belongs (i.e.,
$c=\mathcal{C}_{D}(w)$). If $\mathcal{C}_{R}$ flags the output of decoder as
unreliable (i.e., $\mathcal{C}_{R}(w)=0$), we do not rely on the decoded
cluster code and set our search space $S(z)$ to be equal to $X$ (i.e., the
dataset which includes watermarked samples after the pre-processing phase).
Otherwise, if the decoded cluster code was reliable, we set the search space
$S(z)$ to only include samples from the cluster with the corresponding cluster
code.

Next, we utilize the embedding model $\phi$ to find the data sample in $S(z)$
with the highest similarity to $z$. Since the embedding-based data retrieval
is potentially being performed on a small subset of $X$, it is expected to
observe improvements in both accuracy and speed, compared to performing naive
data retrieval on all of $X$. The pseudocode for the query procedure of the
method is shown in Algorithm 2.

###  3.4 Performance Analysis

We consider $\mathcal{M}_{wm}$ to be our proposed method DREW (refer to
Section 3.3), and $\mathcal{M}_{\phi}$ to be the baseline method of performing
embedding similarity check on the entire dataset.

For the analysis in this section, we focus on queries that have a ground truth
match in the dataset. We will compare the accuracy of detecting the correct
match between $\mathcal{M}_{wm}$ and $\mathcal{M}_{\phi}$ for $z$, where
$z=\mathcal{A}(x_{i})$ and $x_{i}\in X$. We assume that the prediction of
$\mathcal{C}_{D}$ for the cluster code is
$c=\mathcal{C}_{D}(\mathcal{W}_{D}(z))$, and the reliability flag outputted by
$\mathcal{C}_{R}$ is $r=\mathcal{C}_{R}(\mathcal{W}_{D}(z))$. Additionally,
the correct cluster that includes $x_{i}$ is $c_{gt}$ (i.e., $x_{i}\in
X_{c_{gt}}$). Now, if $r=1$, the output of $\mathcal{M}_{wm}$ is
$x^{*}=argmax_{x\in X_{c_{gt}}}\phi(x)^{\top}\phi(z)$. The outputs of
$\mathcal{M}_{\phi}$, or $\mathcal{M}_{wm}$ when $r=0$, are
$\bar{x}^{*}=argmax_{x\in X}\phi(x)^{\top}\phi(z)$.

###### Definition 1

We define $\epsilon_{r}$ to be the error of the error control decoder
$\mathcal{C}_{D}$ in outputting the correct $k$-bit cluster code, in cases
where $\mathcal{C}_{R}$ has an output of $1$. Formally,

$\epsilon_{r}=\mathbb{P}(c\neq c_{gt}|r=1).$

Based on Definition 1, the false positive rate of $\mathcal{C}_{R}$ is
$\epsilon_{r}$. In Figure 4, we show that with the correct setting,
$\epsilon_{r}$ has a small and insignificant value.

For a method $\mathcal{M}$, an attack $\mathcal{A}$, and a dataset $X$, we
define the error in identifying the correct match as
$E(\mathcal{M},\mathcal{A},X)$. We can analyze the difference in error of
$\mathcal{M}_{wm}$ and $\mathcal{M}_{\phi}$ as follows:

$\begin{split}E(\mathcal{M}_{\phi},\mathcal{A},X)&-E(\mathcal{M}_{wm},\mathcal{A},X)\\\
&=\mathbb{P}(x^{*}=x_{i},\bar{x}^{*}\neq x_{i},r=1,c=c_{gt})-\mathbb{P}(c\neq
c_{gt},r=1)\\\ &\geq\mathbb{P}(r=1,c=c_{gt}|x^{*}=x_{i},\bar{x}^{*}\neq
x_{i})\mathbb{P}(x^{*}=x_{i},\bar{x}^{*}\neq x_{i})-\epsilon_{r}\end{split}$
(1)

The term $\mathbb{P}(r=1,c=c_{gt}|x^{=}x_{i},\bar{x}^{\neq}x_{i})$ reflects
the robustness of the watermark and ECC in producing the correct output
against an attack, compared to the robustness of the embeddings against the
same attack. Meanwhile, $\mathbb{P}(x^{=}x_{i},\bar{x}^{\neq}x_{i})$ indicates
the improvement from reducing the dataset samples needed for embedding-based
retrieval. In the following lemma, we measure
$\mathbb{P}(x^{=}x_{i},\bar{x}^{\neq}x_{i})$ under certain assumptions on
embedding-based retrieval:

###### Lemma 1

Assume that the top-1 accuracy of the embedding-based retrieval on dataset $X$
with size $N$, is $\alpha$ (i.e., $\mathbb{P}(\bar{x}^{*}=x_{i})=\alpha$), and
its top-$p$ accuracy is $\alpha_{p}$. Then,

$\mathbb{P}(x^{*}=x_{i},\bar{x}^{*}\neq x_{i})\geq\mathop{max}_{p\geq
2}[(\alpha_{p}-\alpha)(1-\frac{1}{2^{k}})^{p-1}].$

Based on Lemma 1, our method archives the highest accuracy boost in cases
where there is a significant gap between the top-1 and top-$p$ accuracy of the
embedding-based retrieval for some value of $p$ that is not too large. While
$\alpha_{p}-\alpha$ increases for larger values of $p$, the term
$(1-\frac{1}{2^{k}})^{p-1}$ prevents $p$ from having large values, introducing
a trade-off.

In Figure 4 and Figure 3, we provide empirical analysis on terms from Equation
1. According to Figure 4, $\epsilon_{r}$ has an insubstantial value on
practice, and does not limit the performance improvement of DREW. Furthermore,
Figure 3 demonstrates that the term $\mathbb{P}(x^{*}=x_{i},\bar{x}^{*}\neq
x_{i})$ has a noticeable value for suitable values of $k$. Therefore, we can
conclude that the bottleneck of DREW is the term
$\mathbb{P}(r=1,c=c_{gt}|x^{*}=x_{i},\bar{x}^{*}\neq x_{i})$, which
corresponds to the relative robustness of the watermarking technique used,
compared to the robustness of the embeddings. This implies that by designing
more robust watermarks, we can further increase the performance gap between
DREW and traditional embedding-based retrieval.

In the appendix, we provide further analysis on the robustness of the ECC
module (Appendix B), the robustness of DREW against adversarial attacks
(Appendix C), and the performance of DREW in the presence of out-of-dataset
queries (Appendix A).

Dataset Method No Aug Rot 1.0 Rot 0.5 Rot 0.25 Crop 0.5 Crop 0.25 Flip Str 1.0
Str 0.5 Art Images DREW (Trustmark + Dino) 0.993 0.697 0.796 0.861 0.991 0.993
0.993 0.784 0.993 DREW (Trustmark + CLIP) 0.993 0.667 0.780 0.837 0.992 0.993
0.993 0.732 0.993 Naive IR (Dino) 0.990 0.693 0.783 0.834 0.752 0.836 0.892
0.785 0.841 Naive IR (CLIP) 0.990 0.659 0.759 0.795 0.771 0.806 0.856 0.732
0.801 WikiArt DREW (Trustmark + Dino) 1.000 0.699 0.907 0.976 0.998 1.000
1.000 0.911 0.999 DREW (Trustmark + CLIP) 1.000 0.706 0.873 0.947 0.998 1.000
1.000 0.853 1.000 Naive IR (Dino) 1.000 0.698 0.907 0.971 0.974 0.985 0.995
0.911 0.985 Naive IR (CLIP) 1.000 0.706 0.870 0.940 0.949 0.975 0.992 0.853
0.980 ImageNet DREW (Trustmark + Dino) 1.000 0.875 0.975 0.992 1.000 1.000
1.000 0.946 1.000 DREW (Trustmark + CLIP) 1.000 0.698 0.841 0.934 0.995 0.999
1.000 0.840 0.999 Naive IR (Dino) 1.000 0.875 0.976 0.991 0.983 0.997 0.999
0.946 0.996 Naive IR (CLIP) 1.000 0.697 0.836 0.926 0.894 0.929 0.993 0.840
0.980 Str 0.25 Blur Comb 0.5 Comb 0.25 Jitter Diff 0.2 Diff 0.15 Diff 0.1 Art
Images DREW (Trustmark + Dino) 0.993 0.993 0.750 0.841 0.975 0.765 0.790 0.813
DREW (Trustmark + CLIP) 0.993 0.993 0.672 0.799 0.954 0.705 0.764 0.806 Naive
IR (Dino) 0.846 0.912 0.723 0.799 0.876 0.765 0.790 0.813 Naive IR (CLIP)
0.818 0.847 0.638 0.746 0.770 0.705 0.764 0.806 WikiArt DREW (Trustmark +
Dino) 1.000 0.999 0.816 0.948 0.973 0.806 0.904 0.955 DREW (Trustmark + CLIP)
1.000 0.999 0.696 0.908 0.932 0.660 0.816 0.924 Naive IR (Dino) 0.989 0.995
0.811 0.945 0.964 0.806 0.904 0.955 Naive IR (CLIP) 0.988 0.977 0.692 0.905
0.862 0.660 0.816 0.924 ImageNet DREW (Trustmark + Dino) 1.000 1.000 0.932
0.983 0.986 0.972 0.986 0.994 DREW (Trustmark + CLIP) 1.000 0.999 0.660 0.875
0.943 0.859 0.907 0.968 Naive IR (Dino) 1.000 0.999 0.931 0.983 0.984 0.972
0.986 0.994 Naive IR (CLIP) 0.992 0.974 0.648 0.858 0.852 0.859 0.907 0.968

Table 1: Comparison between the robustness of DREW and naive IR, with DinoV2
or CLIP embeddings. For a description of the modification parameters, refer to
Appendix D.

##  4 Experiments

In this section, we present experiments demonstrating DREW’s effectiveness for
source identification in the image domain, comparing its performance with the
baseline of purely embedding-based image retrieval (which we call "naive IR").

###  4.1 Experimental Setup

Datasets. Our experiments utilize a diverse range of image datasets, including
ImageNet (Russakovsky et al., 2015) (1.2M images), WikiArt (Wikiart.org, )
(80k images), PlantVillage (Hughes & Salathe, 2016) (55k images), FGVC
Aircraft (Maji et al., 2013) (10k images), Art Images (artimages, 10) (8k
images), and Chest X-Ray Images (Kermany et al., 2018) (5k images). For
consistency, all images are resized and cropped to $256\times 256$ pixels.

Embedding models. We use DinoV2 (Oquab et al., 2024) and CLIP/ViT-L-14
(Radford et al., 2021) to compute image embeddings for both our method and
naive IR. Both models generate $768$-dimensional embeddings (with DinoV2’s
original size of $257\times 768$ averaged over the first dimension).

Watermarking models. Our experiments primarily utilize Trustmark (Bui et al.,
2023) due to its consistent robustness and minimal visible watermark patterns.
We also report results using StegaStamp (Tancik et al., 2020) in the appendix
(Figure 7), noting that while Trustmark generally offers better robustness,
StegaStamp excels against specific image modifications like diffusion
purification (Saberi et al., 2024). We use $100$-bit watermarks (i.e.,
$n=100$), as higher bit counts can degrade image quality with current
watermarking techniques.

Error control codes (ECC). For error correction, we employ Polar Codes
(Arikan, 2009) with a successive cancellation
decoder111https://github.com/fr0mhell/python-polar-coding. The reliability of
decoding is checked using the last log-likelihood ratio value, with a
threshold set at $0.5$.

Data modifications. To evaluate robustness, we apply a range of common data
augmentations, each parameterized to adjust its severity (e.g., crop.0.5
refers to center cropping images to $192\times 192$ pixels and resizing back
to $256\times 256$). Detailed augmentation parameters are provided in Appendix
D. These augmentations ensure the images retain their semantic content.

Evaluation. For evaluation, we sample $1000$ queries from each dataset and for
each image modification. For an accurate evaluation, both our method and naive
IR use exact nearest neighbor similarity search, as opposed to faster
approximate nearest neighbor (ANN) techniques. We also evaluate out-of-dataset
queries in Appendix A by sampling from the test sets of the datasets. We use
$1024$ clusters in our experiments for DREW ($k=10$).

Figure 3: Accuracy of image retrieval using DinoV2 embeddings on a subset of
$\frac{N}{2^{k}}$ images from each dataset. The plot illustrates the mean
(lines) and std (shades around the lines) of accuracy across a set of
augmentations.
Figure 4: False positive rate of the ECC’s reliability check module
($\epsilon_{r}$), for various datasets and augmentations. This value was used
in analysis in Section 3.4.

###  4.2 Results

Figure 2 compares the accuracy of DREW (using Trustmark for watermarking) to
naive IR in identifying matches with DinoV2 embeddings, on a set of image
augmentations. The full set of augmentation results is shown in Figure 5,
indicating no performance degradation even for less robust augmentations. Our
results in Figure 2 show that DREW’s improvement over the baseline is less
significant in datasets where DinoV2 is highly robust (e.g., ImageNet and
WikiArt). This may be due to the more distinguishable nature of these images
or the embedding models’ prior exposure to similar data during training.
However, for datasets like Art Images or Chest X-Ray Images, watermarking
techniques generalize better to out-of-distribution or underrepresented data
than embedding models, making DREW more suitable for large-scale diverse data.
Detailed results, including those for CLIP embeddings, are presented in Table
1 and visualized in Figure 6. Furthermore, Figure 6 visualizes the results for
CLIP embeddings.

Our experiments show that DREW does not cause any noticeable performance
degradation compared to the naive IR baseline. As depicted in Figure 2,
Trustmark exhibits low robustness against "rotation" and "diffpure"
modifications, likely due to the specific training regimen of the Trustmark
model. In Figure 7, we demonstrate that StegaStamp exhibits greater robustness
to "diffpure" modifications, but performs weakly against other modifications.

A critical analysis raises whether DREW can be enhanced with better
watermarking techniques or if there is an inherent performance ceiling. Figure
3 shows that with a perfectly robust watermarking method accurately
identifying the ground truth cluster for query images, DREW’s accuracy can
improve significantly with practical $k$ values (without requiring excessive
watermark bits). This suggests that
$\mathbb{P}(x^{=}x_{i},\bar{x}^{\neq}x_{i})$ is not the primary performance
bottleneck in Equation 1, suggesting future research to focus on designing
more robust watermarks to enhance DREW’s overall robustness.

Furthermore, empirical results on the false positive rate of $\mathcal{C}_{R}$
are presented in Figure 4. The false positive rate is minimal in most cases,
justifying the practical applicability of DREW, as this is the only scenario
where DREW might underperform compared to naive IR.

##  5 Discussion and Limitations

While our results demonstrate improved robustness compared to the baseline, we
note that we are proposing a generalizable and scalable framework, which can
be further enhanced by the rapid ongoing advancements in watermarking
techniques and data embedding models. To highlight the rapid progress in
watermarking techniques, the Trustmark (Bui et al., 2023) method that we
utilize in our framework, is a recently proposed method that has shown
significant overall robustness compared to the previous state-of-the-art image
watermarks.

As shown in the literature (Saberi et al., 2024; Rabbani et al., 2024),
watermarks with a higher perturbation level (i.e., more visible watermark
traces) can substantially improve robustness against non-adversarial attacks
(e.g., common augmentations, diffusion purification). While our framework may
have limited robustness when using imperceptible watermarking techniques, in
some scenarios, higher perturbation watermarks can be utilized for enhanced
protection. For example, to protect the ownership of images posted on social
media platforms, users can choose to have more visible watermark traces in
their media, benefiting from greater content protection.

In our experiments, we evaluate robustness against simple image modifications.
However, more complex modifications that do not change the semantics of the
image can also be applicable (e.g., text insertion, inpainting). For some
modifications, our framework can potentially provide more substantial
robustness enhancements. For instance, consider inserting an image from the
dataset into a larger random image. While naive retrieval may struggle to find
a match for this type of modification, our framework can use watermark
detectors (Tancik et al., 2020) to first detect and extract the region of the
query image containing the watermark, and then pass the extracted region to
the retrieval module. We leave the analysis of other modification types to
future work.

##  6 Conclusion

In this paper, we introduced DREW (Data Retrieval with Error-corrected codes
and Watermarking), a novel framework that combines error-controlled
watermarking with embedding-based retrieval for source identification in data
provenance. This novel approach addresses the limitations inherent in current
methods, such as the restricted capacity of watermarking and the scalability
issues of embedding-based retrieval in large databases. Furthermore, by
employing ECC algorithms, our method ensures robust and reliable utilization
of watermarks, even under extensive data modifications. In our experiments,
DREW demonstrates improved robustness compared to traditional retrieval,
particularly in challenging datasets. This makes our framework a reliable and
effective alternative for source identification.

##  7 Acknowledgement

This project was supported in part by a grant from an NSF CAREER AWARD
1942230, ONR YIP award N00014-22-1-2271, ARO’s Early Career Program Award
310902-00001, HR00112090132 (DARPA/RED), HR001119S0026 (DARPA/GARD), Army
Grant No. W911NF2120076, the NSF award CCF2212458, NSF Award No. 2229885 (NSF
Institute for Trustworthy AI in Law and Society, TRAILS), an Amazon Research
Award and an award from Capital One.

## References

  * (1) 10\.  Kaggle art images.  https://www.kaggle.com/datasets/thedownhill/art-images-drawings-painting-sculpture-engraving.
  * Arikan (2009) Erdal Arikan.  Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels.  _IEEE Transactions on Information Theory_ , 55(7):3051–3073, 2009.  doi: 10.1109/TIT.2009.2021379.
  * Arya et al. (1998) Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu.  An optimal algorithm for approximate nearest neighbor searching fixed dimensions.  _J. ACM_ , 45(6):891–923, nov 1998.  ISSN 0004-5411.  doi: 10.1145/293347.293348.  URL https://doi.org/10.1145/293347.293348.
  * Bose & Ray-Chaudhuri (1960) R.C. Bose and D.K. Ray-Chaudhuri.  On a class of error correcting binary group codes.  _Information and Control_ , 3(1):68–79, 1960.  ISSN 0019-9958.  doi: https://doi.org/10.1016/S0019-9958(60)90287-4.  URL https://www.sciencedirect.com/science/article/pii/S0019995860902874.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners, 2020.
  * Bui et al. (2023) Tu Bui, Shruti Agarwal, and John Collomosse.  Trustmark: Universal watermarking for arbitrary resolution images, 2023.
  * Buneman et al. (2001) Peter Buneman, Sanjeev Khanna, and Tan Wang-Chiew.  Why and where: A characterization of data provenance.  In Jan Van den Bussche and Victor Vianu (eds.), _Database Theory — ICDT 2001_ , pp. 316–330, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.  ISBN 978-3-540-44503-6.
  * Chakraborty et al. (2018) Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopadhyay.  Adversarial attacks and defences: A survey, 2018.
  * Chen et al. (2023) Wei Chen, Yu Liu, Weiping Wang, Erwin M. Bakker, Theodoros Georgiou, Paul Fieguth, Li Liu, and Michael S. Lew.  Deep learning for instance retrieval: A survey.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(6):7270–7292, 2023.  doi: 10.1109/TPAMI.2022.3218591.
  * Coalition for Content Provenance and Authenticity (2023) Coalition for Content Provenance and Authenticity.  Content credentials: C2pa technical specification.  https://c2pa.org/specifications/specifications/2.0/specs/C2PA_Specification.html, 2023.  Version 2.0.
  * Cohen & Hoshen (2021) Niv Cohen and Yedid Hoshen.  Sub-image anomaly detection with deep pyramid correspondences, 2021.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding, 2019.
  * Gallager (1962) R. Gallager.  Low-density parity-check codes.  _IRE Transactions on Information Theory_ , 8(1):21–28, 1962.  doi: 10.1109/TIT.1962.1057683.
  * Hamming (1950) R. W. Hamming.  Error detecting and error correcting codes.  _The Bell System Technical Journal_ , 29(2):147–160, 1950.  doi: 10.1002/j.1538-7305.1950.tb00463.x.
  * Honsinger (2002) Chris Honsinger.  Digital watermarking.  _Journal of Electronic Imaging_ , 11(3):414–414, 2002.
  * Hua et al. (2016) Guang Hua, Jiwu Huang, Yun Q. Shi, Jonathan Goh, and Vrizlynn L.L. Thing.  Twenty years of digital audio watermarking—a comprehensive review.  _Signal Processing_ , 128:222–242, 2016.  ISSN 0165-1684.  doi: https://doi.org/10.1016/j.sigpro.2016.04.005.  URL https://www.sciencedirect.com/science/article/pii/S0165168416300263.
  * Hughes & Salathe (2016) David. P. Hughes and Marcel Salathe.  An open access repository of images on plant health to enable the development of mobile disease diagnostics, 2016.
  * J. & R. (2022) Anju J. and Shreelekshmi R.  A faster secure content-based image retrieval using clustering for cloud.  _Expert Systems with Applications_ , 189:116070, 2022.  ISSN 0957-4174.  doi: https://doi.org/10.1016/j.eswa.2021.116070.  URL https://www.sciencedirect.com/science/article/pii/S0957417421014093.
  * Kermany et al. (2018) Daniel S. Kermany, Michael Goldbaum, Wenjia Cai, Carolina C.S. Valentim, Huiying Liang, Sally L. Baxter, Alex McKeown, Ge Yang, Xiaokang Wu, Fangbing Yan, Justin Dong, Made K. Prasadha, Jacqueline Pei, Magdalene Y.L. Ting, Jie Zhu, Christina Li, Sierra Hewett, Jason Dong, Ian Ziyar, Alexander Shi, Runze Zhang, Lianghong Zheng, Rui Hou, William Shi, Xin Fu, Yaou Duan, Viet A.N. Huu, Cindy Wen, Edward D. Zhang, Charlotte L. Zhang, Oulan Li, Xiaobo Wang, Michael A. Singer, Xiaodong Sun, Jie Xu, Ali Tafreshi, M. Anthony Lewis, Huimin Xia, and Kang Zhang.  Identifying medical diagnoses and treatable diseases by image-based deep learning.  _Cell_ , 172(5):1122–1131.e9, 2018.  ISSN 0092-8674.  doi: https://doi.org/10.1016/j.cell.2018.02.010.  URL https://www.sciencedirect.com/science/article/pii/S0092867418301545.
  * Kirchenbauer et al. (2024) John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein.  A watermark for large language models, 2024.
  * Lafta & Abdulsada (2022) Ali Lafta and Ayad Abdulsada.  Secure content-based image retrieval with copyright protection within cloud computing environment.  _Iraqi Journal for Electrical and Electronic Engineering_ , 18:82–91, 12 2022.  doi: 10.37917/ijeee.18.2.11.
  * Lewis et al. (2021) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela.  Retrieval-augmented generation for knowledge-intensive nlp tasks, 2021.
  * Maji et al. (2013) Subhransu Maji, Esa Rahtu, Juho Kannala, Matthew Blaschko, and Andrea Vedaldi.  Fine-grained visual classification of aircraft, 2013.
  * Naumov et al. (2019) Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, Jianyu Huang, Narayanan Sundaraman, Jongsoo Park, Xiaodong Wang, Udit Gupta, Carole-Jean Wu, Alisson G. Azzolini, Dmytro Dzhulgakov, Andrey Mallevich, Ilia Cherniavskii, Yinghai Lu, Raghuraman Krishnamoorthi, Ansha Yu, Volodymyr Kondratenko, Stephanie Pereira, Xianjie Chen, Wenlin Chen, Vijay Rao, Bill Jia, Liang Xiong, and Misha Smelyanskiy.  Deep learning recommendation model for personalization and recommendation systems, 2019.
  * Nie et al. (2022) Weili Nie, Brandon Guo, Yujia Huang, Chaowei Xiao, Arash Vahdat, and Anima Anandkumar.  Diffusion models for adversarial purification.  _arXiv preprint arXiv:2205.07460_ , 2022.
  * Oquab et al. (2024) Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Marc Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, Mahmoud Assran, Nicolas Ballas, Wojciech Galuba, Russell Howes, Po-Yao Huang, Shang-Wen Li, Ishan Misra, Michael Rabbat, Vasu Sharma, Gabriel Synnaeve, Hu Xu, Hervé Jegou, Julien Mairal, Patrick Labatut, Armand Joulin, and Piotr Bojanowski.  Dinov2: Learning robust visual features without supervision, 2024.
  * Rabbani et al. (2024) Tahseen Rabbani, Bang An, Mucong Ding, Aakriti Agrawal, Yuancheng Xu, Chenghao Deng, Sicheng Zhu, Abdirisak Mohamed, Yuxin Wen, Tom Goldstein, and Furong Huang.  WAVES: Benchmarking the robustness of image watermarks.  In _Privacy Regulation and Protection in Machine Learning_ , 2024.  URL https://openreview.net/forum?id=tUumjNa7TF.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.  Learning transferable visual models from natural language supervision, 2021.
  * Raffel et al. (2023) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer, 2023.
  * Reed & Solomon (1960) I. S. Reed and G. Solomon.  Polynomial codes over certain finite fields.  _Journal of the Society for Industrial and Applied Mathematics_ , 8(2):300–304, 1960.  doi: 10.1137/0108018.  URL https://doi.org/10.1137/0108018.
  * Roy & Chang (2004) Sujoy Roy and Ee-Chien Chang.  Watermarking with retrieval systems.  _Multimedia Syst._ , 9:433–440, 03 2004.  doi: 10.1007/s00530-003-0116-1.
  * Roy et al. (2005) Sujoy Roy, Ee-Chien Chang, and K. Natarajan.  A unified framework for resolving ambiguity in copy detection.  In _Proceedings of the 13th Annual ACM International Conference on Multimedia_ , MULTIMEDIA ’05, pp. 648–655, New York, NY, USA, 2005. Association for Computing Machinery.  ISBN 1595930442.  doi: 10.1145/1101149.1101294.  URL https://doi.org/10.1145/1101149.1101294.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  Imagenet large scale visual recognition challenge, 2015.
  * Saberi et al. (2024) Mehrdad Saberi, Vinu Sankar Sadasivan, Keivan Rezaei, Aounon Kumar, Atoosa Chegini, Wenxiao Wang, and Soheil Feizi.  Robustness of ai-image detectors: Fundamental limits and practical attacks, 2024.
  * Sadasivan et al. (2024) Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian, Wenxiao Wang, and Soheil Feizi.  Can ai-generated text be reliably detected?, 2024.
  * Shannon (1948) Claude Elwood Shannon.  A mathematical theory of communication.  _The Bell System Technical Journal_ , 27:379–423, 1948.  URL http://plan9.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf.
  * Simhadri et al. (2022) Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang.  Results of the neurips’21 challenge on billion-scale approximate nearest neighbor search, 2022.
  * Simmhan et al. (2005) Yogesh L. Simmhan, Beth Plale, and Dennis Gannon.  A survey of data provenance in e-science.  _SIGMOD Rec._ , 34(3):31–36, sep 2005.  ISSN 0163-5808.  doi: 10.1145/1084805.1084812.  URL https://doi.org/10.1145/1084805.1084812.
  * Song et al. (2013) Jingkuan Song, Yi Yang, Zi Huang, Heng Tao Shen, and Jiebo Luo.  Effective multiple feature hashing for large-scale near-duplicate video retrieval.  _IEEE Transactions on Multimedia_ , 15(8):1997–2008, 2013.  doi: 10.1109/TMM.2013.2271746.
  * Swanson et al. (1998) M.D. Swanson, M. Kobayashi, and A.H. Tewfik.  Multimedia data-embedding and watermarking technologies.  _Proceedings of the IEEE_ , 86(6):1064–1087, 1998.  doi: 10.1109/5.687830.
  * Tancik et al. (2020) Matthew Tancik, Ben Mildenhall, and Ren Ng.  Stegastamp: Invisible hyperlinks in physical photographs, 2020.
  * Wan et al. (2022) Wenbo Wan, Jun Wang, Yunming Zhang, Jing Li, Hui Yu, and Jiande Sun.  A comprehensive survey on robust image watermarking.  _Neurocomputing_ , 488:226–247, 2022.  ISSN 0925-2312.  doi: https://doi.org/10.1016/j.neucom.2022.02.083.  URL https://www.sciencedirect.com/science/article/pii/S0925231222002533.
  * Wen et al. (2023) Yuxin Wen, John Kirchenbauer, Jonas Geiping, and Tom Goldstein.  Tree-ring watermarks: Fingerprints for diffusion images that are invisible and robust, 2023.
  * (44) Wikiart.org.  Wikiart dataset.  https://www.kaggle.com/datasets/steubk/wikiart/data.
  * Zhang et al. (2023) Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak.  Watermarks in the sand: Impossibility of strong watermarking for generative models, 2023.

Figure 5: Accuracy of our method vs naive retrieval using DinoV2 embeddings,
against different types and severity levels of augmentations. The utilized
watermarking method is Trustmark.
Figure 6: Accuracy of our method vs naive retrieval using CLIP/ViT-L-14
embeddings, against different types and severity levels of augmentations. The
utilized watermarking method is Trustmark. In general, CLIP shows lower
robustness than DinoV2 (see Figure 2), and our method provides a higher
accuracy boost to the naive retrieval using CLIP.
Figure 7: Accuracy of our method, implemented with StegaStamp watermark, vs
naive retrieval using DinoV2 embeddings, against different types and severity
levels of augmentations. StegaStamp performs better than Trustmark (see Figure
6) on "diffpure", while showing lower robustness to other image modifications.
Figure 8: AUROC and<EMAIL_ADDRESS>(i.e., True positive rate at $0.1$ false
positive rate) for DREW vs naive IR. DinoV2 embeddings and Trustmark watermark
are used for these results.

##  Appendix A Performance on out-of-dataset queries

In section 3.2, we assumed that a retrieval method $\mathcal{M}$, reports a
match for every query. But in some applications, the method should prevent
reporting false positive matches. For DREW, similar to the traditional data
retrieval, we consider the embedding similarity $\phi(x_{i})^{T}\phi(z)$
between the query $z$, and the match $x_{i}$, and define a threshold $t_{sim}$
to distinguish between true matches (i.e., $\phi(x_{i})^{T}\phi(z)\geq
t_{sim}$) and false matches (i.e., $\phi(x_{i})^{T}\phi(z)<t_{sim}$).

For out-of-distribution queries that are not supposed to match any data from
the dataset, if DREW cannot find a reliable cluster for the query, it reports
the same match as naive IR. Otherwise, if DREW falsely assigns a cluster to
the query, it will report the data sample with the highest embedding
similarity in that cluster, whose similarity score is less than the reported
output of naive IR (i.e., $max_{x\in X_{c}}\phi(x)^{\top}\phi(z)\leq max_{x\in
X}\phi(x)^{\top}\phi(z)$). Therefore, even though the second case does not
often happen in practice (due to the robustness of ECC), in cases where it
happens, it will even further boost the performance of DREW.

In Figure 8, we evaluate DREW on a combination of $1000$ in-dataset and $1000$
out-of-dataset queries, and compare the results to naive IR.

##  Appendix B ECC Analysis

Assume $x\in X$ and $z=\mathcal{A}(x)$ is the altered version of $x$. Passing
these data samples into the watermark decoder results in $n$-bit binary keys
$w_{x}=\mathcal{W}_{D}(x)$ and $w_{z}=\mathcal{W}_{D}(z)$. Based on the
robustness of the watermark, $w_{x}$ and $w_{z}$ can have different bits in
several places. For the current analysis, we assume that an attack
$\mathcal{A}$ causes each bit of $w_{z}$ to flip independently from their
value in $w_{x}$, with probability $p_{\mathcal{A}}$. Note that in practice,
this assumption does not necessarily hold for every attack and watermarking
technique.

In Section 3.4, we have provided discussions on the correlation between
outputs of $\mathcal{C}_{D}$ and $\mathcal{C}_{R}$, and their effect on the
performance of the model. In this section, we analyze the robustness of
$\mathcal{C}_{D}$ against attacks. In other words, if
$c_{x}=\mathcal{C}_{D}(w_{x})$ and $c_{z}=\mathcal{C}_{D}(w_{z})$, we are
interested in the success rate of $\mathcal{C}_{D}$, which is the cases where
$c_{z}=c_{x}$.

As defined in Section 3.2, $\mathcal{C}_{D}$ receives a $n$-bit watermark key,
and outputs a $k$-bit cluster code where $k<n$. The code rate of the ECC
module $\mathcal{C}$ is defined as $\frac{k}{n}$. Generally, a lower code rate
corresponds to more redundant bits used for correction, and will result in a
higher decoding success rate. Shannon’s capacity theorem (Shannon, 1948),
provides an upper-bound on the code rate of an ECC algorithm with a high
probability of successful decoding against an attacker that flips the bits of
the $n$-bit keys with probability $p_{\mathcal{A}}$:

$\frac{k}{n}\leq
1-H(p_{\mathcal{A}})=1+p_{\mathcal{A}}log(p_{\mathcal{A}})+(1-p_{\mathcal{A}})log(1-p_{\mathcal{A}}),$
(2)

where $H$ is the binary entropy function.

Figure 9: Illustration of Equation 2, which shows the amount of bit redundancy
(i.e., $\frac{n}{k}$) required for a successful decoding against
$p_{\mathcal{A}}$ bit-flip rate w.h.p. In our experiments in Section 4, we use
$k=10,n=100$.

In practice, state-of-the-art ECC algorithms such as polar codes (Arikan,
2009) and LDPC (Gallager, 1962), achieve code rates that are close to the
Shannon’s capacity limit. Figure 9 illustrates the limit from Equation 2. In
practice, there is a limit to the number of bits that can be encoded into a
data sample (e.g., image) as a watermark. Therefore, to increase the
robustness of the $\mathcal{C}_{D}$, the solution is to decrease $k$ , which
corresponds to decreasing the number of clusters for our method. This
introduces a trade-off between the terms $P(c=c_{gt})$ and
$P(x^{*}=x_{i},\bar{x}^{*}\neq x_{i})$ that have been used in the analysis
from Section 3.4.

##  Appendix C Robustness to Adversarial Attacks

In this section, we discuss the performance of DREW in various adversarial
scenarios. Since the data retrieval methods we discuss in this work rely on
using embeddings from neural networks, they might be susceptible to
adversarial attacks. We discuss three possible scenarios below:

  1. 1.

Let $x_{i}$ be an image in the dataset $X$. The adversary could imperceptibly
perturb $x_{i}$ as $\tilde{x}_{i}=x_{i}+\delta$ where
$\delta=\min_{\|\delta\|\leq\epsilon}\phi(x_{i})^{\top}\phi(\tilde{x}_{i})$.
In this case, the retrieval technique based on embedding similarity match
would return another image $x_{j}$ as a match for the query $\tilde{x}_{i}$
instead of the datapoint $x_{i}$, where
$\phi(x_{j})^{\top}\phi(\tilde{x}_{i})>\phi(x_{i})^{\top}\phi(\tilde{x}_{i})$.
However, this attack scenario could affect both DREW and the baseline
embedding-based retrieval techniques to the same extent.

  2. 2.

In another scenario, the adversary could add imperceptible noise
$\delta=\min_{\|\delta\|\leq\epsilon}\mathcal{C}_{R}(\mathcal{W}_{D}(x_{i}+\delta))$
such that the output of the error control decoder is flagged as unreliable.
For this case, the ECC-based watermark signal is removed from the query image
$\tilde{x}_{i}=x_{i}+\delta$, and hence, would lead to DREW searching the
entire database for a match. Note that this attack only makes DREW as
effective as the baseline embedding-based retrieval techniques and not any
worse.

  3. 3.

The adversary could spoof the datapoint $x_{i}$ in cluster $X_{i}$ by adding
adversarial noise such that, while querying the perturbed
$\tilde{x}_{i}=x_{i}+\delta$, DREW would search for the query candidate
$\tilde{x}_{i}$ in a different cluster $X_{j}$. Here $\delta$ should satisfy
$\min_{\|\delta\|\leq\epsilon,j\neq
i}|\mathcal{C}_{D}(\mathcal{W}_{D}(x_{i}+\delta))-j|-\mathcal{C}_{R}(\mathcal{W}_{D}(x_{i}+\delta))$.
In this case, DREW would confidently search for $\tilde{x}_{i}$ in a cluster
$X_{j}$ and fail to return the matching datapoint $x_{i}$ present in cluster
$X_{i}$.

Note that the attack scenarios mentioned here could also be practical in a
black-box fashion. In Scenario 1, the adversary could use a surrogate
embedding model instead of $\phi$ to perform their optimization to attack the
embedding-based matching. For scenarios 2 and 3, as shown in (Saberi et al.,
2024), the adversary could use a dataset of watermarked samples from the
dataset $X$ and non-watermarked samples not present in the dataset $X$ to
learn a classifier. The adversary can then attack the datapoints to erase or
spoof watermarks for a query datapoint based on this classifier’s confidence.
As we discuss here, Scenarios 1 and 2 affect DREW and the baseline methods to
the same level. Scenario 3 could lead DREW to yield a degraded performance.
However, for this setting, the adversary should assume having access to
sufficient data points from at least two different clusters, source $X_{i}$
and target clusters $X_{j}$. This may not be practical in all scenarios. For
this reason, in this application, spoofing is not interesting for a practical
adversary since they would resort to using a surrogate embedder, as mentioned
in Scenario 1, to adversarially inhibit accurate retrieval. We leave studying
DREW to be robust in Scenario 3 for the future.

##  Appendix D Data Modifications

In this section, we provide a code for a detailed description of the used
image augmentations and their parameters.

    # inputs:
    # aug
    # severity (in range [0, 1])
    if aug == ’no_aug’:
        transform = transforms.Compose([])
    elif aug == ’rotation’:
        transform = transforms.Compose([
                transforms.RandomRotation([-int(90 * severity), int(90 * severity)]),
        ])
    elif aug == ’crop’:
        transform = transforms.Compose([
                transforms.CenterCrop(256 - int(128 * severity)),
                transforms.Resize((256, 256)),
        ])
    elif aug == ’flip’:
        transform = transforms.Compose([
                transforms.RandomHorizontalFlip(1.0),
        ])
    elif aug == ’stretch’:
        transform = transforms.Compose([
                transforms.Resize(256),
                transforms.CenterCrop((256 - int(128 * severity), 256)),
                transforms.Resize((256, 256)),
        ])
    elif aug == ’blur’:
        transform = transforms.Compose([
                transforms.GaussianBlur(5),
                # transforms.ToTensor(),
        ])
    elif aug == ’combo’:
        transform = transforms.Compose([
                transforms.CenterCrop((256 - int(128 * severity), 256)),
                transforms.RandomHorizontalFlip(1.0),
                transforms.RandomRotation([-int(90 * severity), int(90 * severity)]),
                transforms.Resize((256, 256)),
        ])
    elif aug == "jitter":
        transform = transforms.Compose([
                transforms.ColorJitter(brightness=1.0, contrast=0.5, saturation=1.0, hue=0.1),
        ])
    elif aug == ’diffpure’:
        transform = transforms.Compose([
            DiffPure(steps=severity),
        ])