Zero-bit PRC ⇒ Watermarking

Fully-black-box reduction · standard model · CG24 · security loss: tight: the undetectability distinguisher is forwarded to the PRC pseudorandomness game, and with uniform coins the outputs are exactly the model’s

Statement

A zero-bit PRC yields a watermarking scheme for language models that is undetectable (polynomially many watermarked outputs are computationally indistinguishable from the model’s own outputs) and whose detector survives cropping and a constant rate of random substitutions and deletions, provided the model’s responses carry enough entropy — CG24.

Sketch

Generation samples the response using the bits of a fresh codeword $c\leftarrow {\mathsf{Enc}}_k$ in place of uniform coins; with uniform coins the output is exactly the model’s, so undetectability is PRC pseudorandomness. Detection runs ${\mathsf{Dec}}_k$ on the bit string read off a candidate text, on which edits to the text act as substitutions and deletions that PRC robustness absorbs.

Notes

• Undetectable watermarks robust to a constant fraction of adversarial insertions, substitutions and deletions (edit distance), for alphabets of size polynomial in the security parameter, are built from indexing pseudorandom codes — GM24.