A diffusion model is an image generator that starts from random noise and removes it over many small steps. It does not decide everything at once. The first steps fix the rough layout of the scene, the middle steps settle object shape and identity, and the last steps add texture. Watermarks that try to mark an image as machine-made usually work in that last texture phase. That is also the phase an attacker can erase most cheaply: add noise to the image and let a clean diffusion model redraw it. We propose a provenance mark that uses the timeline on purpose. The layout the model commits to early becomes the message. A short secret-keyed tag computed from that layout is written in during the middle steps, which are the steps a regeneration attack does not redraw. The last steps are left alone so image quality is unchanged.
Moving the tag earlier is not the whole contribution. The mark is meant to resist removal, and also forgery: an attacker should not be able to put a provider's tag on an image the provider never made. That second requirement is a cryptographic one. The tag is derived from a public hash function and a secret key, and verification has to tolerate a few flipped bits. So we analyze forgery in the quantum random oracle model, the standard setting in which an attacker may evaluate the public hash on a superposition of inputs. The analysis gives a concrete rule for how many tag bits the image must carry. That number then becomes the target we must check empirically: can the middle phase of sampling actually carry that many bits through a regeneration attack?
Core Claim
The claim has two parts, and the second constrains the first. First, guidance applied only within a middle window of sampling can embed a tag of $n$ bits that survives the regeneration attacks of Invisible Image Watermarks Are Provably Removable Using Generative AI. Binding that tag to a robust description of the early-phase layout defeats copy-and-paste spoofing. Second, the tag length $n$ needed for a target forgery level is set by a quantum-oracle bound. Fuzzy verification enlarges the attacker's target region, and Grover-type search lets the attacker work through hash and key candidates quadratically faster. The proposal succeeds only if the measured robust capacity of the middle window exceeds this required $n$ at acceptable image quality.
Concretely, let $m$ be a quantized layout descriptor read from the image, $r$ a public per-image salt recovered the same way, $k$ a $\kappa$-bit secret key, and $H$ the public hash. The tag is $\sigma = H(k \,\|\, r \,\|\, m)$, truncated to $n$ bits. The verifier accepts if the decoded tag lies within Hamming distance $d$ of the recomputed $\sigma$. Salting follows the hash-then-salt pattern that Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World shows restores security against superposition queries. The adversary makes $q_H$ quantum queries to $H$, sees $q$ honestly watermarked images, and gets $q_V$ queries to a verification service. We expect a bound of the form
$$\Pr[\text{forge}] \;\le\; O\!\left(\frac{q_H^2}{2^{\kappa}}\right) + (q_V+1)\,\frac{V(n,d)}{2^{n}},$$
where $V(n,d)$ is the number of $n$-bit strings within distance $d$ of a point. The first term comes from Grover-style key search, which is where the square on $q_H$ comes from. The second term comes from blind guesses landing in the acceptance ball. We will prove this formally by a compressed-oracle argument. The unforgeability notion is Boneh and Zhandry's "$q+1$" game, adapted so that the $q$ honest images the attacker sees count as signing queries. The practical consequence is direct. Set the target forgery probability to $2^{-40}$ with a bit-error tolerance matched to the attack. The bound then implies $n$ on the order of a hundred-plus bits. The capacity question is real because the label-image mutual information that On the Separability of Information in Diffusion Models reports is only about 9 nats on Tiny ImageNet. That measurement is of class information, not watermark capacity, but it is a warning that early semantic channels may be narrow.
Relation to Prior Work
Three papers motivate the design. Guidance Watermarking for Diffusion Models steers sampling with gradients from a pretrained watermark detector, applied only in the final steps. It reports near-100% zero-bit detection at a $10^{-10}$ false-alarm rate on Stable Diffusion Prompts and robustness to a 50% center crop. We reuse its guidance machinery, including PCGrad aggregation over a set of transformations. We change three things: the timing (a middle window instead of the final steps), the payload (a keyed, layout-bound tag instead of a fixed detector target), and the security goal (unforgeability, which that paper does not address). Zhao et al. prove that any imperceptible pixel watermark can be removed by a noise-then-redraw attack, with 99% removal on DwtDctSvd, RivaGAN and SSL at PSNR above 30. They also observe that Tree-Ring, a mark placed in the low-frequency structure of the initial noise, survives with near-100% detection. That observation is the empirical motivation for writing the tag where structure is decided. It is also the strongest existing baseline.
The timing choice rests on interpretability work that locates the phases. Emergence and Evolution of Interpretable Concepts in Diffusion Models finds layout crystallizing very early. Uncovering the Disentanglement Capability in Text-to-Image Diffusion Models edits attributes with timestep-specific mixing without disturbing structure. GLIGEN shows the converse windowing: grounding applied early, texture left to the base model. These papers supply the method, not a guarantee. Their phase boundaries were found in other models and tasks, so we must re-measure the window for the watermark channel.
On the cryptographic side, ZK-WAGON is the closest attempt at cryptographic provenance for diffusion images. It has two weaknesses we avoid. Its proofs use classical pairing-style arguments, which a quantum computer would break. And it embeds the proof with least-significant-bit steganography, which Zhao et al.'s attack removes. We deliberately do not follow the "proof of sequential work" route suggested by On the Security of Proofs of Sequential Work in a Post-Quantum World. Its $O(q^3\delta\lambda/2^\lambda)$ bound depends on each hash link being unpredictable. Denoising steps are not like that: distilled one-to-four-step samplers skip the trajectory entirely, so diffusion sampling provides no sequential hardness to prove. We borrow only its compressed-oracle proof style.
Research Program
We will build the scheme on Stable Diffusion 2.1, the model used by Zhao et al. and ZK-WAGON, so their attack code applies directly. Encoding has three parts. A layout descriptor $m$ is read from the predicted clean image at the end of the early phase. It is built from coarse segmentation statistics and low-frequency Fourier coefficients, quantized with a fuzzy-extractor-style error margin so that it can be re-read after attacks. The tag $\sigma$ is computed with a post-quantum hash and spread with an error-correcting code. A tag decoder, trained once on regenerated images so that it learns attack-surviving features, supplies the guidance gradient in a window $[t_1, t_2]$ of the sampling steps.
The theory work proves the bound above. We then extend it to the case where the attacker's $q$ observed images let them estimate the layout-to-tag map statistically, which the oracle abstraction treats as independent samples. We will state plainly where the abstraction ends: the neural decoder is not an oracle, and adversarial optimization against it is analyzed empirically, not proved.
Baselines
The naive reference point is unwatermarked generation. It anchors image-quality metrics, measures the detector's false-alarm rate on clean images, and defines the floor for spoofing: an attacker who simply submits ordinary images. A second naive point is a post-quantum signature attached as metadata, using a Dilithium-style scheme of the kind in A Dilithium-like Multisignature in Fully Split Ring and Quantum Random Oracle Model. It is perfectly unforgeable while intact and fails under any stripping or recompression. It is run on the same images and attacks.
The strongest in-generation competitor is Guidance Watermarking with its published late-step schedule. We run it with the same base model, prompts and number of sampling steps, and with a compute budget matched to ours in guided steps and gradient evaluations, since that paper reports 2x to 13x overhead depending on schedule. Its reported clean-image figure is near-100% detection at a $10^{-10}$ false-alarm rate on Stable Diffusion Prompts. We found no reported result on Lacuna for its detection rate after Regen-Diffusion. Measuring that number is our first experiment.
The strongest regeneration survivor is Tree-Ring, reported by Zhao et al. at near-100% detection after their attack. It is a zero-bit, secret-pattern mark. We compare it on regeneration robustness. We also compare it on spoofing, measured as the fraction of attacker images accepted after the attacker copies or estimates the pattern from $q$ watermarked samples. We beat it if we match its post-regeneration detection while driving copy-spoofing acceptance to the false-alarm floor.
Two ablations isolate our ingredients. The first keeps our layout-bound payload but moves the guidance window to the final steps. If this ablation survives regeneration as well as the middle window, timing is not doing the work. The second keeps the middle window but replaces the layout-bound tag with a fixed key-derived tag. If this ablation resists copy attacks equally well, binding is not doing the work. All methods get the same hyperparameter search budget, tuned on a held-out prompt split.
Why not just…?
Why not just shift Guidance Watermarking's schedule earlier and stop? This is the most serious threat. It may recover most of the robustness. The first ablation tests exactly this. However, a detector-target watermark carries no key-dependent, image-bound message. An attacker who optimizes their own image against a public or leaked detector can therefore spoof it, and nothing in that paper bounds this. If the earlier-shifted baseline matches us on both regeneration and spoofing, we will report the binding mechanism as unnecessary.
Why not just use Tree-Ring, which already survives regeneration? Zhao et al. show it survives. But its secret is one fixed pattern reused across every image. Collecting watermarked outputs therefore lets an attacker estimate the pattern and stamp it elsewhere. Our copy-attack experiment measures this directly. If Tree-Ring's spoofing rate is already at the false-alarm floor, our forgery argument adds little in practice.
Why not just sign the image with a post-quantum signature in metadata? Guidance Watermarking documents that metadata is discarded on re-upload and recompression. Exact hashes also break under any pixel change. We include this baseline to show the robustness gap, not because its unforgeability is weaker.
Why bother with the quantum model if no attacker queries a generation API in superposition? We agree the API queries are classical. The quantum term enters only through local evaluation of the public hash. It costs us roughly a doubling of key length and a modest increase in $n$. We present it as a parameter-sizing rule, not a headline threat.
Proposed Experiments
Prompts come from MS-COCO 2014 captions and the Gustavosta Stable Diffusion Prompts set. False-alarm calibration uses MIRFLICKR and ELSA-D3, following Guidance Watermarking, at rates from $10^{-6}$ to $10^{-10}$. Attacks come from WatermarkAttacker: Regen-Diffusion at noise steps 30, 60 and 100, and Regen-VAE at quality levels 6 down to 1. We add JPEG compression, crops and brightness shifts. We also add a spoofing suite: tag copy-paste across images, pattern averaging over $q$ samples, and gradient-based optimization against our decoder.
The decisive first measurement is a capacity map. For each window $[t_1,t_2]$ we record tag bit accuracy after each attack, alongside image quality measured by FID, CLIP prompt alignment and PSNR to the unguided sample. From the bit-error rate we read off the robust capacity and compare it with the $n$ the bound requires for a $2^{-40}$ forgery target.
Three outcomes settle the idea. If no window carries the required bits through Regen-Diffusion at noise step 60 without a visible quality loss, the proposal fails as stated. In that case we would report the capacity frontier as a negative result. If the middle window carries the bits but the late-window ablation does too, timing is not the mechanism. If both hold, and copy-spoofing acceptance stays at the calibrated false-alarm rate while Tree-Ring's does not, the layout-bound, middle-scheduled tag is the contribution.
References
- Invisible Image Watermarks Are Provably Removable Using Generative AI
- Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World
- On the Separability of Information in Diffusion Models
- Guidance Watermarking for Diffusion Models
- Emergence and Evolution of Interpretable Concepts in Diffusion Models
- Uncovering the Disentanglement Capability in Text-to-Image Diffusion Models
- GLIGEN: Open-Set Grounded Text-to-Image Generation
- ZK-WAGON: Imperceptible Watermark for Image Generation Models using ZK-SNARKs
- On the Security of Proofs of Sequential Work in a Post-Quantum World
- A Dilithium-like Multisignature in Fully Split Ring and Quantum Random Oracle Model