betaFeedback

WorksComputer Science

Provably Secure Diffusion Watermarking Against Removal Adversaries with Batched Detector Access

Abstract

Recent latent-based watermarking methods can embed undetectable watermarks into AI-generated content. However, these approaches are vulnerable to removal attacks as their watermark detection boundaries are exposed, prompting the use of secret long-term transformations to hide these boundaries. We show that such defenses are insecure under a stronger threat model motivated by publicly reachable detectors: an adversary with batched detector access can reconstruct the transformations, permanently re-exposing the decision boundary. To address this, we propose a watermarking scheme based on a hybrid of long-term and one-time secret transformations, which prevents the reuse of structure across samples and keeps the long-term secret hidden. Besides undetectability, we show that this scheme is provably secure against removal adversaries with batched detector access, in the sense that no probabilistic polynomial-time adversary can achieve a non-negligible advantage over an adversary restricted to adding isotropic white-noise with a 2×\sqrt{2}\times larger perturbation budget, and we show this 2\sqrt{2} factor to be tight. Evaluations on Stable Diffusion 2.1 and XL demonstrate the attack against the existing defense, and show that our scheme preserves generation quality and withstands common perturbations and targeted removal attacks.

Introduction

The remarkable quality of Latent Diffusion Models (LDMs) has raised significant provenance and misuse concerns, driving interest in watermarking AI-generated content (AIGC) [1]. Notably, [2] proposed the notion of undetectability in latent-based watermarks, ensuring no polynomial-time algorithm can distinguish between watermarked and unwatermarked content.

However, recent work [3] demonstrated that watermark undetectability does not guarantee unremovability. Undetectability only ensures that watermarked and unwatermarked samples are indistinguishable, but it does not conceal the detector’s decision boundary (e.g. the sign patterns of the individual latents in the PRC watermark [2], exploited in [3]). Thus, an adversary holding a known watermarked sample can perturb it directly toward this exposed boundary with small perturbations. In response, a boundary-hiding defense was proposed [3] using a secret long-term transformation, with a proof that no polynomial-time removal attack outperforms adding random white-noise, under the assumption of a passive adversary, i.e. who observes watermarked samples but has no detector access.

The passive adversary assumption was reasonable when watermark detectors were not publicly reachable, which may not reflect current deployment settings. For example, Google’s SynthID [4], which watermarks Gemini’s AIGC, already permits public detector access [5], with an announced detection API [6] that would enable batched queries. Detectors may also be reverse-engineered, e.g. reverse-SynthID [7], a popular open-source approximation of the SynthID detector. Nor is this an isolated development. Driven in part by the EU AI Act’s transparency requirements [8], other providers are following suit; Anthropic, for example, has announced a detection API for its text watermarks [9]. This suggests that publicly reachable detectors will become the norm across modalities. Thus, a defense proved secure only against a passive adversary offers no guarantee once this access exists, regardless of how that access is provisioned (e.g. a public API, a reverse-engineered proxy, or a leaked detector).

In this work, we present an attack on the boundary-hiding defense under this stronger, more realistic threat model, i.e., a watermark removal adversary with batched (non-adaptive) detector access, which we call REM2 (REM1 corresponds to the passive adversary in [3]). We focus on batched rather than adaptive access for two reasons. First, batched queries reflect realistic deployment conditions: public detection APIs are typically rate-limited per account, but a non-adaptive query set can be parallelized across accounts and time, whereas an adaptive strategy is inherently sequential. Second, as we show, batched access already suffices to break the existing defense. (We discuss the adaptive analogue, REM3, in § 9-C.)

Lifting REM1 to REM2 is not a hypothetical strengthening: we demonstrate how a REM2 adversary can fully break the boundary-hiding defense by recovering the secret long-term transformation, thereby re-exposing the detector’s decision boundaries permanently. As the transformation is long-term, this one-time recovery cost is amortized across all future attacks, constituting a complete break of the defense. The extension from REM1 to REM2 is analogous in spirit to the upgrade from IND-CPA to IND-CCA1 in encryption: an adversary gains oracle access to a secret-keyed algorithm, and an IND-CPA-secure scheme is not necessarily IND-CCA1-secure.

We approach watermark removal from the standpoint of provable security. Similar to certified robustness against adversarial attacks [10], we seek guarantees that hold against an entire class of adversaries rather than fixed attacks. Since our adversary queries the detector to learn the hidden decision boundary, security is a question of boundary secrecy rather than geometry, and is naturally studied through a cryptographic lens. Concretely, we (i) formalize detection and removal adversaries via explicit security games (IND0/IND1 and REM1/REM2, respectively); (ii) prove an information-theoretic guarantee for an idealized instantiation (Theorem 1); and (iii) lift it to a computational guarantee for the deployed construction via standard cryptographic primitives (Theorem 2). Unlike prior schemes, which assume a passive adversary [3] or guarantee only undetectability [11, 2], we formally prove removal security against an adversary with batched detector access, via cryptographic reduction rather than a certified-radius argument.

Our construction combines a long-term and a one-time transformation. Inspired by hybrid encryption, where a long-term public-key scheme exchanges a one-time session key, our scheme generates a fresh one-time transformation per sample. This dynamically obfuscates the detector’s decision boundary, while the long-term transformation hides the per-sample nonce and is used during detection to retrieve it (Figure 1). Because the effective transformation is fresh per sample and its orientation hidden, any adversarial perturbation is rendered independent of the transformation. Our worst-case security analysis proves that an adversary can at best match an isotropic white-noise adversary with a 2×\sqrt{2}\times larger budget, and we show this constant is tight.

Flowchart of Sample

Figure 1. Flowchart of Sample⁡(λ,d,k)\operatorname{Sample}(\lambda,d,k) (Algorithm 2), for sampling watermarked latents. The scheme leverages fresh randomness rr to derive a unique one-time transformation for each sample. In the hybrid transformation, this one-time transformation dynamically obfuscates the detector’s decision boundary, while the long-term secret transformation AA securely hides the per-sample random nonce rr.

Our empirical evaluation focuses on three key aspects. First, we demonstrate that our proposed attack enables an adversary with batched detector access to successfully recover the secret transformation, thereby re-exposing the detection boundary. Second, we show that our latent-based watermark integrates seamlessly into existing LDM pipelines while preserving high image quality. Third, we verify our scheme’s robustness against common benign perturbations, such as Gaussian noise and JPEG compression, regeneration attacks [12], as well as against the targeted removal attack specifically designed for undetectable latent-based watermarks proposed in [3].

Our central contribution is a provably secure watermarking scheme, developed as follows:

  1. A formal threat model for latent-based watermarks is introduced, unifying detectability and removability notions that prior work treats only implicitly (Section III-A).

  2. An attack against boundary hiding [3] is demonstrated under the REM2 threat model, showing how an adversary can successfully recover the underlying long-term secret transformation employed in the existing boundary-hiding defense (Section IV-C).

  3. A provably secure latent-based watermarking construction. Under the REM2 threat model, no PPT adversary removes the watermark with non-negligible advantage over a white-noise baseline granted a 2×\sqrt{2}\times larger perturbation budget (Theorems 1 & 2).

  4. Empirical evaluations demonstrate the proposed attack, verify that the new watermarking scheme preserves high image quality, and measure the overall robustness of the framework (Section VII).

Background

Latent Diffusion Model

A typical latent diffusion model (LDM) (e.g. Stable Diffusion [13]), consists of two main components: (1) a denoising model (e.g., DDIM [14], DDPM [15]), and (2) variational autoencoder (VAE) [16]. The model takes as input: (1) a text prompt, (2) generation hyperparameters (e.g., the number of timesteps), and (3) a random latent vector sampled from the VAE latent space.

At a high level, the generative process is as follows: First, the input text prompt is converted into a text embedding using a text encoder (e.g. CLIP [17]). Next, a randomly sampled starting point is iteratively denoised by the diffusion model, conditional on the text embedding and generation hyperparameters. Finally, the denoised latent representation is decoded by the VAE decoder into the pixel space.

For analysis, let us define the LDM as a deterministic function L:C×Lv→LpL:\mathcal{C}\times\mathcal{L}_{v}\to\mathcal{L}_{p} that takes as input the following: (1) a condition c∈Cc\in\mathcal{C}, and (2) a starting point s∈Lvs\in\mathcal{L}_{v}, sampled from some distribution D\mathcal{D}. The LDM outputs the generated image in the pixel space Lp\mathcal{L}_{p}. That is, conditional on condition cc (i.e. prompt and meta-parameters) and a randomly sampled starting point ss, the output of the LDM is L(c,s)∈LpL(c,s)\in\mathcal{L}_{p}. In Stable Diffusion (SD), D=N(0,Id)\mathcal{D}=\mathcal{N}(0,I_{d}). The output space Lv\mathcal{L}_{v} is a real valued dd-dimensional vector space, where d=4×64×64=16,384d=4\times64\times64=16,384 and d=4×128×128=65,536d=4\times128\times128=65,536 in SD1.5/2.1 and SDXL respectively. Furthermore, the LL typically admits an approximate inversion function L−1:Lp×C→LvL^{-1}:\mathcal{L}_p \times\mathcal{C} \to\mathcal{L}_v. That is, given a condition c∈Cc \in\mathcal{C} and an image I=L(s,c)∈LpI=L(s,c)\in\mathcal{L}_p in the pixel domain, the inverse mapping s^=L−1(I,c)∈Lv\hat{s}=L^{-1}(I,c)\in\mathcal{L}_v outputs an approximation of the original latent ss. Recent work (e.g. [18], [19]) has focused on improving the quality of such inversion procedures, showing that s^\hat{s} can be constructed with small reconstruction error even when the exact cc is unknown.

Latent-Based Watermarking

Latent-based watermarking schemes typically involve two distributions: an underlying distribution D\mathcal{D} and a keyed watermarked distribution Dk\mathcal{D}_k, where kk is a secret key known only to the watermark owner. The procedures for generating watermarked samples and detecting watermarks are as follows.

a) Generation: Instead of sampling the initial latent from D\mathcal{D}, the starting point ss is sampled from the keyed watermarked distribution Dk\mathcal{D}_k. That is, given a condition c∈Cc\in\mathcal{C}, the watermarked output is Iw=L(s,c)I_w=L(s,c), where s∼Dks\sim\mathcal{D}_k.

b) Detection: Given an image II generated by the LDM, an approximate latent starting point s^\hat{s} is recovered via the inversion s^=L−1(I,c∗)\hat{s}=L^{-1}(I,c_*), where c∗c_* is the inversion condition. In practical settings, the exact generation condition may be unknown; thus, one often sets c∗=∅c_*=\varnothing (the null prompt). Empirical evidence from recent work suggests that even under the null prompt, s^\hat{s} remains close to the original ss.

Undetectability: Some latent-based watermarks (e.g., Tree-Ring watermark [20]) are detectable, meaning an adversary with access to polynomial samples from the watermarked distribution Dk\mathcal{D}_k can reliably distinguish a new watermarked sample from the original distribution D\mathcal{D}. There are various notions of undetectability, depending on the threat model, described in the IND0 and IND1 games in Section III-A.

Pseudorandom Error Correcting Codes

Pseudorandom Error-Correcting (PRC) codes [21] are used as cryptographic primitives to construct undetectable watermarks. It consists of two components: an encoder and decoder.

a) Encoder: The encoder Enc⁡:{0,1}n×{0,1}n1→{0,1}n2\operatorname{Enc}:\{0,1\}^n\times\{0,1\}^{n_1}\to\{0,1\}^{n_2} is a probabilistic algorithm, which takes in a nn-bit key kk and a n1n_1-bit message mm respectively, and outputs a codeword of length n2n_2. The output is pseudorandom in the sense that, for any kk and mm, Enc⁡(k,m)\operatorname{Enc}(k,m) is computationally indistinguishable from a truly random binary sequence for any PPT adversary who does not know kk.

b) Decoder: The decoder Dec⁡:{0,1}n×{0,1}n2→{0,1}n1∪{⊥}\operatorname{Dec}:\{0,1\}^n\times\{0,1\}^{n_2}\to\{0,1\}^{n_1}\cup\{\perp\} takes in a nn-bit key and n2n_2-bit codeword, and outputs the mm-bit watermark message, or ⊥\perp if the decoding failed. The scheme is error-correcting in the sense that if c=Enc⁡(m,k)c=\operatorname{Enc}(m,k), there exists a τ\tau s.t.

dH(c,c^)≤τ⇒Dec⁡(k,c^)=m,d_H(c,\hat{c})\leq\tau\Rightarrow\operatorname{Dec}(k,\hat{c})=m,

where dHd_H denotes the Hamming distance, and τ\tau depends on the parameters of the PRC scheme. That is, as long as the number flips between the PRC codeword cc and c^\hat{c} does not exceed τ\tau, the decoder correctly recovers the message mm.

Relationship with PRC Watermarking Scheme [2]

Consistent with existing implementations, let D=N(0,Id)\mathcal{D}=\mathcal{N}(0,I_d). Conditional on a secret key kk and watermark message mm, the PRC latent-based watermarking scheme samples from Dk\mathcal{D}_k as follows:

  1. Sample x=(x1,…,xd)∼N(0,Id)x=(x_1,\ldots,x_d)\sim\mathcal{N}(0,I_d) and compute the codeword c=(c1,…,cd)=Enc⁡(k,m)c=(c_1,\ldots,c_d)=\operatorname{Enc}(k,m).

  1. For i=1,…,di=1,\ldots,d, set

xi={∣xi∣,if ci=1,−∣xi∣,if ci=0.x_i= \begin{cases} |x_i|, & \text{if }c_i=1,\\ -|x_i|, & \text{if }c_i=0. \end{cases}
  1. Output xx.

Similarly, to detect the PRC watermark in a sample s=(s1,…,sd)s=(s_1,\ldots,s_d):

  1. Recover the codeword c=(c1,…,cd)c=(c_1,\ldots,c_d), where ci=1(si≥0)c_i=1(s_i\geq0)

  1. Perform decoding and recover m^=Dec⁡(k,c)\hat{m}=\operatorname{Dec}(k,c).

  1. Declare ss as watermarked if and only if m^=m\hat{m}=m.

It can be shown that, if cc is pseudorandom (i.e. computationally indistinguishable from a random binary sequence), then xx is computationally indistinguishable from N(0,Id)\mathcal{N}(0,I_d).

Boundary-Hiding Defense

In latent-based watermarking, [3] showed that undetectability alone does not guarantee unremovability. Specifically, even if D\mathcal{D} and Dk\mathcal{D}_k are computationally indistinguishable, an adversary may still be able to deduce the decision boundary of the detector O\mathcal{O}. In a known-watermark attack, an adversary perturbs a known watermarked latent s∼Dks\sim\mathcal{D}_k into an unwatermarked state s~\tilde{s} such that:

O(s~)=0andd(s,s~) is small,\mathcal{O}(\tilde{s})=0 \quad\text{and}\quad d(s,\tilde{s})\text{ is small},

for some distance metric d(⋅,⋅)d(\cdot,\cdot). To mitigate this, [3] proposed a boundary-hiding defense that masks the decision boundary via a secret linear transformation. Specifically, consider the transformation T(s)=sAT(s)=sA, where A∈Rd×dA\in\mathbb{R}^{d\times d} is a secret, invertible orthonormal matrix. During detection, a received latent s′s' is first inverted via T−1(s′)T^{-1}(s') before watermark decoding. Since the adversary does not know AA, O\mathcal{O}’s decision boundary is hidden. [3] showed that a watermark removal adversary with a polynomial number of watermarked samples (without detector access) cannot outperform an adversary limited to adding white-noise.

Summary of Notations Used

For convenience, notations introduced throughout this paper (both introduced earlier and later), are summarized in Table I.

NotationDescription
L,L−1L,L^{-1}LDM generation and inversion functions
C,Lv,Lp\mathcal{C},\mathcal{L}_v,\mathcal{L}_pCondition, latent (Rd\mathbb{R}^d), and pixel spaces
D,Dk\mathcal{D},\mathcal{D}_kBase and watermarked latent distributions
O(⋅)\mathcal{O}(\cdot)Watermark detector oracle
AALong-term secret transformation (Rd×d\mathbb{R}^{d \times d})
BiB_iOne-time transformation (Rd2×d2\mathbb{R}^{\frac{d}{2} \times\frac{d}{2}}) for sample ii
Λi\Lambda_iEffective hybrid transformation for sample ii
PRCPseudorandom error-correcting code
τ1,τ2\tau_1,\tau_2Error tolerance thresholds
dH(⋅,⋅)d_H(\cdot,\cdot)Hamming distance metric
A,AdvA,\mathsf{Adv}PPT adversary and its advantage

Table I. Summary of notations used throughout the paper.

Problem Setup

Let I=L(e,s)I=L(e,s) denote the output of a LDM LL with conditioning ee and initial latent ss. In latent-based watermarking, ss is sampled from a watermarked distribution Dk\mathcal{D}_k parameterized by a secret key kk. There are 3 phases involved: Setup, Sample, Detect.

a) Setup: During the setup phase, the system generates the relevant keys kk, which parameterize the watermarked distribution Dk\mathcal{D}_k.

