Paper 2024/898

Edit Distance Robust Watermarks for Language Models

Noah Golowich, Massachusetts Institute of Technology
Ankur Moitra, Massachusetts Institute of Technology
Abstract

Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees. We aim for watermarks which satisfy: (a) undetectability, a cryptographic notion introduced by Christ, Gunn & Zamir (2024) which stipulates that it is computationally hard to distinguish watermarked language model outputs from the model's actual output distribution; and (b) robustness to channels which introduce a constant fraction of adversarial insertions, substitutions, and deletions to the watermarked text. Earlier schemes could only handle stochastic substitutions and deletions, and thus we are aiming for a more natural and appealing robustness guarantee that holds with respect to edit distance. Our main result is a watermarking scheme which achieves both undetectability and robustness to edits when the alphabet size for the language model is allowed to grow as a polynomial in the security parameter. To derive such a scheme, we follow an approach introduced by Christ & Gunn (2024), which proceeds via first constructing pseudorandom codes satisfying undetectability and robustness properties analogous to those above; our key idea is to handle adversarial insertions and deletions by interpreting the symbols as indices into the codeword, which we call indexing pseudorandom codes. Additionally, our codes rely on weaker computational assumptions than used in previous work. Then we show that there is a generic transformation from such codes over large alphabets to watermarking schemes for arbitrary language models.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
watermarkingerror correctionlarge language modelsgenerative AI
Contact author(s)
nzg @ mit edu
moitra @ mit edu
History
2024-06-06: approved
2024-06-05: received
See all versions
Short URL
https://ia.cr/2024/898
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/898,
      author = {Noah Golowich and Ankur Moitra},
      title = {Edit Distance Robust Watermarks for Language Models},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/898},
      year = {2024},
      url = {https://eprint.iacr.org/2024/898}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.