PaperlayerView exact revision on arXiv

Source-linked AI summary

Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models

Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, Boaz Barak

arXiv:2311.04378v5cs.LGcs.CLcs.CR

TL;DR

Strong watermarking asks whether an attacker can remove a model's watermark without significantly degrading output quality. The paper analyzes this under quality- and perturbation-oracle assumptions, using a quality-preserving random walk. It concludes that strong watermarking is impossible under those assumptions, including in secret-key settings.

  • Problem

    The paper asks whether a computationally bounded attacker can remove a watermark without significant quality degradation, including when detection uses a secret key.

    Source: §1 · p. 2

  • Method

    The authors use a quality oracle and a perturbation oracle to construct a random walk among high-quality outputs, accepting perturbations that preserve prompt-level quality.

    Source: §1 · pp. 3–4

  • Results

    Under the stated assumptions, the paper concludes that strong watermarking is impossible, including in secret-key settings.

    Source: §1 · p. 2, §6 · p. 21

  • Takeaways & Limitations

    The authors are not optimistic about strong watermarking that would prevent a determined attacker, while noting that their attack is not very efficient.

    Source: §6 · p. 21

    The result depends on a perturbation oracle that sometimes preserves quality and induces a well-mixing random walk on high-quality outputs.

    Source: §1 · p. 3

Abstract

from arXiv · show

Watermarking generative models consists of planting a statistical signal (watermark) in a model's output so that it can be later verified that the output was generated by the given model. A strong watermarking scheme satisfies the property that a computationally bounded attacker cannot erase the watermark without causing significant quality degradation. In this paper, we study the (im)possibility of strong watermarking schemes. We prove that, under well-specified and natural assumptions, strong watermarking is impossible to achieve. This holds even in the private detection algorithm setting, where the watermark insertion and detection algorithms share a secret key, unknown to the attacker. To prove this result, we introduce a generic efficient watermark attack; the attacker is not required to know the private key of the scheme or even which scheme is used. Our attack is based on two assumptions: (1) The attacker has access to a "quality oracle" that can evaluate whether a candidate output is a high-quality response to a prompt, and (2) The attacker has access to a "perturbation oracle" which can modify an output with a nontrivial probability of maintaining quality, and which induces an efficiently mixing random walk on high-quality outputs. We argue that both assumptions can be satisfied in practice by an attacker with weaker computational capabilities than the watermarked model itself, to which the attacker has only black-box access. Furthermore, our assumptions will likely only be easier to satisfy over time as models grow in capabilities and modalities. We demonstrate the feasibility of our attack by instantiating it to attack three existing watermarking schemes for large language models: Kirchenbauer et al. (2023), Kuditipudi et al. (2023), and Zhao et al. (2023). The same attack successfully removes the watermarks planted by all three schemes, with only minor quality degradation.

1 Introduction

The paper argues that strong watermarking is impossible under quality- and perturbation-oracle assumptions, and develops a generic quality-preserving random-walk attack. Its text implementation removes LLM watermarks while keeping judged quality generally stable.

1 Introduction

  • The attacker need only preserve prompt-dependent quality, not semantic equivalence, using a quality oracle and a perturbation oracle whose walk mixes over high-quality responses.The proposed text perturbations can use span substitutions from a weaker open-source masked language model.Source: §1 · pp. 3–4

1.1 Theoretical Result

  • Under its assumptions, an efficient attacker can produce a likely non-watermarked output without reducing prompt-level quality, even for secret-key watermarking.The attack uses rejection sampling to walk among high-quality outputs and needs only an upper bound on the walk's mixing time, not scheme details.Source: §1 · p. 2, §1.1 · p. 4

1.2 Experimental Results and Implementation of Our Attack

1.3 A Thought Experiment

  • The hash-constrained prompt thought experiment illustrates how added conditions could leave only one high-quality response, eliminating room to watermark; it is not the implemented attack.Source: §1.3 · p. 6

2 Related Work

The related work traces generative-model watermarking across modalities and reviews attacks, post-hoc detection, and other adjacent settings. The paper distinguishes its attack by not requiring semantic preservation.

Watermarks for generative models

Limitations of generative model watermarks

  • Prior attacks include image noise and diffusion purification, while LLM paraphrasing can leave text intact or degrade quality; this paper's attack does not preserve semantics.Earlier impossibility claims concern bounded post-hoc image perturbations or an unbounded adversary able to sample from the original model (Sato et al., 2023).Source: §2 · p. 7