b) Sample: To generate a watermarked image, an embedding ee and starting point s∼Dks \sim\mathcal{D}_k, is provided as input to LL. The model then outputs the generated image I=L(e,s)I=L(e,s).

c) Detect: To detect watermark in an image, diffusion inversion is performed on the image to approximate ss, denoted as s^\hat{s}, which is then passed into a watermark detector O:Rd→{0,1}\mathcal{O}:\mathbb{R}^d \rightarrow\{0,1\}. The detector outputs O(s^)=1(s^∼Dk)\mathcal{O}(\hat{s})=1(\hat{s}\sim\mathcal{D}_k)

Threat Model

The adversary’s primary goals are watermark detection and removal. While some prior work relies on implicit security assumptions, we formalize the adversary’s capabilities into an explicit hierarchy of threat models to provide a unified evaluation framework. Higher indices denote stronger adversaries:

  1. Watermark Detectability: IND0, IND1

  1. Watermark Removal: REM1, REM2

Table II summarizes these threat models, which are formally defined here. In this paper, we consider schemes which achieve at least IND0-security (single-sample indistinguishability), thus excluding detectable watermarking schemes (e.g. Tree-Ring [20]).

Threat ModelWorkGoal1 Sample>1 SamplesDetector Access
IND0GSUndetectability (Single Sample)✓××
IND1PRC, GS++, BH, OursUndetectability (Polynomial Samples)✓✓×
REM1BHUnremovability (Polynomial Samples)✓✓×
REM2OursUnremovability (Polynomial Samples + Batched Detector Access)✓✓✓

Table II. Comparison of threat models and adversary capabilities between prior undetectable latent-based watermarking schemes (Gaussian Shading (GS) [11], GS++ [22], PRC watermark [2], and boundary-hiding (BH) [3] defense) and our proposed construction. Compare to BH defense which achieves IND1-REM1 security, our scheme achieves IND1-REM2 security.

1) IND0: Single Sample Indistinguishability: Given a watermark distribution Dk\mathcal{D}_k parameterized by a secret key kk and a target distribution D\mathcal{D}:

  1. The challenger uniformly samples b←{0,1}b\leftarrow\{0,1\}.

  1. If b=0b=0, the challenger outputs a sample from Dk\mathcal{D}_k. Else, the challenger outputs a sample from D\mathcal{D}.

After receiving the sample, a distinguisher guesses the value of bb, outputs a guess b′b', and wins if and only if b′=bb'=b. A scheme is IND0-secure if for all PPT distinguishers:

∣Pr⁡[b′=b]−12∣≤negl⁡(λ)\left|\Pr[b'=b]-\frac{1}{2}\right|\leq\operatorname{negl}(\lambda)

where negl⁡(⋅)\operatorname{negl}(\cdot) is a negligible function.

2) IND1: Multiple Sample Indistinguishability: IND1 is an extension of IND0 from 1 sample to polynomial number of samples, described as follows. Given a watermark distribution Dk\mathcal{D}_k parameterized by a secret key kk and a target distribution D\mathcal{D}:

  1. The challenger uniformly samples b←{0,1}b\leftarrow\{0,1\}.

  1. The adversary submits an integer tt to the challenger, where tt is bounded by a polynomial in the security parameter λ\lambda.

  1. The challenger sends tt unwatermarked samples sampled independently from D\mathcal{D}, and tt watermarked samples sampled independently from Dk\mathcal{D}_k

  1. If b=0b=0, the challenger outputs a sample sampled independently from Dk\mathcal{D}_k. Else, the challenger outputs a sample sampled independently from D\mathcal{D}.

A scheme is IND1-secure, if for all PPT distinguishers:

∣Pr⁡[b′=b]−12∣≤negl⁡(λ)\left|\Pr[b'=b]-\frac{1}{2}\right|\leq\operatorname{negl}(\lambda)

where negl⁡(⋅)\operatorname{negl}(\cdot) is a negligible function.

3) REM1: Known-Watermark Attack: Unlike the earlier games, REM1 deals with removal attacks. Consider the following security game:

  1. The adversary receives a collection of watermarked and unwatermarked samples YwY_w and YnwY_{nw}, sampled independently from Dk\mathcal{D}_k and D\mathcal{D} respectively. ∣Yw∣|Y_w| and ∣Ynw∣|Y_{nw}| are polynomial in λ\lambda.

  1. The adversary is given a fresh sample Y∼DkY\sim\mathcal{D}_k.

  1. The adversary computes a perturbed sample Y′=Y+ηY'=Y+\eta subject to a distortion budget σ\sigma and passes it to the challenger

  1. The challenger outputs O(Y′)\mathcal{O}(Y')

Let Aw(Y,σ)\mathcal{A}_w(Y,\sigma) denote a baseline algorithm that outputs a perturbed sample by adding randomly sampled white-noise of magnitude σ\sigma to YY. Let A(Y,Yw,Ynw,σ)\mathcal{A}(Y,Y_w,Y_{nw},\sigma) denote a PPT adversary that observes YwY_w and YnwY_{nw}, and outputs a perturbed sample by adding a computed perturbation of magnitude at most σ\sigma to YY. A scheme is cc-REM1-secure for constant c≥1c\geq1 iff for all PPT adversaries A\mathcal{A} and all valid perturbation budgets σ>0\sigma>0:

Pr⁡[O(A(Y,Yw,Ynw,σ))=0]−Pr⁡[O(Aw(Y,cσ))=0]≤negl⁡(λ)\Pr[\mathcal{O}(\mathcal{A}(Y,Y_w,Y_{nw},\sigma))=0]-\Pr[\mathcal{O}(\mathcal{A}_w(Y,c\sigma))=0]\leq\operatorname{negl}(\lambda)

where negl⁡(⋅)\operatorname{negl}(\cdot) is a negligible function.

4) REM2: Chosen Noise Attack + Batch Detector Access: This threat model extends REM1 by granting the adversary batched oracle access to the detector O\mathcal{O}. In this scenario, the adversary has access to a polynomial number of watermarked samples Y={Y1,…,Yt}Y=\{Y_1,\ldots,Y_t\} and can issue a polynomial number of queries to the detector to observe its decision boundary. This is formalized in the following security game:

  1. The adversary receives a collection of watermarked and unwatermarked samples YwY_w and YnwY_{nw}, sampled independently from Dk\mathcal{D}_k and D\mathcal{D} respectively. ∣Yw∣|Y_w| and ∣Ynw∣|Y_{nw}| are polynomial in λ\lambda.

  1. The adversary submits a sequence of ss queries q1,…,qsq_1,\ldots,q_s to the detector oracle O\mathcal{O}, where ss is bounded by a polynomial in λ\lambda.

  1. The challenger returns the detector outputs O(q1),…,O(qs)\mathcal{O}(q_1),\ldots,\mathcal{O}(q_s).

  1. The adversary is given a fresh watermarked sample Y∼DkY\sim\mathcal{D}_k.

  1. The adversary outputs a perturbed sample Y′=Y+ηY'=Y+\eta

  1. Challenger outputs O(Y′)\mathcal{O}(Y')

Let Aw(Y,σ)\mathcal{A}_w(Y,\sigma) denote a baseline algorithm that outputs a perturbed sample by adding randomly sampled white-noise of magnitude σ\sigma to YY, and let AO(Y,Y,σ)\mathcal{A}^{\mathcal{O}}(Y,Y,\sigma) denote a PPT adversary with oracle access to O\mathcal{O} that outputs a perturbed sample by adding a computed perturbation of magnitude at most σ\sigma to YY. A watermarking scheme cc-REM2-secure for constant c≥1c \ge1, iff for all PPT adversaries AO\mathcal{A}^{\mathcal{O}}, Y∼DkY \sim\mathcal{D}_k and σ>0\sigma> 0:

Pr⁡[O(AO(Y,Y,σ))=0]−Pr⁡[O(Aw(Y,cσ))=0]≤negl⁡(λ)\Pr[\mathcal{O}(\mathcal{A}^{\mathcal{O}}(Y,Y,\sigma))=0]-\Pr[\mathcal{O}(\mathcal{A}_w(Y,c\sigma))=0]\leq\operatorname{negl}(\lambda)

where negl⁡(⋅)\operatorname{negl}(\cdot) is a negligible function

Attacks on Existing Undetectable Latent-Based Watermarking Schemes

Attack on Gaussian Shading Watermark

Gaussian Shading (GS) theoretically achieves IND1 security by employing a stream cipher initialized with a secret key and a random nonce. Provided this nonce is randomly sampled for every watermarked sample generation, the resulting sequence is computationally indistinguishable from N(0,Id)\mathcal{N}(0,I_d).

However, to circumvent the prohibitive computational cost of exhaustive nonce searching during verification, practical GS deployments frequently rely on a restricted nonce pool or static session nonces. An adversary who intercepts a polynomial number of watermarked samples generated with reused nonces can successfully distinguish between watermarked and unwatermarked distributions [2, 23]. This breaks IND1 security, and the scheme is only IND0-secure.

Attack on PRC Watermark

Recent work [3] proves that IND1 security does not imply REM1 security by demonstrating a “known-watermark attack” against the PRC scheme. Specifically, the PRC watermark exposes its decision boundary to adversaries by directly embedding the codeword into the signs of the starting latent vector. Consequently, an adversary with a restricted perturbation budget σ\sigma can strategically flip the signs of the latent components with the smallest magnitudes. This targeted approach achieves a non-negligible advantage over a baseline adversary restricted to adding white-noise of equivalent magnitude σ\sigma. This removal strategy also generalizes to GS++, as both schemes inadvertently leak their watermark detection boundaries through similar underlying detector mechanisms.

Proposed Attack on Boundary-Hiding Defense

The boundary-hiding defense detailed in Section II-D is designed to obscure the watermark detector’s decision boundary, which mitigates the known-watermark attack outlined in Section IV-B. However, if an adversary recovers or sufficiently approximates the transformation matrix AA, the decision boundary is re-exposed, which reduces back to the known-watermark attack setting.

Under the REM2 threat model, we describe an algorithm to approximate AA. Let Y=T(X)=XAY=T(X)=XA be a watermarked sample, and let τ\tau be the detector’s threshold (as described in Section II-C). Because the decision boundary is an intersection of hyperplanes defined by the orthonormal rows of AA, the attack aims to isolate the normal vectors to these bounding hyperplanes using filtered random noise.

  1. Noise Magnitude Calibration. The adversary first determines a target perturbation scale σ\sigma designed to push the watermarked sample just past the decision boundary with a small, controlled probability of evasion. For a detector with a sign-flip threshold τ\tau, this target magnitude scales proportionally to tan⁡(πτ)\tan(\pi\tau).

  • For G∼N(0,Id)G \sim\mathcal{N}(0,I_d) and H∼N(0,σ2Id)H \sim\mathcal{N}(0,\sigma^2 I_d), where both GG and HH are independent, it can be shown that setting σ=tan⁡(πτ)\sigma=\tan(\pi\tau) guarantees that the expected proportion of sign flips between GG and G+HG+H is exactly τ\tau.

  • Because the latent dimension dd is typically very large, the empirical proportion of sign flips tightly concentrates around its expected value τ\tau with high probability.

  1. Probing. The adversary generates a massive batch of NN random noise vectors ηi∼N(0,σ2I)\eta_i \sim\mathcal{N}(0,\sigma^2 I). The adversary adds these to the watermarked sample and queries the oracle for the entire batch simultaneously: oi=O(Y+ηi)o_i=\mathcal{O}(Y+\eta_i).

  1. Boundary-Crossing Filtration. The adversary retains only the perturbations that successfully evaded the detector, which is the set E={ηi∣O(Y+ηi)=0}\mathcal{E}=\{\eta_i \mid\mathcal{O}(Y+\eta_i)=0\}. Geometrically, E\mathcal{E} represents the collection of perturbations possessing sufficiently large projections onto at least ⌈d⌉\lceil d\rceil rows of AA. Filtering out non-evading vectors physically truncates the Gaussian noise cloud, skewing its principal directions of variance outward along the normal vectors of these active hyperplanes.

  1. Independent Component Analysis (ICA). The

adversary applies ICA to the mean-centered matrix of E\mathcal{E} to compute V={v1,…,vd}\mathcal{V} = \{v_1,\ldots,v_d\}. By maximizing non-Gaussianity, ICA isolates the statistically independent components responsible for the large projections within E\mathcal{E}. These extracted vectors viv_i serve as approximations of the individual orthonormal rows of the secret matrix AA.

1) Number of Queries Needed: In Step 4, the adversary applies ICA to E\mathcal{E}, thus the number of queries to O\mathcal{O} is lower bounded by ∣E∣|\mathcal{E}|. We establish a lower bound of ∣E∣|\mathcal{E}| by appealing to Theorem 2.4 of [24], which gives the following information-theoretic result: Any PPT algorithm requires ∣E∣∈Ω(d2/polylog⁡(d))|\mathcal{E}| \in\Omega(d^2/\operatorname{polylog}(d)) to successfully unmix the independent components of AA. In other words, if ∣E∣∈o(d2/polylog⁡(d))|\mathcal{E}| \in o(d^2/\operatorname{polylog}(d)), an adversary can at most recover ARAR, where R∼Haar(d)R \sim Haar(d) is a randomly sampled d×dd \times d orthonormal matrix. Since AA and ARAR share the same Haar(d)Haar(d) distribution, the adversary gains no meaningful information regarding AA. Thus, Ω~(d2)\widetilde{\Omega}(d^2) queries are needed.

Although this requirement makes the attack computationally prohibitive for typical values of dd (e.g., 16,384 in SD2.1), we nonetheless demonstrate a polynomial-time adversary who significantly outperforms randomly guessing the transformation.

Proposed Watermark Construction

Cryptographic Primitives

Our watermark construction relies on the existence of the following coding and cryptographic primitives:

  1. Pseudorandom Error-Correcting Code (PRC): The details and requirements of the PRC scheme is described in Section II-C.

  1. Pseudorandom Function (PRF): Given key space K\mathcal{K}, let F={fk:k∈K}\mathcal{F} = \{f_k : k \in\mathcal{K}\} denote a PRF family, where each member of the family is indexed by a key kk. For a uniformly sampled kk and any input rr, the function fk(r)f_k(r) is computationally indistinguishable from a truly random sequence.

Watermark Scheme

We now formalize our watermarking scheme through three core algorithms: KeyGen, Sample, and Decode, described in Algorithms 1, 2, and 3. A high level description of these algorithms are as follows:

  • KeyGen(λ,d)(\lambda, d): Samples and outputs secret key k=(k1,k2,k3)k = (k_1,k_2,k_3), where k1k_1 is the PRC key, k2k_2 is used to generate the secret fixed transformation, and k3k_3 is used as the PRF key.

  • Sample(λ,d,k)(\lambda, d, k): Generates a sample from the watermarked distribution Dk\mathcal{D}_k.

  • Decode(λ,Y,k,t)(\lambda, Y, k, t): Outputs whether a sample YY is sampled from the watermarked distribution Dk\mathcal{D}_k. The parameter tt controls the false positive rate.

Additionally, let us define the following functions, both used in the watermark Sample and Decode function

  • SRandOrthonormal: d,{0,1}λ→Rd×dd,\{0,1\}^{\lambda} \to\mathbb{R}^{d \times d}. A function which outputs a uniformly sampled d×dd \times d orthonormal matrix conditional on a nonce uniformly sampled from {0,1}λ\{0,1\}^{\lambda}. For a uniformly sampled uu, SRandOrthonormal(d,u)(d,u) is computationally indistinguishable from a truly random d×dd \times d orthonormal matrix, its implementation is discussed in Appendix A.

  • fk:M→{0,1}d/2f_k : \mathcal{M} \to\{0,1\}^{d/2}: A keyed PRF. Using a secret key kk, this function takes any input m∈Mm \in\mathcal{M} (e.g. M\mathcal{M} is the set of all binary strings) and produces an output fk(m)f_k(m). Without kk, fk(m)f_k(m) is computationally indistinguishable from a truly random sequence.

An illustration of the Sample(λ,d,k)(\lambda,d,k) algorithm is given in Figure 1.

Algorithm 1 Watermarking KeyGen
1: procedure KEYGEN(λ)(\lambda)
2: Sample secret keys k1,k2,k3←{0,1}λk_1,k_2,k_3 \leftarrow\{0,1\}^{\lambda}
3: return k=(k1,k2,k3)k=(k_1,k_2,k_3)
4: end procedure

Table 1 (PDF p. 6).

Algorithm 2 Watermark Sample
1: procedure SAMPLE(λ,d,k)(\lambda,d,k)
2: k1,k2,k3←kk_1,k_2,k_3 \leftarrow k
3: r←{0,1}nrr \leftarrow\{0,1\}^{n_r} ▷ Sample random nonce
4: X∼N(0,Id)X \sim\mathcal{N}(0,I_d) ▷ Sample Gaussian vector
5: A←A \leftarrow SRandOrthonormal(d,k2)(d,k_2)
6: B←B \leftarrow SRandOrthonormal(d2,r)(\frac{d}{2},r) ▷ Sample orthonormal matrix
7: C1←C_1 \leftarrow PRC(k1,r)(k_1,r)
8: C2←fk3(r)C_2 \leftarrow f_{k_3}(r)
9: C←(C1,C2)C \leftarrow(C_1,C_2) ▷ Concatenate binary sequence
10: X′←X' \leftarrow Embed(X,C)(X,C)
11: Form block matrix M=(Id/200B)M=\begin{pmatrix} I_{d/2} & 0 \\ 0 & B \end{pmatrix}
12: Y←X′MAY \leftarrow X'MA
13: return YY
14: end procedure
15: procedure EMBED(X,S)(X,S)
16: for i=1,…,∣X∣i=1,\ldots,|X| do
17: X[i]←∣X[i]∣×(−1)S[i]X[i] \leftarrow|X[i]| \times(-1)^{S[i]}
18: end for
19: return XX
20: end procedure

