The Cryptographic Turn in AI Watermarking

As generative AI output becomes harder to distinguish from human-created content, the need to reliably identify machine-generated artifacts grows. Model operators scraping the web for training data must avoid polluting their datasets with AI output, while society at large faces challenges from deepfakes and misattributed content. Watermarking — embedding identifying information into a model's artifacts — is one proposed piece of the solution.

Established approaches like the C2PA initiative attach provenance via metadata, forming a chain of digital signatures as content is modified. That approach requires every entity handling an artifact to participate. Watermarking offers a complement: rather than storing provenance in metadata, the identifying signal is baked directly into the pixels, text, or audio of the artifact itself. This survives unattributed modification that would strip metadata.

Current state-of-the-art watermarks, such as Google's SynthID and Meta's Video Seal, rely on deep learning. These schemes train an encoder–decoder model, subjecting watermarked artifacts to known attacks during training. The resulting system is robust only against the attacks it has seen; new attack variants require retraining. This is the familiar cat-and-mouse game of security engineering.

Cryptography offers a different route. Rather than defending against an open-ended set of attacks, cryptographic watermarks aim to reduce the attack surface to a narrow, well-understood problem — such as guessing a secret key or solving a presumed-hard computational puzzle. The goal is watermarks with rigorous guarantees on three fronts:

  • Robustness: watermarks should remain verifiable after the artifact is modified.
  • Undetectability: watermarked artifacts should be statistically indistinguishable from non-watermarked ones.
  • Unforgeability: only the model operator should be able to produce valid watermarked artifacts.

Pseudorandom Error-Correcting Codes

The first cryptographic AI watermark, proposed by Scott Aaronson in 2022, was tailored to chatbots and met the undetectability and unforgeability goals, but was susceptible to simple robustness attacks — for instance, asking the chatbot to embed a pattern in its response, then manually removing the pattern. Subsequent proposals traded off detectability against robustness.

A framework articulated by Miranda Christ and Sam Gunn at CRYPTO 2024 aims to provide all three properties simultaneously. The starting point is an error-correcting code, a tool normally used to transmit messages over noisy channels. To create a watermark, the operator embeds a codeword into the randomness used by the generative model. Verification runs the model "in reverse" to recover an approximation of that randomness, extracts the (possibly corrupted) codeword, and attempts to decode it. The error-correcting property tolerates bit flips introduced by imperfect inversion or by an attacker modifying the artifact.

Naively embedding a fixed codeword biases the model's output, making the watermark detectable. And since the encoding algorithm is public, anyone could forge a watermark. The solution is a pseudorandom error-correcting code, where codewords are computationally indistinguishable from random strings and can only be generated with a secret watermarking key. The framework defines three algorithms:

  • k = key_gen(): generates the watermarking key.
  • c = encode(k, m): produces a codeword for message m.
  • m = decode(k, c): recovers the message or indicates failure.

For undetectability, the codeword must be embedded in the randomness without altering its distribution. The details depend on the model.

Embedding Watermarks in Stable Diffusion

Stable Diffusion takes as input a normally distributed tensor of floating point numbers — the latent — and denoises it according to a user's prompt to produce an image. Approximating the initial latent from a generated image is possible via DDIM Inversion, an iterative process that reverses the sampling procedure. DDIM Inversion is computationally fast but imprecise; more sophisticated methods recover exact initial latents at higher cost.

Watermark embedding can exploit a simple property of the latent distribution: each number is equally likely to be positive or negative. A bit of pseudorandom codeword determines the sign of each entry in the latent tensor. To verify, the operator runs inversion on the image, extracts the sign pattern as the noisy codeword, and decodes.

Empirical evaluation on the PartiPrompts benchmark showed that for paired initial latents and DDIM-inverted latents, an average of 82% of signs matched, with at least 75% matching for 90% of pairs. This leaves a meaningful margin for error correction, though better inversion techniques would provide a wider robustness cushion.

Candidate Constructions

Building pseudorandom codes requires more than composing standard primitives. "Encrypt-then-encode" fails because error-correcting codes are highly structured, betraying their presence. The dual "encode-then-encrypt" approach fails because non-malleable encryption cannot tolerate bit flips, while malleable encryption allows targeted forgery. Current candidates instead modify existing error-correcting codes.

Pseudorandom LDPC codes

Christ and Gunn start from Low-Density Parity-Check (LDPC) codes, defined by a sparse parity-check matrix P and a derived generator matrix G. Their contribution is choosing parameters so that, when P is selected at random, the induced G is pseudorandom — meaning codewords c = G * m look random. Robustness follows immediately from LDPC's error-correction capacity, but undetectability rests on relatively strong, understudied computational assumptions.

The security concern is that the attacker might guess a row of P. The dot product of a codeword with any row of P yields a small value, while the same operation on a random bit string yields a value around ½. This distinguishes codewords from random strings. Guessing rows becomes easier with sparser matrices or shorter codewords, establishing a tension between pseudorandomness and robustness.

Pseudorandom codes from PRFs

A construction by Noah Golowich and Ankur Moitra instead uses a pseudorandom function (PRF). A codeword consists of pairs (x_i, F(k, x_i)) for random bit strings x_i. Verification parses the codeword and checks how many PRF evaluations match. This construction is naturally pseudorandom if the PRF is secure. However, flipping a single w_i causes that pair's check to fail. Defeating this requires a secret random permutation over all codeword bits, forcing the attacker to guess positions blindly. Robustness still scales with the number of PRF checks, which trades against pseudorandomness through the length of the x_i strings.

Practical Assessment

Engineering practice reveals the gap between theory and deployment. In experiments with Stable Diffusion, the LDPC code could be tuned to tolerate up to 33% corrupted bits — likely more than sufficient for robustness — but only with a parity-check matrix sparse enough that pseudorandomness was severely weakened. With plausibly pseudorandom parameters, tolerated bit flips dropped below 5%. The PRF-based code fared worse, tolerating at most 1% bit flips with pseudorandom parameters, and no tested parameter set surpassed 5% while maintaining pseudorandomness.

These limitations suggest several avenues forward. Larger latent spaces would allow longer codewords and better robustness; short outputs, like chatbot responses, remain difficult for any watermarking strategy. More accurate inversion methods, though computationally expensive, would provide a better margin. And for some applications, cryptographic undetectability may be stronger than necessary — statistical tests for bias or correlation could suffice, accepting the risk of perceptible output differences.

The value of the pseudorandom code framework is its clean separation of concerns. Cryptographers refine constructions and prove security properties; AI practitioners work on embedding techniques. This division could make watermarking practical for model operators who do not train their own models. The field, barely a couple years old, still needs better parameter analysis and new construction ideas. Public verification — where anyone, not just the operator, can check a watermark — remains an open challenge. And while the current focus is generative AI, the underlying idea — embedding a codeword in randomness at the source of an artifact's creation — could eventually extend to provenance for digital photography and other non-AI content.