Related settings

  • Post-hoc detectors rely on empirical differences between human and model outputs, while network-weight watermarking targets intellectual-property protection rather than individual outputs.The section also situates generative-model watermarking within steganography (Fang et al., 2017; Tancik et al., 2020; Ziegler et al., 2019).Source: §2 · p. 8

3 Secret-key Watermarking Schemes for Generative Models

This section formalizes generative models and secret-key watermarking, then specifies quality and security criteria used to assess whether watermark removal preserves response quality.

3.1 Generative Models

  • A conditional generative model is a randomized efficient algorithm mapping a prompt to an output, and its universal quality function scores responses, including ones the model did not generate.The quality score lies in [0, 1].Source: §3.1 · p. 8

3.2 Secret-Key Watermarking Schemes

  • A secret-key scheme pairs a watermarked-model generation algorithm with a detector that uses the same key and returns whether an output contains the watermark.The watermarking algorithm may use non-black-box access to the model, while detection is prompt-conditional.Source: §3.2 · p. 9
  • False-negative and false-positive rates measure missed watermarks on generated outputs and false watermark detections on other outputs, respectively.The false-positive rate is important where many outputs are screened, since a high rate can falsely implicate people; practical schemes can trade it against false negatives.Source: §3.2 · pp. 9–10
  • Robustness requires more than a watermark's basic detection properties: appending a removable sentence can satisfy those properties without resisting removal.The security criterion therefore requires removal while keeping quality near the original response.Source: §3.2 · p. 10
  • An erasure attack succeeds when it produces an undetected output whose quality is at least that of the original watermarked response.The paper also notes a relaxed definition allowing degradation by γ, but focuses on no degradation and an exact quality oracle.Source: §3.2 · pp. 10–11
  • The paper treats robustness as resistance to computationally efficient attackers meeting the erasure condition, while noting that restricting edits may permit resistance; weak watermarking is outside its scope.The attack model allows black-box queries to the watermarked model and efficient computation without model or training-data access.Source: §3.2 · p. 10

4 Impossibility Result

The paper argues that watermarks can be removed when an attacker can check response quality and perturb outputs through a sufficiently mixing space of high-quality responses. Its proof uses a quality-filtered random walk and bounds the attack's success and query cost under stated conditions.

4 Impossibility Result

  • The impossibility result applies when outputs can be perturbed without affecting quality, including text edits that preserve meaning and small image changes.The paper states that this covers LLMs and image models.Source: §4 · p. 11

4.1 Assumptions and Discussion

  • The attack assumes a quality oracle and a perturbation oracle whose induced walk mixes over high-quality outputs; for language, perturbations may replace tokens or spans.The perturbation oracle need only preserve quality with probability bounded away from zero, not on every invocation.Source: §4.1 · p. 11

4.1.1 Mixing Condition

  • For a fixed prompt, the x-prompt graph represents perturbation transitions, while its q-quality subgraph retains only outputs meeting the quality threshold.The theorem requires the relevant subgraphs to be irreducible and aperiodic.Source: §4.1.1 · p. 12

4.1.2 Discussion

  • Quality can be checked with zero-shot prompting or reward models for language, and with image-quality measures or reward models; the authors expect evaluation to become easier as model capabilities and modalities grow.The perturbation assumption can fail for prompts with no variation among high-quality answers, though the authors argue watermarking also needs multiple potential high-quality outputs.Source: §4.1.2 · pp. 12–13
  • High-quality outputs that are very unlikely under the model can make the perturbation graph disconnected; the authors say probability-weighting vertices addresses this without changing their argument.Source: §4.1.2 · p. 13

4.2 Proof Overview of the Impossibility Result

  • Starting from a watermarked output, the attack repeatedly perturbs and accepts only responses meeting the original quality threshold, producing a walk over high-quality outputs.After mixing, the final output distribution is independent of the watermark key; the false-positive rate then bounds detection of the result.Source: §4.2 · pp. 13–14
  • Under the stated conditions, a universal oracle-aided adversary ϵ-breaks the scheme using at most O(tmax/ϵpert) perturbation queries, with ϵ ≈ (1−ϵpos)/2.The conditions include irreducibility and aperiodicity of the relevant high-quality output graphs.Source: §4.2 · pp. 14–15

5 Experiments

The experiments test a quality-preserving random-walk attack against language and image watermarks, evaluating detection and output quality. Across these tests, the attack reduces watermark detection while generally causing only minor quality degradation.

5.1 Attack Implementation

  • The text attack uses Llama2-7B against three schemes, with T5-XL infilling perturbations and a reward-model quality oracle, followed by GPT-3.5 checks on approved responses.The T5-XL model is used for masked-span infilling; GPT-3.5 checks for issues such as incoherence and grammar errors.Source: §5.1 · p. 16