Table 2.

1) Encoding Multi-bit Messages: The construction described in Algorithms 1, 2, and 3 embeds a single-bit watermark (i.e., a binary indicator of whether a sample is watermarked). We can easily extend this construction to accommodate multi-bit messages. Let M\mathcal{M} denote a set of allowable messages, and let ECC.Encode and ECC.Decode represent the encoding and decoding functions of an error-correcting code.

a) Sample: To encode a message m∈Mm \in\mathcal{M}, replace Line 8 in Algorithm 2 with C2←fk3(r)⊕ECC.Encode(m)C_2 \leftarrow f_{k_3}(r) \oplus\mathrm{ECC.Encode}(m). Because fk3(r)f_{k_3}(r) is a pseudorandom sequence, this XOR

Algorithm 3 Watermark Decode

1: procedure DECODE($\lambda,Y,k,t$)
2:     $k_1,k_2,k_3 \leftarrow k$
3:     $A \leftarrow \operatorname{SRandOrthonormal}(d,k_2)$
4:     $\zeta \leftarrow YA^{\mathsf{T}}$ ▷ Reversing the global mask $A$
       ▷ Extract signs to recover $\hat{C}_1$
5:     for $i=1,\ldots,d/2$ do
6:         $\hat{C}_1[i] \leftarrow \begin{cases} 0 & \text{if }\zeta[i]\ge 0 \\ 1 & \text{if }\zeta[i]<0 \end{cases}$
7:     end for
8:     $\hat{r} \leftarrow \operatorname{PRC}^{-1}(k_1,\hat{C}_1)$
9:     $\hat{B} \leftarrow \operatorname{SRandOrthonormal}\left(\frac{d}{2};\hat{r}\right)$
10:    Form transpose block matrix $M^{\mathsf{T}}=\begin{pmatrix} I_{d/2} & 0 \\ 0 & \hat{B}^{\mathsf{T}} \end{pmatrix}$
11:    $\hat{X} \leftarrow \zeta M^{\mathsf{T}}$
       ▷ Extract signs to recover $\hat{C}_2$
12:    for $j=1,\ldots,d/2$ do
13:        $\hat{C}_2[j] \leftarrow \begin{cases} 0 & \text{if }\hat{X}[d/2+j]\ge 0 \\ 1 & \text{if }\hat{X}[d/2+j]<0 \end{cases}$
14:    end for
       ▷ $d_H(\cdot,\cdot)$ = Hamming distance
15:    return $\mathbf{1}\left(d_H(\hat{C}_2,f_{k_3}(\hat{r}))<t\right)$
16: end procedure

operation effectively acts as a one-time pad. This encrypts the ECC codeword, ensuring that the embedded sequence remains pseudorandom and preserves the statistical properties of the baseline scheme.

b) Decode: To recover the message, replace Line 15 of Algorithm 3 with return ECC.Decode($\hat{C}_2\oplus f_{k_3}(\hat{r})$). If a multi-bit message is used, the FPR rates will depend on the configuration of the error correcting code scheme.

Per-sample Transformations

As shown in Section IV-C, relying solely on the fixed transformation AA allows a REM2 adversary to reconstruct the transformation. To prevent the adversary from learning AA, we enforce two requirements:

  1. Per-Sample Transformations: The applied transformation must remain strictly unique for each generated sample.

  2. Obfuscated Fixed Transformation: The adversary’s interaction with the system should not reveal any information about the fixed transformation.

To analyze the adversary’s capabilities, let us write AA as

A=(A1A2A3A4)A=\begin{pmatrix} A_1 & A_2 \\ A_3 & A_4 \end{pmatrix}

As per the Sample($\lambda,d,k$) function in Algorithm 2, watermarked sample YiY_i can be rewritten as Yi=XiΛiY_i=X_i\Lambda_i, where the effective orthonormal transformation matrix is:

Λi=(Id/200Bi)(A1A2A3A4)=(A1A2BiA3BiA4)(1)\Lambda_i=\begin{pmatrix} I_{d/2} & 0 \\ 0 & B_i \end{pmatrix}\begin{pmatrix} A_1 & A_2 \\ A_3 & A_4 \end{pmatrix}=\begin{pmatrix} A_1 & A_2 \\ B_iA_3 & B_iA_4 \end{pmatrix} \tag*{(1)}

Detector

For any adversarial perturbation η\eta added to YiY_i, the detector evaluates Xi+ηΛiTX_i+\eta\Lambda_i^{\mathsf{T}}. Define the detector as follows:

O(Y)=Decode⁡(λ,Y,k,t).(2)\mathcal{O}(Y)=\operatorname{Decode}(\lambda,Y,k,t). \tag*{(2)}

Let dH(⋅,⋅)d_H(\cdot,\cdot) denote the Hamming distance, and the codewords (C1,C2)(C_1,C_2) be as defined in Algorithm 2. If C~1\widetilde{C}_1 and C~2\widetilde{C}_2 represent the codewords recovered from the perturbed sample Yi+ηY_i+\eta, we can formally define the indicator variables α\alpha and β\beta as:

α=1[dH(C~1,C1)∣C1∣>τ1],β=1[dH(C~2,C2)∣C2∣>τ2],(3)\alpha=\mathbf{1}\left[\frac{d_H(\widetilde{C}_1,C_1)}{|C_1|}>\tau_1\right],\qquad \beta=\mathbf{1}\left[\frac{d_H(\widetilde{C}_2,C_2)}{|C_2|}>\tau_2\right], \tag*{(3)}

where α=1\alpha=1 denotes the event where more than τ1\tau_1 proportion of signs in C1C_1 are flipped, and likewise for β=1\beta=1. Conceptually, we can view τ1\tau_1 as the maximum proportion of bit flips the PRC codeword C1C_1 can sustain while still being successfully authenticated. Similarly, τ2\tau_2 represents the tolerable error rate for the C2C_2 portion, beyond which the decoder fails and returns 0. Therefore, we can express

O(Y)=((α=0)∧(β=0)).(4)\mathcal{O}(Y)=((\alpha=0)\land(\beta=0)). \tag*{(4)}

Requirement on Error Thresholds

We require the error thresholds τ1\tau_1 and τ2\tau_2 to satisfy:

τ1−τ2>ln⁡dln⁡ln⁡dd,(5)\tau_1-\tau_2>\sqrt{\frac{\ln d\ln\ln d}{d}}, \tag*{(5)}

for sufficiently large dd. If Λi\Lambda_i is unknown to the adversary, any chosen perturbation η\eta results in an effective noise vector ηΛiT\eta\Lambda_i^{\mathsf{T}} that disperses evenly across the dd-dimensional space, yielding uniform expected error rates across both codeword components. By standard concentration bounds, the statistical fluctuation between these components is strictly bounded by the threshold gap. Consequently, any undirected noise strong enough to trigger α=1\alpha=1 will simultaneously trigger β=1\beta=1 with all but negligible probability, preventing the adversary from isolating the state α=1\alpha=1 and β=0\beta=0. We formalize this intuition and apply this threshold in the security analysis detailed in Section VI-C.

Security Analysis

In this section, we prove that our proposed watermarking scheme achieves IND1-REM2 security, as defined in Section III-A. Throughout the following analysis, we assume the scheme is initialized by sampling a secret key via KeyGen⁡(λ)\operatorname{KeyGen}(\lambda).

Security Under IND1 (Undetectability)

To formally establish watermark undetectability, we demonstrate that no PPT adversary can achieve a non-negligible advantage in the IND1 security game (Section II). Consistent with standard diffusion models, we let D=N(0,Id)\mathcal{D}=\mathcal{N}(0,I_d).

The function Sample⁡(λ,d,k)\operatorname{Sample}(\lambda,d,k) in Algorithm 2 generates samples from Dk\mathcal{D}_k. The indistinguishability of Dk\mathcal{D}_k from D\mathcal{D} follows directly from its construction. First, the codeword CC is constructed by concatenating two sequences that are computationally indistinguishable from a truly random binary sequence (Line 9). Next, a sample from DkD_k is generated by drawing a base sample from DD, preserving its magnitude, but assigning its signs according to CC (Line 10).

Consequently, any PPT adversary which distinguishes DkD_k from DD could trivially distinguish CC from a uniformly random sequence. Therefore, DkD_k is computationally indistinguishable from DD, and the scheme is IND1-secure.

Watermark Removal and Adversary’s Advantage

Given a watermarked sample YY, the adversary’s goal is to compute a perturbed sample Y~=Y+η\widetilde{Y}=Y+\eta for some sufficiently small η\eta (e.g., ∥η∥2≤ϵ\lVert\eta\rVert_2\leq\epsilon for a predetermined budget ϵ\epsilon) such that Decode⁡(λ,Y,k,t)\operatorname{Decode}(\lambda,Y,k,t) returns False.

Let A\mathcal{A} be a probabilistic polynomial-time (PPT) adversary operating under the REM2 threat model. We evaluate A\mathcal{A} at the challenge phase, meaning it has already completed Steps (1)–(3) of the REM2 security game (Section III-A4). First, we define the success probability of any adversary A\mathcal{A}, bounded by a perturbation budget ϵ\epsilon, as:

Succ⁡(A,ϵ)=Pr⁡k←KeyGen⁡(λ)Y←Sample⁡(λ,d,k)Y~←A(Y,ϵ)[Decode⁡(λ,Y~,k,t)=False⁡∧∥Y~−Y∥2≤ϵ].(6)\operatorname{Succ}(\mathcal{A},\epsilon)=\Pr_{\substack{k\leftarrow\operatorname{KeyGen}(\lambda)\\Y\leftarrow\operatorname{Sample}(\lambda,d,k)\\\widetilde{Y}\leftarrow\mathcal{A}(Y,\epsilon)}}\left[\operatorname{Decode}(\lambda,\widetilde{Y},k,t)=\operatorname{False}\land\lVert\widetilde{Y}-Y\rVert_2\leq\epsilon\right]. \tag*{(6)}

Let Aw\mathcal{A}_w denote a baseline adversary limited to adding isotropic white-noise of magnitude ϵ\epsilon. We define the advantage of A\mathcal{A} w.r.t. the baseline Aw\mathcal{A}_w as:

Adv⁡(A,ϵ)=Succ⁡(A,ϵ)−Succ⁡(Aw,2ϵ).(7)\operatorname{Adv}(\mathcal{A},\epsilon)=\operatorname{Succ}(\mathcal{A},\epsilon)-\operatorname{Succ}(\mathcal{A}_w,\sqrt{2}\epsilon). \tag*{(7)}

The watermarking scheme is said to be 2\sqrt{2}-REM2-secure if and only if, for all PPT adversaries A\mathcal{A},

Adv⁡(A,ϵ)≤negl⁡(λ)\operatorname{Adv}(\mathcal{A},\epsilon)\leq\operatorname{negl}(\lambda)

where negl⁡(⋅)>0\operatorname{negl}(\cdot)>0 is a negligible function.

1) The 2\sqrt{2} factor: The 2\sqrt{2} factor establishes a strict upper bound on the adversarial efficiency operating under the REM2 threat model. Our subsequent security analysis reveals that while an adversary can isolate the d/2d/2-dimensional subspace associated with either the fixed or dynamic transformation—and restrict their perturbations accordingly—they cannot recover its specific orthonormal basis. By keeping the exact decision boundaries obfuscated, the scheme successfully thwarts targeted boundary attacks (e.g. the sign-flip attack in [3]). As shown later in Theorem 1, this 2ϵ\sqrt{2}\epsilon factor is a tight constant.

Security Analysis under REM2

Under the REM2 threat model, an adversary observes a sequence of watermarked samples Y=(Y1,…,Yt)Y=(Y_1,\ldots,Y_t) and submits polynomial queries Q=(q1,…,qs)Q=(q_1,\ldots,q_s) to the detector. Let us express each query as qj=Y+ηjq_j=Y+\eta_j for some Y∈YY\in\mathcal{Y} and perturbation ηj\eta_j. The detector evaluates O(qj)O(q_j) and returns 0 if and only if αj=1\alpha_j=1 or βj=1\beta_j=1 (as defined in (4)).

To establish REM2 security, we show that the adversary gains negligible information about the static boundary from the oracle, i.e.:

Pr⁡[αj∣Y,O(q1),…,O(qj),ηj]=Pr⁡[αj∣Y,ηj]+negl⁡(d),\Pr[\alpha_j\mid Y,O(q_1),\ldots,O(q_j),\eta_j]=\Pr[\alpha_j\mid Y,\eta_j]+\operatorname{negl}(d),

where Pr⁡[⋅]\Pr[\cdot] denotes the probability taken over k←KeyGen⁡(λ)k\leftarrow\operatorname{KeyGen}(\lambda), i.e. that the distribution of αj\alpha_j given the oracle’s responses is indistinguishable from its distribution without oracle access.

Our proof proceeds in two steps:

  1. Information-Theoretic Security (Theorem 1): We first idealize the Sample algorithm by replacing all pseudorandom primitives (PRC, PRF, and SRandOrthonormal) with perfectly random sources, proving that the scheme is statistically secure under these idealized conditions.

  1. Computational Security (Theorem 2): Next, a hybrid argument is employed to reduce the security of our real-world instantiation to the computational hardness of the underlying pseudorandom primitives, proving that no PPT adversary can achieve a non-negligible advantage.

1) Information-Theoretic Security: Our proof of information-theoretic security (Theorem 1) relies on the following lemmas.

  1. Lemma 1 (Oracle Indistinguishability): Establishes that the real detector is statistically indistinguishable from an idealized detector that evaluates only the dynamic component (β\beta). Hence, the oracle responses reveal only negligible information about the static component (α\alpha).

  1. Lemma 2 (Basis Indistinguishability): Extends Lemma 1 to show that the fixed transformation is identifiable only up to an independent uniformly sampled rotation. In particular, the adversary obtains no non-negligible information about the orientation of the fixed basis.

  1. Lemma 3 (Hidden-Basis Isotropization): Shows that if a subspace basis is hidden by a uniformly sampled rotation, then any perturbation chosen independently of this rotation is transformed into isotropic noise with the same projected magnitude.

  1. Lemma 4 (2ϵ\sqrt{2}\epsilon Baseline Comparison): Applies Lemma 3 to show that even an adversary who perfectly isolates the fixed and dynamic subspaces cannot outperform a full-space isotropic white-noise baseline of magnitude 2ϵ\sqrt{2}\epsilon, up to negligible error.

  1. Lemma 5 (Advantage Implies Distinguishability): Any adversary achieving non-negligible advantage over the 2ϵ\sqrt{2}\epsilon baseline must distinguish the true orientation of the fixed basis from a uniformly rotated copy. This contradicts Lemma 2, and therefore no such adversary can exist.

At a high level: by Lemma 1 the oracle reveals nothing about the long-term transformation (Figure 2 in Appendix B), so it is recoverable only up to an unknown rotation (Lemma 2), while the one-time transformation is re-randomized per sample. Any adversarial perturbation is therefore isotropized into white-noise (Lemma 3), giving no advantage over the 2ϵ\sqrt{2}\epsilon baseline (Lemmas 4, 5) and establishing Theorem 1. For readability, the detailed proofs of these lemmas are deferred to Appendix B. We present their formal statements below.

Figure 2. The hybrid watermark masks components with long-term (α\alpha) and one-time per-sample (β\beta) transformations. The watermark detector O\mathcal{O} (which checks both long-term α\alpha and short-term β\beta) is computationally indistinguishable from O3\mathcal{O}_3 (only β\beta), preventing adversaries from learning the fixed long-term transformation. Consequently, no polynomial-time adversary achieves non-negligible advantage in removing watermarks from fresh samples.

Lemma 1 (Oracle Indistinguishability). Suppose the threshold gap τ1−τ2\tau_1-\tau_2 satisfies (5). For a given Y∼DkY \sim D_k and any query q=Y+ηq=Y+\eta, the output distribution of the real oracle O(q)=1((α=0)∧(β=0))O(q)=1((\alpha=0)\wedge(\beta=0)) is statistically indistinguishable from an oracle O3=1(β=0)O_3=1(\beta=0).

Lemma 2 (Basis Indistinguishability). Let Λ:=Λi\Lambda:=\Lambda_i be as defined in (1), and let Λ⊤=[F,D]\Lambda^\top=[F,D], where

F=(A1⊤A2⊤)andD=(A3⊤B3⊤A4⊤B4⊤).F=\begin{pmatrix} A_1^\top\\ A_2^\top\end{pmatrix} \qquad\text{and}\qquad D=\begin{pmatrix} A_3^\top& B_3^\top\\ A_4^\top& B_4^\top\end{pmatrix}.

