ADD for Multi-Bit Image Watermarking
arXiv:2604.11491v1 [stat.ML] 13 Apr 2026
An Luo and Jie Ding School of Statistics, University of Minnesota [email protected] and [email protected]
Abstract As generative models enable rapid creation of high-fidelity images, societal concerns about misinformation and authenticity have intensified. A promising remedy is multi-bit image watermarking, which embeds a multi-bit message into an image so that a verifier can later detect whether the image is generated by someone and further identify the source by decoding the embedded message. Existing approaches often fall short in capacity, resilience to common image distortions, and theoretical justification. To address these limitations, we propose ADD (Add, Dot, Decode), a multi-bit image watermarking method with two stages: learning a watermark to be linearly combined with the multi-bit message and added to the image, and decoding through inner products between the watermarked image and the learned watermark. On the standard MSCOCO benchmark, we demonstrate that for the challenging task of 48-bit watermarking, ADD achieves 100% decoding accuracy, with performance dropping by at most 2% under a wide range of image distortions, substantially smaller than the 14% average drop of state-of-the-art methods. In addition, ADD achieves substantial computational gains, with 2-fold faster embedding and 7.4-fold faster decoding than the fastest existing method. We further provide a theoretical analysis explaining why the learned watermark and the corresponding decoding rule are effective.
Keywords: Multi-bit Watermarking, Image Watermarking, Hypothesis Testing, Regularization
1
1
Introduction
In recent years, generative artificial intelligence (Rombach et al. 2022, Zhang et al. 2023, Lipman et al. 2023) has achieved unprecedented levels of realism and versatility, enabling rapid creation of high-fidelity images and videos (Esser et al. 2024, Google DeepMind 2025). At the same time, this proliferation has raised significant concerns over misinformation like DeepFake (Verdoliva 2020) and intellectual property infringement (Sag 2023, Chandra et al. 2024). As these issues intensify, reliable methods for verifying the authenticity and provenance of digital content have become increasingly important. In this context, image watermarking has emerged as a promising approach to invisibly embed information into images for purposes such as content verification and copyright protection (Cox et al. 2007). Among watermarking techniques, multi-bit watermarking (see Figure 1 for an overview) is particularly important because it enables the embedded watermark to carry information for origin tracking and attribution. In contrast to single-bit watermarking, which only indicates whether an image is watermarked, multi-bit watermarking embeds a message that can represent richer information, such as an owner identifier, a user fingerprint, a timestamp, or an IP address. However, increasing the message capacity also makes the problem more challenging: the watermark must remain invisible while still enabling resilient recovery of embedded message under common image distortions. Despite substantial progress, existing multi-bit image watermarking methods still exhibit limitations. Traditional watermarking techniques embed watermark by modifying pixel values (van Schyndel et al. 1994, Nikolaidis & Pitas 1998, Chen & Wornell 2001, Altun et al. 2009, Jie & Zhiqiang 2009) or adding signals in frequency domain (Cox et al. 1996, O’Ruanaidh & Pun 1997, Hernandez et al. 2000, Al-Haj 2007, Navas et al. 2008) of images. Despite their simple implementation and historical significance, these classical methods either consider only
2
Watermarked image
Image
Potential Distortions
Message 011 ⋯ 01
Signature
Timestamp
⋯
IP address
⋯
Detection “Watermarked?” Decoding 011 ⋯ 01
Private key
⋯
Figure 1: An overview of multi-bit image watermarking. An image, which may be generated by AI models or created as digital artwork such as paintings or photographs, can be embedded with a multi-bit message. Such messages may encode information such as a timestamp, IP address, signature, or private key. The resulting watermarked image is then distributed over the Internet and may undergo distortions (e.g., compression or rotation). Given a possibly distorted image, the goal is to detect whether the image is watermarked and further decode the embedded multi-bit message to recover the information. single-bit watermark, or struggle to handle intensive image distortions, such as compression and rotation (Ballé et al. 2018). With the advent of deep learning (Goodfellow et al. 2016), a new wave of watermarking schemes has emerged that harness the power of neural networks with encoder–decoder architectures (Zhu et al. 2018, Tancik et al. 2020, Fernandez et al. 2022, Xian et al. 2024, Sander et al. 2025), where encoders hide messages within images and decoders are designed to resiliently decode the hidden messages. These approaches can achieve better performance than traditional methods, but ensuring consistent resilience to diverse distortions still remains challenging (Zhong et al. 2023, An et al. 2024). In addition, most of them operate at low capacity (no more than 32 bits) and provide limited theoretical guidance. Some recent works have proposed watermarking methods designed specifically for certain image generative models, including diffusion models (Fernandez et al. 2023, Wen et al. 2023, Yang et al. 2024, Gunn et al. 2025) and autoregressive models (Jovanović et al. 2025), which can achieve better resilience in some cases but are inherently tied to a particular
3
architecture and do not work for other model families or post-hoc settings. From a theoretical perspective, watermarking has been studied mainly in single-bit settings, particularly through information-theoretic perspectives (Willems 2000, Moulin & O’Sullivan 2000, Moulin 2001, Moulin & O’Sullivan 2003, Liu & Moulin 2003a,b, Sion & Atallah 2004), and more recently through statistical frameworks for LLM-generated text (Li et al. 2025a,b, Xie et al. 2025). To address these limitations, we propose Add, Dot, Decode (ADD), a simple yet effective multi-bit image watermarking method together with theoretical analysis that explains why it works. ADD embeds a multi-bit message by adding to the image a linear combination of a learned watermark weighted by the multi-bit message; through dot products between the watermarked image and the learned watermark, ADD decodes the embedded message. Such watermark is learned through a training objective designed to jointly pursue image quality, decoding performance, and resilience to distortions. The key insight underlying ADD is that the learned watermark possesses a specific geometric structure. Under the assumption that the image data concentrate around a low-dimensional subspace with Gaussian noise perturbation, the training objective learns a watermark that is orthogonal to the low-dimensional image subspace, with mutually orthogonal watermark components corresponding to the bits of the message. These properties ensure that the inner products between images and the watermark are well separated for watermarked and unwatermarked images, enabling reliable detection. Moreover, because each message bit is embedded with a distinct watermark component, the sign of the inner product between the watermarked image and that component reveals the bit value, enabling accurate decoding. Building on this geometric structure, we derive detection and decoding rules using the likelihood principle and establish corresponding performance guarantees. We further show that this geometric property also holds asymptotically for a watermark learned from the
4
corresponding finite-sample objective, and the detection and decoding performance converge to their population counterparts. Empirically, ADD achieves state-of-the-art performance under a wide range of image distortions, while maintaining high image quality and offering substantially faster embedding and decoding than competing approaches. The outline of the paper is given as follows. In Section 2, we state the problem formulation of watermarking. In Section 3, we introduce ADD. In Section 4, we provide a theoretical analysis on how ADD can work. We present experiments in Section 5 and conclude the paper in Section 6. The supplementary material includes proofs and details of discussions and experiments.
2
Problem Formulation of Watermarking
Consider a signal x ∈ X and a message m ∈ M. We define a watermarking mechanism W as a map that produces a watermarked signal x̃ = W (x, m), where x̃ should remain close to x in quality. After x̃ being distributed through a channel, a potentially distorted version x̃′ is observed by a verifier. On x̃′ , the verifier performs: 1) watermark detection, to decide whether x̃′ is watermarked by W , and further 2)
watermark decoding, to
recover the message m embedded in x̃ by W . In this paper, X is the space of images and m ∈ M = {−1, 1}K is a K-bit message that serves as an identifier, where K is a positive integer. Throughout the paper, we use k = 1, . . . , K and k ∈ [K] interchangeably. We consider the setting where an image is either unwatermarked or watermarked by W . The above formulation is generic, and we explain below with some concrete scenarios depending on who chooses m, who knows m, and how the message m can relate to identifiers. Example 1 (Watermark embedded by a model provider). A model provider Alice (e.g., OpenAI) embeds watermark in images generated for each user. A user Bob requests image 5
generation through Alice’s application programming interface (API), and Bob will always receive a watermarked image x̃ = W (x, m) with an assigned identifier m. Such a message m can be deterministically derived from Bob’s metadata (e.g., IP address and timestamp), and assigned by Alice, while remaining unknown to Bob. A verifier (Alice or a third-party auditor) later detects whether an image is watermarked by W in order to determine whether the image is generated by Alice’s model, and further decodes the embedded m to identify which user of Alice’s model generated that image. Example 2 (Watermark embedded by an artist). An artist Bob watermarks their own images, e.g., photographs or digital paintings, with their identifier m, e.g., a signature or a timestamp, before releasing the images to the public. In this setting, Bob knows m and can act as a verifier that detect whether or not an image is distributed by them to claim ownership. Example 3 (Watermark embedded by multiple entities). A single watermarking mechanism W can be adopted by multiple entities. To avoid collisions, e.g., same message m being associated with different users, the message space M can be partitioned so that each entity is assigned a disjoint subset. This ensures that the recovered message can be uniquely attributed to the issuing entity. When released to the public, the watermarked image x̃ may undergo distortions, resulting in x̃′ ∈ X . Such distortion includes natural noises such as compression and intentional attack such as cropping. Let A denote a discrete distribution over a finite set of image distortion operators A : X → X . Given a watermarked image x̃, the distorted version is x̃′ = A(x̃) for some A ∼ A. A watermarking mechanism W should be designed for the following objectives: 1) Quality: The quality of watermarked images x̃ should remain visually close to that of unwatermarked images x; 2) Identifiability: Watermarked and unwatermarked images should be accurately 6
distinguished, and the embedded message m should be accurately recovered; 3) Resilience: The watermark should be resilient to common image distortions. Formally, consider the space of images X = RD , where D is a positive integer. Let x ∈ X denote an original image and let m = (m1 , . . . , mK )⊤ ∈ M = {−1, 1}K denote a K-bit watermark message. A (K-bit) watermarking mechanism W : X × {−1, 1}K → X produces a watermarked image x̃ = W (x, m). Watermark detection for W can be formulated as a hypothesis testing problem for an image x ∈ X to be verified: H0 : x is not watermarked H1 : x is watermarked
(1)
To formalize the hypothesis problem (1), let P0 denote the distribution of unwatermarked image on X . For each fixed message m ∈ {±1}K , define the embedding map Wm (x) := W (x, m), and define the induced distribution of watermarked images with watermark message
−1 m by PW |m := P0 ◦ Wm , i.e., PW |m (E) = P W (x, m) ∈ E for all measurable E ⊆ X . Then
the watermark detection problem can be posed as the composite hypothesis test: H0 : x ∼ P0
H1 : x ∼ PW |m for some m ∈ {±1}K .
(2)
As explained in Examples 1-3, a verifier may have access to a dictionary D of messages embedded. This makes the detection problem different from (2) as the search space of messages are potentially smaller, and it is another detection problem to be considered H0 : x ∼ P0
H1′ : x ∼ PW |m for some m ∈ D.
(3)
Watermark decoding for W aims to build a decoder Dec : X → {−1, 1}K that recovers the c = Dec(x̃), with the ultimate goal watermark message from the watermarked image with m h
of maximizing the expected bit accuracy E K1
ck = mk } . We consider bit accuracy k=1 1{m
PK
i
rather than the probability of perfect decoding for two reasons. First, bit accuracy is the standard metric in multi-bit watermarking and allows direct comparison with prior work.
7
Second, perfect decoding is an all-or-nothing criterion that becomes increasingly stringent as the message length K grows, since an error on a single bit makes the entire message incorrect, so bit accuracy provides a more informative measure of decoding performance.
3
Add, Dot, Decode (ADD)
In this section, we propose ADD, with an overview provided in Section 3.1 (see also Figure 2), followed by details on watermark training in Section 3.2 and deployment (watermark embedding, decoding and detection procedures) in Section 3.3. 1
2 𝑖 ′ ⟩) + 𝛽 σ𝐾 Training to find watermarks: ℒ𝑛 𝒘1:𝐾 = 𝑛 σ𝑛𝑖=1 𝔼𝐴∼𝒜 𝔼𝒎𝑖∼Unif ±1 𝐾 σ𝐾 𝑘=1 𝑉(𝑚𝑖,𝑘 ⟨𝒘𝑘 , 𝒙 𝑘=1 ‖𝒘𝑘 ‖
′ , 𝚪 = Γ1 , … , ΓK ⊤ Γ𝑘 = 𝒘𝒌 , 𝒙
𝒘1:𝐾
Detection “Watermarked?”
𝒙 + σ𝐾 𝑘 𝑚𝑘 𝒘𝑘 ′ 𝒙
𝒙
𝒙
Image
Watermarked image
Distortion 𝐴(⋅) Message 𝒎 ∈ ±1 𝐾 Dictionary of Messages 𝒟
For Detection & Decoding
𝑆 = σ𝐾 𝑘 |Γ𝑘 | ≷ 𝑠 Decoding 𝑚 ෝ 𝑘 = 𝑠𝑖𝑔𝑛(Γ𝑘 )
𝑆𝒟 = max⟨𝒎, 𝚪⟩ 𝑚∈𝒟
ෝ = arg max⟨𝒎, 𝚪⟩ 𝒎 𝒎∈𝒟
Figure 2: Overview of ADD for multi-bit image watermarking. Given an image P x ∈ X , a K-bit message m ∈ {±1}K is embedded by x̃ = x + K k=1 mk wk . After distribution, the watermarked image may be distorted by an distortion operator A, yielding the observed image x̃′i = A(x̃). Detection is performed to decide whether x̃′ is watermarked by ADD and if detected, decoding is performed to recover m. Specifically, detection and decoding are based on the inner products Γk = ⟨wk , x̃′ ⟩, collected as I = (Γ1 , . . . , ΓK )⊤ : detect with P S= K k=1 |Γk |, and decode with m̂k = sign (Γk ). As indicated in the dashed region, when an optional dictionary of embedded messages D ⊂ {±1}K is available, detection and decoding can be improved with SD = maxm∈D ⟨m, I⟩ and m̂ = arg maxm∈D ⟨m, I⟩. The watermark w1:K is trained from the top objective Ln as proposed in (5).
3.1
Overview of ADD
Our goal is to develop a watermarking mechanism that embeds a K-bit message m ∈ {±1}K into an image x, and ensures quality, identifiability, and resilience, as discussed in Section 2. 8
We first learn a watermark w1:K to be added to x by optimizing a training objective that balances the above three goals. Then, our watermarking mechanism W is additive to original image x, i.e., x̃ = W (x, m) = x +
PK
k=1 mk wk . We store watermark w1:K for later
detection and decoding. When an image x is received for detection or decoding, we compute inner products Γk = ⟨wk , x⟩, k = 1, . . . , K, between the image and our saved watermark w1:K . For detection, we aggregate these inner products into a test statistics S =
PK
k=1 |Γk |
and reject H0 (in (2)) if S > s for a threshold s. For decoding, we recover each bit via ck = sign(Γk ), k = 1, . . . , K. If a message dictionary D is available, we detect with statistics m
SD = maxm∈D
PK
k=1 mk Γk and decode with arg maxm∈D
PK
k=1 mk Γk . We will explain these
in detail in the rest of this section.
3.2
Training to find the desirable watermark
To train the desirable w1:K that satisfy the requirements on quality, identifiability, and resilience, we construct a training objective that jointly pursues these three goals. Below we explain how we incorporate each goal into our training objective. For quality, we include β
PK
2 k=1 ∥wk ∥ with a hyperparameter β > 0, where ∥ · ∥ denotes the
Euclidean (ℓ2 ) norm, so that we constrain the magnitude of w1:K in terms of the squared ℓ2 norms. This is a common practice to penalize the magnitude of the watermark (Zhu et al. 2018, Tancik et al. 2020, Fernandez et al. 2022), which is also a classical way to penalize the magnitude of parameters as introduced by Hoerl & Kennard (1970) and Zou & Hastie (2005). For identifiability, we first explain our approach with the simplest case K = 1. When K = 1, the watermark decoding problem boils down to a binary classification problem, i.e., predicting the message m = m1 =: m embedded in a watermarked image x̃ with label m ∈ {±1}. A standard solution to such binary classification problem is to train with a margin-based loss (Lin 2004) of the form V (mf (·)), where V is a margin-based loss such as hinge loss, m 9
is the prediction target (here, the message embedded and to be recovered), and f (·) is the classification function with classification rule sign(f ) (here, f (·) should be some quantity c = 1 if determined by the watermarked image x̃ and the watermark w := w1 ), i.e., predict m c = −1 if sign(f ) < 0. As described earlier in Section 3.1, f (·) would be the sign(f ) ≥ 0 and m
inner product ⟨w, x̃⟩. Therefore, at K = 1 the term for the loss that enforces identifiabiliy would be V (m⟨w, x̃⟩). One key difference between our watermarking at K = 1 and binary classification is that, we take full control on the prediction target m, i.e., as training data we only need to independently sample m ∼ Unif(±1), take them as prediction targets, and embed them through our watermarking mechanism. This requires a expectation form in the loss, i.e., Em∼Unif(±1) V (m⟨w, x̃⟩). Extending to the case K > 1, since decoding is going to be performed with sign(⟨wk , x⟩) for each k, we only need to do binary classification separately for each bit mk , and this leads to the term Em∼Unif({±1}K ) detection is given by S =
PK
k=1 V (mk ⟨wk , x̃⟩). Watermark
PK
k=1 |⟨wk , x⟩| would be large for watermarked images and small
for unwatermarked images, as will be explained in Section 4.2. For resilience, we add distortion simulation in training, to ensure the decoding mechanism also works well for watermarked images under common image distortions (examples of such image distortions are provided in Section E of the supplementary material). Specifically, we simulate the distorted watermarked image x̃′ by applying a randomly sampled distortion operator A ∼ A to the watermarked image x̃, and set x̃′ = A(x̃). This yields the term EA∼A Em∼Unif(±1K )
PK
′ k=1 V (mk ⟨wk , x̃ ⟩).
As discussed above, to ensure the quality, identifiability, and resilience of the watermark w1:K , we propose our population training objective here:
L(w1:K ) = Ex∼P0 EA∼A Em∼Unif({±1}K )
K X k=1
10
V (mk ⟨wk , x̃′ ⟩) + β
K X k=1
∥wk ∥2 ,
(4)
where P0 denotes the distribution of unwatermarked images x ∈ X , A is a discrete distribution over a finite set of image distortion operators A : X → X , m = (m1 , . . . , mK )⊤ is randomly
sampled from Unif {±1}K , x̃′ = A(x̃) = A ◦ W (x, m) is the distorted version of the watermarked image, and β > 0 is the regularization parameter. The finite-sample objective is obtained by replacing the expectation Ex∼P0 in (4) with an average over a finite training set {xi }ni=1 of unwatermarked images: n K K X X 1X ′ EA∼A Emi ∼Unif({±1}K ) V (mi,k ⟨wk , x̃i ⟩) + β ∥wk ∥2 , Ln (w1:K ) = n i=1 k=1 k=1
(5)
where mi = (mi,1 , . . . , mi,K )⊤ ∼ Unif {±1}K , and for each given mi and A, the watermarked image is x̃i = W (xi , mi ) and its distorted version is x̃′i = A(x̃i ) = A ◦ W (xi , mi ). The finite-sample objective (5) describes the exact optimization problem. When implementing it, we use Monte Carlo samples of the message mi and distortion operator A at each gradient update of stochastic gradient descent (SGD). Moreover, rather than optimizing w1:K directly in the pixel space of high dimension, we learn it through a low-dimensional parameterization. We present the implementation of our training algorithm with pseudo code in Algorithm 1 and also explain it below. To construct the watermark w1:K , instead of directly optimizing in the high-dimensional image space, we optimize over a space with much lower dimension. We first extract features from the original image using a pretrained and frozen feature extractor ψ : X → Rdf with output dimension df < D. To match the watermark dimension, for each k we train a watermark
map gk : Rdf → RD , yielding a per-image watermark wk = gk ψ(x) . When computing the penalty term, we normalize by the dimension D to ensure numerical stability. After training converges, we freeze the learned watermark maps gk and compute their dataset-level averages
11
by evaluating them on all training images and averaging the resulting outputs. These averages directly construct a fixed watermark w1:K , which is used for deployment. Algorithm 1 Training (learn watermark for K bits) Require: Training set {xi }ni=1 , number of bits K, feature extractor ψ : X → Rdf (frozen), watermark maps {gk : Rdf → RD }k∈[K] (trainable), margin-based loss V , regularization β > 0, distortion sampler A. Ensure: Trained and fixed watermark w1:K for deployment. 1: for each minibatch {xi }i∈I do 2: Sample message bits {mi,k }i∈I, k∈[K] i.i.d. from Unif(±1). 3: Compute features fi ← ψ(xi ) ∈ Rdf for all i ∈ I. 4: Form watermark (per image): wi,k ← gk (fi ) ∈ RD , for k = 1, . . . , K. P 5: Embed the K-bit message: x̃i ← xi + K k=1 mi,k wi,k , i ∈ I. 6: Apply a distortion: Sample A ∼ A and set x̃′i ← A(x̃i ) for all i ∈ I. 7: Compute total loss on the minibatch: K K 1 1 XX 1 XX ′ V mi,k ⟨wi,k , x̃i ⟩ + β · ∥wi,k ∥2 . Lbatch ← |I| i∈I k=1 |I| D i∈I k=1
8: Backpropagate ∇Lbatch through {gk }k∈[K] and update parameters with SGD. 9: end for 10: Freeze the trained {gk }k∈[K] and compute dataset-level averages:
wk ← 11:
3.3
n 1X gk ψ(xi ) , for k = 1, . . . , K. n i=1
return w1:K .
Deployment of ADD
Deployment consists of watermark embedding and watermark detection and decoding. To embed watermark (see Algorithm 2 for pseudo code), we do x̃ = x +
PK
k=1 mk wk , where
w1 , . . . , wK is the watermark trained in the way mentioned in Section 3.2. Algorithm 2 Watermark embedding Require: Input image x, number of bits K, learned watermark w1:K (from Algorithm 1), message m ∈ {±1}K (given or sampled). Ensure: Watermarked image x̃. P 1: x̃ ← x + K k=1 mk wk . 2: return x̃. 12
To do watermark detection and decoding (see Algorithm 3 for pseudo code), we first obtain the inner products Γk := ⟨wk , x⟩, k = 1, . . . , K. We use S =
PK
k=1 |Γk | as test statistics for
watermark detection as defined in (2), i.e., reject H0 if S > s, where s is a threshold determined
ck = sign Γk , before deployment. Given a received image x, we decode for each bit k with m
which is also derived in Section 4.2. If D is available, We use SD = maxm∈D
PK
k=1 mk Γk as
test statistics for watermark detection as defined in (3) , i.e., reject H0 if SD > sD , where sD c = arg maxm∈D is another threshold. Then decode with m
PK
k=1 mk Γk . These test statistics
and decoding rules are derived based on generalized likelihood ratio tests in Section 4.2. Algorithm 3 Watermark detection and decoding Require: Received image x (possibly watermarked), number of bits K, fixed watermark {wk }K k=1 , detection threshold s > 0. optional message dictionary D and threshold sD > 0. c (if detected). Ensure: Detection decision dˆ ∈ {0, 1}, and decoded message m 1: Γk ← ⟨w̄k , x⟩, for k = 1, . . . , K. 2: if D is provided then P 3: SD ← maxm∈D K k=1 mk Γk . ˆ 4: d ← 1{SD > sD }. ▷ dˆ = 1 means watermark detected PK c ← arg maxm∈D 5: m ▷ Watermark decoding k=1 mk Γk . 6: else P 7: S← K k=1 |Γk |. ˆ 8: d ← 1{S > s} ▷ dˆ = 1 means watermark detected ck ← sign(Γk ), for k = 1, . . . , K. 9: m ▷ Watermark decoding 10: end if ˆ m c (if dˆ = 1). 11: return d,
4
Theoretical Analysis
In this section, we provide theoretical insights into our proposed watermarking method. Specifically, in Section 4.1 we elucidate how our method leverages a low-dimensional data assumption and produces watermark that is orthogonal (or nearly orthogonal) to the lowdimensional subspace of images. Based on this property of watermark, in Section 4.2 we derive principled detection and decoding rules, and further analyze the performance.
13
4.1
Existence and properties of the learned watermark
4.1.1
Low-dimensional image data and loss assumptions
Empirical studies suggest that high-dimensional data, such as natural images, lie near a low-dimensional manifold (Goodfellow et al. 2016, Pope et al. 2021). Motivated by this, we adopt the following assumption for image data we consider: Assumption 1. Let d < D − K be a positive integer and B ∈ RD×d be a matrix with full column rank. Define U the column space of B, U ⊥ the null space of B ⊤ , and ΠU , ΠU ⊥ the projections onto U and U ⊥ . The image data follow the perturbed low-dimensional model
X = BZ + ϵ, Z ∼ N (0, ΣZ ), ϵ ∼ N (0, σϵ2 ID ),
(6)
where N (·, ·) denotes a Gaussian distribution with the first argument being the mean vector and the second the covariance matrix, Z and ϵ are independent, ΣZ is a positive definite d × d matrix, ID is the D × D identity matrix, and σϵ ≥ 0. We provide empirical evidence consistent with Assumption 1 in Section J of the supplementary material, showing that the pretrained feature vectors of images concentrate near a lowdimensional linear subspace. Below we propose the population objective and the finite-sample objective for theoretical analysis. The only difference from (4) and (5) we proposed in Section 3 is that we set A as the degenerate distribution that assigns probability 1 to the identity operator in the training objectives for tractability. Population objective. Let m = (m1 , . . . , mK ) ∈ {±1}K be i.i.d. discrete uniform over {±1}K and independent of X. For watermark w1:K = (w1 , . . . , wK ) ∈ (RD )K , the water-
14
marked image is X̃ := X +
PK
j=1 mj wj . The population objective is given by
L(w1:K ) := EX,m
"K X
D
V mk wk , X̃
E
#
+β
k=1
K X
∥wk ∥2 .
(7)
k=1
Finite-sample objective. Given i.i.d. sample x1 , . . . , xn from X, for each xi , let mi = (mi,1 , . . . , mi,K ) ∈ {±1}K be i.i.d. discrete uniform over {±1}K and independent of X. The finite-sample objective is given by
n K K K X X X 1X Ln (w1:K ) := Emi V mi,k wk , xi + mi,j wj + β ∥wk ∥2 . n i=1 j=1 k=1 k=1
(8)
By construction, L(w1:K ) = Ex1:n [Ln (w1:K )]. Assumption 2. V : R → R is convex, bounded below, and not affine in R. Assumption 3. V is L-Lipschitz for some L > 0, i.e. |V (a) − V (b)| ≤ L|a − b| for all a, b ∈ R, or ∂V (t) ⊆ [−L, 0], ∀t ∈ R, where ∂V (t) denotes the subdifferential of V at t, i.e. n
o
∂V (t) := g ∈ R : V (s) ≥ V (t) + g (s − t) for all s ∈ R . Here we introduce a one-dimensional population loss that will be used in the theoretical analysis. Let Z ∼ N (0, 1) and define √ ϕ(r) := E V r + σϵ r Z ,
hpop (r) := ϕ(r) + β r,
r ≥ 0.
(9)
Assumption 4. hpop (r) admits a unique minimizer r⋆ > 0. Remark 1 (When does Assumption 4 hold?). We consider two common margin-based losses: 1) Hinge loss V (x) = (1 − x)+ . A sufficient condition is σϵ2 < 4 and β < 1. 2) Logistic √ 2 loss V (x) = log(1 + e−x ). A sufficient condition is σϵ2 < −4 + 2 6 and β < 12 − σ8ϵ . The
15
insight is that to ensure Assumption 4, σϵ2 and β should not be too large. A detailed discussion on these results is in Section C of the supplementary material. Assumption 5. Either V is hinge loss with σϵ2 < 4 and β < 1, or V is logistic loss with √ 2 σϵ2 < −4 + 2 6 and β < 12 − σ8ϵ . Remark 1 says that Assumption 5 implies Assumption 4. Because hinge loss and logistic loss satisfy Assumptions 2-3, Assumption 5 also implies Assumptions 2-3.
4.1.2
Population objective: watermark perfectly orthogonal to U
We first establish the properties of the minimizer of the population objective (7). Theorem 1 (Existence and properties of watermark learned from L). Under Assumptions 1 ⋆ and 2, and assuming σϵ > 0, there exists at least one minimizer of L in (RD )K . Let w1:K be
any minimizer of L. Then ∥wk⋆ ∥2 is a minimizer of hpop , wk⋆ ∈ U ⊥ and ⟨wk⋆ , wj⋆ ⟩ = 0 for all ⋆ 2 j, k ∈ [K] with j ̸= k. Moreover, under Assumption 4, ∥w1⋆ ∥2 = · · · = ∥wK ∥ = r⋆ > 0.
Theorem 2 (Unique but trivial minimizer of L). Under Assumptions 2 and 3, assuming that β > K · L and E∥X∥ < ∞, it follows that L admits a unique but trivial global minimizer 0.
4.1.3
Finite-sample objective: watermark nearly orthogonal to U
We now establish the results for the minimizer of the finite-sample objective (8). Throughout the paper, we write a ≲ b if there exists a constant c > 0 such that a ≤ c b; a ≳ b if there exists a constant c > 0 such that a ≥ c b; a ≍ b if a ≲ b and a ≳ b. Theorem 3 (Existence and properties of watermark learned from Ln ). Under Assumptions 1 ⋆ and 5, there exists at least one minimizer of Ln in (RD )K . Let w1:K,n be any minimizer
of Ln .
⋆ Then w1:K,n ∈ W :=
D K
w1:K ∈ (R )
:
PK
k=1 ∥wk ∥
2
≤R
2
, where R2 = K(V (0) −
inf V )/β. There exists a constant τ > 0 that does not depend on n, such that if ε ≤ τ and 16
supw1:K ∈W |Ln (w1:K ) − L(w1:K )| ≤ ε, the following hold: ⋆ ∥2 ≥ (i) Nontriviality. mink∈[K] ∥wk,n
r⋆ . 2
⋆ ∥2 − r ⋆ ≲ (ii) Radius concentration. maxk∈[K] ∥wk,n
√
ε.
⋆ (iii) Near-orthogonality to the image subspace U. maxk∈[K] ∥ΠU wk,n ∥ ≲
√ ε.
(iv) Mutual near-orthogonality. Case (A): logistic V with σϵ ≥ 0 or hinge V with ⋆ ⋆ σϵ > 0. maxk̸=j |⟨wk,n , wj,n ⟩| ≲ ε1/4 + ε1/2 + ε. Case (B): hinge V with σϵ = 0. √ ⋆ ⋆ maxk̸=j |⟨wk,n , wj,n ⟩| ≲ ε + ε.
q
Furthermore, for any δ ∈ (0, 1) and εn (δ) := LR Ktr(ΣX ) with ΣX := BΣZ B
⊤
+ σϵ2 ID , we have P
4+ 25 3
√
log( 4δ ) log( 4n ) log( 4δ ) δ √ + 752log(2e) n log 2 n
supw1:K ∈W |Ln (w1:K ) − L(w1:K )| ≤ εn (δ) ≥ 1 − δ
i.i.d.
over the training sample {xi }ni=1 ∼ X. Consequently, with probability at least 1 − δ, the bounds in (i)–(iv) hold with ε replaced by εn (δ). Remark 2 (Comparison to population result). Theorem 1 gives exact properties that hold for every population minimizer: wk⋆ ∈ U ⊥ , ⟨wk⋆ , wj⋆ ⟩ = 0, ∥wk⋆ ∥ = r⋆ . Theorem 3 gives the corresponding statement for empirical minimizers of Ln : with high probability over the training sample, the same geometric relations hold up to errors controlled by εn (δ). Similar to the result in Theorem 2, one can show that if β > K · L, the finite-sample objective Ln admits the unique but trivial minimizer 0. Therefore in practice we should set β < K · L.
4.2
Watermark detection and decoding: derivation and analysis
In this section, we suppose that w1:K has been learned from the objectives (7) or (8) and is fixed for deployment. We discuss the detection and decoding rule under the watermarking mechanism W (x, m) = x +
PK
k=1 mk wk , based on the inner products Γ = (Γ1 , . . . , ΓK )
⊤
,
where Γk = ⟨wk , x⟩ for k = 1, . . . , K. In Section 4.2.1, we assume w1:K is learned from the
17
population objective L and derive appropriate detection and decoding rules based on the likelihood principle. In Section 4.2.2, we apply these rules to the finite-sample minimizer ⋆ w1:K,n and show that, as n → ∞, they satisfy desirable asymptotic properties.
4.2.1
Detection and decoding rules for the oracle watermark
Here we assume that the watermark w1:K is learned from the population objective L and satisfies the properties established in Theorem 1. We refer to it as oracle watermark, as stated in the following assumption. Assumption 6. The watermark w1:K satisfies wk ∈ U ⊥ , ∥wk ∥2 = r⋆ > 0 and ⟨wk , wj ⟩ = 0 for all j, k ∈ [K] with j ̸= k, and w1:K is called oracle watermark. Theorem 4 (Distribution of Γ under H0 and the alternatives). Under Assumptions 1 and 6, Γ ∼ N (0, σ 2 IK ) under H0 and Γ ∼ N (µm, σ 2 IK ) under H1 or H1′ , where µ := r⋆ and σ 2 := r⋆ σϵ2 . When σϵ2 = 0, Γ = 0 a.s. under H0 and Γ = µm a.s. under H1 or H1′ . With Theorem 4 and σϵ2 > 0, the watermark detection problems (2) and (3) can be reduced to the following ones: For watermark detection with no information on what m is embedded, H0 : Γ ∼ N (0, σ 2 IK ) H1 : Γ ∼ N (µm, σ 2 IK ) for some message m ∈ {±1}K .
(10)
For watermark detection with a known dictionary D ⊂ {±1}K for embedded messages, H0 : Γ ∼ N (0, σ 2 IK ) H1′ : Γ ∼ N (µm, σ 2 IK ) for some message m ∈ D.
(11)
With Theorem 4 and σϵ2 = 0, the detection problem is degenerate and the bit accuracy would always be 1. Theorem 5 (Test statistic and decoding rule for (10)). Under the same conditions as in Theorem 4 with σϵ2 > 0, the generalized likelihood ratio test (GLRT) for (10) is based on the test statistic S :=
PK
k=1 |Γk | with the rejection region {S > s} for a threshold s, and the
⊤
c sign := sign(Γ1 ), . . . , sign(ΓK ) corresponding maximum likelihood estimator of m is m
18
,
which is the decoded message. Theorem 6 (Test statistic and decoding rule for (11)). Fix a dictionary D ⊂ {±1}K of size |D| ∈ {1, . . . , 2K }. Under the same conditions as in Theorem 4 with σϵ2 > 0, the GLRT for (11) is based on the test statistic SD := maxm∈D ⟨m, Γ⟩ = maxm∈D
PK
k=1 mk Γk with the
rejection region {SD > sD } for a threshold sD , and the corresponding maximum likelihood c D := arg maxm∈D ⟨m, Γ⟩, which is the decoded message. estimator of m is m c = (m c1 , . . . , m cK )⊤ by For any message m ∈ {±1}K denote the bit accuracy of a decoder m c m) := 1 ba(m, K
dH (m, m′ ) :=
PK
k=1
PK
k=1
ck = mk }. For m, m′ ∈ {±1}K , denote the Hamming distance 1{m
1{mk ̸= m′k } and dmin := minm̸=m′ ∈D dH (m, m′ ).
Theorem 7 (Bit accuracy and a sufficient condition for improvement from D). Under the same c sign , m) | H1 , m] = conditions as in Theorem 4 with σϵ > 0, for any m ∈ {±1}K , E[ba(m
Φ( σµ ), where Φ(·) denotes the cdf of a standard normal random variable, and for any m ∈ D, h i √ c D , m) | H1′ , m ≥ 1 − (|D| − 1) Φ − µ dmin . Furthermore, a sufficient condition E ba(m σ h
i
c D , m) | H1′ , m ≥ E[ba(m c sign , m) | H1 , m] uniformly over m ∈ D is |D| ≤ for E ba(m √ µ2 dmin 2 µ +σ 2
exp
µ2 (dmin − 1) 2σ 2
.
Practical implication for |D| and dmin . Since 1 ≤ dmin ≤ K, the sufficient condition in
2
Theorem 7 implies that |D| ≲ exp (µ/σ) dmin . Thus the admissible size of the dictionary 2 can grow exponentially with dmin . In particular, if dmin ≍ K, then |D| ≲ exp(cK) for some constant c > 0, meaning that |D| can grow exponentially in K while still ensuring higher expected bit accuracy than decoding without D. Practical implication for β. There is a trade-off from β between identifiability (bit √
accuracy, the larger the better, given by Φ( σµ ) = Φ( σrϵ⋆ )) and quality (∥x̃ − x∥2 , the smaller the better, given by ∥x̃ − x∥2 = ∥
P
mk wk⋆ ∥2 = Kr⋆ ): since r⋆ decreases with β (as indicated
in Section C.2 of the supplementary material), a larger β will result in worse identifiability 19
and better quality for the learned watermark. To compare the two test statistics S =
PK
k=1 |Γk | and SD = maxm∈D ⟨m, Γ⟩, a natural way is
to evaluate their true positive rates (TPRs) at a common false positive rate (FPR) α, i.e., to compare P(S > s⋆α | H1 ) and P(SD > t⋆α | H1′ ) where s⋆α and t⋆α are the exact (1 − α)-quantiles of S and SD under H0 . Here H1′ restricts the message to D ⊂ ±1K , so this comparison is valid only when the true message is in D. While these quantiles are well-defined under the hypothesis testing problems (10) and (11), neither admits a simple closed form: S is a sum of folded-normal variables, and SD is the maximum of a generally correlated Gaussian family indexed by D (with correlation determined by the geometry of D). As a result, an exact equal-FPR comparison is not available in closed form. Instead, we can compare the TPR or type II error under conservative FPRs, as discussed in Section D of the supplementary material. In practice, for a target FPR α, the thresholds s⋆α and t⋆α can be set empirically as (1 − α)-quantiles of S and SD computed on a held-out calibration set of unwatermarked images.
4.2.2
Detection and decoding with finite-sample watermark
Watermark detection is performed on a single test image x using the inner products Γk = ⟨wk , x⟩ and the statistic S =
PK
k=1 |Γk | (Section 3.3).
Consequently, the usual “n → ∞”
asymptotics in hypothesis testing does not refer to the number of test samples. Instead, the natural n for asymptotic here is the number of training images in the finite-sample objective ⋆ ⋆ ⋆ Ln . Let w1:K,n = (w1,n , . . . , wK,n )⊤ be a minimizer of the finite-sample objective Ln in (8).
We emphasize here that the test image x is independent of the training data {xi }ni=1 . ⋆ Specifically, we directly replace w1:K in Γ and S with w1:K,n , and consider inner products ⋆ Γn := (Γ1,n , . . . , ΓK,n )⊤ , where Γk,n := ⟨wk,n , x⟩, and detection statistic Sn :=
PK
k=1 |Γk,n |.
In this section we characterize the watermark detection and decoding problem given the 20
⋆ finite-sample minimizer w1:K,n and show that, as n → ∞, the FPR and TPR of the test
based on Sn converge to those of the oracle detection problem (10), and the bit accuracy of the corresponding decoder converges to its oracle counterpart. Theorem 8 (Distribution of Γn under H0 and the alternatives). Under Assumption 1, Γn ∼ N (0, Σn ) under H0 and Γn ∼ N (Gn m, Σn ) under H1 or H1′ , where Gn is the K × K ⋆ ⋆ matrix whose (k, j)-th entry is ⟨wk,n , wj,n ⟩, and Σn is the K × K matrix whose (k, j)-th entry ⋆ ⊤ ⋆ is wk,n ΣX wj,n .
With Theorem 8, the watermark detection problem (2) can be reduced to the following one: H0 : Γn ∼ N (0, Σn ) H1 : Γn ∼ N (Gn m, Σn ) for some message m ∈ {±1}K .
(12)
Following the detection and decoding rules derived in Theorem 5, reject H0 when Sn > s for c sign a threshold s, and decode with m := (sign(Γ1,n ), . . . , sign(ΓK,n ))⊤ . n
For s ∈ R, define the FPR αn (s) := P(Sn > s | H0 ) and the TPR πn (s) := inf m∈{±1}K P(Sn > s | H1 , m) for (12), and define the FPR αorc (s) := P(S > s | H0 ) and the TPR πorc (s) := inf m∈{±1}K P(S > s | H1 , m) for (10). Define SD,n := maxm∈D ⟨m, Γn ⟩. With Theorem 8, the watermark detection problem (3) can be reduced to the following one: H0 : Γn ∼ N (0, Σn ) H1′ : Γn ∼ N (Gn m, Σn ) for some message m ∈ D.
(13)
Following the detection and decoding rules derived in Theorem 6, reject H0 when SD,n > t cD for a threshold t, and decode with m n := arg maxm∈D ⟨m, Γn ⟩.
For any threshold t ∈ R, define the FPR αD,n (t) := P(SD,n > t | H0 ) and the TPR πD,n (t) := inf m∈D P(SD,n > t | H1 , m) for (13), and define the FPR αD,orc (t) := P(SD > t | H0 ) and the TPR πD,orc (t) := inf m∈D P(SD > t | H1 , m) for (11). Theorem 9 (Convergence of FPR, TPR, and bit accuracy). Suppose that the same conditions
21
of Theorem 3 hold and σϵ > 0. For any δ ∈ (0, 1), let εn (δ) be as defined in Theorem 3. Then there exists a constant τ1 > 0 that does not depend on n, such that if εn (δ) ≤ τ1 , the following hold with probability at least 1 − δ over the training sample {xi }ni=1 : 1/2 (i) FPR and TPR with Sn . For any s ∈ R, |αn (s) − αorc (s)| ≲ ε1/4 n (δ) + εn (δ) + εn (δ) 1/2 and |πn (s) − πorc (s)| ≲ ε1/4 n (δ) + εn (δ) + εn (δ).
(ii) FPR and TPR with SD,n . Fix a dictionary D ⊂ {±1}K . For any t ∈ R, |αD,n (t) − 1/2 1/4 1/2 αD,orc (t)| ≲ ε1/4 n (δ) + εn (δ) + εn (δ) and |πD,n (t) − πD,orc (t)| ≲ εn (δ) + εn (δ) + εn (δ).
(iii) Bit accuracy.
sup m∈{±1}K
c sign c sign , m) | H1 , m] ≲ ε1/4 E[ba(m n , m) | H1 , m]−E[ba(m n (δ)+
cD c D , m) | H1 , m] ≲ ε1/4 ε1/2 n , m) | H1 , m] − E[ba(m n (δ) + εn (δ) and sup E[ba(m n (δ) + m∈D
ε1/2 n (δ) + εn (δ).
5
Experiments
In this section, we evaluate the performance of ADD through experiments on real image datasets. In Section 5.1, we compare the performance of ADD with representative watermarking methods under a wide range of image distortions. In Section 5.2, we demonstrate the computational advantage of ADD. In Section 5.3, we demonstrate the generalizability of ADD to other datasets. In Section 5.4, we present and discuss the empirical trade-offs from hyperparameters β and n. Setup. The training data is sampled from the train split of MS-COCO (Lin et al. 2014) dataset, which is one of the most widely used large-scale benchmarks in computer vision and contains natural images depicting a wide range of real-world scenes and objects. Its train split contains about 118,000 images, and the full dataset includes over 330,000 images with annotations for 80 object categories and more than 1.5 million object instances. All
22
images are resized to a fixed resolution of 256 × 256 pixels and processed as RGB images. We set K = 48 for the multi-bit message, which already represents a challenging regime to the best of our knowledge. Existing watermarking methods often experience substantial degradation in decoding performance at K = 48, while ADD is not restricted to this value of K. The metrics for the three goals of watermarking as discussed in Section 2 are as follows: 1) Quality is evaluated by the Peak Signal-to-Noise Ratio (PSNR) (a widely used metric for image watermarking (Cox et al. 2007)) between the original image x and the watermarked image x̃, defined as PSNR = 10 log10
MAX2 MSE
, where MAX denotes
the maximum possible pixel value of the image (255 for an 8-bit image), and MSE := PC PH PW 2 1 w=1 (xc,h,w − x̃c,h,w ) , where C, H, and W denote the number of channels, h=1 c=1 C·H·W
image height, and image width, respectively. 2) Identifiability is evaluated by the area under the receiver operating characteristic curve (AUROC) for detection performance, and bit accuracy for decoding performance. 3) Resilience is evaluated by the detection and decoding performance under a wide range of image distortions introduced in An et al. (2024). See details of these image distortions in Section E of the supplementary material. For training with Algorithm 1, we set β = 1000 (note that in Algorithm 1 we scaled down the penalty term by D so this corresponds to β = 1000/(2562 × 3) ≈ 0.005 in Section 4) and n = 2000. The remaining training details are provided in Section F of the supplementary material. Baselines. The representative baseline methods we considered include: DwtDct (Al-Haj 2007), a traditional frequency-based method deployed by a popular generative model Stable Diffusion (Rombach et al. 2022); HiDDeN (Zhu et al. 2018), a widely used deep learning-based method; SSL (Fernandez et al. 2022), a watermarking method that optimizes the watermark for each image during embedding and typically achieves strong performance, while decoding the multi-bit message with inner products, which is similar to our decoding rule. Together, these baselines cover both traditional frequency-based and deep learning-based watermarking 23
methods, and represent competitive approaches commonly used in prior watermarking studies.
5.1
Competitive performance of ADD
For multi-bit watermarking, decoding performance is the primary quantity of interest. As shown in Table 1, our method achieves the best decoding performance (bit accuracy) under all distortion settings, while preserving a comparable quality (PSNR) with others. A qualitative comparison of image quality is shown in Figure 3, showing that our method maintains visual fidelity to the original image comparable to the competing methods.
rase
Gau
Rota
Crop
Ran
Aver ag
50.8 57.6 93.8
50.5 91.2 88.4
46.7 98.2 88.6
54.1 99.6 91.8
50.0 50.5 54.7
51.3 49.2 96.6
69.5 98.5 80.7
76.6 98.1 69.9
59.8 82.5 84.9
ADD (Ours)
32.36 ± 0.06
100.0
98.1
98.6
99.6
99.9
98.8
99.8
99.9
99.9
99.4
e
Con tras t
89.2 99.7 100.0
tion
Brig htne s
dom E
Nois
JPE G
37.22 ± 0.08 32.88 ± 0.05 33.09 ± 0.00
ssian
Gau
DwtDct HiDDeN SSL
ssian
PSNR
e
Method
Non
s
Blur
e
Table 1: Watermark decoding results. All methods are evaluated on the same 1000 randomly sampled image–message pairs from the MS-COCO test split. PSNR (dB, higher is better) is reported as mean ± standard error. Bit accuracy (%, higher is better) is reported in under each distortion setting. The Average column reports the mean bit accuracy across all distortion settings.
Figure 3: Qualitative comparison of image quality across watermarking methods. All methods are evaluated on the same image, with PSNR values reported. Our method is visually close to the original image, as the rest of the methods do. A visual comparison of the magnified pixel-wise differences is in Section G of the supplementary material.
24
Watermark detection is also evaluated as part of the performance. Among competing methods considered in this paper, there is no implementation that can detect an image without the assistance of a dictionary of embedded messages. Therefore, for these methods, detection is performed via a matching-bit test: given a decoded message m, declare an image as watermarked when the maximum number of matched bits with entries in the message dictionary D exceeds a threshold γ, i.e., when maxm∈D
PK
k=1
1{m̂k = mk } > γ. Our method,
on the other hand, can do detection either with or without a dictionary of embedded messages. The results in Table 2 show that our method achieves the strongest overall detection performance, as reflected by the highest average AUROC across distortions. Even without access to a message dictionary, our method substantially outperforms competing methods on average. When a dictionary D is available, our method further improves performance and yields the best overall detection results. The results of the receiver operating characteristic curve (ROC) are in Section H of the supplementary material.
Rota
Crop
Ran do
Aver ag
e
rase
Gau
mE
Con tras
tion
Nois
Brig
ssian
JPE
t
Gau
htne ss
PSNR
DwtDct HiDDeN SSL
37.05 32.82 33.09
88.0 100.0 100.0
49.8 48.4 99.6
50.0 97.6 95.9
50.5 99.2 92.1
52.7 99.9 95.8
49.8 50.0 50.4
49.8 49.5 99.9
54.9 99.9 81.4
69.0 99.3 55.3
57.2 82.6 85.6
ADD (w/o D) ADD (w/ D)
32.27
100.0 100.0
94.5 98.5
95.0 98.3
99.5 99.7
100.0 100.0
100.0 100.0
100.0 100.0
100.0 100.0
100.0 100.0
98.8 99.6
G
Method
Non e
ssian
Blur
e
Table 2: Watermark detection results. All methods are evaluated on the same 10,000 randomly sampled image–message pairs from the MS-COCO test split. PSNR (dB, higher is better) is reported as mean. AUROC (%, higher is better) is reported under each distortion setting. The Average column reports the mean AUROC across all distortion settings. DwtDct/HiDDeN/SSL use dictionary-based detection with dictionary D (dmin = 6) consisting of all 10,000 embedded 48-bit messages (threshold γ ∈ {0, . . . , 48} on best-match score). ADD (w/o D) uses the dictionary-agnostic statistic S (threshold sweep on S). ADD (w/ D) uses the dictionary-dependent statistic SD (threshold sweep on SD ).
25
5.2
Computational advantage of ADD
A side benefit of our method is its computational efficiency. As reported in Table 3, our approach is at least 2× faster at the embedding stage and 7.4× faster at the decoding stage than competing methods. This improvement arises from the simplicity of the underlying operations: embedding only requires linear addition of the watermark, while decoding reduces to computing inner products. In contrast, competing methods with comparable performance typically rely on more sophisticated computations or neural network–based processing, resulting in substantially higher runtime. Table 3: Runtime comparison of watermark embedding and decoding. We report average time per image (ms/image) ± standard error for the watermark embedding step (embedding a multi-bit watermark m into an image) and the decoding step (recovering the embedded bits m̂ from the watermarked image). All methods were evaluated on the same 1,000 images from the MS-COCO test split using a single NVIDIA A100 GPU. Standard errors are computed across processing batches (batch size 64), treating each batch’s per-image time as one observation.
5.3
Method
Embedding (ms/img)
Decoding (ms/img)
DwtDct HiDDeN SSL
8.37 ± 0.01 1.54 ± 0.01 546.50 ± 2.37
5.41 ± 0.01 1.41 ± 0.01 6.50 ± 0.00
ADD (Ours)
0.76 ± 0.01
0.19 ± 0.00
Generalizability to other datasets
Here we evaluate our watermark w1:K (trained with Algorithm 1 once using n = 2000 images from MS-COCO) on three other popular datasets, including ImageNet (Deng et al. 2009), CIFAR-10 and CIFAR-100 (Krizhevsky 2009). Overall, our watermark trained only on MS-COCO generalizes well to multiple unseen domains without retraining. Table 4 summarizes the result on MS-COCO (in-domain) and on out-of-domain datasets (ImageNet, CIFAR-10, and CIFAR-100), each with 1000 images. Across all datasets, decoding remains nearly perfect (≥ 99.27% bit accuracy) and detection 26
remains good (AUROC ≥ 0.9893). Note that on CIFAR-10 and CIFAR-100 ADD achieves higher PSNR due to up-sampling from 32 × 32 to 256 × 256, which yields smoother images. Table 4: Cross-dataset generalization. Our watermark is trained on MS-COCO only and evaluated on multiple test domains, each with 1000 images. We report PSNR (mean ± standard error), average bit accuracy, and average AUROC. Bit accuracy and AUROC are averaged over the performance under each distortion setting. See detailed per-distortion result in Section I of the supplementary material.
5.4
Test domain
PSNR (dB)
Avg Bit Accuracy
Avg AUROC
MS-COCO (in-domain) ImageNet CIFAR-10 CIFAR-100
32.36 ± 0.06 32.21 ± 0.07 36.16 ± 0.08 35.75 ± 0.09
99.37% 99.33% 99.37% 99.27%
0.9927 0.9893 0.9987 0.9978
Empirical trade-offs from β and n
Figure 4 illustrates how the empirical performance of ADD varies with the regularization parameter β and the training sample size n. Panel (a) in Figure 4 shows a clear trade-off from β between image quality and decoding performance. As β increases, PSNR increases while the average bit accuracy decreases. This is well aligned with the practical implication in Section 4.2.1: a larger β enforces stronger regularization, which leads to a smaller watermark magnitude r⋆ , and hence better image quality but weaker decoding performance. Panel (b) in Figure 4 shows that as n increases, the average bit accuracy improves substantially, while PSNR remains relatively stable when n ≥ 500. This is consistent with our finite-sample theory: larger n reduces the discrepancy between the finite-sample and population objectives, so the learned watermark is closer to its population counterpart. When n is small, this discrepancy is larger and the learned watermark is less reliable.
27
(a) Varying β.
(b) Varying sample size n.
Figure 4: Empirical trade-offs from β and n. Trade-off between PSNR and average bit accuracy from (a) different β values and (b) different training sample sizes n. In (a), n = 2000 and β ∈ {1, 10, 100, 500, 1000, 5000, 10000}. In (b), β = 1000 and n ∈ {10, 15, 20, 50, 100, 500, 1000, 2000}. The dashed red lines indicate acceptable thresholds chosen to reflect practical deployment requirements: PSNR = 32 dB in (a) and average bit accuracy = 0.99 in (b). The rest of the training setup is the same.
6
Conclusion
We propose ADD, a multi-bit image watermarking method that learns an additive watermark, embeds a K-bit message by linear combination, and performs detection and decoding using only inner products with the stored watermark. On MS-COCO, ADD achieves nearperfect decoding under common distortions while maintaining competitive visual quality, outperforming competing methods and offering substantially faster embedding and decoding due to its simple structure. We further provide a theoretical explanation for why ADD works. Under a low-dimensional subspace model for images, we show that the population objective yields watermark that is orthogonal to the image subspace and mutually orthogonal, which leads naturally to a generalized likelihood ratio test for detection and a corresponding decoding rule. We further establish that, for the finite-sample watermark, the FPRs, TPRs, and bit accuracy under the derived detection and decoding rules converge to their population
28
counterparts as the training sample size grows. We highlight two directions for future work. First, a natural next step would be to extend ADD for other modalities such as video, audio, and text, which will require modality-specific adjustments. Second, this paper assumes that the images are watermarked by only one watermarking mechanism. In reality, different entities may deploy different watermarking mechanisms, which will require a centralized allocation and verification of messages. We discuss our vision on this in Section B of the supplementary material, which points out a future direction for scaling provenance mechanisms and enabling accountable use of generative media in practical applications.
Use of Generative AI Tools During the preparation of this manuscript, the authors used ChatGPT-5.2 (OpenAI) and AgentLab (MorphMind) for language improvement and figure design, and Claude Opus 4.6 (Anthropic) for coding assistance. These tools were used only to improve clarity of writing, assist with programming, and support figure preparation. The authors reviewed and edited all outputs and take full responsibility for the content of this manuscript.
References Al-Haj, A. (2007), ‘Combined DWT-DCT digital image watermarking’, Journal of Computer Science 3(9), 740–746. Altun, H. O., Orsdemir, A., Sharma, G. & Bocko, M. F. (2009), ‘Optimal spread spectrum watermark embedding via a multistep feasibility formulation’, IEEE Transactions on Image Processing 18(2), 371–387. Publisher: IEEE. An, B., Ding, M., Rabbani, T., Agrawal, A., Xu, Y., Deng, C., Zhu, S., Mohamed, A., Wen,
29
Y., Goldstein, T. & Huang, F. (2024), WAVES: Benchmarking the robustness of image watermarks, in ‘Proceedings of the 41st International Conference on Machine Learning’. Ballé, J., Minnen, D., Singh, S., Hwang, S. J. & Johnston, N. (2018), Variational image compression with a scale hyperprior, in ‘International Conference on Learning Representations’. Chandra, B., Dunietz, J., Roberts, K., Lee, Y., Fontana, P. & Awad, G. (2024), Reducing risks posed by synthetic content: An overview of technical approaches to digital content transparency, Technical report, National Institute of Standards and Technology. Chen, B. & Wornell, G. W. (2001), ‘Quantization index modulation methods for digital watermarking and information embedding of multimedia’, Journal of VLSI signal processing systems for signal, image and video technology 27, 7–33. Cox, I. J., Kilian, J., Leighton, T. & Shamoon, T. (1996), Secure spread spectrum watermarking for images, audio and video, in ‘Proceedings of 3rd IEEE International Conference on Image Processing’, IEEE, pp. 243–246. Cox, I., Miller, M., Bloom, J., Fridrich, J. & Kalker, T. (2007), Digital Watermarking and Steganography, Morgan Kaufmann. Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K. & Li, F.-F. (2009), ImageNet: A largescale hierarchical image database, in ‘IEEE Conference on Computer Vision and Pattern Recognition’, pp. 248–255. Esser, P., Kulal, S., Blattmann, A., Entezari, R., Müller, J., Saini, H., Levi, Y., Lorenz, D., Sauer, A., Boesel, F., Podell, D., Dockhorn, T., English, Z. & Rombach, R. (2024), Scaling rectified flow transformers for high-resolution image synthesis, in ‘International Conference on Machine Learning’. Fernandez, P., Couairon, G., Jégou, H., Douze, M. & Furon, T. (2023), The Stable Signa30
ture: Rooting watermarks in latent diffusion models, in ‘2023 IEEE/CVF International Conference on Computer Vision’, pp. 22409–22420. Fernandez, P., Sablayrolles, A., Furon, T., Jégou, H. & Douze, M. (2022), Watermarking images in self-supervised latent spaces, in ‘ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)’, IEEE, pp. 3054–3058. Goodfellow, I., Bengio, Y. & Courville, A. (2016), Deep Learning, MIT Press. Google DeepMind (2025), ‘Veo 3: Latent diffusion for text-to-video and audio generation’, https://storage.googleapis.com/deepmind-media/veo/Veo-3-Tech-Report.pdf. Gunn, S., Zhao, X. & Song, D. (2025), An undetectable watermark for generative image models, in ‘International Conference on Learning Representations’. Hernandez, J. R., Amado, M. & PerezGonzalez, F. (2000), ‘DCT-domain watermarking techniques for still images: Detector performance analysis and a new structure’, IEEE Transactions on Image Processing 9(1), 55–68. Hoerl, A. E. & Kennard, R. W. (1970), ‘Ridge regression: Biased estimation for nonorthogonal problems’, Technometrics 12(1), 55–67. Jie, N. & Zhiqiang, W. (2009), A new public watermarking algorithm for RGB color image based on quantization index modulation, in ‘2009 International Conference on Information and Automation’, IEEE, pp. 837–841. Jovanović, N., Labiad, I., Soucek, T., Vechev, M. & Fernandez, P. (2025), Watermarking autoregressive image generation, in ‘Proceedings of the 39th International Conference on Neural Information Processing Systems’. Krizhevsky, A. (2009), Learning multiple layers of features from tiny images, Technical report,
31
University of Toronto. https://www.cs.toronto.edu/~kriz/learning-features-2009-TR.pdf. Li, X., Ruan, F., Wang, H., Long, Q. & Su, W. J. (2025a), ‘Robust detection of watermarks for large language models under human edits’, Journal of the Royal Statistical Society Series B: Statistical Methodology p. qkaf056. Li, X., Ruan, F., Wang, H., Long, Q. & Su, W. J. (2025b), ‘A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules’, The Annals of Statistics 53(1), 322 – 351. Lin, T.-Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollár, P. & Zitnick, C. L. (2014), Microsoft COCO: Common objects in context, in ‘Computer Vision – ECCV 2014’, Vol. 8693 of Lecture Notes in Computer Science, Springer, Cham, pp. 740–755. Lin, Y. (2004), ‘A note on margin-based loss functions in classification’, Statistics & Probability Letters 68(1), 73–82. Lipman, Y., Chen, R. T. Q., Ben-Hamu, H., Nickel, M. & Le, M. (2023), Flow matching for generative modeling, in ‘International Conference on Learning Representations’. Liu, T. & Moulin, P. (2003a), Error exponents for one-bit watermarking, in ‘2003 IEEE International Conference on Acoustics, Speech, and Signal Processing, 2003. Proceedings.’, Vol. 3, pp. III–65. Liu, T. & Moulin, P. (2003b), ‘Error exponents for watermarking game with squared-error constraints’, IEEE International Symposium on Information Theory - Proceedings p. 190. Moulin, P. (2001), ‘The role of information theory in watermarking and its application to image watermarking’, Signal Processing 81(6), 1121–1139. Moulin, P. & O’Sullivan, J. (2000), Information-theoretic analysis of watermarking, in ‘2000
32
IEEE International Conference on Acoustics, Speech, and Signal Processing.’, Vol. 6, pp. 3630–3633 vol.6. Moulin, P. & O’Sullivan, J. (2003), ‘Information-theoretic analysis of information hiding’, IEEE Transactions on Information Theory 49(3), 563–593. Navas, K. A., Ajay, M. C., Lekshmi, M., Archana, T. S. & Sasikumar, M. (2008), DWTDCT-SVD based watermarking, in ‘2008 3rd International Conference on Communication Systems Software and Middleware and Workshops (COMSWARE ’08)’, pp. 271–274. Nikolaidis, N. & Pitas, I. (1998), ‘Robust image watermarking in the spatial domain’, Signal Processing 66(3), 385–403. O’Ruanaidh, J. & Pun, T. (1997), Rotation, scale and translation invariant digital image watermarking, in ‘Proceedings of International Conference on Image Processing’, Vol. 1, pp. 536–539 vol.1. Pope, P., Zhu, C., Abdelkader, A., Goldblum, M. & Goldstein, T. (2021), The intrinsic dimension of images and its impact on learning, in ‘International Conference on Learning Representations’. Rombach, R., Blattmann, A., Lorenz, D., Esser, P. & Ommer, B. (2022), ‘High-resolution image synthesis with latent diffusion models’, 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition pp. 10674–10685. Sag, M. (2023), ‘Copyright safety for generative AI’, Houston Law Review 61(2), 295–347. Sander, T., Fernandez, P., Durmus, A. O., Furon, T. & Douze, M. (2025), Watermark anything with localized messages, in ‘International Conference on Learning Representations’. Sion, R. & Atallah, M. (2004), Attacking digital watermarks, in ‘Security, Steganography,
33
and Watermarking of Multimedia Contents VI’, Vol. 5306, pp. 848 – 858. Tancik, M., Mildenhall, B. & Ng, R. (2020), Stegastamp: Invisible hyperlinks in physical photographs, in ‘Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition’, pp. 2117–2126. van Schyndel, R. G., Tirkel, A. Z. & Osborne, C. F. (1994), ‘A digital watermark’, Proceedings of 1st International Conference on Image Processing 2, 86–90 vol.2. Verdoliva, L. (2020), ‘Media Forensics and DeepFakes: An overview’, IEEE Journal of Selected Topics in Signal Processing 14(5), 910–932. Wen, Y., Kirchenbauer, J., Geiping, J. & Goldstein, T. (2023), Tree-rings watermarks: Invisible fingerprints for diffusion images, in ‘Proceedings of the 37th International Conference on Neural Information Processing Systems’. Willems, F. (2000), An informationtheoretical approach to information embedding, in ‘Proceedings of the 21st Symposium on Information Theory in the Benelux, May 25-26, Wassenaar, The Netherlands’, pp. 255–260. Xian, X., Wang, G., Bi, X., Srinivasa, J., Kundu, A., Hong, M. & Ding, J. (2024), RAW: A robust and agile plug-and-play watermark framework for AI-generated images with provable guarantees, in ‘Proceedings of the 38th International Conference on Neural Information Processing Systems’. Xie, Y., Li, X., Mallick, T., Su, W. & Zhang, R. (2025), ‘Debiasing watermarks for large language models via maximal coupling’, Journal of the American Statistical Association 120(551), 1424–1436. Yang, Z., Zeng, K., Chen, K., Fang, H., Zhang, W. & Yu, N. (2024), Gaussian Shading:
34
Provable performance-lossless image watermarking for diffusion models, in ‘2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition’, pp. 12162–12171. Zhang, L., Rao, A. & Agrawala, M. (2023), Adding conditional control to text-to-image diffusion models, in ‘2023 IEEE/CVF International Conference on Computer Vision’, pp. 3813–3824. Zhong, X., Das, A., Alrasheedi, F. & Tanvir, A. (2023), ‘A brief, in-depth survey of deep learning-based image watermarking’, Applied Sciences 13(21). Zhu, J., Kaplan, R., Johnson, J. & Fei-Fei, L. (2018), HiDDeN: Hiding data with deep networks, in ‘Proceedings of the European Conference on Computer Vision’, pp. 657–672. Zou, H. & Hastie, T. (2005), ‘Regularization and variable selection via the Elastic Net’, Journal of the Royal Statistical Society Series B: Statistical Methodology 67(2), 301–320.
35