ML8502 · Fall 2026 · Week 05

Content Watermarking

A watermark is a hidden signal embedded into a medium that can later be detected using a secret watermarking key.

Graphite drawing on a white ground: a printed sheet stands upright in a wooden stand, lit from behind by a small desk lamp so a faint regular pattern of dots shows through the paper, with one small crimson triangle in the pattern; a small brass key lies in front of the stand.

Five chapters

Lecture Schedule

Chapter	Wk	Lectures	Lab	Topic
I Foundations	01	25 · 26 Aug		Security mindset. Threat models, LLM stack
	02	1 · 2 Sep	4 Sep	Adversarial ML. Evasion, transfer, backdoors
	03	8 · 9 Sep	11 Sep	(Certified) Defenses. Adversarial training, randomized smoothing
II Provenance	04	15 · 16 Sep	18 Sep	Model extraction. Distillation, capability upliftonline
	05	22 · 23 Sep	25 Sep	Watermarking. Fingerprinting, deepfake detection
III Systems	06	29 · 30 Sep	2 Oct	Prompt attacks. Jailbreaks, injection, red-teaming
	07	6 · 7 Oct	9 Oct	Project pitches
	08			No class: exams, Fall Break
	09	20 · 21 Oct	23 Oct	Agent security. Jailbreaks, tool use, containment
	10	27 · 28 Oct	30 Oct	Agent defenses. Information-flow control, least privilege, identity
IV Safety	11	3 · 4 Nov	6 Nov	Alignment. RLHF, reward hacking, emergent misalignment
	12	10 · 11 Nov	13 Nov	Deception. Scheming, sandbagging
	13	17 · 18 Nov	20 Nov	AI control. Scalable oversight, interpretability
V Frontier	14	24 · 25 Nov	27 Nov	Multi-agent security. Collusion, offensive AI
	15	1·2 Dec	4 Dec	Project work
	16	8 · 9 Dec		Final presentations

uploaded 6–7 Oct

Yellow: student sessions.

Sixteen papers

Week 5 Reading List

01	SchemeKirchenbauer et al. · A Watermark for Large Language Models · ICML 2023	09	AttackSouček et al. · Transferable Black-Box One-Shot Forging of Watermarks via Image Preference Models · NeurIPS 2025
02	TheoryZhao et al. · Invisible Image Watermarks Are Provably Removable Using Generative AI · NeurIPS 2024	10	EvaluationDing et al. · A Technical Report on “Erasing the Invisible”: The 2024 NeurIPS Competition on Stress Testing Image Watermarks · NeurIPS 2025 D&B
03	TheoryZhao et al. · SoK: Watermarking for AI-Generated Content · IEEE S&P 2025	11	AttackHuang et al. · RLCracker: Evaluating the Worst-Case Vulnerability of LLM Watermarks with Adaptive RL Attacks · ICML 2026
04	SchemeSander et al. · Watermark Anything with Localized Messages · ICLR 2025	12	TheoryWang et al. · Cryptanalysis of LDPC-Based Pseudorandom Error-Correcting Codes · USENIX Security 2026
05	AttackDiaa et al. · Optimizing Adaptive Attacks against Watermarks for Language Models · ICML 2025	13	TheoryLee et al. · Rethinking Forgery Attacks on Semantic Watermarks in Black-Box Settings: A Geometric Distortion Perspective · ICML 2026
06	AttackMüller et al. · Black-Box Forgery Attacks on Semantic Watermarks for Diffusion Models · CVPR 2025	14	AttackCao et al. · MarkNull: Model-Agnostic Watermark Removal in AI-Generated Images via On-Manifold Latent Manipulation · USENIX Security 2026
07	EvaluationHarel-Canada et al. · Sandcastles in the Storm: Revisiting the (Im)possibility of Strong Watermarking · ACL 2025	15	SchemeBakshi et al. · OpenStamp: A Watermark for Open-Source Language Models · COLM 2026
08	SchemeHu et al. · Mask Image Watermarking · NeurIPS 2025	16	ProvenanceGolaszewski et al. · Verifying Provenance of Digital Media: Why the C2PA Specifications Fall Short · arXiv preprint 2026

Bid for one paper on the LMS, then submit the review by Fri 2 Oct.

This week

Lecture Overview

Introduction to Content Watermarking

What watermarking is
Why attribution fails
How a watermark works
Removal, forgery, quality
Classical image marks

Building a Watermark

One keyed hash
KGW, the green-red list
Counting green tokens
Tournaments and image marks
How diffusion generates

Distortion-Free Watermarks

The observer with no key
Randomness a mark needs
Sampling from a key table
The same idea in an image latent

Watermark Removal

Training a paraphraser
A mark on meaning
Random-walk removal
Provable removal, images

Forgery and Provenance

Planting another's mark
Learning the green list
Forging from one image
Signatures and public detection

Two sessions

Tuesday: chapters 1 to 3
Wednesday: chapters 4 and 5, three student talks

Chapter 1

Introduction to Content Watermarking

The problem.Generated text and images look human-made. How can a provider later prove which content came from its model?

Why mark content?: six harms, one question
How does a watermark work?: a key and three algorithms
What can an attacker do?: remove, forge, keep quality
What came before?: spread-spectrum image watermarks

Graphite drawing on a white ground: a heavy metal desk seal stamp stands beside a printed sheet that carries a faint embossed circular seal impression with a small crimson triangle at its centre; a small key lies between them.

Motivation

Six Harms, One Question

Six harms, one question. First a map of the players: a provider holding a secret key k and running a model M releases text, audio and images across the API boundary to users and to an adversary who edits, forges and reposts; days later somebody holding one file asks who made it. Then a wall of six exhibits, each headed by its harm, source number and date: Impersonation [28], 03/2024, The Verge headline OpenAI's voice cloning AI model only needs a 15-second sample to work; Deepfake NCII [29], 03/2024, the Guardian headline Nearly 4,000 celebrities found to be victims of deepfake pornography, headline only; Astroturfing [32], 01/2024, the Washington Post headline AI bots are everywhere now; Misinformation [27], 03/2023, a synthetic picture of Trump kneeling in prayer with a red FAKE badge added afterwards; Social engineering [30], S&P 2024, Roy et al. Figure 4, a QR-code offer card leading to a generated AT&T sign-in page; Data pollution [31], 05/2024, a Google Images result for leopard claws with two AI-generated stock images circled by the poster. Underneath: in no tile can the file itself say who made it; the red FAKE label was added by a person afterwards.

*Headline only: the harm is named and, deliberately, not illustrated.

The Goal

What Do We Want?

What do we want: after release, tell content this model made from content it did not. First the question: a model M releases x, and days later somebody holding x asks whether this model made it. Then three ways. Retrieval-based: store every output in a dataset D and answer by lookup; plus an exact answer and generation untouched; minus high storage and retrieval costs, no open source, no user privacy. Post-hoc detection: train a classifier on real data and generated data, with no key; plus no cooperation needed; minus unreliable and low accuracy; under it the Decrypt headline OpenAI Quietly Shuts Down Its AI Detection Tool. Watermarking, in the middle: KeyGen makes a key, the model marks while generating, the content crosses the API line to the user and comes back to a detector that needs the key; plus nothing stored and a false-alarm rate you can prove; minus the key must stay secret and generation must be modified; under it the MIT Technology Review headline Google DeepMind is making its AI text watermark open source.

Deployments

Watermarks in Production

A timeline, later to the right and not to scale. Above it two captured pages: the Google DeepMind post Watermarking AI-generated text and video with SynthID, May 14 2024, and the TechCrunch headline Anthropic says it will watermark text generated by its AI models. Four milestones: 14 May 2024, SynthID for text; 23 Oct 2024, the Nature paper, starred; 2 Aug 2026, AI Act Article 50(2), Claude marks from here; 2 Dec 2026, the amending act. Underneath: EU AI Act, Article 50(2): generated text, audio, image and video must carry a machine-readable mark from 2 Aug 2026; systems already on the market have until 2 Dec 2026.

*The Nature paper measured what users notice (thumbs up or down on Gemini answers), not what a test looking for the mark could notice.

Watermark Definition

How a Watermark Works