Here, FF and DD denote the fixed secret transformation and the one-time masked transformation, respectively. Let F\mathcal{F} be the set of all bases that are orthogonal to DD. For any fixed rotation matrix R∈Haar⁡(d/2)R\in\operatorname{Haar}(d/2) and any measurable subset S⊆FS\subseteq\mathcal{F}, the conditional probability over the randomized choice of the secret basis yields:

∣Pr⁡[F∈S∣Y,O(q1),…]−Pr⁡[F∈SR∣Y,O(q1),…]∣≤negl⁡(d),\left|\Pr[F\in S\mid Y,O(q_1),\ldots]-\Pr[F\in S_R\mid Y,O(q_1),\ldots]\right|\leq\operatorname{negl}(d),

where the set SR={sR:s∈S}S_R=\{sR:s\in S\}. That is, the secret fixed transformation FF is only recoverable up to a random rotation.

Lemma 3 (Hidden-basis isotropization). Let F∈Rd×d/2F\in\mathbb{R}^{d\times d/2} be an orthonormal basis, and R∼Haar⁡(d/2)R\sim\operatorname{Haar}(d/2) be independent of a perturbation η\eta. It follows that

Δ(ηFR,∥ηF∥2Ud/2)=0.\Delta(\eta FR,\lVert\eta F\rVert_2 U_{d/2})=0.

That is, an adversary that knows FF only up to a rotation RR sampled uniformly from Orth⁡(d/2)\operatorname{Orth}(d/2) cannot outperform adding isotropic white-noise of magnitude ∥ηF∥2\lVert\eta F\rVert_2.

Lemma 4 (2ϵ\sqrt{2}\epsilon Baseline Comparison). Suppose an adversary A\mathcal{A} is given the two d/2d/2-dimensional subspaces corresponding to AFA_F and ADA_D, up to rotations sampled independently from Haar⁡(d/2)\operatorname{Haar}(d/2). Then any perturbation η\eta chosen by A\mathcal{A} with ∥η∥2≤ϵ\lVert\eta\rVert_2\leq\epsilon has negligible advantage over full-space isotropic white-noise of magnitude 2ϵ\sqrt{2}\epsilon. That is, Succ⁡(A,ϵ)≤Succ⁡(Aw,2ϵ)\operatorname{Succ}(\mathcal{A},\epsilon)\leq\operatorname{Succ}(\mathcal{A}_w,\sqrt{2}\epsilon).

Lemma 5 (Advantage Implies Basis Distinguishability). Continuing from the setting in Lemma 2. If there exists an adversary A\mathcal{A} operating under the REM2 threat model such that Adv⁡(A,ϵ)\operatorname{Adv}(\mathcal{A},\epsilon) is non-negligible, then there exists a measurable subset S⊆FS\subseteq\mathcal{F}, a rotation R∈Haar⁡(d/2)R\in\operatorname{Haar}(d/2), and polynomial p(⋅)>0p(\cdot)>0 such that:

∣Pr⁡[F∈S∣Y,O(q1),…]−Pr⁡[F∈SR∣Y,O(q1),…]∣≥1p(d),\left|\Pr[F\in S\mid Y,O(q_1),\ldots]-\Pr[F\in S_R\mid Y,O(q_1),\ldots]\right|\geq\frac{1}{p(d)},

where SR={MR:M∈S}S_R=\{MR:M\in S\}. That is, A\mathcal{A} can distinguish the specific orientation of the fixed basis FF from a rotated counterpart with non-negligible probability.

Theorem 1. If the threshold gap τ1−τ2\tau_1-\tau_2 satisfies (5), then for any PPT adversary A\mathcal{A} operating under the REM2 threat model, with access to a polynomial number of watermarked samples and queries to the detector oracle OO, Adv⁡(A,ϵ)≤negl⁡(d)\operatorname{Adv}(\mathcal{A},\epsilon)\leq\operatorname{negl}(d).

Proof. We proceed by contradiction. Assume there exists a PPT adversary A\mathcal{A} operating under the REM2 threat model with a perturbation budget ϵ\epsilon s.t. Adv⁡(A,ϵ)\operatorname{Adv}(\mathcal{A},\epsilon) is non-negligible. By Lemma 1, the adversary’s interaction with the real oracle OO is statistically indistinguishable from interaction with the simulated oracle O3O_3. Consequently, the oracle responses leak strictly negligible information regarding the static decision boundaries. Building upon this, Lemma 2 establishes that given the adversary’s view, the exact orientation of the fixed basis FF remains statistically indistinguishable from a randomly rotated counterpart FRFR, where R∼Haar⁡(d/2)R\sim\operatorname{Haar}(d/2). However, by Lemma 5, since Adv⁡(A,ϵ)\operatorname{Adv}(\mathcal{A},\epsilon) is non-negligible, there exists a PPT distinguisher which distinguishes between FF and FRFR with non-negligible probability, which contradicts Lemma 2. Thus, such an A\mathcal{A} does not exist. Thus, for all PPT A\mathcal{A}, Adv⁡(A,ϵ)≤negl⁡(d)\operatorname{Adv}(\mathcal{A},\epsilon)\leq\operatorname{negl}(d). □

Remark 1 (Tightness of the 2\sqrt{2} factor). The 2\sqrt{2} factor is tight for the full-space white-noise comparison. By Lemma 3, an adversary who knows the fixed and dynamic subspaces can choose how to split its perturbation energy

(a,b),a2+b2≤ϵ2,(a,b),\qquad a^2+b^2\leq\epsilon^2,

but within each subspace the perturbation is still isotropized by the hidden rotation. Lemma 4 proves that an adversary operating within these isolated subspaces has the same success probability of the 2ϵ\sqrt{2}\epsilon white-noise adversary, up to a negligible difference. Lemma 5 then shows that any adversary exceeding this baseline would contradict Lemma 2. Thus, the 2\sqrt{2} factor is tight.

Computational Security

Having established information-theoretic security under idealized conditions, we prove in Theorem 2 that the watermarking construction detailed in Algorithms 1, 2, and 3 achieves computational security against any PPT adversary. Due to space constraints, we will state Theorem 2 here, and the proof is deferred to Appendix B.

Theorem 2. If the underlying PRC encoder, PRF, and orthonormal matrix generators are secure pseudorandom primitives, and the condition in (5) is met, then under the REM2 threat model, for all PPT adversaries A\mathcal{A},

Adv⁡(A,ϵ)≤negl⁡(λ),\operatorname{Adv}(\mathcal{A},\epsilon)\leq\operatorname{negl}(\lambda),

where λ\lambda is the security parameter and negl⁡(⋅)\operatorname{negl}(\cdot) is a negligible function.

False Positive Rates

As outlined in Algorithm 3, the decoding function Decode⁡(λ,Y,k,t)\operatorname{Decode}(\lambda,Y,k,t) takes a threshold parameter tt that governs the false positive rate (FPR) of the detection process. Based on prior work (e.g. [22]), for a given threshold tt and dimension d>0d>0, the FPR for the watermarking scheme is given by

FPR(t,d)=12d/2∑i=0t−1(d/2i)∼exp⁡(−d(12−2td)2)(8)FPR(t,d)=\frac{1}{2^{d/2}}\sum_{i=0}^{t-1}\binom{d/2}{i}\sim\exp\left(-d\left(\frac{1}{2}-\frac{2t}{d}\right)^2\right) \tag*{(8)}

where the latter approximation holds for sufficiently large dd. For a fixed dd and predetermined FPR (e.g. 2−1002^{-100}), the corresponding tt can be computed.

Errors Due To Diffusion Inversion

Existing latent-based watermarking schemes typically rely on diffusion inversion to recover the approximate starting point, and ours is no exception. This inversion is imperfect, e.g. due to null-prompt inversion or limitations of the inversion algorithm. Let s^:=s+δ\hat{s}:=s+\delta denote the recovered latent, where δ\delta is the inversion error and ss is the original starting point. Since the inversion process never observes Λ=MA\Lambda=M A, δ\delta is independent of Λ\Lambda; hence δΛ⊤\delta\Lambda^{\top} is isotropic white-noise of magnitude ∥δ∥2\lVert\delta\rVert_2, perturbing the fixed and dynamic subspaces symmetrically. Inversion error is therefore statistically equivalent to the white-noise baseline in our REM2 analysis and can be absorbed into the detection threshold without affecting Theorems 1 and 2. Formally, this corresponds to adding an isotropic term independent of Λ\Lambda to the adversary’s perturbation in the REM2 game; since the argument of Lemma 1 depends only on the threshold gap and the symmetry of the induced flips, the analysis is unchanged. Our security games (Section III-A) are defined over latent perturbations, consistent with [2], [3]; adversarial exploitation of the inversion map itself lies outside this model and is evaluated empirically in § 8. Finally, as Decode is agnostic to the inversion algorithm, one may employ more accurate inversion techniques (e.g., [18], [19]).

Empirical Evaluation

We empirically evaluate the following:

  1. Recovery of the secret transformation: We demonstrate the effectiveness of our proposed attack against the boundary-hiding defense by measuring the accuracy the recovered secret transformation.

  2. Performance on generation quality: We demonstrate that our hybrid latent-based watermark preserves the visual quality and text alignment of the generated images compared to unwatermarked baselines.

  3. Robustness against perturbations: We assess the scheme’s resilience by measuring watermark recovery rates under benign perturbations (e.g., JPEG compression and Gaussian noise), and robustness against recent latent-based watermark removal attacks.

Setup

Defense Baselines: In § 8-B, we evaluate the efficacy of the transformation recovery attack (detailed in Section IV-C) against the boundary-hiding defense proposed in [3]. Furthermore, in § 8-E, we assess the robustness of our proposed watermarking scheme against the targeted latent-flipping attack introduced in [3], which is explicitly designed to remove undetectable latent-based watermarks, as well as the latent-space regeneration attack described in [12].

Dataset and Model Used: We employed Stable Diffusion 2.1 [13] and Stable Diffusion XL models [25], with their respective default parameters, downloaded from HuggingFace. Images were generated using prompts sourced from the Stable Diffusion Prompt (SDP) dataset [26]. This is consistent with the evaluations performed in prior work [2], [11], [3].

Coding Primitives: We utilized the PRC codeword implementation from [2]. To support multi-bit message payloads, we applied a Low-Density Parity-Check (LDPC) error-correcting code using the Python pyldpc package, with their suggested default parameters. Similar to [2], [11], [22], we set the message length to be 512-bits in the multi-bit watermarking setting. We empirically verify that these parameters meet the condition (5) in Appendix C-C.

PRF and SRandOrthonormal Functions: We employed the HMAC-SHA256 PRF provided in Python’s hashlib package. The SRandOrthonormal function is as described in Appendix A.

System Configuration: A Linux system with the following specifications was used – Processor: Intel Xeon CPU E5-2620; RAM: 256GB; GPU: NVIDIA A100.

Evaluation Metrics: We use three metrics: FID and CLIP scores for visual quality and text alignment of generated images; watermark recovery rate for robustness under benign perturbations; and attack success rate (ASR) for the effectiveness of targeted latent-based removal attacks.

For the watermark recovery rate and ASR evaluations (§ 8-D & VII-E), we run the full generation and decoding pipeline: each image is generated from a freshly sampled watermarked latent, and detection follows prior work (e.g. [2], [3], [11], [22]) by inverting under the null prompt (i.e., imperfect inversion) and passing the inverted latent to the detector.

Recovery of Secret Transformation

As established in Section IV-C1, the attack requires Ω~(d2)\tilde{\Omega}(d^2) oracle queries. We evaluate the boundary-hiding defense for d∈{4096,8192,16384}d\in\{4096,8192,16384\} and τ∈{0.01,0.1,0.3}\tau\in\{0.01,0.1,0.3\}, where d=16,384d=16,384 corresponds to Stable Diffusion 2.1, allocating a budget of d2d^2 queries for the non-adaptive blind probing phase (Step 2, Section IV-C). While the query count is large, the attack’s non-adaptivity allows for efficient parallelization. Over 5 GPUs, the d=16,384d=16,384 case completes in ∼23\sim23 hours.

To evaluate the accuracy of our attack, we measure how closely our extracted components (the rows of V∈Rd×dV\in\mathbb{R}^{d\times d}) match the target axes of the true secret transformation matrix AA. We compute the alignment matrix U=VA⊤U=VA^{\top}, whose diagonal entries correspond to the cosine similarity between the actual and recovered components. For an ideal extraction where the target axes are recovered perfectly (up to a sign flip), every row in UU will contain exactly one entry of 1 or −1-1, with all other entries being 0.

We quantify the success of the extraction using μalign\mu_{\mathrm{align}}, the average cosine similarity between the actual and recovered components, corresponding to the average of the diagonal values of UU. Note that this is equivalent to Tucker’s congruence coefficient, where a standard measure of factor recovery in PCA, for which a value above 0.85 indicates good recovery and a value above 0.95 implies near-perfect recovery [27]. A μalign\mu_{\mathrm{align}} score approaching 1 indicates perfect recovery, whereas an unsuccessful extraction yields a matrix uncorrelated with AA, causing μalign\mu_{\mathrm{align}} to collapse toward 0. For reference, random guessing yields an expected alignment score of 1/d1/\sqrt{d}.

The results are summarized in Table III. Across all evaluated configurations of dd and τ\tau, the attack successfully recovers the secret transformation, achieving μalign≥0.85\mu_{\mathrm{align}} \ge0.85.

ddτ\tauμalign\mu_{\mathrm{align}}Recovered Axes (>0.85)
4,0960.010.999100%
0.100.998100%
0.300.996100%
8,1920.010.999100%
0.100.930100%
0.300.899100%
16,3840.010.987100%
0.100.915100%
0.300.871100%

Table III. Extraction performance of the attack detailed in Section IV-C, evaluated under a fixed budget of d2d^2 queries across various tolerances (τ\tau) and dimensionalities (dd). The metric μalign∈[0,1]\mu_{\mathrm{align}} \in[0,1], rounded to 3 decimal places, denotes the mean maximum absolute alignment score, where 1 indicates perfect recovery of the secret transformation AA. The rightmost column reports the proportion of target axes successfully recovered with an individual alignment score exceeding 0.85.

We further evaluated our transformation recovery attack on our proposed scheme, and observed μalign≤0.01\mu_{\mathrm{align}} \le0.01 across all values of τ\tau and dd, empirically demonstrating that the attack fails to recover any useful information about the fixed transformation.

Generation Quality Under Stable Diffusion

To empirically verify whether our watermarked latents introduce any degradation or structural bias during the reverse diffusion process, we evaluate the Fréchet Inception Distance (FID) and CLIP scores against unwatermarked baselines. The initial latents are drawn using the Sample procedure detailed in Algorithm 2, and generation is performed using the default hyperparameters of Stable Diffusion 2.1. Due to the substantial computational cost associated with large-scale image generation and metric evaluation, we restrict this specific analysis to SD2.1. Samples of watermarked images generated using SD2.1 and SDXL are given in Appendix C-C.

Following the evaluation protocol established in [2], our dataset comprises 10,000 generated images, obtained by selecting 100 random prompts and generating 100 images per prompt. Table IV presents our computed FID and CLIP scores alongside the baseline scores reported in [2] for both the PRC watermark and the unwatermarked baseline. These results empirically corroborate our theoretical claims: our hybrid watermarking scheme does not degrade visual quality or text alignment, yielding outputs with fidelity identical to those initialized with standard N(0,Id)\mathcal{N}(0,I_d) noise.

WatermarkFIDCLIP
MeanStdMeanStd
None63.46250.25070.61190.0018
PRC63.73500.35110.61460.0014
Ours63.80440.30700.60990.0025

Table IV. Mean and standard deviation of FID and CLIP scores, rounded to 4 decimal places. Results demonstrate that our hybrid watermarking scheme achieves performance comparable to the baseline with no watermark, empirically verifying that the watermarking process preserves generation quality.

Performance Against Benign Pixel-Level Perturbations

We evaluate the robustness of the watermark under benign yet realistic image perturbations, specifically:

  1. Additive Gaussian noise with standard deviation parameter σ∈{0.01,0.05,0.10}\sigma\in\{0.01, 0.05, 0.10\},

  2. JPEG compression with quality factors q∈{90,75,50}q \in\{90,75,50\}.

All pixel values are assumed to lie in the normalized range [0,1][0,1]. The evaluation protocol is as follows:

  1. Generation: We randomly sample 100 text prompts and generate a corresponding dataset of 100 watermarked images.

  2. Perturbation: The various described perturbations are applied to each image.

  3. Inversion & Detection: Conditional on null prompt, we invert each generated image back into the latent space and its approximate starting point, which is passed to the detection algorithm to detect the watermark.

We consider two payload settings:

  1. Single-bit watermark: Evaluating the binary detection accuracy to determine whether an image is successfully flagged as watermarked.

  2. Multi-bit watermark: Embedding a randomly sampled 512-bit payload into the generated images and evaluating whether the message can be successfully extracted post-perturbation.

The results are given in Table V, which confirm that the proposed watermarking scheme remains highly robust against realistic pixel-level perturbations. Notably, the SDXL model yields slightly higher robustness, which is an expected outcome given its significantly larger (4×4\times) latent space.

