Pseudorandom Error-Correcting Codes with Applications to Watermarking Generative AI

Miranda Christ (Columbia University)
https://simons.berkeley.edu/talks/miranda-christ-columbia-university-2024-10-17
Alignment, Trust, Watermarking, and Copyright Issues in LLMs

The rise of increasingly realistic generative models has necessitated tools for distinguishing between human-generated and AI-generated content. A promising approach is watermarking, where a hidden pattern is embedded in this AI-generated content. We introduce a powerful new framework for watermarking, which can be instantiated with a cryptographic primitive that we define, called a pseudorandom error-correcting code (PRC). While motivated by watermarking, a PRC is a natural cryptographic object of independent interest.

A PRC is an error-correcting code with the property that any polynomial number of codewords are pseudorandom to any efficient adversary. We construct PRCs from standard cryptographic assumptions, and in this talk I will give an overview of our construction relying on subexponential hardness of LPN. Our PRCs are robust to a constant rate of substitutions and random deletions. I will show how PRCs yield LLM watermarks with strong quality and robustness guarantees.

This is based on work with Sam Gunn: https://eprint.iacr.org/2024/235.pdf