How a watermark works, on the map of the players. Left of a dashed API boundary: the provider; KeyGen takes one to the lambda (the security parameter) and makes the secret key k; Wat_k takes the prompt When do mangoes ripen? and returns x = Mangoes ripen in late summer, four of five words favoured by the key; a detector and an attribution test sit inside the provider. Right of the boundary: the user receives x as plain text, and the adversary, the channel E, edits one word, late to early, giving x'. x' returns across the boundary to the detector, which reads it with the key: Det_k(x') -> true, three of five words keyed. A second key ak drives the attribution test Att_ak(x) -> true or false. KeyGen runs once, Wat on every answer, Det and Att on anything shown to them; only k and ak are secret.

*Kerckhoffs: the algorithms are public; only the keys are secret. **The sentence and which words are keyed are illustrative; Chapter 2 builds the real rule.

Threat Model

A Written Threat Model

Black-box attack

Threat Model

Quality and Robustness

Quality and robustness. A generated sentence x: The tower opened in 1889 and stayed the tallest structure for 41 years. Five edits with the quality a judge gives against x: a paraphrase (four decades), kept; spelling errors (towr, talest), kept; a cut that strikes half the answer, lost; the words shuffled into nonsense, none; a smiley after every word, then the smileys removed, kept, and the mark is gone. The win condition: x' is drawn from the channel E applied to x, and the adversary wins if and only if Det_k(x') is false and the quality Q(x', x) is at least the floor Q_0, what open models already give; an edit counts only if it stays usable. Above it, the survey's Definition 3.1, distortion: the maximum over messages m and prompts pi of one half the sum over responses x in R of the absolute difference between Pr[M(pi) -> x] and Pr over gk of [Watermark_gk(m, pi) -> x]; and Definition 3.2, distortion-freeness: for any polynomial-time distinguisher D with query access to M, the two probabilities that D outputs 1 on a plain and on a marked response differ by at most negl(lambda); statistically distortion-free if even unbounded D cannot tell.

*The smiley attack (Kirchenbauer et al. 2023, Fig. 5, after Goodside, January 2023): every green list was drawn with a smiley in the context, so the plain words no longer match.

Watermarking in the 2000s

Classical Image Watermarks

*After one JPEG save 50.3% of the hidden last bits still match: chance. N = 1000, α = 0.1 and the JPEG quality are our choices; every number is computed on this picture.

Chapter 2

Building a Watermark

The problem.Hide a keyed signal in content that only the key holder detects, at a known false-alarm rate.

KGW green list: a keyed vocabulary split, a z-test
SynthID tournament sampling: the scheme in Gemini
Tree-Ring: a key in the starting noise
Watermark Anything: localized marks in one image

Graphite drawing on a white ground: an old key lies beside a sheet laid out as a grid of small blank tiles, like word tokens; the left tiles carry a pale green wash, the rest are grey, and one grey tile carries a small crimson triangle.

The Plan

What Every Watermark Does

The three parts every watermark has, on a pipeline. A provider runs a model behind a dashed API boundary; a user receives its content. Part 1, make a key: KeyGen draws one secret key k, once; the algorithms are public. Part 2, mark while generating: the key reaches the model, written Wat_k, and the content x that crosses the boundary is marked in itself, with nothing attached to strip. Part 3, check with the key: the content returns to a detector Det_k inside the provider's boundary, which takes content and key and outputs true or false; anyone else must ask the provider. On the right: the same three parts for any medium: text (token choice), images (pixels, frequencies), audio (a signal you cannot hear). Next: one scheme, for text, KGW.

Cryptography

A Keyed Random Function

A keyed random function in three calls and a definition. The problem: the detector must replay the generator's random choices from the text alone, and nobody else may predict them. Row 1: the tokens cat, in, the and the secret key k go through the keyed function f_k, which outputs 0110 0011 1001 0101. Row 2: the same input gives the same output, so the detector can replay it. Row 3: one token changed to dog gives 0011 0111 1110 1111, and 8 of the 16 bits agree, exactly chance. Right, without the key: to an adversary the bits look like 16 fair coin flips. The definition of a pseudorandom function: k is drawn by KeyGen of 1 to the lambda, lambda the security parameter; f_k maps an input u, the last h tokens, to n_out output bits; equal inputs give equal outputs, so it is deterministic and the detector replays it; and f_k is indistinguishable from a random function to anyone who does not hold k.

*No efficient algorithm without k tells its outputs from a uniformly random function's. The strings are real HMAC-SHA256 outputs under a fixed key.

Watermarking LLMs

KGW (Green-Red List Watermarking)

KGW, one generation step on a running example, then detection. The context I saw a cat in the goes into the LLM, which gives logits over the vocabulary (more than 100k tokens; four drawn: Park 5.1, Street 2.4, Bar 1.9, end-of-text minus 5.1). Step 1, seed: the last h = 3 tokens, cat in the, and the secret key k go through the keyed function f_k, which outputs a seed beginning 0110 0011 1001 0101. Step 2, split: Split_gamma shuffles the vocabulary with the seed into Street, end-of-text, Bar, Park and keeps the first gamma times |V| (gamma = 1/2) as the green list G_t; Street and end-of-text are green, Park and Bar red. Step 3, bias: plus eta is added to the two green logits (the paper calls it delta). Step 4, sample: the probabilities before the bias, 0.90, 0.06, 0.04, 0.00, become 0.65, 0.32, 0.03, 0.00 after it; Street is drawn, s^(t) ~ softmax(Z + eta 1_G_t), and joins the context, so the window in the Street seeds the next split. Step 5, detect: on the finished text I saw a cat in the Street full stop, each window is rerun through the keyed hash and the split with no model call; Street is green and the full stop red, so the green count is 1 of T = 2 scored.

*The four logits are illustrative and the softmax runs over these four only; the seed, the split and both probability rows are computed (HMAC-SHA256 under a fixed key).

The definition

The Green-List Rule, Formally

$Definition of the green-list watermark in two lines, every symbol labelled in handwriting. Line 1, split: G_t, the green list at position t, equals Split_gamma, which keeps a gamma share, applied to f_k, the keyed function that returns a seed, of the h tokens just written, s^(t-h) to s^(t-1); the size of G_t is gamma, the green fraction, times V_vocab, the vocabulary size. Line 2, sample: s^(t), the token at t, is drawn from softmax of Z, the logits, plus eta, the logit bias (the paper's delta), times the indicator of G_t, which is 1 on green and 0 on red. Below: the detector reruns line 1 on the finished text and asks whether each written token is in its green set, with no model call; the split is recomputed at every t, so there is no global list. For text the artifact is the completion itself: x = s = (s^(1), ..., s^(T)).$

Watermark Detection

The z-Test

The z-test on 200 scored positions. Left, a grid of 200 cells, 128 filled: the green count |s|_G = 128 of T_eff = 200 scored positions. Chance, with no key, predicts gamma T_eff = 0.5 times 200 = 100; the spread is sigma = (T_eff gamma (1 - gamma))^(1/2) = 50^(1/2) = 7.071; the detection statistic z = (|s|_G - gamma T_eff) / sigma = (128 - 100) / 7.071 = 3.960. With 128 green, z = 3.960 is below 4: not detected; one more, 129 green, gives z = 4.101: detected. Right, a plot over the number of green tokens: the exact Binomial(200, 1/2) curve for text without the key peaks at 100; a crimson line marks the threshold tau_det = 4, a count of 128.3, beyond which chance lands 2.5 times in 100,000; ticks mark 128 and 129. A teal curve for text with the key peaks at 159.5. OPT-1.3B, gamma 1/2, delta 2, 200 tokens: 98.4% of generations are detected at z = 4.

*Exact P[X ≥ 129]; the normal tail 1 − Φ(4) is 3.2 in 100,000 (the paper quotes 3). **§4.1: measured mean 159.5 (Thm. 4.2 promises ≥ 142.2); the width is their bound σ ≤ 6.41. Which cells are green is illustrative.

The whole argument

The z-Test, Proved

Lemma, the detection statistic under the null: two conditions make the green count binomial, so z has a normal tail. C1: the keyed function is modelled as a random function. C2: no context repeats. Rung 1, one coin per position: the indicator that the written token is green is Bernoulli(gamma); C1 spent. Rung 2, distinct contexts, independent coins: the green count |s|_G, the sum of the indicators, is Binomial(T_eff, gamma); C2 spent, a repeat is one coin seen twice. Rung 3: the mean is gamma T_eff and the variance T_eff gamma (1 - gamma); no model enters. Rung 4: z = (|s|_G - gamma T_eff) / sqrt(T_eff gamma (1 - gamma)) has mean 0 and variance 1 exactly. Rung 5: z converges in distribution to N(0, 1), and the false-alarm rate alpha_FPR is approximately 1 - Phi(tau_det), Phi the normal CDF and tau_det the threshold; approximately, not at most. Right: the exact Binomial(200, 1/2) curve over a count ruler (86, 93, 100, 107, 114) and a z ruler (-2 to 2, and 4) beneath it; standardising moves the ruler, not the curve. Beyond z = 4 the tail is too thin to see: exact 2.49e-5, normal 3.17e-5, about 22% apart. So the threshold is priced by a normal tail in the limit; the exact price is binomial.

Watermark Detection

Detection as Hypothesis Testing

Detection as hypothesis testing. Left: two bell curves of the detection statistic z, one for content without the key centred at 0 and one, dashed teal, for content with the key centred at 3; a crimson line at the threshold tau_det = 2.33; right of the line is called marked. False alarms alpha = 0.010, misses beta = 0.250; at alpha = 1%, tau = 2.33 and the catch rate 1 - beta = 0.75; a catch rate means nothing without its false-alarm rate. Top right, the definition of the false-positive rate: the probability over the key alone that Det_k(x0) returns true is at most alpha_FPR, for every unmarked x0 independent of k; no distribution over human writing is assumed; independent of k is stronger than k is secret. Middle right, the number papers report: TPR at FPR = q is 1 - beta_FNR, the catch rate, at the threshold where alpha_FPR = q. Bottom right, the price: expected false accusations a day when 10^8 unmarked documents are screened, on a log axis, falling with the threshold: tau = 4 gives 3,167 a day, tau = 5.612 one a day.

*Content made by querying the generator or the detector depends on k without revealing it, and the bound says nothing about it. The price curve assumes z is standard normal under the null and one test per document.

Exercise, three parts

Base Rates and Multiple Testing

Exercise in three parts with its solution. Setting: N = 10^8 documents a day; the false-alarm rate at threshold tau is 1 - Phi(tau); W = 50 windows per document; one document is drawn as a strip with 50 overlapping windows above it. Questions: (a) none of the N is marked: choose tau for one expected false accusation a day; (b) bound the per-document rate over W windows, and choose again; (c) say why a miss rate alone is not a number. Rung 1: 1 - Phi(tau) at most 10^-8 gives tau at least 5.612; 5.61 would leave 1.01 a day; quote 5.62. Rung 2: a scanner is fifty tests: the probability that any window fires is at most W times alpha_FPR, the union bound. Rung 3: so alpha_FPR at most 2 x 10^-10 gives tau at least 6.254; quote 6.26. Rung 4: either error alone is free: always false gives alpha_FPR = 0, always true gives beta_FNR = 0; quote the pair.

Watermarking LLMs

Spike Entropy

Spike entropy. Three distributions over tokens A, B and C, drawn at one scale: open (0.1, 0.3, 0.6), many choices; peaked (0.005, 0.005, 0.99), almost decided; forced (0, 0, 1), no choice. The same split makes B green and A and C red in all three, and the same bias eta = 2 on B gives a second bar per token: the green probability goes from 0.30 to 0.76 in the open panel, from 0.005 to 0.036 in the peaked one, and from 0 to 0 in the forced one. The bias multiplies a probability, it never creates one: no freedom, no room for a mark. A ruler of spike entropy S marks the floor 0.568, which the forced panel reaches, peaked 0.574, open 0.749 and the ceiling 0.798; more room for a mark to the right. The definition: S(p, c_spike) is the sum over i of p_i divided by 1 + c_spike p_i, with c_spike the modulus (the paper's z) and p_i the probability of token i; it lies between 1 / (1 + c_spike), all mass on one token, and V / (V + c_spike), uniform over V.

*Here the modulus is 0.762, fixed by the paper's green-count bound from γ = ½ and η = 2; the ceiling is over these three tokens (0.999985 over 50,000).

Watermarking LLMs

Utility/Effectiveness Trade-off

$Two panels redrawn from Kirchenbauer et al. Left, Fig. 3(b), green-list fraction gamma = 0.25, OPT-1.3B: the average detection statistic z, higher is better, against the number of tokens generated T, for logit biases eta = 0.5, 1, 2, 5 and 10. Every curve rises like the square root of T; at T = 190 they reach about 2, 4.7, 10.4, 20.7 and 23.6. A dot marks z = 5 near T = 50 on the eta = 2 curve. Reading: z grows like the square root of T and the bias sets the constant; eta = 2 passes z = 5 near 50 tokens, eta = 0.5 stays under 2.5 by 180. Right, Fig. 2 (left), T = 200 tokens: z against oracle-model perplexity on a reversed axis, lower perplexity to the right is better; marker shape is the bias eta (10, 5, 2, 1, 0) and colour the green fraction gamma (0.1 to 0.9). The points run from about perplexity 5 and z 0 with no bias up to perplexity 12.9 and z 41.6 at eta = 10 and gamma = 0.1. Reading: more bias buys z and costs perplexity; the paper reads a small green list, gamma = 0.1, as Pareto-optimal.$

*The paper writes δ for the bias (the course's η). Multinomial sampling in both panels; right, T = 200 ± 5 tokens and about 500 sequences per point. Redrawn from values read off the paper's figures.

Open Problems

Where the Green List Falls Short

KGW works, ships, and is every later paper's baseline; each scheme after it fixes one gap. A table of five gaps, why each happens, and where the week takes it on. 1, it costs quality: more bias buys detection and costs perplexity; chapter 3, distortion-free sampling, Kuditipudi et al. and Aaronson. 2, low-entropy text carries no mark: facts and code leave no choice to bias; chapter 3, the entropy budget, Christ, Gunn and Zamir. 3, the rule can be learned: enough outputs reveal it, to remove the mark or forge it on any text; chapter 5, randomized keys, Aremu et al. 4, a paraphrase re-rolls it: one changed word re-seeds every window through it; chapter 4, semantic marks, SemStamp by Hou et al. 5, only the key holder can check: detection needs the key, and publishing it publishes the list; chapter 5, public detection, Fairoze et al.

Watermarking LLMs

Tournament Sampling

Tournament sampling, one generation step on the paper's Fig. 2 example. The watermarking key and the last four tokens of the context, "my favourite tropical fruit is", go into the seed generator, which gives the seed r_t. Every vocabulary token gets three keyed coin values g1, g2, g3: mango (probability .50) 1 0 1, lychee (.30) 0 1 0, papaya (.15) 0 0 1, durian (.05) 1 0 0. Eight candidates are drawn from the model: durian, mango, lychee, mango, papaya, lychee, mango, mango. Layer 1 under g1: durian beats mango on a coin flip, mango beats lychee 1 to 0, lychee beats papaya on a coin flip, mango beats mango on a coin flip. Layer 2 under g2: mango beats durian on a coin flip, lychee beats mango 1 to 0. Layer 3 under g3: mango beats lychee 1 to 0, and mango is written. Detection: Score(x) is the mean of g_l(x_t, r_t) over all T tokens and m layers, computed from the text and the key without calling the model; mango scores 2/3. Right: Fig. 3a redrawn, true positive rate at 1 % false positive rate against the number of tokens: SynthID-Text 0.22, 0.50, 0.70, 0.77, 0.87 and Gumbel sampling 0.18, 0.34, 0.60, 0.68, 0.74 at 50, 100, 200, 300 and 400 tokens.

*Gumbel sampling is also non-distortionary, so the curves compare at equal quality (Fig. 3a, Gemma 7B-IT). Live in Gemini, ~20 M replies: no significant rating change.

Image Watermarks

Post-Processing and In-Processing

Two lanes. Post-processing, top: a photograph of a teddy bear in front of the White House, x_0, plus a speckle pattern delta, the change added, equals the marked picture x_0 + delta. An arrow leads to a small dashed ball holding a few pictures: the pictures the provider could release are only those close to x_0. Quality is Q(x_0, x_0 + delta), a reference metric that needs the original. In-processing, bottom: a random start array x_T, an arrow labelled write the key, and the keyed array x_T^w, which looks the same; the ordinary sampler leads to a large dashed set of pictures: anything the model can make for this prompt. Quality is Q(x_w, pi), judged against the prompt pi because no original exists.

*The pattern is amplified so that it can be seen. **An attacker who regenerates the picture picks from this big set too (Chapter 4).

Image Generation

Diffusion Models in One Picture

$A diffusion model in one strip. Right: a photograph of a teddy bear in front of the White House, x_0. Going left, the forward process adds a little Gaussian noise T times, fixed and not learned: x_t, x_{t+1} and finally x_T, nothing left but pure noise; x_t equals the square root of alpha-bar t times x_0 plus the square root of one minus alpha-bar t times fresh Gaussian noise epsilon, where alpha-bar t is how much picture is left. Above, the backward process runs left to right: the network epsilon-theta of x_t and t guesses the noise, which is removed, from step T down to 0. Left: generation starts by drawing x_T from an isotropic Gaussian N(0, I); another draw from that cloud gives a different picture, drawn as an empty frame with a question mark.$

*The network is never asked to draw a bear, only to guess noise. The tiles are our own noising of Dr. Lukas’s Fall 2025 image.

Image Watermarks

Tree-Ring Generation

Tree-Ring generation. A row of five stations: x_T, a 64 by 64 array of Gaussian noise; FFT gives F(x_T), the same numbers as frequencies and still noise, whose centre holds the low frequencies; write the key gives F(x_T) keyed, with rings inside the circular mask M and the rest unchanged; IFFT gives x_T^w, which still looks like noise; the DDIM sampler with the prompt "A Teddy bear in Washington DC" gives the picture of a teddy bear in front of the Capitol, with nothing added to its pixels. Lower left: the key k*, one Gaussian value per ring, and Equation 2: F(x_T)_i is set to k*_i for every mode i in the mask, radius 10. Table 1, Stable Diffusion: FID 25.29 to 25.93, lower is better; CLIP 0.363 to 0.364, higher is better. Lower right: the start arrays drawn with the key are a shifted region of those drawn without it, and so are the pictures, inside the much larger set of pictures the model can make for this prompt.

*Aggregate quality holds, the single picture does not: the same seed with and without the key gives a different bear (Fig. 2). The arrays are our own, made with Eq. 2.

Watermark Detection

Tree-Ring Detection

Tree-Ring detection. Top row: the marked teddy-bear picture; an edit by the adversary, the paper's Strong Perturbation, rotated and pasted on a new background; DDIM inversion plus FFT, the sampler run backwards, which needs the model and uses an empty prompt because the prompt is unknown, gives the Fourier transform of the recovered start array F(x'_T), with rings visible; the mask keeps the modes inside M, radius 10, the low frequencies; they are compared with the key k*. The test: d equals one over the size of M times the sum over the mask of the absolute difference between the key and the recovered value, a distance, not a decoding; d below tau means watermarked. Bottom: Fig. 7 redrawn, AUC (solid pink) and true positive rate at 1 % false positive rate (dashed green), higher is better. Rotation: AUC stays above 0.93, the TPR dips to 0.46 at 45 degrees and 0.35 at 315 degrees and returns to 1 at every quarter turn. JPEG quality 90 down to 10: both near 1, TPR 0.93 at quality 10. Crop and scale, percent kept 90 down to 10: AUC falls to 0.64, TPR falls to 0.31 at 70 % and to about 0.04 at 30 % and 10 %.

*Averaged over six edits, 0.694 of marked pictures are caught at 1 % FPR, against 0.448 for RivaGAN (Table 1). The p-value comes from a chi-squared score, not from d.

Image Watermarks

Localized Image Marks

Localized image marks. Top row, the paper's Fig. 1: two 32-bit messages, 1101..1001 and 0101..0010, are embedded into two regions of a photo of rubber ducks; the marked picture looks unchanged; an edit cuts two ducks out and pastes them on a photo of the sea; extraction decides for every pixel whether it is marked and reads 32 bits per pixel, giving a mask that is white on the two ducks; clustering with DBSCAN, without a preset number of messages, reads one message per region: both messages are recovered; 31 of 32 bits are read with only 10 % of the image marked. Bottom left: Fig. 4 (left) redrawn, detection mIoU against the watermarked area in percent, higher is better: WAM stays near 0.97 to 0.99 up to 90 % with or without a 25 % crop and drops to 0.83 and 0.73 at 95 %; EditGuard without the crop reaches 0.88 at best and falls to 0.64; EditGuard after the crop starts at 0.47 and falls to 0.02. Bottom right: Mask Image Watermarking (NeurIPS 2025), its decoder diagram: find the marked region, zero the rest, read the bits; 100K training steps on one A6000 for 20 hours against 3,680K steps on eight V100 for 90 hours, about 15 times less training compute (Table 2).

*EditGuard, the earlier localized scheme, is not robust to cropping (Sec. 5.4). Values read off Fig. 4, left (COCO, 512 × 512).

Chapter 3

Distortion-Free Watermarks

The problem.Mark the output without changing what the model would have produced, so nobody without the key can tell.

Marking the Wrong Symptoms: missed harms
Christ, Gunn & Zamir: marks can only spend entropy
Kuditipudi et al.: the exponential scheme
Gaussian Shading: the same idea for diffusion

Graphite drawing on a white ground: an old balance scale in perfect equilibrium with one sheet of paper on each pan, the two sheets identical except for a small crimson triangle on one corner of the right-hand sheet; a small key hangs from the beam.

Quality Metrics

What Quality Metrics Miss

Does an accuracy number see what a watermark breaks? Measured at the weakest setting with 99 per cent TPR at 1 per cent FPR; for KGW on PHI-4-14B, MedQA, a green list of one half and bias delta 3, 99.2 per cent TPR. Left, the paper's Figure 2 for PHI-4-14B: MedQA accuracy against TPR at 1 per cent FPR for five schemes stays inside the unmarked band up to 99 per cent TPR. Middle, redrawn from Table 2: accuracy change in percentage points, AAR -2.5, DipMark -0.9, KGW -0.7, PPL -8.6, SynthID -3.2; higher is better. Right: added errors per 100 questions in three families, fabricated, misapplied and corrupted spelling; PPL's corrupted spellings rise by 69.6 and SynthID's by 10.6; lower is better. Bottom: a marked sentence, Start Pentaprazole 40 mg., beside the unmarked Start Pantoprazole 40 mg. The claim: benchmark accuracy of the marked answers lies inside the 95 per cent band of the unmarked run while the term errors per 100 far exceed those on the same questions without the key; here, KGW: accuracy -0.7 points, inside the band; fabricated terms 0.3 to 1.8 per 100.

*Pentaprazole is no drug (Table 1, a fabricated entity); the sentence around the pair is ours. Errors are counted by an LLM judge checked against a physician (Cohen's κ 0.75 fabricated, 0.42 misapplied).

The Key Idea

Distortion-Freeness

Distortion-freeness. Top left, the survey's Definition 3.2 as printed: a watermark is computationally distortion-free if for any prompt, message, security parameter lambda and polynomial-time algorithm D with access to the model, the two probabilities that D outputs 1 on a response from the model and on a response from the watermarked model differ by at most negl(lambda); if this holds even for unbounded D it is statistically distortion-free. The question: can a watermark leave the distribution of responses exactly as it was? The test: a hidden coin b picks the plain model M or the marked model Wat_k with key k; one response x goes to the distinguisher D, which holds no key, may query M, and answers 0 or 1. Distortion-free: the absolute difference between the probability that D outputs 1 when x comes from M and when x comes from Wat_k is at most negl(lambda), negligible but not zero, with lambda the security parameter. The idea: a plain sampler writes word t as Sample(p_t, u_t) with u_t fresh; a keyed sampler takes u_t = f_k(t), pseudorandom numbers from the key k. So: without k the numbers look fresh, so every response is a fair draw; with k one can recompute every number and check that the text agrees. Two constructions: a language model's sampler (keyed sampling, the exponential scheme) and a diffusion model's latent (Gaussian latent sampling).

*Def. 3.2, last line: if even a computationally unbounded D cannot tell, the watermark is statistically distortion-free.

Entropy

The Entropy Budget

Counting the randomness two responses spend. The question: a watermark can only spend randomness the model spends anyway; how much is there? A forced answer, Paris and a full stop, with probabilities 0.97 and 0.99, costs 0.04 and 0.01 bits; its meter reaches H_e = 0.06 bits: nothing to hide a mark in. An open response, A grey cat sat, with probabilities 0.45, 0.35, 0.60 and 0.40, costs 1.15, 1.51, 0.74 and 1.32 bits; its meter reaches 4.73 bits and crosses the dashed threshold lambda = 4 bits at its fourth token. The scale runs from 0 to 6 bits. Below, the definition: the empirical entropy H_e of x is minus log base 2 of the probability that the unmarked model M writes x for the prompt, which is the sum over positions j of minus log base 2 of p_j of x_j, the probability of the token written at j.

*An illustrative threshold: the paper's guarantees are asymptotic and name no value. Both responses and their probabilities are ours.

Keyed Sampling

Keyed Sampling Randomness

Inverse-transform sampling with a key table, two positions deep. Each key entry xi is a pair: a number u in zero to one and an order on the words. The model's probabilities, six 0.1, seven 0.3, eight 0.6, are laid along a line from 0 to 1 as blocks as wide as their probabilities, in the entry's order. Entry 1 is 0.25 with the order seven, six, eight: walking 0.25 along the line stops inside seven, so seven is written. The chance of stopping in a block is its width, here p of seven is 0.3, so the probability over the key entry that the keyed decoder Gamma writes y equals p of y: Theorem 1, every word is an exact draw from p. Entry 2 is 0.81 with the order six, seven, eight: 0.81 stops in eight, so eight is written. Detection: u1 = 0.25 gave seven, place 1 of 3, eta1 = 0; u2 = 0.81 gave eight, place 3 of 3, eta2 = 1; the alignment cost d is minus the sum of (u_i minus one half) times (eta_i minus one half), minus 0.28; low means marked. OPT-1.3B and LLaMA-7B: detected at p at most 0.01 from 35 tokens, even after 40 to 50 per cent of the tokens were randomly edited.

*Abstract, p. 1: random substitutions, insertions and deletions. Exactness holds while no key entry is reused. The two entries are illustrative and p is held fixed across the two positions.

Keyed Sampling

The Exponential Scheme

Exponential sampling on one worked position. The context Five plus three is goes into an LLM, which gives three candidates: six with probability 0.1, seven with 0.3 and eight with 0.6, drawn as bars to scale. Step 1, key: a keyed function f_k of the context and the candidate gives each a number r_i: 0.5, 0.7 and 0.3. Step 2, reweight: the score v_i is r_i to the power one over p_i: 0.5 to the 1/0.1 is 0.00098, 0.7 to the 1/0.3 is 0.3046, 0.3 to the 1/0.6 is 0.1344; a rare word gets a big exponent, so its number is crushed. Step 3, write: the written token is the argmax of the scores, seven, although eight was twice as likely. Step 4, detect: the score s is the sum over positions of ln of 1 over 1 minus the key number of the written token; here ln of 1 over 1 minus 0.7 is 1.20, and without the key each term averages 1. Why it is fair: the argmax of r_i to the 1/p_i equals the argmax of log p_i minus log of minus log r_i, Gumbel noise on the log-probabilities, so with fresh uniform numbers the written word is an exact draw from p.

*Eight was twice as likely and lost: its key number was low. **Exact only with fresh uniform numbers; a keyed function of the context repeats them when a context repeats. The numbers are illustrative.

Image Watermarks

Gaussian Latent Sampling

Gaussian Shading, the whole round trip. Top: the watermark 1011 is encrypted with the key by a stream cipher, ChaCha20, into random bits 1001 that look like coin flips to anyone without the key. Left: the bell curve of one latent coordinate z, cut at zero into two halves of equal area, bit 0 on the left and bit 1 on the right. Each bit picks a half and a uniform number places the coordinate inside it: z equals the inverse CDF of (u plus y) over 2. y = 1, u = 0.40 gives ppf(0.70) = +0.52; y = 0, u = 0.72 gives ppf(0.36) = -0.36; y = 0, u = 0.15 gives ppf(0.075) = -1.44; y = 1, u = 0.90 gives ppf(0.95) = +1.64. One half times p of z given y = 0 plus one half times p of z given y = 1 equals f of z, the plain bell curve. Right: the paper's Figure 3, the marked latent z_T and the image the ordinary sampler makes from it. Detect: DDIM inversion recovers the latent, the sign of each coordinate is read, y equals the floor of 2 cdf(z), giving 1001, and decrypting with the key gives the watermark 1011 back. 256 bits per image; FID 25.20 plus or minus .22 marked versus 25.23 plus or minus .18 unmarked: t = 0.36 below 2.10, equal means not rejected.

*Table 7, Stable Diffusion: ten groups each; failing to reject is not evidence of equality. The bits and the uniform draws are illustrative.

Properties

Six Properties, One Drawing

Six cards in two rows. Top row, the three notions of quality, weakest first. Distortion: two groups of bars, the plain model M and the marked model Wat_k, with a double arrow between them: how far the distribution moved; defined on Quality and Robustness. Distortion-free: one response x goes to a distinguisher D, which answers with a question mark: one response tells nothing; defined on Distortion-Freeness. Undetectable: D exchanges many adaptive queries with an oracle that is M or Wat_k and answers with a question mark: many queries tell nothing; the test on Distortion-Freeness with an oracle. Bottom row, what the detector owes. Robustness: x passes an edit channel E, becomes x prime, and the detector Det_k still answers true: still detected after an edit; defined on A Written Threat Model. Unforgeability: the adversary holds a tray Q of what it was given and makes a fresh x, and the attribution test Att_ak answers false: it cannot plant a fresh mark; on A Written Threat Model, taught in chapter 5. False positives: content x_0 made without the key goes to Det_k, which answers true at a rate at most epsilon: unmarked content flagged; defined on Detection as Hypothesis Testing.

Top row: three notions of quality, weakest first; bottom row: three things the detector owes. *The bar heights are illustrative.

Properties

The Six Bounds

A table of the six properties with the bound each one states and what it ranges over. False positives: the probability over the detection key that the detector answers true on x is at most epsilon, for every fixed x; ranges over the key only. Distortion: the maximum over messages and prompts of half the sum over responses of the absolute difference between the probabilities that the model and the marked model produce x; ranges over response distributions. Distortion-free: the absolute difference between the probability that D with access to M outputs 1 on a response of M and on a response of the marked model is at most negl(lambda); ranges over key, coins, one response. Undetectable: the absolute difference between D's chance of outputting 1 with oracles M, M and with oracles M and the marked model is at most negl(lambda); ranges over key, coins, many queries. Robustness: the probability that the detector answers false on the edited x prime while x has enough entropy is at most epsilon; ranges over keys, artifact and a named channel. Unforgeability: the probability that the attribution test accepts an x the adversary made, with x not among what it was given, is at most negl(lambda); ranges over both keys and the adversary's coins. Under the table a handwritten strip names every symbol: M model, Wat marked model, Det and Att the detection and attribution tests, pi prompt, m message, R all responses, gk, dtk, ak the three keys, D a polynomial-time distinguisher, E edit channel, P an entropy condition, A adversary, Q what A was given, lambda security parameter, epsilon an error bound, negl negligible in lambda.

Undetectable implies distortion-free, not conversely; robustness and unforgeability pull apart; a detector that never fires meets the first row and answers nothing.

Part II · Chapter 4

Watermark Removal

The problem.An attacker edits marked content until the detector misses it, keeping it useful.

Adaptive attacks: tuned against surrogate keys
SemStamp: a paraphrase-robust mark
Watermarks in the Sand: removal always possible
Sandcastles in the Storm: testing its two assumptions
Regeneration: noise, then regenerate

Graphite drawing on a white ground: a rubber eraser rests on a sheet of paper, half of a faint circular seal impression already rubbed away into smudges and crumbs; a small crimson triangle remains on the surviving half; a hand roller lies beside the sheet.

Robustness

Robustness Against a Channel

Left: the definition of robustness against a channel. x is drawn from Wat_k(prompt), the marked text from the generator with key k; x prime is drawn from E(x), the edited copy, where E is the channel, a named edit. The probability over the key, the sampling and the edit that Det_k(x prime) is false, the detector misses, and P(prompt, x) is true, x could carry a mark, is at most eps_rob, the allowed miss rate. Under it: eps_rob exists only for a named channel E; change the channel and the number changes. Right: KGW under one channel, T5 span replacement. Detector AUC, higher is better, against the perplexity of the edited text, lower is better. No edit: AUC 0.998 at perplexity 6.3. Replacing a share eps of the words: 0.1 gives 0.988 at 13.1, 0.3 gives 0.954 at 21.2 (starred), 0.5 gives 0.838 at 28.4, 0.7 gives 0.696 at 33.9. A dashed line at 0.5 marks a coin flip.

*Fig. 6 caption: the mark degrades seriously only from ε = 0.3, at about 15 points of perplexity. Points: the legend of Fig. 6 (γ = 0.5, δ = 2).

Watermark Removal

One Edited Sentence

length 200 green share 0.25 logit bias 2.0 edits 0

one edit, two positions

biasedchanceedited

evidence for the mark

Here 74 of 200 words must change, 37%, to push under 4.

(Green rate and the statistic).

With uniform tokens each edit turns two biased positions into fair coins.

$g$ green rate$\gamma$ green share$\eta$ logit bias$k^{*}$ edits needed

Watermark Removal

The Measured Version

A line chart in the style of Cheng et al.'s Figure 2, drawn from their Table 6. Across: seven watermarking schemes, KGW-1 (the green list of chapter 2), Unigram, UPV, EWD, DIP, SIR and EXP (the exponential scheme of chapter 3). Up: detection at 1% false alarms in per cent, higher meaning the mark survives. A black line at 100 is no attack. DIPPER-1 (89.0 on Unigram, 74.8 UPV, 66.2 EWD, 64.6 SIR), DIPPER-2 and the GPT paraphraser (paraphrasing the whole text) sit between 0.4 and 89. The three self-information rewrites, SIRA Tiny, Small and Large (rewrite only the tokens with the most self-information), sit between 0.4 and 52.8; on KGW-1 SIRA Tiny is at 26.4, starred, the weakest attack there.

*Drawn from Tab. 6 (p. 16), the numbers behind Fig. 2. Not a ranking: on KGW-1 SIRA Tiny (26.4) is the weakest attack, the paraphrasers sit under 2.

Adaptive Attacks

Adaptive Removal

The provider's marked text x, the river rose fast after the long rain, six of its scored words on the green list, goes to Det_k: z = 5.6, marked; k is the only secret, KeyGen, Wat and Det are published. The adversary wants Det_k(x prime) = false, the detector silent, and Q(x prime, x) at least Q_0, the text still good, where Q is an LLM judge. Step 1: a rewriter, an open LLM, proposes four rewrites. Step 2: each gets a detector score z under a key the adversary holds and a quality Q, and lands on a plane of quality (higher is better) against z (lower is better). Step 3: the line z = 4 and the floor Q_0 cut out a region; two rewrites land inside it and the better text is kept. Step 4, measured (Fig. 2): the evasion rate of the best of N rewrites against N from 1 to 16: Inverse 0.82 to 1.00, Binary 0.62 to 0.99, Dist-Shift = KGW 0.23 to 0.85, Exp 0.27 to 0.83.

*Under a key it holds: where that key comes from is the next slide. Curves read off Fig. 2 (p-value 0.1, untuned Llama2-7b rewriter); the sentence, rewrites and scores are illustrative.

The definition

Adaptive Removal, Formally

Adaptive removal, formally: maximise over E, the search over every edit, the probability that Det_k, the provider's detector, answers false on E(x), the mark is missed, subject to Q(E(x), x), a quality judge comparing the edited and the original text, being at least Q_0, what open models already give. Under it: drop the constraint and an empty string wins, destroying the text is not removal; the paper (Eq. 2) adds both terms inside one expectation over seeds, messages and prompts.

*The adversary cannot evaluate this as written: the detector needs the provider's key k. Surrogate Keys replaces k by keys it makes itself.

Adaptive Attacks

Surrogate Keys

Left of a dashed API boundary, the provider: KeyGen makes the key k, Wat_k marks the text x, the river rose fast after the long rain, which it releases; its detector Det_k is never queried by the adversary. A crimson dashed wire from k is crossed at the boundary: k never crosses. Right, the adversary, holding x. Step 1: it runs the published KeyGen on its own model theta_S and gets its own keys k prime 1, 2, 3, one per seed. Step 2: Wat_k prime marks a text of its own, a gale hit the bay late last night, whose key it knows. Step 3: its own detector says true on that text, z = 6.0, and false after a rewrite, z = 1.2: a score for every rewrite, free, as often as it likes. Step 4, test time: the tuned rewriter E_thetaP rewrites the provider's x and the provider's detector Det_k stays silent, z = 1.4. Trained under k prime, tested under k: evasion 0.943 to 1.000 in every cell of their transfer matrix (Fig. 3); no-box, offline, under 10 dollars.

*This free score is what tunes the rewriter: the next slide runs that loop. Sentences, green patterns and z values are illustrative; the transfer range is Fig. 3 (left).

Adaptive Attacks

The Attack Loop

Two keys drawn apart: the provider's key k, crossed, never seen and never queried; the adversary's own keys k prime 1, 2, 3. Left, Algorithm 1 in course notation, eight lines: D is empty; for each scheme and prompt; k prime from KeyGen(theta_S) and x from Wat_k prime(prompt); if Det_k prime(x) is true; rewrites x prime i from E_thetaP(x) for i up to N; b_i is one when Q(x prime i, x) is at least Q_0 and Det_k prime(x prime i) is false; add (x, r minus, x prime i) to D for each kept rewrite, where r minus is a rejected rewrite or x itself; return D. Right, one pass on a toy text: x is marked under k prime, z = 5.4, and enters the loop; the rewriter, being tuned, draws four rewrites; their quality and z: 0.91 and 1.3, 0.90 and 4.8 (the mark was kept, b = 0), 0.88 and 2.1, 0.86 and 1.6, so R1 holds three and R0 one; D gets (x, x prime 2, x prime 1), (x, x, x prime 3), (x, x, x prime 4): marked, rejected, chosen, and x stands in when R0 runs out. A dashed arrow labelled DPO returns from D to the rewriter. D: 7,000 samples of 512 tokens.

*Under 5 GPU hours to curate D and under $10 to curate and tune (Sec. 6.1). The sentence, rewrites and scores are illustrative.

Adaptive Attacks

Evasion for Ten Dollars

Left, a heat map of evasion rates (Fig. 3 left): rows are the scheme tested on, columns the scheme the rewriter was tuned against; Dist-Shift is KGW, the green list of chapter 2. Dist-Shift row: 0.973, 0.970, 0.943, 0.980, 0.983 (tuned on Dist-Shift, Exp, Binary, Inverse, All). Exp: 0.956, 0.980, 0.973, 0.986, 0.963. Binary: 0.986, 0.990, 0.966, 0.983, 0.970. Inverse: 1.000 in every column. The diagonal, tuned and tested on the same scheme, is outlined in crimson. Right, Fig. 4: paraphrase quality from an LLM judge (higher is better) against evasion rate (higher is better). Typos, synonyms, swaps and translation sit at the far left, barely evading; Dipper at 0.30 and 0.68; Llama2-7b, Llama2-13b, Qwen-7b and GPT-3.5 higher and further right; the tuned rewriters in the top right corner, evasion above 0.9 at quality above 0.8; squares adaptive, circles not. Bottom: under 7 GPU hours and under 10 dollars, with a rewriter up to 46 times smaller than the provider.

*Off the diagonal the rewriter meets a scheme it never trained on, and every cell is still 0.943 or more. Fig. 3: Llama2-13b provider; Fig. 4: Exp scheme, Llama3.1-70b provider, points read off.

Paraphrasing

Why Paraphrasing Removes the Mark

Eight words at context width one: the storm closed our port for two days, with arrows showing each word seeding the next position's green list; six of the seven scored positions are green. Rewritten: the storm shut our docks for two days, with shut and docks changed. Each changed word sends two arrows down: its own position and the next become fair coins; the row after the rewrite shows four half-and-half squares and three solid green ones, the untouched positions that still lean green; the first word is never scored. Right, at T = 200 scored positions, full freedom, one-token window, gamma 0.5, eta 2: green count about 176, z = 10.8, detected; k = 80 words changed, 0.4 of the text; 2k = 160 positions re-rolled, green with probability gamma; green count about 40 times 0.881 plus 160 times 0.5, about 115; z = 2.2, under 4, silent. Bottom left, the formula: z after the rewrite equals the untouched positions T minus 2k, times their excess green rate g minus gamma, over the chance spread, the square root of T gamma (1 minus gamma); g = gamma e to the eta over (gamma e to the eta plus 1 minus gamma) = 0.881. Bottom right, measured (Fig. 5 right): median p-value (lower is stronger evidence, log scale) against tokens: KGW with no attack falls below the 0.01 line near 90 tokens; a plain Llama2-7b rewrite stays above it out to 480 tokens; the tuned rewriter stays near 0.3.

*The plain rewrite never reaches the 1% line out to 480 tokens (Fig. 5 right, read off). The sentence and its green pattern are illustrative; the tally is computed, not measured.

Semantic Watermarks

A Semantic Watermark

SemStamp as a walk on a toy semantic space drawn as a disk cut by two random planes with normals n1 and n2 into four regions labelled 00, 01, 10 and 11. The previous sentence, the storm hit the coast at dawn, lands in region 01 and seeds which regions are valid: two of four, tinted. Step 1, embed: a candidate sentence goes through the encoder M_embd, SBERT tuned so a sentence and its paraphrase land close, and becomes a point v. Step 2, hash: LSH_i(v) = 1[n_i dot v > 0], so v has signature 11. Step 3, split: the number of valid regions is gamma times 2 to the d, here 2 of 4, 0.25 in the paper. Step 4, resample: boats stayed in the harbour lands in a blocked region and is rejected; the port was closed for days lands near a plane and is rejected by the margin rule min_i |cos(n_i, v)| > m (m = 0.02); officials shut the port for days lands well inside a valid region and is kept. Step 5, detect: a paraphrase of the kept sentence lands in the same region; detection counts valid sentences with the same z-test as KGW. Measured on RealNews under a bigram paraphrase: AUC (higher is better) from 100 to 400 tokens, SemStamp 91.6 to 98.5 above KGW 88.2 to 94.7; at 200 tokens, detected at 1% false alarms: KGW 42.7%, SemStamp 76.7%.

*Under a stronger GPT-3.5 bigram paraphrase the same row reads 5.9 for KGW and 31.3 for SemStamp (Tab. 1): better, still broken. Sentences and the two-plane picture are illustrative.

Impossibility

Watermarks in the Sand

*In each pair the attacked image is on the left, the marked original on the right; CLIP score 34.82 → 33.60 and 32.27 → 31.58 (Fig. 5).

Impossibility

A Quality-Preserving Walk

Zhang et al.'s quality-preserving walk run on one toy answer. The prompt is What is fair use; the adversary holds the marked answer and has no key, no scheme and no detector. The answer is a row of word chips, the green tokens of the mark drawn teal, which only the audience sees. Step 1, propose: the perturbation oracle E-step masks one span and T5-XL fills it in, giving a candidate x_t. Step 2, accept: the quality oracle checks Q(x_t given prompt) at least Q(x given prompt), 0.82 against 0.80, and the candidate becomes x prime. A later proposal that breaks the answer scores 0.41 and is rejected, so the state stays; the counter of proposals t advances while the accepted count does not. After N_prop proposals the answer reads Fair use allows anyone to cite brief excerpts of a text for critique or teaching, with 4 of 15 tokens green, about the share an unmarked text gets by chance. Zhang et al. ran this on Llama2-7B with T5-XL proposing and a reward model and GPT-3.5 accepting; KGW, Unigram and EXP all end below z = 1.645, KGW from 6.24 to 1.63 (Table 1).

*Illustrative: the answer, the two edits, the scores and the green tokens are ours; the oracles and the Table 1 numbers are the paper’s.

Black-box attack

Impossibility

Impossibility Under Two Oracles

Zhang et al.'s impossibility claim drawn on their Figure 1. Top: their claim, an attacker who can judge quality and propose small edits can remove the mark from any scheme without losing quality. Left: the space of outputs; an orange box of high-quality outputs and a green box of watermarked outputs overlapping it, a small subset of the good answers. The marked answer x sits at node 1; two proposals that leave the good set are refused and crossed out; the accepted walk runs through node 14, still marked, to node 24, outside the green box and inside the orange one, labelled x prime. A dashed box marks the subset a second key k prime would have marked, and dots spread over the good answers show the key-free law mu where long walks end. Right: the two oracles, E-step proposes one small edit (a masked language model, far weaker than the attacked model) and Q given the prompt asks whether it is still a good answer; after many accepted edits x prime carries no detected mark and its quality never dropped; where long walks end does not depend on the start, so not on the key. The theorem: the probability that the detector with key k says unmarked on x prime is at least one minus the false-alarm rate times one minus the mixing error, and Q of x prime is at least Q of x.

*Their proof overview (§4.2); Thm. 2 carries a further factor of about one half, because mixing is required only above the median quality; Thm. 6 removes it.

Exercise, three parts

Key Independence and Mixing

Exercise, key independence and mixing. The box defines mu_k, the attacked law under key k, mu, the key-free law (assumed), and the hypothesis that the total variation distance between them, the largest gap any event shows, is at most the mixing error epsilon-mix for every k. Tasks: (a) show every detector has 1 minus beta-FNR at most alpha-FPR plus epsilon-mix; (b) what must mixing promise; (c) design the falsifying experiment. Left, our exact picture: two laws over six outcomes, blue bars for mu_k and dashed outlines for mu; total variation is half the summed gap, 0.08; an accept set over outcomes 2 and 3 gets 0.50 against 0.44, a gap of 0.06. Right, six rungs: 01 fix the key and read one event, the gap between Pr under mu_k and Pr under mu that Det_k fires is at most epsilon-mix; 02 average over the key, 1 minus beta-FNR at most the key-average of Pr under mu plus epsilon-mix; 03 use the quantifier in the definition, that average is at most alpha-FPR because mu is fixed without k; 04 the two errors collapse, beta-FNR at least 1 minus alpha-FPR minus epsilon-mix, for every detector; 05 mixing must promise t-mix polynomial and epsilon-mix negligible in the security parameter lambda; 06 the falsifying measurement: paired walks from marked and unmarked starts, blinded quality, fixed budget.

Impossibility

Removal by Random Walk

Removal by random walk, Zhang et al.'s measurements redrawn. Top left, our picture: a walk of thirty accepted edits leaves the marked subset of the good answers. Top middle, their Figure 2 left: the KGW z-score, lower meaning less evidence of a mark, falls from 5.88 after the first edit to 1.15 after thirty, crossing the dashed z = 1.645 line near the end. Top right, their Figure 2 right: the GPT-4 judge score, higher meaning the attacked text is preferred, stays near zero between minus 0.08 and plus 0.17. Bottom middle, their Figure 3b: the GPT-4 verdict over hundreds of pairs, 68 percent similar quality, 20 percent slightly worse, 8 percent much worse, under 4 percent better. Bottom right, their Table 1: z before and after the walk for KGW 6.24 to 1.63, Unigram 8.21 to 1.46 and EXP 3.54 to 0.745, all below 1.645. Bottom left: the setting, Llama2-7B with KGW on 12 prompts, T5-XL proposing, a reward model accepting, GPT-4 grading only afterwards.

*Each example enters twice, once per ordering of the two texts; the averages cover the examples the attack finished, not every prompt.

Impossibility

Testing the Two Assumptions

Harel-Canada et al., Sandcastles in the Storm. Top left, the paper's title page: Sandcastles in the Storm, Revisiting the (Im)possibility of Strong Watermarking, by Fabrice Harel-Canada, Boran Erol, Connor Choi, Jason Liu, Gary Jiarui Song, Nanyun Peng and Amit Sahai, University of California, Los Angeles. Under it the two assumptions: KA1 mixing, after enough good edits a text forgets where it started; KA2 quality, an automatic oracle judges each edit as people would; and the setting: Llama-3.1-70B, KGW, SIR and Adaptive, seven edit oracles, up to 1,000 steps, 270 marked texts, 795 edits rated by people. Right, their Table 1: seven perturbation oracles with step budgets from 1000 to 100, 4,555 lineage tests in total, 53, 4 and 0 failures for Llama-3.1-70B, GPT-4o and o3-mini-high, cumulative 98.84, 99.91 and 100 percent; reading: a judge names which of two starts each sampled draft came from, none wrong in the end, where a mixed walk would sit near 50 percent. Their Table 2: six quality oracles with QP precision from 65.69 to 84.62 and Overall F1 from 66.93 to 77.38; reading: the best Overall F1, 77.38, the authors read as one edit in five misjudged. Bottom left: removal averaged over all pairs, 26.1 percent by the pipeline and 10.5 percent after human review.

*An estimate, not a recount: the pipeline’s rate scaled by the share of reviewed successes people still judged quality-preserving.

Watermark Removal

The Regeneration Attack

The regeneration attack of Zhao et al. run on the paper's own Figure 1 example. Top row: the original polar-bear photograph and the same photograph carrying the mark, x_w, with no visible difference. Step 1, encode: z_0 equals phi of x_w, phi a public encoder, the latent drawn as the paper's line-art bear. Step 2, noise: z_t-star is drawn from a Gaussian with mean alpha of t-star to the one half times z_0 and covariance one minus alpha of t-star times the identity, noise in the latent and not the pixels; the bear covered in noise. Step 3, redraw: z-hat_0 equals denoise of z_t-star at t-star, the attacker's dial, and x-hat equals theta of z-hat_0, theta decoding the redrawn latent; the regenerated photograph; detector: no mark. Bottom: their Figure 4 redrawn, four panels for DwtDctSvd, RivaGAN, SSL and StegaStamp, true-positive rate at 1 percent false-positive rate against PSNR; the three regeneration attacks (diffusion and two VAEs) solid, JPEG, blur, brightness, noise and contrast dashed. Over 99 percent of the marks are removed on the first three schemes with the picture intact; StegaStamp only by heavy diffusion noise.

Black-box attack

Watermark Removal

Certified Removal

Certified removal by regeneration. Top: after regeneration, can any detector still tell a marked image from an unmarked one? Left, our computed picture: on one axis, the line between the two latent centres in units of sigma, a dashed unmarked Gaussian and a solid marked Gaussian whose centres are at most L Delta over sigma apart, here 0.862; the threshold of a test at 1 percent false alarms, 2.326, and the tail it can catch, 0.072. Right, the paper's Figure 2 redrawn: Type I error, false alarm, against Type II error, miss, both lower better for the detector; the coin diagonal, the shaded impossibility region under the bound, and the measured DwtDctSvd curve on 500 MS-COCO images at sigma = 1.16 Delta, running just under the coin and outside the shaded region. Bottom: if the marked and clean images are within Delta in l2, the defender's invisibility budget, the encoder stretches distances by at most L, and the attacker adds Gaussian noise of scale sigma in the embedding, then the miss rate beta-FNR is at least Phi of Phi-inverse of one minus alpha-FPR minus L Delta over sigma: for every detector, every threshold, no key.

*Stated for marks that keep the clean and marked images close in the embedding; a semantic mark such as Tree-Ring sits outside the hypothesis (their App. E).

Black-box attack

One projection, one threshold

The Regeneration Bound, Proved

The regeneration bound, proved in five rungs. Top box: before regeneration, two Gaussians and one draw: N_0, the unmarked image embedded, and N_1, the marked image embedded, with the same covariance sigma squared times the identity, the attacker's noise. Left, our computed picture at L = 1 and sigma = 1.16 Delta: on the projection axis in units of sigma, the dashed unmarked and the solid marked density mu_sep = 0.862 apart, the cut at 2.33 and the caught tail 0.072. Right: 01 invisibility bounds the two centres, the l2 distance between the embeddings is at most L_x,w times Delta; 02 project on the line joining them, mu_sep is that distance over sigma; 03 Neyman-Pearson picks the test, the likelihood ratio is exp of mu_sep t_proj minus half mu_sep squared, monotone in the projection; 04 read the power at that level, 1 minus beta-FNR is at most Phi of mu_sep minus Phi-inverse of 1 minus alpha-FPR, carried to the image by data processing; 05 complement then monotonicity, beta-FNR is at least Phi of Phi-inverse of 1 minus alpha-FPR minus L Delta over sigma, the theorem of Certified Removal.

Chapter 5

Forgery and Provenance

The problem.An attacker forges a provider’s mark. Can a mark be unforgeable yet publicly checkable?

Watermark Stealing: spoof a learned green list
Randomized Key Selection: a fresh key per query
Black-Box Forgery: one image forges a mark
Fairoze et al.: signatures in the sampler
OpenStamp: marking open-weight models

Graphite drawing on a white ground: on the left an unrolled certificate with a ribbon and a wax seal; on the right a carved hand stamp beside a fresh stamped impression on a loose slip that looks almost the same, marked with a small crimson triangle; a magnifying glass lies between them.

Unforgeability

The Unforgeability Game

The unforgeability game played once. The provider runs KeyGen, which issues a marking key k that stays with the marked generator Wat_k and an attribution key ak that is handed to the adversary. Behind a dashed API boundary the adversary sends prompts to Wat_k and keeps the marked answers, the tray Q. A copied answer x2 is accepted by the provider's attribution test Att_ak but is in Q, so it is a replay, not a forgery. A genuine marked span pasted into new text x star is accepted and is not in Q: a forgery. Below, the definition: x is produced by the adversary with oracle access to Wat_k, given 1 to the lambda and ak; the probability that Att_ak accepts x and x is not in Q is at most negligible in lambda.

*Robustness keeps a moved span marked, which is exactly what a forger needs. The answers and the span drawn are illustrative.

Watermark Forgery

Stealing the Green List

Watermark stealing in four steps. Step 1, query: the adversary sends prompts to the watermarked API, whose key and detector are hidden, and keeps 30,000 marked answers for 42 dollars; it sends the same prompts to its own base model for reference text. Step 2, count: after the context the old, the share of each next token in the marked answers and in the reference: house 30 against 15, man 12 against 16, car 18 against 12, tree 8 against 10. Step 3, score: the ratios 2.0, 0.75, 1.5 and 0.8 become the clipped scores 1, 0, 0.75 and 0, so house and car are the estimated green list after the old; the score is one over C times the minimum of the ratio and C when the ratio is at least one, else zero, with C equal to 2. Step 4, spoof or scrub: the logit Z_i plus eta times the score; added to its own model the text reads as marked, subtracted in a paraphraser the mark is dropped. The result: over 80 percent of its own texts pass a detector at one false alarm in 1,000, against KGW2-SelfHash on Llama-7B and 13B.

*Table 1: 0.81 (Llama-7B) and 0.86 (Llama-13B) at FPR 10⁻³, texts a GPT-4 judge scores below 6.5 discarded. The tokens and counts drawn are illustrative.

Black-box attack

Watermark Forgery

Spoofed and Scrubbed

Left, the paper's Figure 3 redrawn: spoofing success in percent at one false alarm in a million against the number of API queries on a log scale from 10 to 30,000. The full attacker's best-of-5 line rises from 7 to about 97 percent and its average from 2 to about 77; the ablation without partial contexts reaches about 85 and 46. All curves climb steeply between 1,000 and 10,000 queries and then flatten. Right, planting from Table 1: 0.81 of the attacker's own texts are accepted against Llama-7B and 0.86 against Llama-13B, at one false alarm in 1,000. Scrubbing from Table 3: a paraphraser alone removes the mark from 0.02 of marked texts, and steered by the stolen score from 0.90 (Llama-7B owner; 0.02 and 0.84 for Llama-13B).

*Without partial contexts the average success at 30,000 queries falls from about 80 % to below 50 % (§6.1). Curves read off Fig. 3.

Black-box attack

Forgery Defense

Randomized Key Selection

Randomized key selection on three keys. Top row: from N equal 3 secret keys k1, k2, k3, one key, k2, is drawn for this query and the provider's LLM marks the answer with it; the three detectors score the answer and only k2 crosses the threshold tau, so s equals 1: authentic. Bottom row: the adversary pools answers made under all three keys, distils its forgery model and writes a forged text; two detectors cross the threshold, so s equals 2: forged, rejected. The rule: 0 keys, not ours; 1 key, authentic; more than 1 key, forged; s of x is the number of keys whose detector answers true, and the text is accepted if and only if s of x equals 1. Right: the paper's own Figure 1, and under it Table 1 redrawn: forgery success against the number of keys r, flat at 0.75 for one key, falling to 0.35 at r equal 8 for Kirchenbauer's multi-key baseline, and to 0.21 at 4 keys and 0.12 at 8 for the randomized scheme.

*An attacker told which key made each sample clusters at 92 % and forges at most 65 % (§4.3). Images, Tree-Ring: 100 % to 2 % at four keys (Fig. 5). Bar lengths illustrative.

Watermark Forgery

Forging a Mark

The imprint forgery on the paper's own photographs. Top row: the victim's published watermarked image, a cat in diving gear holding a sign, goes through the inverse sampler of the attacker's proxy, Stable Diffusion 2.1, giving an initial-noise estimate z tilde T w. From that estimate one branch runs the proxy forward with a new prompt to a new scene with the same mark, which goes to the target service. Below the estimate, the loss: minimise over delta the distance between the inversion of the cover latent plus delta and the noise estimate. Bottom row: the adversary's own cover, a moon landing, plus delta, the change the optimisation adds, decodes to the forged picture, which the target service, detecting and attributing, answers watermarked, user Alice. Bottom right, the paper's Figure 5 redrawn: bit accuracy against gradient steps from 0 to 150, rising fastest in the first 25 steps and ending near 0.99 for SD2.1-Anime, 0.93 for SDXL, 0.88 for PixArt-Sigma and 0.81 for FLUX.1. Bottom left, Table 1 for Gaussian Shading: anime-tuned target 1.00 detected and 1.00 attributed; FLUX.1 0.95 and 0.95; averaging 5,000 marked images 0.00.

*The averaging baseline still forges Tree-Ring (0.90 or better). Fig. 5 curves read off the paper; the noise square and loss counter are drawn stand-ins.

Black-box attack

Public Detection

Public-Key Signatures

Hash-and-sign on one message. The provider holds the signing key sk. The message m_msg, Meet at noon., goes through Hash to a short digest, 3f9a...c2; the digest and sk go through Sign to the signature sigma_sig, a short string of bits. Across a dashed boundary, anyone holding the public key pk runs Verify on the message and the signature, which answers true: pk checks a tag, it cannot make one. Below, the message with one character changed, Meet at noon!, hashes to an unrelated digest, b71e...04, and the same signature verifies false. At the bottom the scheme: sigma_sig is Sign under sk of Hash of m_msg; Verify under pk of the hash and the signature is true or false; the probability of a fresh forgery is negligible in lambda.

The message, digests and signature bits drawn are illustrative; the paper’s scheme is BLS (§4).

Public Detection

Signatures in the Sampler

The publicly detectable gadget on a toy text. Top: a strip of text blocks, the opening block s_msg, The council met on, then five carrier blocks Tuesday, to vote, on a, new, budget, carrying the bits 1 0 1 1 0; a ruler under the strip marks the cost, ell_blk times one plus lambda_c. Step 1: the opening block is hashed twice. Step 2: the first hash is signed with sk, error-corrected and masked by exclusive-or with the second hash, giving the codeword 1 0 1 1 0. Step 3: to plant each bit, candidate blocks are resampled until their hash equals the bit: a rainy and late on hash to 0 and are rejected, Tuesday hashes to 1 and is kept. Step 5: anyone verifies, re-hashing the blocks into bits, unmasking with the second hash and decoding, then checking the signature with the public key pk; Det_pk answers true. Bottom: c_code equals Hash_2 of s_msg exclusive-or Encode of Sign_sk of Hash_1 of s_msg, and Hash_3 of each block equals its bit. More than 1,000 tokens per signature; verifying takes about 0.01 seconds against 1 to 300 seconds for the secret-key scheme.

*Fig. 3: detection with the public key alone, from a known start; the symmetric scheme scans in quadratic time. Words and bits drawn are illustrative.

Public Detection