AttackParam.SD2.1 SingleSD2.1 MultiSDXL SingleSDXL Multi
Baseline-1.001.001.001.00
JPEG Comp.q=90q=901.001.001.001.00
JPEG Comp.q=75q=750.990.951.000.95
JPEG Comp.q=50q=500.930.910.940.93
Gaussian Noiseσ=0.01\sigma=0.011.001.001.001.00
Gaussian Noiseσ=0.05\sigma=0.051.000.991.001.00
Gaussian Noiseσ=0.10\sigma=0.100.960.920.980.94

Table V. Watermark recovery rates under various image perturbation for single-bit and multi-bit payloads across Stable Diffusion 2.1 and SDXL.

Evaluation of Latent-Based Watermark Removal Attacks

  1. Regeneration Attack [12]: To assess robustness against generative adversaries, we employ the regeneration attack. This method targets invisible watermarks by injecting noise into the latent space and reconstructing the image via the denoising process of Latent Diffusion Models (LDMs). We include this attack because its latent-based perturbation serves as an established benchmark in recent works (e.g., [2]). To

rigorously evaluate our proposed scheme, we tested it across varying attack intensities, specifically applying diffusion noise steps of 50, 60 (the attack’s default), and 70. Empirically, our watermark successfully survives all configurations for both single and multi-bit setting, demonstrating strong resilience against LDM-driven image reconstruction.

  1. “Stealthy” Removal Attack [3]: We selected this attack because it is specifically formulated to target the removal of undetectable latent-based watermarks in diffusion models. Following their evaluation protocol, the adversary’s perturbation budget is strictly constrained to specific ℓ2\ell_2-norms. To empirically measure the success rate of the removal attack, we perform the following:

  1. Generation: We randomly sample 100 text prompts and generate a corresponding dataset of 100 watermarked images.

  1. Inversion: We invert the generated image back to its original starting point.

  1. Perturbation: We apply the respective attacks to the inverted latent representation within the bounded ℓ2\ell_2 budget, proceeding as follows:

a) For the white-noise attack, we inject isotropic Gaussian noise scaled to match the specified ℓ2\ell_2 magnitude.

b) For the “stealthy” attack, we iteratively flip the signs of the latent components with the smallest magnitudes until the ℓ2\ell_2 perturbation budget is exhausted.

  1. Detection: Finally, we pass the starting point through the detection algorithm to detect the watermark.

Similar to the experimental setup in [3], evaluations are performed on SD2.1. As demonstrated in Table VI, the targeted “stealthy” attack fails to outperform the white-noise adversary. This corroborates our theoretical guarantees in Theorem 1, demonstrating that no PPT adversary operating under the REM2 threat model can achieve a non-negligible advantage over random white-noise injection.

Noise LevelSingle-bit White-NoiseSingle-bit “Stealthy” AttackMulti-bit White-NoiseMulti-bit “Stealthy” Attack
80.000.000.000.00
100.010.010.010.01
300.080.080.170.19

Table VI. Performance of the “stealthy” removal attack [3] against an isotropic white-noise baseline on the proposed watermarking scheme under varying ℓ2\ell_2 perturbation budgets. Values represent the attack success rate.

Discussion

Computational Limitations and Tradeoffs

a) Computational Overhead: Similar to the boundary-hiding defense in [3], our approach introduces computational overhead (see Appendix C-B). Memory requirements increase by approximately 25% compared to the boundary-hiding baseline due to an additional (d/2)×(d/2)(d/2) \times(d/2) one-time transformation matrix. Taken over 100 trials, the sample and decode algorithms took 0.1s and 0.2s respectively in SD 2.1, and 1.2 s and 1.9s in SDXL. Currently, our theoretical security guarantees depend on dense orthonormal transformations during the Sample and Decode steps. A possible approach is to explore structured or sparse transformations (e.g [28]) to reduce computational cost without compromising security. Nonetheless, this overhead is incurred only once per image and remains a fraction of the generation time itself (2.5s and 7.3s for unwatermarked generation in SD2.1 and SDXL, respectively).

b) Overhead of Secret Transformation: As noted in § 8-B, recovery requires d2d^2 samples, which is expensive but parallelizable efficiently across multiple GPUs. Thus, motivated and computationally powerful adversary may parallelize queries across multiple black-box detector accounts, and recover the secret transformation for large dd. Since the secret transformation is long-term, it only needs to be broken once to re-expose the detector’s decision boundary, and all subsequent removal attacks can be carried out cheaply. The cost of recovering the secret transformation is therefore amortized across an unlimited number of subsequent attacks, constituting a complete break of the boundary hiding defense.

Error-Correcting Codes for Multi-Bit Watermarking

For our multi-bit watermark implementation, we utilize Low-Density Parity-Check (LDPC) codes, with recommended parameters from prior work. Because our hybrid scheme imposes a global, one-time orthogonal transformation, any targeted perturbation crafted by an adversary in the latent space is uniformly dispersed across all dd dimensions during the extraction phase. Consequently, the ideal Error-Correcting Code (ECC) for our framework must be resilient to independent, uniformly distributed noise rather than localized corruptions. Although a comprehensive comparative analysis of ECCs falls outside the primary scope of this paper, our watermarking framework is entirely code-agnostic. Exploring advanced coding schemes to further maximize payload capacity and robustness remains a promising direction for future work.

A Stronger Adaptive Adversary: REM3 Threat Model

A natural follow-up is to consider an even more powerful adversary, with adaptive oracle access to the detector O\mathcal{O}, allowing them to craft queries based on past detector responses. Let us call this the REM3 threat model.

Let us reuse the formulation from Lemma 2, denote the hybrid transformation as [F,D][F,D], where FF and DD correspond to the fixed and dynamic basis vectors, respectively. The REM3 adversary could proceed as follows:

  1. Dynamic Basis Recovery: The adversary executes the baseline attack described in Section IV-C to approximate DD.

  2. Subspace Isolation: With DD known, the adversary constrains subsequent queries strictly to the subspace orthogonal to DD. This effectively zeroes out the dynamic component of the transformation.

  3. Fixed Basis Deduction: By isolating the fixed transform in this manner, the adversary with sufficient queries is likely able to approximate FF.

Nonetheless, the information-theoretic bound in Section IV-C1 still applies: learning a dense d/2×d/2d/2 \times d/2 transformation still requires Ω(d2)\Omega(d^2) queries, which although computationally expensive, is a substantial improvement over random guessing. A REM3-secure scheme likely requires eliminating the fixed transformation entirely. This introduces non-trivial complications regarding how the dynamic transformation can be reliably encoded and extracted. We leave this as future work.

a) Deployment-Level Mitigations Against Adaptivity: While we do not claim a cryptographic guarantee against REM3, practical deployment constraints substantially raise the bar for this adversary. The power of an adaptive strategy stems from sequential dependence: each query qj+1q_{j+1} depends on the response to qjq_j, forming a dependency chain that, unlike a non-adaptive batch, has limited parallelization. Consequently, defenses commonly used in real-world query-access APIs against adversarial perturbations, such as per-account rate limiting [29], query latency, and stateful detection [30], though these approaches target different attack surfaces and provide different types of guarantees. A REM3-secure scheme remains an important direction for future work.

Related Works

AI-Generated Content Watermarking

Current approaches to watermarking AIGC can generally be categorized into the following categories [1]: post-processing, in-process, and pre-processing techniques.

a) Post-processing Watermarks: These methods apply watermarks directly to the generated media, similar to traditional digital watermarking [1], [31]. Recent approaches adopt learning-based frameworks, utilizing trained neural networks to both inject and extract watermarks from content [32], [33]. There has also been recent work exploring techniques to embed watermarks into the VAE latent prior to the final upscaling step [34], [35].

b) In-process Watermarks: This category modifies the generative diffusion process itself. Techniques include altering specific model weights [36], injecting watermark signals directly during the denoising phase [37], or integrating plugins (e.g. LoRA) into the diffusion model [38]. Typically, these approaches rely on a separately trained watermark detector models.

c) Pre-processing Watermarks: These methods operate before the core generation begins by manipulating the initial conditions. A prominent approach involves sampling from a specifically watermarked initial distribution (e.g., Tree-Ring [20], Gaussian Shading (GS) [11], GS++ [22], and PRC [2]), which is then verified via a detection algorithm to determine if a sample originated from that distribution. Closely related are seed-based techniques that manipulate the initial noise vector. For instance, NoisePrints derives the starting seed using a secret key [39], whereas other proof-of-authorship schemes select the seed by passing authorship related information into a cryptographic hash [40].

Attacks on Watermarking

In response to large number of work on watermarking, there has been increasing interest in attacking AIGC watermarks [1]. For example, adversaries have successfully leveraged LDMs to erase pre and post-processing watermarks [12], and there have been work directly targeting specific watermarking algorithms (e.g. [41]). On the other hand, [3] demonstrated that undetectable latent-based watermarks are still susceptible to removal attacks, proving that undetectability does not guarantee unremovability.

Besides removal, watermarking schemes must withstand ambiguity attacks, where adversaries exploit coincidental statistical artifacts to falsely claim ownership [42], [43]. DNN-based methods mitigate this using weight-embedded ”passports” [44], which act as a digital signature to authenticate watermarks. In general, the security of latent-based schemes ultimately hinges on minimizing their False Positive Rate (FPR) to prevent attackers from finding valid watermarks through random guessing [45].

Conclusion

We showed that an adversary with batched detector access can reconstruct the secret transformation underlying existing boundary-hiding defenses. In response, we proposed a hybrid long-term/one-time transformation scheme that is provably secure under this stronger threat model. That is, no PPT adversary removes the watermark with non-negligible advantage over an isotropic white-noise adversary granted a 2×\sqrt{2}\times larger budget, and the scheme remains undetectable. Empirically, it preserves generation quality, withstands benign perturbations (e.g. JPEG compression and Gaussian noise), and is robust against the evaluated latent-based removal attacks.

Ethics Considerations

This research characterizes vulnerabilities in existing latent-based watermarking schemes and proposes a new watermarking scheme. Because our work involves the disclosure of an attack capable of removing undetectable watermarks, we have conducted a stakeholder-based ethics analysis in accordance with the principles outlined in NDSS’s “call for papers” and the Menlo Report.

Stakeholders

We identify three primary stakeholders impacted by our research and its publication:

  1. AIGC providers: Watermarking schemes and possible removal attacks are of interest in provenance and misuse tracking. Furthermore, as AIGC provenance is a rapidly developing area, watermarking AIGC may be necessary as part of regulatory compliance (e.g. EU AI Act [8]).

  1. Model users: They may rely on such watermarking tools to establish provenance or authorship

  1. The general public: The public may rely on tools that use watermarks (such as C2PA) to establish content provenance. Removal attacks may undermine public confidence in these tools.

Impacts

a) Ethical Principles: We prioritize Beneficence and Respect for Law and Public Interest. We determine that the security posture of the public and developers is best served by proactively identifying the limitations of boundary-hiding defenses before they are widely adopted and simultaneously providing a provably secure alternative.

b) Potential Harms: By demonstrating that adversaries with batched detector access can reconstruct secret transformations and recover detection boundaries, we introduce a method that could theoretically be used to remove watermarks from watermarked content, thereby complicating claims which rely on watermarking (e.g. misuse protection)

Mitigations and Decision

We concurrently propose and validate a robust countermeasure. By introducing a resilient scheme based on a hybrid of long-term and one-time secret transformations, we prevent the reuse of structure across queries and effectively neutralize the attack we disclose. Since the paper provides a defense against the proposed attack, and aims to further the understanding of this topic, we are of the opinion that the benefits greatly outweigh potential harms.

Implementation of SRandomOrthonormal (dd, rr)

Recall from Section V-B that the watermark Sample and Decode functions assume that given a pseudorandom string rr, the output of SRandomOrthonormal(dd, rr) is computationally indistinguishable from a matrix sampled from Haar(dd).

The algorithm of [46] converts a d×dd \times d matrix of i.i.d. N(0,1)\mathcal{N}(0,1) entries into an exactly Haar(dd)-distributed sample as follows:

  1. Sample a d×dd \times d matrix MM where each entry is i.i.d. N(0,1)\mathcal{N}(0,1).

  2. Perform QR decomposition M=QRM = QR, where QQ is orthogonal and RR is upper triangular.

  3. Output U=Q⋅DU = Q \cdot D, where D=Diag⁡(Rii∣Rii∣)D = \operatorname{Diag}\left(\frac{R_{ii}}{|R_{ii}|}\right) and RiiR_{ii} denotes the ii-th diagonal entry of RR.

The Box–Muller transform [47] is a deterministic algorithm that converts pairs of independent uniform samples on (0,1)(0,1) into pairs of independent standard Gaussian samples. Let Gauss : {0,1}λ→Rd2\{0,1\}^{\lambda} \to\mathbb{R}^{d^2} denote the function that interprets rr as a sequence of uniform floats on (0,1)(0,1) and applies the Box–Muller transform to return d2d^2 approximately N(0,1)\mathcal{N}(0,1) samples. When λ\lambda is insufficient to supply d2d^2 floats directly, rr is first expanded using a secure pseudorandom generator before applying the transform. We implement SRandomOrthonormal(dd, rr) as follows:

  1. Compute Z=Gauss⁡(r)Z = \operatorname{Gauss}(r) and arrange the d2d^2 entries into a d×dd \times d matrix MM.

  2. Apply the algorithm of [46] to MM and output the resulting UU.

We now argue that this implementation satisfies the required indistinguishability property. Since rr is pseudorandom, Gauss⁡(r)\operatorname{Gauss}(r) is computationally indistinguishable from Gauss⁡(U)\operatorname{Gauss}(U) where U←{0,1}λU \leftarrow\{0,1\}^{\lambda} is truly uniform, as Gauss is a deterministic polynomial-time function. Furthermore, provided the floating-point precision is sufficiently large, the statistical distance between the discretized output of Gauss⁡(U)\operatorname{Gauss}(U) and the continuous Ginibre ensemble is negligible. Therefore, MM is computationally indistinguishable from a truly Ginibre-distributed matrix.

It then follows from the lemma below that the output UU is computationally indistinguishable from Haar(dd), as required.

While the following result is implicit in standard arguments, we include it for completeness as we are not aware of a prior reference that states it explicitly.

Lemma 6. If MM is computationally indistinguishable from the Ginibre ensemble, then the output SRandomOrthonormal(dd, rr) is computationally indistinguishable from Haar(dd).

Proof. The proof follows by a cryptographic reduction. Suppose for contradiction that a PPT adversary DD could distinguish the output of SRandomOrthonormal(d,rd,r) from Haar(dd) with non-negligible advantage. We construct an adversary BB that distinguishes MM from a truly Ginibre-distributed matrix as follows. BB receives a challenge matrix M′M', applies the algorithm of [46], and passes the result to DD. Because this transformation maps a truly Ginibre-distributed M′M' exactly to Haar(dd) by [46], BB’s distinguishing advantage is identical to DD’s, which is non-negligible by assumption.

This contradicts the assumption that MM is computationally indistinguishable from a truly random Ginibre sample.

Deferred Proofs from Section VI

Indistinguishability of Oracles

Figure 2 illustrates the intuition behind Lemma 1. Whenever the threshold gap condition (5) holds, any perturbation strong enough to trigger α=1\alpha=1 triggers β=1\beta=1 with all but negligible probability. Hence the real oracle O\mathcal{O}, which rejects whenever (α=0)∧(β=0)(\alpha=0)\wedge(\beta=0) fails, is statistically dominated by the value of β\beta alone, and is therefore computationally indistinguishable from the simplified oracle O3\mathcal{O}_3, which checks only β\beta. Since O3\mathcal{O}_3 carries no dependence on the long-term transformation AA, this indistinguishability prevents the adversary from extracting any information about AA through detector queries.

“Well-Behaved” Detector

Let CC be a valid codeword (Algorithm 2, Line 9) and let dHd_H denote the Hamming distance. A detector O\mathcal{O} satisfies the “well-behaved” property if, for all C^\hat{C}:

dH(C,C^)≤τ⟹O(C)=O(C^).d_H(C,\hat{C})\leq\tau\Longrightarrow\mathcal{O}(C)=\mathcal{O}(\hat{C}).

a) Necessity of the “Well-Behaved” Property: To illustrate the necessity of this property, let O\mathcal{O} be a well-behaved detector, and consider an alternative detector O′\mathcal{O}' defined as:

