Pipelines that generate synthetic vision-language data already work like rejection samplers. A language model writes several candidate instructions or captions, a diffusion model (an image generator that turns random noise into a picture step by step) renders several candidate images, and a vision-language model keeps only the ones that pass a quality check. MultiEdit, for example, generates edits with GPT-4o and GPT-Image-1 and filters them with Qwen2.5-VL. We propose to use that existing choice among acceptable candidates to hide a digital signature across the dataset. The signature is carried by what each kept sample depicts and instructs: which object was added, which attribute changed, which viewpoint was chosen. It is not carried by pixels or by exact wording. Anyone holding the public key can check the signature. No one can forge it unless a one-way function can be inverted. Pixel purification and caption paraphrasing leave it intact, because both keep a sample's meaning, and meaning is what a data thief wants to keep.
The cryptographic angle is deliberate. Most provenance schemes in practice treat SHA-256 as a "random oracle", an idealized public box that returns fresh random answers. Security proofs then rely on powers the proof is allowed to use but no real attacker faces: seeing every hash query, and choosing the box's answers on the fly. Our construction needs only pseudorandom functions and signatures, both of which follow from one-way functions, so its guarantees do not depend on that idealization. The practical claim is that the usual cost of avoiding random oracles, the "efficiency tax", mostly disappears in data factories. The expensive step in a standard-model watermark is repeated sampling until an output matches the signature bits, and here that step is already paid for by the filter.
Core Claim
Inaccessible Entropy for Watermarking Generative Agents proves that, if one-way functions exist, watermarks can be distortion-free, unforgeable and publicly detectable. It gets there by hash-and-sign combined with rejection sampling over the tokens a text model generates. It pays for this with codewords of length $O(\lambda^7)$, where $\lambda$ is the security parameter. Its robustness is also only "weak": the mark survives only if long contiguous runs of original tokens survive. Both limits come from its choice of embedding unit, a single token.
We change the unit to a single dataset sample, and we change the channel to that sample's semantic content. For each sample $i$, the pipeline produces $k$ candidates, and the existing filter marks a subset $A_i$ of them as acceptable. A canonicalizer $c(\cdot)$ is a fixed vision-language model prompted to output a short discrete description, such as a scene-graph edit triple. It maps each candidate to a semantic key. The pipeline then keeps an acceptable candidate $x \in A_i$ that satisfies
$$ F_K\big(i, c(x)\big) \oplus m_i = 0 . $$
Here $F_K$ is a pseudorandom function with secret key $K$ that outputs one bit. $m_i$ is the $i$-th bit of an error-corrected encoding of a signature over the dataset's metadata: pipeline stages, model checkpoints and seed hashes. If no acceptable candidate matches, the sample is kept anyway and counted as an erasure.
Detection works like this. The owner publishes the verification key. When disputed data appears, the canonicalizer is re-run on it and the bits are read back with $F_K$, which the owner reveals or evaluates inside a verifiable disclosure. Error correction then decodes the bits, and the signature is checked. If canonicalization succeeds with probability $p$ and the filter leaves real semantic choice, an erasure-coded payload needs roughly $n/(p\,(1-\epsilon))$ samples for an $n$-bit code, where $\epsilon$ is the erasure rate. This follows from the capacity of the binary erasure channel. The practical consequence is that the payload is spread across thousands of samples. Most of them can be lost and the mark survives.
The novelty over prior work is in three places. The mark lives in the semantic distribution of the dataset rather than in per-item signals. It reuses a filter the pipeline already has. And its proof avoids random-oracle programmability.
Research Program
The first strand is the construction and its proof. We will prove three properties in the standard model. Distortion-freeness means the marked dataset cannot be told apart from the filtered unmarked one by anyone without $K$; this reduces to the security of the pseudorandom function. Unforgeability means no one without the signing key can produce data that verifies, which rules out framing an innocent party; this reduces to signature security from one-way functions. Detectability means the owner can recover the mark from a subset of the data after meaning-preserving attacks.
The proof matters because of Non Observability in the Random Oracle Model. That paper formalizes reductions that cannot see adversary hash queries, and it shows some extractors cannot exist without that ability. That result warns that a ROM-style proof of "you could only forge by querying the hash on our samples" would quietly rely on observing queries. We also follow Instantiability of RSA-OAEP under Chosen-Plaintext Attack, which shows that a random oracle can sometimes be replaced by a merely $t$-wise independent hash when the proof only needs extraction. Following it, we will work out whether the bit-balancing step can use such a limited-independence hash while unforgeability keeps a real pseudorandom function. Doing so would shrink the per-sample cost to near nothing.
The second strand is the canonicalizer, which is the weakest part of the design and where most of the empirical effort goes. It must satisfy two conditions. It must give the same key on a sample before and after purification, recompression and paraphrase. It must also be coarse enough that the $k$ acceptable candidates actually differ in key; otherwise every sample is an erasure. We will measure both properties across key granularities, from object category alone up to full edit triples, and choose the setting that maximizes effective capacity $p(1-\epsilon)$.
The third strand is the efficiency accounting. Blömer et al. documents the overheads standard-model schemes typically carry. A Transform for NIZK Almost as Efficient and General as the Fiat-Shamir Transform Without Programmable Random Oracles avoids programmable oracles but needs 6 exponentiations for Diffie-Hellman proofs instead of 2. We will measure the actual extra wall-clock and GPU cost of our scheme in a working pipeline: one canonicalizer call per candidate plus cheap pseudorandom-function evaluations. We will compare that against the cost of generating the candidates themselves.
Baselines
The naive reference point is an unmarked dataset built by the same pipeline with the same filter and the same $k$. It sets the utility ceiling. Its detection rate is the false-positive floor, and a correct verifier should report no signature on it.
The strongest per-image competitor is image dataset watermarking of the kind benchmarked in Evaluating Dataset Watermarking for Fine-tuning Traceability of Customized Diffusion Models. That work evaluates DiffusionShield and WatermarkDM, which embed learned pixel or latent signals so they transfer into fine-tuned models. It reports that DiffusionShield reaches nearly 100% detection when only 20% of training data is marked. It also reports that DeAttack, which degrades images and then restores them with an IRNeXt network, cuts WatermarkDM detection on CelebA-HQ with LoRA from 96.88% to 56.25%. We will apply WatermarkDM and DiffusionShield to the same generated images and attack them with the same DeAttack reimplementation and the same perturbation budget. Our scheme beats them if its detection stays above 95% where theirs falls near chance, at equal downstream utility.
The strongest text-side competitor is VLA-Mark. VLA-Mark biases a vision-language model's word choices toward visually grounded tokens and reports 98.8% detection AUC, 96.1% resilience to word swaps, deletions and paraphrase, and 1–2.5% latency overhead. We will apply it to the instructions and captions in our pipeline and attack with the same paraphrasers. VLA-Mark uses a shared secret key and has no public verification or unforgeability. So beating it means matching its detection under paraphrase while also resisting the framing attack it cannot address: an adversary who produces text that tests as watermarked. Its reported numbers are on its own benchmark, and we will rerun it rather than compare across setups.
The key ablation is a random-oracle version of our own scheme. It replaces $F_K$ with SHA-256 over the semantic key and uses a hash-then-sign signature proven in the ROM, with everything else identical. We expect it to behave the same empirically. Its role is to isolate what the standard-model design costs in throughput. If the gap is under a few percent, the proof comes nearly free. A second ablation keeps the signature but embeds it in pixel seeds instead of semantic keys. This isolates whether the choice of semantic channel is what buys robustness.
Why not just…?
Why not just sign the dataset file and publish the signature alongside it? Signing the whole dataset file, or attaching signed metadata to each file, is simpler and fully secure while the dataset stays intact. The threat we target is content that has been separated from its metadata. It gets scraped, re-hosted, purified to strip marks, recaptioned, subsampled or mixed with other data, and a detached signature says nothing about such material. We treat intact distribution as solved by ordinary signatures and scope our claim to the detached case. One experiment makes this concrete: after re-encoding and 10% subsampling, a manifest signature verifies on 0% of recovered data by construction.
Why not just use a SHA-256 hash and accept the random oracle heuristic, as industry does? This is a real threat to the significance of the work, and the random-oracle ablation will likely show identical detection. Our answer is not that SHA-256 breaks. It is that the property we care about most in disputes, "this data could not have been forged to look like ours", is exactly where ROM proofs rely on observing or programming queries. Non Observability in the Random Oracle Model shows such reliance can be essential, and Instantiability of RSA-OAEP under Chosen-Plaintext Attack shows that instantiating an oracle needs explicit properties of the concrete hash. If the measured throughput tax is negligible, the standard-model version should simply be the default. If it is large, we will report that honestly.
Why not just use a robust image watermark and a text watermark together? The file's evidence says each channel breaks under the attacks that preserve utility. Evaluating Durability reports image watermark accuracy dropping by over 80% under Zoom Blur and Unigram-WM detection dropping by nearly 99% under sentence rewrites. DeAttack defeats WatermarkDM. Stacking two brittle channels does not bind image and text together, and neither channel is publicly verifiable. Our experiments include this combined baseline under the same attack suite.
Why not just embed the mark in the diffusion model's starting noise? Choosing the starting noise is cheaper than generating $k$ candidates. However, it is a pixel-level channel, and restoration attacks like DeAttack regenerate exactly the high-frequency structure that noise-level marks depend on. The seed-embedding ablation tests this directly. If seed marks survive DeAttack in our pipeline, the semantic channel is unnecessary and we will say so.
Proposed Experiments
We build two pipelines. The first reproduces the MultiEdit recipe using the released inclusionAI/MultiEdit source images, with open models substituted where needed for reproducibility. The second is an InstructPix2Pix-style caption-to-edit pipeline built with Stable Diffusion, following InstructPix2Pix. Each produces roughly 100K marked samples at $k=4$ candidates.
The first decisive check is utility. We fine-tune Stable Diffusion 3 on marked versus unmarked data and evaluate on MultiEdit-Test. MultiEdit reports that this fine-tune raises DINO from 0.5751 to 0.7359 and that its best model reaches CLIPimg 0.8174. Distortion-freeness predicts no difference beyond seed noise between marked and unmarked training. For the second pipeline, we compare against unmarked training on the same editing metrics.
The second check is robustness. Detection must be recovered from the fewest samples possible after four kinds of attack: DeAttack purification, the image and text perturbation suites from Evaluating Durability, LLM recaptioning and instruction paraphrase, and subsampling to 20%, 5% and 1% mixed with unmarked MS-COCO pairs. We report true-positive rate at a false-positive rate bounded by signature forgery probability. The claim fails if the scheme needs more than a few thousand surviving samples, or if canonicalization agreement after DeAttack falls below the level at which error correction can decode.
The third check is framing resistance. An adversary with the public key and marked samples tries to make an unrelated dataset verify. Heuristic baselines may be forgeable here; our scheme should succeed with only negligible probability.
The fourth check is cost. We report the added wall-clock time per sample relative to candidate generation, for both the standard-model scheme and its ROM twin. We also report effective capacity $p(1-\epsilon)$ as a function of canonicalizer granularity. That capacity is the quantity that decides whether the idea works at all.
As an exploratory fifth check, we ask whether a model fine-tuned on marked data inherits the semantic bias well enough that probing its edits recovers bits. The reference point is DiffusionShield's near-100% transfer at a 20% marking rate. A negative result here would narrow the claim to detecting datasets rather than models, which remains useful.
References
- Inaccessible Entropy for Watermarking Generative Agents
- Non Observability in the Random Oracle Model
- Instantiability of RSA-OAEP under Chosen-Plaintext Attack
- 07381 Abstracts Collection – Cryptography
- A Transform for NIZK Almost as Efficient and General as the Fiat-Shamir Transform Without Programmable Random Oracles
- Evaluating Dataset Watermarking for Fine-tuning Traceability of Customized Diffusion Models: A Comprehensive Benchmark and Removal Approach
- VLA-Mark: A cross modal watermark for large vision-language alignment model
- Evaluating Durability: Benchmark Insights into Multimodal Watermarking
- InstructPix2Pix: Learning to Follow Image Editing Instructions
- MultiEdit: Advancing Instruction-based Image Editing on Diverse and Challenging Tasks