5.2 Experimental Results

  • With enough quality-preserving perturbations, the attack pushes average C4 news-completion detection below z=1.645 and above p=0.05, while GPT-4 quality scores remain generally stable.For KGW, the attack substantially degrades detection and typically induces only minor quality degradation.Source: §5.2 · p. 17, Figure 3 · p. 18
  • As text length grows beyond 400 tokens, KGW detection z-scores rise while attack performance plateaus, indicating watermark removal on long texts.The length analysis is shown for Llama2-7B-Chat with KGW and aggregates hundreds of examples.Source: §5.2 · p. 18, Figure 4 · p. 19

5.3 Experimental Results on Vision-Language Models

  • The image attack removes Invisible Watermark and Stable Signature with slight image-quality degradation under the reported evaluation protocol.The perturbation oracle uses stable-diffusion-2-base inpainting; the reported image results are averages across the two schemes.Source: Table 2 · p. 18, §5.3 · pp. 19–20

5.4 Qualitative Examples

  • Non-cherrypicked text examples remain coherent, fluent, and on-topic after attack, while image examples retain prompt fit despite changes to backgrounds and object shapes.The text examples include an LFQA prompt and an SAT essay prompt; the image examples show before-and-after results for two schemes.Source: Figure 5 · p. 19, §5.4 · p. 20, Figure 6 · p. 20

6 Concluding Remarks

The authors conclude that strong watermarking is unlikely to withstand determined attackers under their assumptions, while weak watermarking can still help in low-risk settings. They frame watermarking as one tool among others, including cryptographic provenance methods.

6 Concluding Remarks

  • The work gives general impossibility results for strong watermarking, but its specific attack is not very efficient and its concepts extend across generative modalities.The authors argue, without formal proof, that increasing model capabilities may benefit attackers more than defenders.Source: §6 · p. 21
  • Weak watermarking can still help guard against unintentional leaks or low-effort attackers, though it will not foil a determined attacker.The authors describe watermarking as one tool among broader generative-AI safety efforts.Source: §6 · p. 21
  • For some disinformation cases, verifying data provenance may matter more than determining whether AI generated the data.The authors mention cryptography as another means of establishing provenance.Source: §6 · p. 21

Broader Impact

The authors frame their work as exposing fundamental weaknesses in watermarking while informing expectations about its trade-offs and scope.

Broader Impact

  • The attack implementation targets text generation; adapting the ideas to deployed image-generation models is possible, but this paper provides no recipe.The authors also note that their techniques are not the most efficient way to remove watermarks, prioritizing generality over efficiency.Source: Broader Impact · p. 21

A Questions & Answering

The paper evaluates watermark removal by prompt-conditioned quality rather than semantic similarity, and relates that criterion to the behavior of quality-preserving perturbations and random walks.

A Questions & Answering

  • Prompt fitness can permit changed semantic details when a prompt leaves them unspecified, while explicitly specified details constrain both watermark insertion and removal.The authors therefore evaluate text quality conditioned on the prompt, rather than relying on response-only measures such as perplexity.Source: A Questions & Answering · p. 29
  • The attack's quality-preservation objective differs from prior attacks' semantic-equivalence objective, and its perturbation acceptance rule is fundamentally different.The cited prior attacks are Saberi et al. (2023) and Sadasivan et al. (2023).Source: A Questions & Answering · p. 29
  • The impossibility result applies to sufficiently good watermarking schemes without depending on output-space entropy or type-I and type-II detection errors.The discussion says the result applies to schemes with a small false-positive rate, a condition it identifies as necessary for distinguishing machine-generated from human-generated content.Source: A Questions & Answering · pp. 29–30

B.1 Notation

  • The notation distinguishes random variables, concrete values, sets, and algorithms, and uses r← to denote uniform or distribution-based sampling.Vectors and matrices use bold notation; |x| denotes string length or set cardinality, depending on whether x is a string or set.Source: §B.1 · p. 30

B.2 Graphs, Random Walks, and Mixing Time

  • For irreducible, aperiodic graphs, random walks converge to a unique stationary distribution; mixing time bounds how many steps convergence requires.The passage relates a mixing-time bound to the second-largest eigenvalue in absolute value of the transition matrix.Source: §B.2 · p. 31

C Extended Impossibility Theorem

The extended theorem specifies assumptions for a universal oracle-aided attacker and bounds its perturbation queries using mixing times and an error allowance.