O′(C^)={0,if a designated bit pattern Γ is present in C^,O(C^),otherwise,\mathcal{O}'(\hat{C})= \begin{cases} 0, & \text{if a designated bit pattern }\Gamma\text{ is present in }\hat{C},\\ \mathcal{O}(\hat{C}), & \text{otherwise}, \end{cases}

for some pattern Γ\Gamma where ∣Γ∣≤τ|\Gamma|\leq\tau. An adversary can “backdoor” O′\mathcal{O}' by embedding Γ\Gamma into CC using at most ∣Γ∣|\Gamma| bit flips. This yields a modified codeword C^\hat{C} satisfying dH(C,C^)≤τd_H(C,\hat{C})\leq\tau, yet O′(C)≠O′(C^)\mathcal{O}'(C)\ne\mathcal{O}'(\hat{C}). The “well-behaved” property was utilized in the security analysis of [3], and we likewise assume that our detector O\mathcal{O} exhibits this property.

Deferred Proofs

Let Ud/2U_{d/2} denote a uniformly random vector on the unit sphere Sd/2−1S^{d/2-1}, and Orth⁡(m)\operatorname{Orth}(m) be the orthonormal group in Rm\mathbb{R}^{m}. For adversary A\mathcal{A}, define

ZA:=(Yw,Ynw,q1,…,qs,O(q1),…,O(qs),Y),Z_{\mathcal{A}:}=(Y_w,Y_{nw},q_1,\ldots,q_s,\mathcal{O}(q_1),\ldots,\mathcal{O}(q_s),Y),

as the view of A\mathcal{A} at the challange phase (step 4) of the REM2 game, where the variables Yw,Ynw,q1,…,qs,O(q1),…,O(qs),YY_w,Y_{nw},q_1,\ldots,q_s,\mathcal{O}(q_1),\ldots,\mathcal{O}(q_s),Y are as defined in the game.

Lemma 7. Suppose τ1−τ2\tau_1-\tau_2 satisfies (5) and let Y∼DkY\sim D_k. For all η∈Rd\eta\in\mathbb{R}^d, if there exists a polynomial p(⋅)p(\cdot) such that Pr⁡[αj=1∣qj=Y+ηj]≥1/p(d)\Pr[\alpha_j=1\mid q_j=Y+\eta_j]\geq1/p(d) for sufficiently large dd, it implies that Pr⁡[β=1∣qj=Y+ηj]=1−negl⁡(d)\Pr[\beta=1\mid q_j=Y+\eta_j]=1-\operatorname{negl}(d), where negl⁡(⋅)\operatorname{negl}(\cdot) is a negligible function.

Proof. Let Y=XA+ηY=XA+\eta, where X∼N(0,Id)X\sim\mathcal{N}(0,I_d), A∼Haar(d)A\sim Haar(d). For convenience, let α:=αj\alpha:=\alpha_j, β:=βj\beta:=\beta_j, and Pr⁡[⋅∣qj]=Pr⁡[⋅]\Pr[\cdot\mid q_j]=\Pr[\cdot]. Then, the detector O(X+ηAT)\mathcal{O}(X+\eta A^T) returns True if and only if α=1\alpha=1 or β=1\beta=1. Let Ii=1(Sign⁡(Xi)≠Sign⁡(Xi+ui))I_i=1(\operatorname{Sign}(X_i)\ne\operatorname{Sign}(X_i+u_i)), where U:=(u1,…,ud)=ηATU:=(u_1,\ldots,u_d)=\eta A^T. Thus, the random variables

N1=∑i=1d/2IiandN2=∑i=d/2+1dIiN_1=\sum_{i=1}^{d/2}I_i\quad\text{and}\quad N_2=\sum_{i=d/2+1}^{d}I_i

denote the number of sign flips in the first and second half of XX due to η\eta, respectively. Let I={I1,…,Id}I=\{I_1,\ldots,I_d\}.

First, we prove that N1N_1 and N2N_2 share the same distribution. Since UU is rotationally invariant (i.e., for any orthonormal matrix RR, since AA and ARAR share the same distribution, UU and URUR share the same distribution), it follows that UU is exchangeable. That is, for any permutation π:{1,…,d}→{1,…,d}\pi:\{1,\ldots,d\}\to\{1,\ldots,d\}, both

(u1,…,ud)and(uπ(1),…,uπ(d))(u_1,\ldots,u_d)\quad\text{and}\quad(u_{\pi(1)},\ldots,u_{\pi(d)})

share the same distribution. Therefore, for any partitions I′,I′′I',I'' of II where ∣I′∣=∣I′′∣=d2|I'|=|I''|=\frac{d}{2}, it follows that

∑i∈I′Iiand∑i∈I′′Ii\sum_{i\in I'}I_i\quad\text{and}\quad\sum_{i\in I''}I_i

share the same distribution. It thus follows that N1N_1 and N2N_2 follow the same distribution.

With this established, we are ready to prove that

(Pr⁡[α=1∣qj]≥1p(d))⇒(Pr⁡[β=1∣qj]=1−negl⁡(d))(9)\left(\Pr[\alpha=1\mid q_j]\geq\frac{1}{p(d)}\right)\Rightarrow\left(\Pr[\beta=1\mid q_j]=1-\operatorname{negl}(d)\right) \tag*{(9)}

Since N1N_1 and N2N_2 share the same distribution, they have the same expectation μ:=E[N1∣qj]=E[N2∣qj]\mu:=\mathbb{E}[N_1\mid q_j]=\mathbb{E}[N_2\mid q_j]. To bound the concentration of N1N_1, we condition on the rotation UU. Conditioned on UU, the coordinates XiX_i remain independent, and hence I1,…,Id/2I_1,\ldots,I_{d/2} are independent 0-1 random variables. By Hoeffding’s inequality, we have

Pr⁡[α=1∣qj]=Pr⁡[N1>q∣η]=Pr⁡[N1>μ+t∣qj]where t:=q−μ,≤exp⁡(−2t2d/2)(10)\Pr[\alpha=1\mid q_j]=\Pr[N_1>q\mid\eta] =\Pr[N_1>\mu+t\mid q_j]\quad\text{where }t:=q-\mu, \leq\exp\left(-\frac{2t^2}{d/2}\right) \tag*{(10)}

where the first line is due to the “well-behaved” property (as described in Section B-B). Therefore, for Pr⁡[α=1∣qj]≥1p(d)\Pr[\alpha= 1 \mid q_j] \ge\frac{1}{p(d)} to hold, the following must hold:

1p(d)≤exp⁡(−4t2d).\frac{1}{p(d)} \le\exp\left(-\frac{4t^2}{d}\right).

This implies that t≤d4ln⁡p(d)t \le\sqrt{\frac{d}{4}\ln p(d)}. Since ln⁡p(d)∈O(ln⁡d)\ln p(d) \in O(\ln d), we have q=μ+t≤μ+O(dln⁡d)q=\mu+t\le\mu+O(\sqrt{d\ln d}).

Next, recall that q=τ1d2q=\tau_1\frac{d}{2} and w=τ2d2w=\tau_2\frac{d}{2}. Since τ1−τ2≥ln⁡dln⁡ln⁡dd\tau_1-\tau_2\ge\sqrt{\frac{\ln d\ln\ln d}{d}}, it follows that q−w≥12dln⁡dln⁡ln⁡dq-w\ge\frac{1}{2}\sqrt{d\ln d\ln\ln d}. Therefore:

w≤q−12dln⁡dln⁡ln⁡d≤μ+O(dln⁡d)−12dln⁡dln⁡ln⁡d=μ−dln⁡dln⁡ln⁡d,\begin{aligned} w&\le q-\frac{1}{2}\sqrt{d\ln d\ln\ln d}\\ &\le\mu+O(\sqrt{d\ln d})-\frac{1}{2}\sqrt{d\ln d\ln\ln d}\\ &=\mu-\sqrt{d\ln d\ln\ln d}, \end{aligned}

for sufficiently large dd. By Hoeffding’s inequality (similar to (10)), we have

Pr⁡[N2≤μ−dln⁡dln⁡ln⁡d∣qj]=Pr⁡[−N2≥−μ+dln⁡dln⁡ln⁡d∣qj]≤exp⁡(−2(dln⁡dln⁡ln⁡d)2d/2)=exp⁡(−4(ln⁡dln⁡ln⁡d))=1d4ln⁡ln⁡d,\begin{aligned} \Pr\left[N_2\le\mu-\sqrt{d\ln d\ln\ln d}\mid q_j\right] &=\Pr\left[-N_2\ge-\mu+\sqrt{d\ln d\ln\ln d}\mid q_j\right]\\ &\le\exp\left(-\frac{2\left(\sqrt{d\ln d\ln\ln d}\right)^2}{d/2}\right)\\ &=\exp(-4(\ln d\ln\ln d))\\ &=\frac{1}{d^{4\ln\ln d}}, \end{aligned}

which is negligible in dd. Thus,

Pr⁡[β=1∣qj]=Pr⁡[N2>μ−dln⁡dln⁡ln⁡d∣qj]=1−negl(d),\Pr[\beta=1\mid q_j]=\Pr\left[N_2>\mu-\sqrt{d\ln d\ln\ln d}\mid q_j\right]=1-negl(d),

and the claim in (9) follows.

Lemma (Lemma 1). Suppose the threshold gap τ1−τ2\tau_1-\tau_2 satisfies (5). For a given Y∼DkY\sim D_k and any adversarial query q=Y+ηq=Y+\eta, the output distribution of the real oracle O(q)=1((α=0)∧(β=0))O(q)=1((\alpha=0)\wedge(\beta=0)) is statistically indistinguishable from an oracle O3=1(β=0)O_3=1(\beta=0).

Proof. We proceed via a hybrid argument. Recall from (4) that for a given Y∼DkY\sim D_k and query q=Y+ηq=Y+\eta

O(q)=1⟺((α=0)∧(β=0)).O(q)=1\Longleftrightarrow((\alpha=0)\wedge(\beta=0)).

Let η∗\eta^* be the smallest value of ∥η∥2\|\eta\|_2 s.t. there exists a polynomial p(⋅)p(\cdot) where Pr⁡[α=1∣∥η∥≥η∗]≥1p(d)\Pr[\alpha=1\mid\|\eta\|\ge\eta^*]\ge\frac{1}{p(d)}. Consider the following 3 hybrid experiments.

  1. H1H_1 (the real system): In this hybrid, the oracle behaves exactly as described above.

  1. H2H_2 (norm bounded perturbation oracle): In this hybrid, the oracle deterministically returns 0 if ∥η∥≥η∗\|\eta\|\ge\eta^*. Else, the oracle behaves as described in (4). Denote this oracle as O2O_2

  1. H3H_3 (oracle which ignores α\alpha). In this hybrid, the oracle returns 1 if and only if β=0\beta=0, regardless of the value of α\alpha. Denote this oracle as O3O_3

Because the adversary’s view in each hybrid experiment is entirely determined by the sequence of oracle responses, it suffices to show that the statistical distance between the output distributions of OO and O2O_2, as well as between O2O_2 and O3O_3, is negligible in dd.

For any query qi=X+ηq_i=X+\eta, the oracles OO and O2O_2 differ strictly when ∥η∥≥η∗\|\eta\|\ge\eta^*. By definition of η∗\eta^*, Pr⁡[α=1∣(∥η∥≥η∗)]≥1/p(d)\Pr[\alpha=1\mid(\|\eta\|\ge\eta^*)]\ge1/p(d). By Lemma 7, it follows that Pr⁡[β=0∣(∥η∥≥η∗)]=negl1(d)\Pr[\beta=0\mid(\|\eta\|\ge\eta^*)]=negl_1(d). Since O2(qi)O_2(q_i) deterministically outputs 0 in this regime and the real oracle O(qi)O(q_i) outputs 1 if and only if both components succeed, the probability of divergence is bounded by:

Pr⁡[O(qi)≠O2(qi)]≤Pr⁡[(α=0)∧(β=0)∣(∥η∥≥η∗)]≤Pr⁡[β=0∣(∥η∥≥η∗)]=negl1(d)(11)\Pr[O(q_i)\ne O_2(q_i)]\le\Pr[(\alpha=0)\wedge(\beta=0)\mid(\|\eta\|\ge\eta^*)] \le\Pr[\beta=0\mid(\|\eta\|\ge\eta^*)] =negl_1(d) \tag*{(11)}

Next, consider the divergence between O2O_2 and O3O_3. We analyze this across the two regimes of the perturbation magnitude ∥η∥2\|\eta\|_2:

a) For ∥η∥2≥η∗\|\eta\|_2\ge\eta^*: The oracle O2(qi)O_2(q_i) deterministically outputs 0, while O3(qi)O_3(q_i) outputs 1 if and only if β=0\beta=0. By Lemma 7, Pr⁡[β=0∣∥η∥2≥η∗]=negl1(d)\Pr[\beta=0\mid\|\eta\|_2\ge\eta^*]=negl_1(d).

b) For ∥η∥2<η∗\|\eta\|_2<\eta^*: The oracle O2(qi)O_2(q_i) outputs 1 if and only if (α=0)∧(β=0)(\alpha=0)\wedge(\beta=0), whereas O3(qi)O_3(q_i) outputs 1 if β=0\beta=0. The oracles differ strictly when the static component fails but the dynamic component does not. By the definition of η∗\eta^*, we have Pr⁡[α=1∣∥η∥2<η∗]=negl2(d)\Pr[\alpha=1\mid\|\eta\|_2<\eta^*]=negl_2(d).

Therefore, the probability that the two oracles disagree on any query qiq_i is bounded by the union of these negligible events:

Pr⁡[O2(qi)≠O3(qi)]≤Pr⁡[β=0∣∥η∥2≥η∗]+Pr⁡[α=1∣∥η∥2<η∗]≤negl(d)(12)\Pr[O_2(q_i)\ne O_3(q_i)] \le\Pr[\beta=0\mid\|\eta\|_2\ge\eta^*]+\Pr[\alpha=1\mid\|\eta\|_2<\eta^*]\le negl(d) \tag*{(12)}

Since the probability of divergence for each query is negligible, the statistical distance between the outputs of O2O_2 and O3O_3 over a polynomial number of queries remains negligible in dd.

To conclude the proof, let us denote Δ(⋅,⋅)\Delta(\cdot,\cdot) as the total variation distance over the output distribution of the input oracles. From (11), we have

Δ(O,O2)≤negl(d)\Delta(O,O_2)\le negl(d)

and similarly from (12)

Δ(O2,O3)≤negl(d),\Delta(O_2,O_3)\le negl(d),

for some negligible function neglnegl. Therefore,

Δ(O,O3)≤2⋅negl(d)\Delta(O,O_3)\le2\cdot negl(d)

and the claim follows.

Lemma (Lemma 2). Let Λ:=Λb\Lambda:=\Lambda_b be as defined in (1), and let ΛT=[F,D]\Lambda^{\mathsf T}=[F,D], where

F=(A1TA2T)andD=(A3TBiTA4TBiT).F=\begin{pmatrix}A_1^{\mathsf T}\\A_2^{\mathsf T}\end{pmatrix} \qquad\text{and}\qquad D=\begin{pmatrix}A_3^{\mathsf T}B_i^{\mathsf T}\\A_4^{\mathsf T}B_i^{\mathsf T}\end{pmatrix}.

Here, FF and DD denote the fixed secret transformation and the one-time masked transformation, respectively. Let F\mathcal{F} be the set of all bases that are orthogonal to DD. For any fixed rotation matrix R∈Haar⁡(d/2)R \in\operatorname{Haar}(d/2) and any measurable subset S⊆F\mathcal{S} \subseteq\mathcal{F}, the conditional probability over the randomized choice of the secret basis yields:

∣Pr⁡[F∈S∣Y,O(q1),…]−Pr⁡[F∈SR∣Y,O(q1),…]∣≤negl⁡(d),\left|\Pr[F \in\mathcal{S}\mid Y,\mathcal{O}(q_1),\ldots]-\Pr[F \in\mathcal{S}_R\mid Y,\mathcal{O}(q_1),\ldots]\right|\leq\operatorname{negl}(d),

where the set SR={sR:s∈S}\mathcal{S}_R=\{sR:s\in\mathcal{S}\}. That is, the secret fixed transformation FF is only recoverable up to a random rotation.

Proof. It suffices to show that FF is conditionally independent of both the watermarked samples YY and oracle responses O(q1),…\mathcal{O}(q_1),\ldots.

By Lemma 1, the outputs of the actual oracle O\mathcal{O} are statistically indistinguishable from an oracle O3\mathcal{O}_3 that evaluates solely on the dynamic component β\beta. For any query q=Yi+ηq=Y_i+\eta, the perturbation’s projection onto the effective transformation is:

ηΛT=(ηFTηDi)\eta\Lambda^{\mathsf T}=(\eta F^{\mathsf T}\quad\eta D_i)

Because O3\mathcal{O}_3 evaluates strictly on β\beta, the oracle responses depend exclusively on the projection ηDi\eta D_i.

Since the fixed transformation A∼Haar⁡(d)A\sim\operatorname{Haar}(d), it follows that FF consists of d/2d/2 random dd-dimensional components which are mutually orthonormal. Thus, for any rotation matrix R∼Haar⁡(d/2)R\sim\operatorname{Haar}(d/2) and any matrix f∈Rd×d/2f\in\mathbb{R}^{d\times d/2} with orthonormal columns, the prior distribution of FF is rotationally invariant, i.e.

Pr⁡[F∈S]=Pr⁡[F∈SR]=Pr⁡[FRT∈S].\Pr[F\in\mathcal{S}]=\Pr[F\in\mathcal{S}_R]=\Pr[FR^{\mathsf T}\in\mathcal{S}].

Thus, both

(ηFTηDi)(\eta F^{\mathsf T}\quad\eta D_i)

and

(ηFRηDi)(\eta FR\quad\eta D_i)

are statistically indistinguishable.

To conclude the proof, it suffices to show that FF and FRFR are conditionally indistinguishable given DiD_i. Let MiM_i denote the orthonormal block-diagonal masking matrix such that Λi=MiA\Lambda_i=M_iA. Because A∼Haar⁡(d)A\sim\operatorname{Haar}(d) and left-multiplication by a fixed orthonormal matrix preserves the Haar measure, the product Λi\Lambda_i is also Haar(d)(d)-distributed. Therefore,

