Edit Distance Robust Watermarks for Language Models

• URL: http://arxiv.org/abs/2406.02633v1
• Date: Tue, 4 Jun 2024 04:03:17 GMT
• Title: Edit Distance Robust Watermarks for Language Models
• Authors: Noah Golowich, Ankur Moitra,
• Abstract summary: 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) and (b) robustness to channels which introduce a constant fraction of adversarial insertions, substitutions, and deletions.
• Score: 29.69428894587431
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Watermarking Language Models with Error Correcting Codes [41.21656847672627]
  We propose a watermarking framework that encodes statistical signals through an error correcting code. Our method, termed robust binary code (RBC) watermark, introduces no distortion compared to the original probability distribution. Our empirical findings suggest our watermark is fast, powerful, and robust, comparing favorably to the state-of-the-art.
  arXiv  Detail & Related papers  (2024-06-12T05:13:09Z)
• Watermarking Language Models for Many Adaptive Users [47.90822587139056]
  We study watermarking schemes for language models with provable guarantees. We introduce multi-user watermarks, which allow tracing model-generated text to individual users. We prove that the undetectable zero-bit scheme of Christ, Gunn, and Zamir (2024) is adaptively robust.
  arXiv  Detail & Related papers  (2024-05-17T22:15:30Z)
• Provably Secure Disambiguating Neural Linguistic Steganography [66.30965740387047]
  The segmentation ambiguity problem, which arises when using language models based on subwords, leads to occasional decoding failures. We propose a novel secure disambiguation method named SyncPool, which effectively addresses the segmentation ambiguity problem. SyncPool does not change the size of the candidate pool or the distribution of tokens and thus is applicable to provably secure language steganography methods.
  arXiv  Detail & Related papers  (2024-03-26T09:25:57Z)
• Pseudorandom Error-Correcting Codes [0.716879432974126]
  We build pseudorandom codes that are robust to cryptographic substitution and deletion errors. We present an undetectable watermarking scheme for outputs of random substitutions and deletions. Our second application is to steganography, where a secret message is hidden in innocent-looking content.
  arXiv  Detail & Related papers  (2024-02-14T18:17:45Z)
• Adaptive Text Watermark for Large Language Models [8.100123266517299]
  It is challenging to generate high-quality watermarked text while maintaining strong security, robustness, and the ability to detect watermarks without prior knowledge of the prompt or model. This paper proposes an adaptive watermarking strategy to address this problem.
  arXiv  Detail & Related papers  (2024-01-25T03:57:12Z)
• Improving the Generation Quality of Watermarked Large Language Models via Word Importance Scoring [81.62249424226084]
  Token-level watermarking inserts watermarks in the generated texts by altering the token probability distributions. This watermarking algorithm alters the logits during generation, which can lead to a downgraded text quality. We propose to improve the quality of texts generated by a watermarked language model by Watermarking with Importance Scoring (WIS)
  arXiv  Detail & Related papers  (2023-11-16T08:36:00Z)
• A Resilient and Accessible Distribution-Preserving Watermark for Large Language Models [65.40460716619772]
  Our research focuses on the importance of a textbfDistribution-textbfPreserving (DiP) watermark. Contrary to the current strategies, our proposed DiPmark simultaneously preserves the original token distribution during watermarking. It is detectable without access to the language model API and prompts (accessible), and is provably robust to moderate changes of tokens.
  arXiv  Detail & Related papers  (2023-10-11T17:57:35Z)
• A Watermark for Large Language Models [84.95327142027183]
  We propose a watermarking framework for proprietary language models. The watermark can be embedded with negligible impact on text quality. It can be detected using an efficient open-source algorithm without access to the language model API or parameters.
  arXiv  Detail & Related papers  (2023-01-24T18:52:59Z)
• Adversarial Watermarking Transformer: Towards Tracing Text Provenance with Data Hiding [80.3811072650087]
  We study natural language watermarking as a defense to help better mark and trace the provenance of text. We introduce the Adversarial Watermarking Transformer (AWT) with a jointly trained encoder-decoder and adversarial training. AWT is the first end-to-end model to hide data in text by automatically learning -- without ground truth -- word substitutions along with their locations.
  arXiv  Detail & Related papers  (2020-09-07T11:01:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.