C Extended Impossibility Theorem

  • The theorem generalizes the quality threshold from the median to an arbitrary v-th percentile across models and prompts.Its qmin is the minimum of those v-th quality percentiles.Source: C Extended Impossibility Theorem · pp. 31–32
  • Under the stated preservation and graph-mixing conditions, a universal oracle-aided attacker breaks the watermark using at most t queries.The bound sets t to the maximum mixing time tx,q over prompts and quality thresholds, plus terr.Source: C Extended Impossibility Theorem · p. 32
  • For sufficiently small v and ϵdist and sufficiently high ϵpert, adversarial advantage approaches 1 − ϵpos.If ϵpos is also small, the stated advantage is close to 1; lower ϵpert can be offset by increasing terr and thus the query bound.Source: C Extended Impossibility Theorem · p. 32

C.1 Proof of Theorem 6

The proof analyzes the attacker as a quality-thresholded random walk, showing that it can return an output that retains quality while escaping watermark detection.

C.1 Proof of Theorem 6

  • The attacker queries quality, accepts perturbations scoring at least the initial output's q0, and returns the final output only after enough accepted steps.Otherwise, it returns an error; rejected perturbations do not increment the counter.Source: §C.1 · p. 33
  • The proof bounds completion by counting quality-preserving perturbations, whose count follows a binomial distribution with increment probability ϵpert.The initial output meets the qmin threshold with probability at least 1 − v/100.Source: §C.1 · pp. 33–34
  • Conditioned on completing, the accepted perturbations form a random walk over outputs of quality at least q0, which converges toward its stationary distribution.The theorem's irreducibility and aperiodicity conditions, together with enough steps relative to mixing time, yield the stated convergence.Source: §C.1 · p. 34
  • Conditioned on completion, the returned output has quality at least q0 and is undetected with probability at least (1 − ϵpos)(1 − ϵdist).The stationary distribution is independent of the secret-key watermarked model, allowing the scheme's false-positive rate to bound detection probability.Source: §C.1 · p. 35

D.1 Qualitative Results through Steps

Across successive attack steps, watermark detection generally declines while the resulting texts remain high quality according to the GPT-4 quality oracle. The examples include final texts judged similar in quality to the watermarked response.

D.1 Qualitative Results through Steps

  • The appendix showcases an attacked response to a C4 news-article prefix as a qualitative example of the resulting text.The passage presents the final response after watermark removal.Source: §D.1 · p. 35
  • The initial KGW detection result for the example has a z-score of 7.340 and p-value of 0.000.Results are reported every five valid random walks.Source: §D.1 · p. 35
  • The perturbation-oracle graph is defined before the watermark key is sampled.The passage gives this ordering as the reason for the stated property.Source: §D.1 · p. 35
  • Detection generally decreases while GPT-4 judges the perturbed texts high quality, with final examples receiving a score indicating quality similar to the original.The oracle score stays at 0 for the final several examples.Source: §D.1 · p. 36

E.1 Implementation Details of Attack

The implementation section describes quality-preserving text perturbations, quality-oracle trade-offs, and stopping choices, then details the watermark schemes and prompts used in experiments. Its implementation discussion also notes position bias in quality checking, especially for responses longer than 200 words.

E.1 Implementation Details of Attack

  • The attack replaces six-word spans using top-p infilling and backtracks after repeated quality-check failures; words are masked rather than tokens to avoid nonsensical output.The authors generally use default hyperparameters and do not tune them extensively.Source: §E.1 · p. 36
  • The authors use three quality-oracle alternatives that trade off quality, cost, and efficiency, and report substantial GPT-3.5/GPT-4 position bias for responses longer than 200 words.Reward models filter obviously bad texts, while two-round comparisons reject a candidate that loses both rounds.Source: §E.1 · p. 36, Table 3 · p. 37
  • Repetitive watermarked examples are filtered because the perturbation oracle may preserve repetition; stopping uses z-score below 1.645 or a replacement-fraction threshold.For high-stakes use without detector knowledge, the threshold is 70% for texts of length 500 or 512 and 80% for length 600.Source: §E.1 · p. 37

E.2 Watermark Details

  • KGW promotes a randomized green list and uses a z-test, EXP detects via a permutation-test p-value, and Unigram uses a green-list z-statistic.The cited schemes are KGW (Kirchenbauer et al., 2023a), EXP (Kuditipudi et al., 2023), and Unigram (Zhao et al., 2023a).Source: §E.2 · p. 37
  • The visual watermark details cover Stable Signature’s latent-decoder signature and an invisible watermark embedded in image frequency components.Stable Signature uses an IMATAG VAE checkpoint; the invisible watermark uses DWT and DCT transformations.Source: §E.2 · pp. 37–38

E.3 Prompt Examples

Loading 2311.04378v5…