ΛiT=[F,Di]\Lambda_i^{\mathsf T}=[F,D_i]

is a Haar-distributed orthonormal basis of Rd\mathbb{R}^d. Since for any R∼Haar⁡(d/2)R\sim\operatorname{Haar}(d/2), FRFR spans the exact same orthogonal complement of DiD_i (i.e. if FF and DD are orthogonal, then FRFR and DD are also orthogonal), it follows that

Pr⁡[F∈F∣Di]=Pr⁡[F∈FR∣Di]\Pr[F\in\mathcal{F}\mid D_i]=\Pr[F\in\mathcal{F}R\mid D_i]

for any set F\mathcal{F} orthogonal to DiD_i. That is, all choices of

{Fr:r∈Supp⁡(Haar⁡(d/2))}\{Fr:r\in\operatorname{Supp}(\operatorname{Haar}(d/2))\}

are equally likely, where Supp⁡(Haar⁡(d/2))\operatorname{Supp}(\operatorname{Haar}(d/2)) denotes the support of the Haar⁡(d/2)\operatorname{Haar}(d/2) distribution, i.e. all d/2×d/2d/2\times d/2 orthonormal matrices. Since the oracle responses depend only on DiD_i (by Lemma 1), and the passive samples YY are drawn from an isotropic Gaussian distribution N(0,Id)\mathcal{N}(0,I_d) regardless of FF, the full observation history yields the same indistinguishability. The claim thus follows. □\square

Lemma (Lemma 3). Let F∈Rd×d/2F\in\mathbb{R}^{d\times d/2} be an orthonormal basis, and R∼Haar⁡(d/2)R\sim\operatorname{Haar}(d/2) be independent of a perturbation η\eta. It follows that

Δ(ηFR,∥ηF∥2Ud/2)=0.\Delta(\eta FR,\|\eta F\|_2U_{d/2})=0.

That is, an adversary that knows FF only up to a rotation RR sampled uniformly from Orth⁡(d/2)\operatorname{Orth}(d/2) cannot outperform adding isotropic white-noise of magnitude ∥ηF∥2\|\eta F\|_2.

Proof. Condition on any realization of η∈Rd\eta\in\mathbb{R}^d. Since R∼Haar⁡(d/2)R\sim\operatorname{Haar}(d/2), the vector ηFR\eta FR is uniformly distributed on Sd/2−1\mathbb{S}^{d/2-1}. Hence Δ(ηFR,∥ηF∥2Ud/2)=0\Delta(\eta FR,\|\eta F\|_2U_{d/2})=0. Since the equality holds for all realization of η\eta, the total variation distance between the two distributions is zero. □\square

Lemma (Lemma 4). Suppose an adversary A\mathcal{A} is given the two d/2d/2-dimensional subspaces corresponding to AFA_F and ADA_D, up to rotations sampled independently from Haar⁡(d/2)\operatorname{Haar}(d/2). Then any perturbation η\eta chosen by A\mathcal{A} with ∥η∥2≤ϵ\|\eta\|_2\leq\epsilon has negligible advantage over full-space isotropic white-noise of magnitude 2ϵ\sqrt{2\epsilon}. That is,

Succ⁡(A,ϵ)≤Succ⁡(Aw,2ϵ)\operatorname{Succ}(\mathcal{A},\epsilon)\leq\operatorname{Succ}(\mathcal{A}_w,\sqrt{2\epsilon})

Proof. For any perturbation η\eta with ∥η∥2≤ϵ\|\eta\|_2\leq\epsilon, write the hidden fixed and dynamic bases as

PF=FR,D=ADR′,P_F=FR,\qquad D=A_DR',

where R,R′∼Haar⁡(d/2)R,R'\sim\operatorname{Haar}(d/2) are sampled independently. Define

a:=∥ηPF∥2,b:=∥ηD∥2.a:=\|\eta P_F\|_2,\qquad b:=\|\eta D\|_2.

Since PFP_F and DD are orthonormal bases for orthogonal d/2d/2-dimensional subspaces,

a2+b2=∥ηPF∥22+∥ηD∥22≤∥η∥22≤ϵ2.a^2+b^2=\|\eta P_F\|_2^2+\|\eta D\|_2^2\leq\|\eta\|_2^2\leq\epsilon^2.

We first consider the fixed component. Since right multiplication by an orthogonal matrix preserves norm,

∥ηF∥2=∥ηFR∥2=∥ηPF∥2=a.\|\eta F\|_2=\|\eta FR\|_2=\|\eta P_F\|_2=a.

Moreover, since RR is sampled uniformly from O(d/2)O(d/2),

Δ(ηPF,aUd/2)=0.\Delta(\eta P_F,aU_{d/2})=0.

where Ud/2U_{d/2} is uniform on Sd/2−1\mathbb{S}^{d/2-1}.

Similarly, since D=ADR′D=A_DR' and R′∼Haar⁡(d/2)R'\sim\operatorname{Haar}(d/2) is the one-time rotation for the dynamic component,

∥ηAD∥2=∥ηADR′∥2=∥ηD∥2=b,\|\eta A_D\|_2=\|\eta A_DR'\|_2=\|\eta D\|_2=b,

and hence

Δ(ηD,bVd/2)=0.\Delta(\eta D,bV_{d/2})=0.

where Vd/2V_{d/2} is sampled uniformly from Sd/2−1\mathbb{S}^{d/2-1}. Therefore, the effective perturbation in detector coordinates satisfies

Δ(ηΛiT,(aUd/2,bVd/2))=0.\Delta(\eta\Lambda_i^{\mathsf T},(aU_{d/2},bV_{d/2}))=0.

That is, the adversary is limited to isotropic white-noise of magnitude aa and bb within the two subspaces.

Since a,b≤ϵa,b\le\epsilon, the perturbation (aUd/2,bVd/2)(aU_{d/2},bV_{d/2}) is dominated by (ϵUd/2,ϵVd/2)(\epsilon U_{d/2},\epsilon V_{d/2}).

Under the well-behaved threshold detector model, increasing the isotropic perturbation magnitude in either half can only increase the probability that the corresponding sign-flip threshold is exceeded. Hence,

Pr⁡[reject under (aUd/2,bVd/2)]≤Pr⁡[reject under (ϵUd/2,ϵVd/2)].\Pr[\text{reject under }(aU_{d/2},bV_{d/2})]\le\Pr[\text{reject under }(\epsilon U_{d/2},\epsilon V_{d/2})].

Furthermore, (ϵUd/2,ϵVd/2)(\epsilon U_{d/2},\epsilon V_{d/2}) has total squared norm

ϵ2+ϵ2=2ϵ2,\epsilon^2+\epsilon^2=2\epsilon^2,

and hence total magnitude 2ϵ\sqrt{2}\epsilon. Let Aw\mathcal{A}_w output isotropic white-noise WW over the entire dd-dimensions with ∥W∥2=2ϵ\lVert W\rVert_2=\sqrt{2}\epsilon. Let ss be a random subset of d/2d/2 elements from WW. Standard concentration of measure results gives

Pr⁡[∣∥s∥22−ϵ2∣>ϵ2d−1/3]≤exp⁡(−Ω(d1/3)).\Pr\left[\left|\lVert s\rVert_2^2-\epsilon^2\right|>\epsilon^2d^{-1/3}\right]\le\exp(-\Omega(d^{1/3})).

By a union bound, with probability at least

1−2exp⁡(−Ω(d1/3)),1-2\exp(-\Omega(d^{1/3})),

the split isotropic perturbation (ϵUd/2,ϵVd/2)(\epsilon U_{d/2},\epsilon V_{d/2}) and the full-space isotropic perturbation of magnitude 2ϵ\sqrt{2}\epsilon induce the same detector behavior up to a negligible concentration error. It follows that

Succ⁡(A,ϵ)≤Succ⁡(Aw,2ϵ)+negl⁡(d).\operatorname{Succ}(\mathcal{A},\epsilon)\le\operatorname{Succ}(\mathcal{A}_w,\sqrt{2}\epsilon)+\operatorname{negl}(d).

Lemma (Lemma 5). Continuing from the setting in Lemma 2. If there exists a adversary A\mathcal{A} operating under the REM2 threat model such that Adv⁡(A,ϵ)\operatorname{Adv}(\mathcal{A},\epsilon) is non-negligible, then there exists a measurable subset S⊆FS\subseteq\mathcal{F}, a rotation R∈Haar⁡(d/2)R\in\operatorname{Haar}(d/2), and polynomial p(⋅)>0p(\cdot)>0 such that:

∣Pr⁡[F∈S∣Y,O(q1),…]−Pr⁡[F∈SR∣Y,O(q1),…]∣≥1p(d),\left|\Pr[F\in S\mid Y,O(q_1),\ldots]-\Pr[F\in S_R\mid Y,O(q_1),\ldots]\right|\ge\frac{1}{p(d)},

where SR={MR:M∈S}S_R=\{MR:M\in S\}. That is, A\mathcal{A} can distinguish the specific orientation of the fixed basis FF from a rotated counterpart with non-negligible probability.

Proof. We prove the contrapositive. Suppose that A\mathcal{A} obtains negligible orientation information about FF. That is, for all polynomial p(⋅)>0p(\cdot)>0 and adversary’s view ZAZ_{\mathcal{A}},

Pr⁡ZA[∃S⊆F,∃R∈Orth⁡(d/2) such that∣Pr⁡[F∈S∣ZA]−Pr⁡[F∈SR∣ZA]∣≥1p(d)]\Pr_{Z_{\mathcal{A}}}\left[ \exists S\subseteq\mathcal{F},\exists R\in\operatorname{Orth}(d/2)\text{ such that} \left|\Pr[F\in S\mid Z_{\mathcal{A}}]-\Pr[F\in S_R\mid Z_{\mathcal{A}}]\right|\ge\frac{1}{p(d)} \right]

is negligible, where Orth⁡(m)\operatorname{Orth}(m) denote the orthonormal group in mm dimensions.

Let

η=A(ZA),∥η∥2≤ϵ,\eta=\mathcal{A}(Z_{\mathcal{A}}),\qquad\lVert\eta\rVert_2\le\epsilon,

and PFP_F and PDP_D denote the orthogonal projectors onto the fixed and dynamic half-subspaces, respectively. Define

a:=∥ηPF∥2,b:=∥ηPD∥2.a:=\lVert\eta P_F\rVert_2,\qquad b:=\lVert\eta P_D\rVert_2.

Since PFP_F and PDP_D project onto orthogonal half-subspaces,

a2+b2≤∥η∥22≤ϵ2.a^2+b^2\le\lVert\eta\rVert_2^2\le\epsilon^2.

Because the conditional distribution of FF remains invariant under right multiplication by rotations in Orth⁡(d/2)\operatorname{Orth}(d/2), the adversary does not know the orientation of the detector basis inside the fixed subspace. Therefore, the total variation distance

Δ(ηFT,aUd/2)≤negl⁡(d),\Delta(\eta F^{\mathsf T},aU_{d/2})\le\operatorname{negl}(d),

where UmU_m is uniform on the unit sphere Sd/2−1\mathbb{S}^{d/2-1}. Similarly, for the challenge sample, the dynamic detector basis is masked by a fresh one-time Haar rotation. Hence

Δ(ηDT,bUd/2)≤negl⁡(d),\Delta(\eta D^{\mathsf T},bU_{d/2})\le\operatorname{negl}(d),

where DD denotes the dynamic basis for the challenge sample. Thus, conditioned on this realization of ZAZ_{\mathcal{A}}, the adversary’s perturbation is equivalent to an isotropic perturbation in the two hidden half-spaces, with some energy split (a,b)(a,b) satisfying a2+b2≤ϵ2a^2+b^2\le\epsilon^2. The adversary cannot target individual detector coordinates; it can only choose how much energy to allocate to each half.

By the subspace-isotropization and 2ϵ\sqrt{2}\epsilon baseline comparison lemma, every such rotation-hidden perturbation is dominated by the full-space isotropic white-noise adversary of magnitude 2ϵ\sqrt{2}\epsilon. Hence

Succ⁡(A,ϵ∣ZA)≤Succ⁡(Aw,2ϵ)+negl⁡(d)\operatorname{Succ}(\mathcal{A},\epsilon\mid Z_{\mathcal{A}})\le\operatorname{Succ}(\mathcal{A}_w,\sqrt{2}\epsilon)+\operatorname{negl}(d)

where Succ⁡(A,ϵ∣ZA)\operatorname{Succ}(\mathcal{A},\epsilon\mid Z_{\mathcal{A}}) denotes the success probability of A\mathcal{A} conditional on view ZAZ_{\mathcal{A}}.

Averaging over ZAZ_{\mathcal{A}}, and using that bad realizations occur with negligible probability, gives

Succ⁡(A,ϵ)≤Succ⁡(Aw,2ϵ)+negl⁡(d).\operatorname{Succ}(\mathcal{A},\epsilon)\le\operatorname{Succ}(\mathcal{A}_w,\sqrt{2}\epsilon)+\operatorname{negl}(d).

Therefore

Adv⁡(A,ϵ)≤negl⁡(d).\operatorname{Adv}(\mathcal{A},\epsilon)\le\operatorname{negl}(d).

Taking the contrapositive proves the lemma. □

Theorem (Theorem 2). If the underlying PRC encoder, PRF, and orthonormal matrix generators are secure pseudorandom primitives, and the condition in (5) is met, then under the REM2 threat model, for all PPT adversaries A\mathcal{A},

Adv⁡(A,ϵ)≤negl⁡(λ),\operatorname{Adv}(\mathcal{A},\epsilon)\le\operatorname{negl}(\lambda),

where λ\lambda is the security parameter.

Proof. We proceed via a sequence of hybrid experiments, starting from the real-world instantiation and replacing the pseudorandom matrices with their idealized counterparts. Let A\mathcal{A} be a PPT adversary bounded by a perturbation budget ϵ\epsilon, and assume d≥λd\ge\lambda. We denote the advantage of A\mathcal{A} in hybrid Hx\mathsf{H}_x as Adv⁡Hx(A,ϵ)\operatorname{Adv}_{\mathsf{H}_x}(\mathcal{A},\epsilon).

  • Hybrid 0 (H0H_0): This corresponds to the real-world watermarking system defined in Algorithms 1, 2, and 3. By definition, AdvH0(A,ϵ)=Adv(A,ϵ)Adv_{H_0}(\mathcal{A},\epsilon)=Adv(\mathcal{A},\epsilon).

  • Hybrid 1 (H1H_1): We modify H0H_0 by replacing the long-term secret matrix A←SRandOrthonormal⁡(d,k2)A\leftarrow\operatorname{SRandOrthonormal}(d,k_2) with a truly random A∗∼Haar⁡(d)A^* \sim\operatorname{Haar}(d), applied consistently in both sample generation and oracle detection. This transition is valid because k2k_2 is never revealed to A\mathcal{A}. Any PPT distinguisher between H0H_0 and H1H_1 directly breaks the pseudorandomness of SRandOrthonormal⁡\operatorname{SRandOrthonormal}:

∣AdvH0(A,ϵ)−AdvH1(A,ϵ)∣≤negl1(λ)\left|Adv_{H_0}(\mathcal{A},\epsilon)-Adv_{H_1}(\mathcal{A},\epsilon)\right|\le negl_1(\lambda)
  • Hybrid 2 (H2H_2): We modify H1H_1 by replacing each per-sample matrix Bi=SRandOrthonormal⁡(d/2,r)B_i=\operatorname{SRandOrthonormal}(d/2,r) with a perfectly random matrix Bi∗∼Haar⁡(d/2)B_i^*\sim\operatorname{Haar}(d/2), consistently in both generation and detection. This transition is valid because the nonce rr is computationally hidden from A\mathcal{A}; it appears in the adversary’s view only through C1=PRC⁡(k1,r)C_1=\operatorname{PRC}(k_1,r) and C2=fk3(r)C_2=f_{k_3}(r). Recovering rr requires breaking the computational security of the PRC or the PRF. Since A\mathcal{A} cannot recover rr, the output of SRandOrthonormal⁡\operatorname{SRandOrthonormal} is computationally indistinguishable from a Haar-random matrix:

∣AdvH1(A,ϵ)−AdvH2(A,ϵ)∣≤negl2(λ)+negl3(λ)+negl4(λ)\left|Adv_{H_1}(\mathcal{A},\epsilon)-Adv_{H_2}(\mathcal{A},\epsilon)\right| \le negl_2(\lambda)+negl_3(\lambda)+negl_4(\lambda)

where negl2negl_2 is the cost of the SRandOrthonormal⁡\operatorname{SRandOrthonormal} reduction, and negl3,negl4negl_3,negl_4 bound the probability of rr being recovered from C1C_1 or C2C_2.

Note that H2H_2 matches the conditions of the information-theoretic result in Theorem 1. Therefore,

AdvH2(A,ϵ)≤negl5(d)≤negl5(λ),Adv_{H_2}(\mathcal{A},\epsilon)\le negl_5(d)\le negl_5(\lambda),

where the latter is due to λ≤d\lambda\le d. By the triangle inequality,

∣Adv(A,ϵ)−AdvH2(A,ϵ)∣=∣AdvH0(A,ϵ)−AdvH2(A,ϵ)∣≤∣AdvH0(A,ϵ)−AdvH1(A,ϵ)∣+∣AdvH1(A,ϵ)−AdvH2(A,ϵ)∣≤negl1(λ)+negl2(λ)+negl3(λ)+negl4(λ)\begin{aligned} \left|Adv(\mathcal{A},\epsilon)-Adv_{H_2}(\mathcal{A},\epsilon)\right| &=\left|Adv_{H_0}(\mathcal{A},\epsilon)-Adv_{H_2}(\mathcal{A},\epsilon)\right|\\ &\le\left|Adv_{H_0}(\mathcal{A},\epsilon)-Adv_{H_1}(\mathcal{A},\epsilon)\right|+\left|Adv_{H_1}(\mathcal{A},\epsilon)-Adv_{H_2}(\mathcal{A},\epsilon)\right|\\ &\le negl_1(\lambda)+negl_2(\lambda)+negl_3(\lambda)+negl_4(\lambda) \end{aligned}

which is negligible in λ\lambda. It follows that,

Adv(A,ϵ)≤∣Adv(A,ϵ)−AdvH2(A,ϵ)∣+AdvH2(A,ϵ)Adv(\mathcal{A},\epsilon)\le\left|Adv(\mathcal{A},\epsilon)-Adv_{H_2}(\mathcal{A},\epsilon)\right|+Adv_{H_2}(\mathcal{A},\epsilon)

which is negligible in $\lambda.

Additional Empirical Studies

Validating Threshold Gap Condition

We empirically verify that the threshold gap condition in (5) is fulfilled. To empirically estimate τ1\tau_1, we proceed as follows:

  1. Randomly sample a PRC latent codeword CC of length d/2d/2, embedding a uniformly sampled 100-bit message.

  2. Generate 1,000 noisy copies C1,p,…,C1000,pC_{1,p},\ldots,C_{1000,p}, where each Ci,pC_{i,p} is a copy of CC with each entry’s sign randomly flipped with probability pp.

  1. Find the maximum value of p′p' such that all C1,p′,…,C1000,p′C_{1,p'},\ldots,C_{1000,p'} successfully decode. We set this p′p' as our estimate for τ1\tau_1.

In our experiments, the value of τ1\tau_1 is estimated to be 0.31 for d=16,384d=16,384 (SD2.1), and 0.37 for d=65,536d=65,536 (SDXL).

Single-Bit Watermarking: By setting t<d2(τ1−ln⁡dln⁡ln⁡dd)t < \frac{d}{2}\left(\tau_1-\sqrt{\frac{\ln d\ln\ln d}{d}}\right), the condition in (5) is satisfied.

Multi-Bit Watermarking: For multi-bit watermarking, we use the parameters suggested in the pyldpc package. Similar to the PRC case, we empirically estimate the threshold τ2\tau_2 using the same sign-flipping noise injection method described above. In our experiments, the value of τ2\tau_2 is estimated to be 0.26 for d=16,384d=16,384 (SD2.1), and 0.34 for d=65,536d=65,536 (SDXL). This meets the threshold gap condition in (5).

Performance Overhead

We evaluate the memory and computational overhead of our proposed defense on both SD2.1 and SDXL.

Memory Overhead: For efficiency, the fixed d×dd\times d transformation matrix AA and the one-time (d/2)×(d/2)(d/2)\times(d/2) matrix BB are stored in memory. This combined storage results in a total memory footprint of approximately 1.3 GB for SD2.1 and 20.0 GB for SDXL, representing an approximate 15.4×\times increase in memory requirements.

Time Overhead: We measured the average execution time for the sampling and decoding phases across 100 independent trials. In both Algorithm 2 (Line 12) and Algorithm 3 (Lines 4 and 11), the primary computational bottlenecks are dense matrix multiplications, which require O(d2)O(d^2) operations.

Because the latent dimension dd in SDXL is 4 times larger than in SD2.1, the O(d2)O(d^2) complexity yields a theoretical 16×\times increase in computational workload. As shown in Table VII, our empirical latency measurements closely align with this expected scaling factor, demonstrating 12.0×\times and 9.5×\times increases for sampling and decoding, respectively. The deviation from the theoretical 16×\times likely stems from other fixed overhead incurred during the sampling and decoding steps.

MetricSD2.1SDXLEmpirical ScalingTheoretical Scaling
Total Memory∼\sim1.3 GB∼\sim20.0 GB15.0×\times16.0×\times
Sample Time (s)0.11.212.0×\times16.0×\times
Decode Time (s)0.21.99.5×\times16.0×\times

Table VII. Average memory and time overhead for sampling and decoding phases (averaged over 100 trials), rounded to the nearest 1 decimal place. The empirical scaling closely tracks the theoretical 16×\times increase expected from the O(d2)O(d^2) matrix operations. As a comparison, the average unwatermarked per-image generation times are approximately 2.5s and 7.3s for SD2.1 and SDXL, respectively

Samples of Watermarked Images

Samples of watermarked images generated are in Figure 3 and Figure 4 for Stable Diffusion 2.1 and Stable Diffusion XL, respectively.

Watermarked images generated using Stable Diffusion 2.1

Figure 3. a comic potrait of a female necromamcer with big and cute eyes, fine - face, realistic shaded perfect face, fine details. night setting. very anime style. realistic shaded lighting poster by ilya kuvshinov katsuhiro, magali villeneuve, artgerm, jeremy lipkin and michael garmash, rob rey and kentaro miura style, trending on art station

steampunk market interior, colorful, 3 d scene, greg rutkowski, zabrocki, karlkka, jayison devadas, trending on artstation, 8 k, ultra wide angle, zenith view, pincushion lens effect

A portrait of a cyborg in a golden suit, D&D sci-fi, artstation, concept art, highly detailed illustration.

A full portrait of a beautiful post apocalyptic offworld nanotechnician, intricate, elegant, highly detailed, digital painting, artstation, concept art, smooth, sharp focus, illustration, art by Krenz Cushart and Artem Demura and alphonse mucha

Watermarked images generated using Stable Diffusion 2.1 using prompts from the Stable Diffusion Prompts dataset

Watermarked images generated using Stable Diffusion XL using prompts from the Stable Diffusion Prompts dataset

Figure 4. Watermarked images generated using Stable Diffusion XL using prompts from the Stable Diffusion Prompts dataset

References

  1. [1]X. Zhao, S. Gunn, M. Christ, J. Fairoze, A. Fabrega, N. Carlini, S. Garg, S. Hong, M. Nasr, F. Tramer et al., “Sok: Watermarking for ai-generated content,” in IEEE Symposium on Security and Privacy (SP), 2025.arxiv.org/abs/2411.18479
  2. [2]S. Gunn, X. Zhao, and D. Song, “An undetectable watermark for generative image models,” 2025. [Online]. Available: https://arxiv.org/abs/2410.07369
  3. [3]D. Z. Lee, H. Fang, H. Wang, and E.-C. Chang, “Removal attack and defense on ai-generated content latent-based watermarking,” in ACM SIGSAC Conference on Computer and Communications Security (CCS), 2025.arxiv.org/abs/2509.11745
  4. [4]S. Gowal, R. Bunel, F. Stimberg, D. Stutz, G. Ortiz-Jimenez, C. Kouridi, M. Vecerik, J. Hayes, S.-A. Rebuffi, P. Bernard, C. Gamble, M. Z. Horváth, F. Kaczmarczyk, A. Kaskosali, A. Petrov, I. Shumailov, M. Tothakuri, O. Wiles, J. Yung, Z. Ahmed, V. Martin, S. Rosen, C. Savčák, A. Senoner, N. Vyas, and P. Kohli, “Synthid-image: Image watermarking at internet scale,” 2025. [Online]. Available: https://arxiv.org/abs/2510.09263
  5. [5]Google DeepMind, SynthID: A tool to watermark and identify content generated through AI. [Online]. Available: https://deepmind.google/models/synthid/
  6. [6]J. Weatherbed. Google is trying to make deepfake detection more accessible for everyone. The Verge. Archived at https://archive.is/puRhV. [Online]. Available: https://www.theverge.com/tech/933424/google-synthid-c2pa-content-credentials-expansion
  7. [7]A. Denny. (2026) reverse-SynthID: Reverse engineering Gemini’s SynthID detection. [Online]. Available: https://github.com/alosheddny/Reverse-SynthID
  8. [8]European Parliament and Council of the European Union, “Regulation (EU) 2024/1689 of the European Parliament and of the Council of 13 June 2024 laying down harmonised rules on artificial intelligence (Artificial Intelligence Act),” Official Journal of the European Union, L series, 12 July 2024, 2024, https://eur-lex.europa.eu/eli/reg/2024/1689/oj.
  9. [9]Anthropic, “How Claude’s text watermark works,” https://www.anthropic.com/news/claude-text-watermark, Aug. 2026, accessed: 2026-08-19.
  10. [10]J. Cohen, E. Rosenfeld, and Z. Kolter, “Certified adversarial robustness via randomized smoothing,” in International Conference on Machine Learning, (ICML), 2019.arxiv.org/abs/1902.02918
  11. [11]Z. Yang, K. Zeng, K. Chen, H. Fang, W. Zhang, and N. Yu, “Gaussian shading: Provable performance-lossless image watermarking for diffusion models,” in IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2024.arxiv.org/abs/2404.04956
  12. [12]X. Zhao, K. Zhang, Z. Su, S. Vasan, I. Grischenko, C. Kruegel, G. Vigna, Y.-X. Wang, and L. Li, “Invisible image watermarks are provably removable using generative ai,” in Advances in Neural Information Processing Systems (NeurIPS), 2024.arxiv.org/abs/2306.01953
  13. [13]R. Rombach, A. Blattmann, D. Lorenz, P. Esser, and B. Ommer, “High-resolution image synthesis with latent diffusion models,” in IEEE/CVF conference on computer vision and pattern recognition (CVPR), 2022.arxiv.org/abs/2112.10752
  14. [14]J. Song, C. Meng, and S. Ermon, “Denoising diffusion implicit models,” 2022. [Online]. Available: https://arxiv.org/abs/2010.02502
  15. [15]J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” 2020. [Online]. Available: https://arxiv.org/abs/2006.11239
  16. [16]D. P. Kingma and M. Welling, “Auto-encoding variational bayes,” 2022. [Online]. Available: https://arxiv.org/abs/1312.6114
  17. [17]A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, K. Krueger, and I. Sutskever, “Learning transferable visual models from natural language supervision,” in International Conference on Machine Learning, (ICML), 2021.arxiv.org/abs/2103.00020
  18. [18]H. Fang, K. Chen, Z. Yang, B. Cui, W. Zhang, and E.-C. Chang, “Cosda: Enhancing the robustness of inversion-based generative image watermarking framework,” AAAI Conference on Artificial Intelligence, 2025.DOI
  19. [19]H. Wang, H. Fang, S.-L. Wang, and E.-C. Chang, “Roar: Reducing inversion error in generative image watermarking,” in IEEE/CVF International Conference on Computer Vision (ICCV), 2025.DOI
  20. [20]Y. Wen, J. Kirchenbauer, J. Geiping, and T. Goldstein, “Tree-rings watermarks: invisible fingerprints for diffusion images,” in International Conference on Neural Information Processing Systems (NIPS), 2023.DOI
  21. [21]M. Christ and S. Gunn, “Pseudorandom error-correcting codes,” 2024. [Online]. Available: https://arxiv.org/abs/2402.09370
  22. [22]Z. Yang, X. Zhang, K. Chen, K. Zeng, Q. Yao, H. Fang, W. Zhang, and N. Yu, “Gaussian shading++: Rethinking the realistic deployment challenge of performance-lossless image watermark for diffusion models,” 2025. [Online]. Available: https://arxiv.org/abs/2504.15026
  23. [23]K. Shehata, A. Kolluri, and P. Saxena, “ClueMark: Watermarking diffusion models using clwe,” 2025. [Online]. Available: https://arxiv.org/abs/2411.11434
  24. [24]A. Auddy and M. Yuan, “Large dimensional independent component analysis: Statistical optimality and computational tractability,” 2023. [Online]. Available: https://arxiv.org/abs/2303.18156
  25. [25]D. Podell, Z. English, K. Lacey, A. Blattmann, T. Dockhorn, J. Müller, J. Penna, and R. Rombach, “Sdxl: Improving latent diffusion models for high-resolution image synthesis,” 2023. [Online]. Available: https://arxiv.org/abs/2307.01952
  26. [26]Gustavosta, “Stable-diffusion-prompts dataset,” https://huggingface.co/ datasets/Gustavosta/Stable-Diffusion-Prompts, 2022.
  27. [27]U. Lorenzo-Seva and J. M. Ten Berge, “Tucker’s congruence coefficient as a meaningful index of factor similarity,” Methodology, vol. 2, no. 2, pp. 57–64, 2006.
  28. [28]G.-S. Chou, S.-G. Hwang, S.-H. Rim, B. L. Shader, and S.-Z. Song, “Sparse orthogonal matrices,” Linear algebra and its applications, vol. 373, 2003.
  29. [29]J. R. Douceur, “The sybil attack,” in International workshop on peer-to-peer systems, 2002.DOI
  30. [30]L. Shi, L. Shan, E. Wenger, J. Zhang, H. Zheng, and B. Y. Zhao, “Blacklight: Scalable defense for neural networks against {Query-Based} {Black-Box} attacks,” in USENIX Security Symposium (USENIX), 2022.
  31. [31]M. M. Rahman, “A dwt, dct and svd based watermarking technique to protect the image piracy,” International Journal of Managing Public Sector Information and Communication Technologies, 2013.
  32. [32]Z. Jia, H. Fang, and W. Zhang, “Mbrs: Enhancing robustness of dnn-based watermarking by mini-batch of real and simulated jpeg compression,” in ACM International Conference on Multimedia (MM), ser. MM ’21, 2021.
  33. [33]M. Cao, Y. Huang, H. Guan, H. C. Song, N. B. Niu, and J. Liu, “A survey of dnn-based image watermarking,” in International Conference on Communication and Information Processing (ICCIP). Association for Computing Machinery, 2024.DOI
  34. [34]S. J. Lee and N. I. Cho, “Phasemark: A post-hoc, optimization-free watermarking of ai-generated images in the latent frequency domain,” 2026. [Online]. Available: https://arxiv.org/abs/2601.13128
  35. [35]Y. Guo, R. Li, M. Hui, H. Guo, C. Zhang, C. Cai, L. Wan, and S. Wang, “Freakmark: Invisible image watermarking via frequency based optimization in latent space,” 2024. [Online]. Available: https://arxiv.org/abs/2410.20824
  36. [36]B. Tondi, A. Costanzo, and M. Barni, “Robust and large-payload dnn watermarking via fixed, distribution-optimized, weights,” 2024. [Online]. Available: https://arxiv.org/abs/2208.10973
  37. [37]E. Gesny, E. Giboulot, T. Furon, and V. Chappelier, “Guidance watermarking for diffusion models,” 2025. [Online]. Available: https://arxiv.org/abs/2509.22126
  38. [38]D. Lin, Y. Li, B. Tondi, K. Lin, B. Li, and M. Barni, “An efficient watermarking method for latent diffusion models via low-rank adaptation and dynamic loss weighting,” 2025. [Online]. Available: https://arxiv.org/abs/2410.20202
  39. [39]N. Goren, O. Katzir, A. Nakarmi, E. Ronen, M. Sharif, and O. Patashnik, “Noiseprints: Distortion-free watermarks for authorship in private diffusion models,” 2025. [Online]. Available: https://arxiv.org/abs/2510.13793
  40. [40]D. Z. Lee, H. E. Fang, and E.-C. Chang, “Proof-of-authorship for diffusion-based ai generated content,” 2026. [Online]. Available: https://arxiv.org/abs/2603.17513
  41. [41]Y. Hu, Z. Jiang, M. Guo, and N. Gong, “Stable signature is unstable: Removing image watermark from diffusion models,” 2024. [Online]. Available: https://arxiv.org/abs/2405.07145
  42. [42]A. Adelsbach, S. Katzenbeisser, and H. Veith, “Watermarking schemes provably secure against copy and ambiguity attacks,” in ACM Workshop on Digital Rights Management, 2003.
  43. [43]Q. Li and E.-C. Chang, “On the possibility of non-invertible watermarking schemes,” in International Conference on Information Hiding, 2004.DOI
  44. [44]L. Fan, K. W. Ng, and C. S. Chan, “[extended version] rethinking deep neural network ownership verification: Embedding passports to defeat ambiguity attacks,” 2019. [Online]. Available: https://arxiv.org/abs/1909.07830
  45. [45]H. T. Sen, C. L. Li, and N. Memon, “A new approach to countering ambiguity attacks,” in Workshop on Multimedia & Security, 2007.
  46. [46]F. Mezzadri, “How to generate random matrices from the classical compact groups,” 2007. [Online]. Available: https://arxiv.org/abs/math-ph/0609050
  47. [47]G. E. Box and M. E. Muller, “A note on the generation of random normal deviates,” The annals of mathematical statistics, 1958.DOI

Paper details

vlnc:W_ayrkdhrz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents