LLM-Text Watermarking based on Lagrange Interpolation

• URL: http://arxiv.org/abs/2505.05712v3
• Date: Tue, 13 May 2025 02:12:54 GMT
• Title: LLM-Text Watermarking based on Lagrange Interpolation
• Authors: Jarosław Janas, Paweł Morawiecki, Josef Pieprzyk,
• Abstract summary: This work presents a watermarking scheme for LLM-generated text based on Lagrange adversarial.<n>The core idea is to embed a continuous sequence of points $(x, f(x))$ that lie on a single straight line.<n>During extraction, the algorithm recovers the original points along with many spurious ones.
• Score: 1.3904534961196113
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The rapid advancement of LLMs (Large Language Models) has established them as a foundational technology for many AI and ML-powered human computer interactions. A critical challenge in this context is the attribution of LLM-generated text -- either to the specific language model that produced it or to the individual user who embedded their identity via a so-called multi-bit watermark. This capability is essential for combating misinformation, fake news, misinterpretation, and plagiarism. One of the key techniques for addressing this challenge is digital watermarking. This work presents a watermarking scheme for LLM-generated text based on Lagrange interpolation, enabling the recovery of a multi-bit author identity even when the text has been heavily redacted by an adversary. The core idea is to embed a continuous sequence of points $(x, f(x))$ that lie on a single straight line. The $x$-coordinates are computed pseudorandomly using a cryptographic hash function $H$ applied to the concatenation of the previous token's identity and a secret key $s_k$. Crucially, the $x$-coordinates do not need to be embedded into the text -- only the corresponding $f(x)$ values are embedded. During extraction, the algorithm recovers the original points along with many spurious ones, forming an instance of the Maximum Collinear Points (MCP) problem, which can be solved efficiently. Experimental results demonstrate that the proposed method is highly effective, allowing the recovery of the author identity even when as few as three genuine points remain after adversarial manipulation.

Related papers

• StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models [4.76514657698929]
  StealthInk is a stealthy multi-bit watermarking scheme for large language models (LLMs)<n>It preserves the original text distribution while enabling the embedding of provenance data.<n>We derive a lower bound on the number of tokens necessary for watermark detection at a fixed equal error rate.
  arXiv  Detail & Related papers  (2025-06-05T18:37:38Z)
• Optimized Couplings for Watermarking Large Language Models [8.585779208433465]
  Large-language models (LLMs) are now able to produce text that is, in many cases, seemingly indistinguishable from human-generated content.<n>This paper provides an analysis of text watermarking in a one-shot setting.
  arXiv  Detail & Related papers  (2025-05-13T18:08:12Z)
• DERMARK: A Dynamic, Efficient and Robust Multi-bit Watermark for Large Language Models [18.023143082876015]
  We propose a dynamic, efficient, and robust multi-bit watermarking method that divides the text into variable-length segments for each watermark bit.<n>Our method reduces the number of tokens required per embedded bit by 25%, reduces watermark embedding time by 50%, and maintains high robustness against text modifications and watermark erasure attacks.
  arXiv  Detail & Related papers  (2025-02-04T11:23:49Z)
• Signal Watermark on Large Language Models [28.711745671275477]
  We propose a watermarking method embedding a specific watermark into the text during its generation by Large Language Models (LLMs) This technique not only ensures the watermark's invisibility to humans but also maintains the quality and grammatical integrity of model-generated text. Our method has been empirically validated across multiple LLMs, consistently maintaining high detection accuracy.
  arXiv  Detail & Related papers  (2024-10-09T04:49:03Z)
• Large Language Model Watermark Stealing With Mixed Integer Programming [51.336009662771396]
  Large Language Model (LLM) watermark shows promise in addressing copyright, monitoring AI-generated text, and preventing its misuse. Recent research indicates that watermarking methods using numerous keys are susceptible to removal attacks. We propose a novel green list stealing attack against the state-of-the-art LLM watermark scheme.
  arXiv  Detail & Related papers  (2024-05-30T04:11:17Z)
• Topic-Based Watermarks for Large Language Models [46.71493672772134]
  We propose a lightweight, topic-guided watermarking scheme for Large Language Model (LLM) output.<n>Our method achieves comparable perplexity to industry-leading systems, including Google's SynthID-Text.
  arXiv  Detail & Related papers  (2024-04-02T17:49:40Z)
• Provably Robust Multi-bit Watermarking for AI-generated Text [37.21416140194606]
  Large Language Models (LLMs) have demonstrated remarkable capabilities of generating texts resembling human language.<n>They can be misused by criminals to create deceptive content, such as fake news and phishing emails.<n> Watermarking is a key technique to address these concerns, which embeds a message into a text.
  arXiv  Detail & Related papers  (2024-01-30T08:46:48Z)
• WatME: Towards Lossless Watermarking Through Lexical Redundancy [58.61972059246715]
  This study assesses the impact of watermarking on different capabilities of large language models (LLMs) from a cognitive science lens. We introduce Watermarking with Mutual Exclusion (WatME) to seamlessly integrate watermarks.
  arXiv  Detail & Related papers  (2023-11-16T11:58:31Z)
• A Robust Semantics-based Watermark for Large Language Model against Paraphrasing [50.84892876636013]
  Large language models (LLMs) have show great ability in various natural language tasks. There are concerns that LLMs are possible to be used improperly or even illegally. We propose a semantics-based watermark framework SemaMark.
  arXiv  Detail & Related papers  (2023-11-15T06:19:02Z)
• SemStamp: A Semantic Watermark with Paraphrastic Robustness for Text Generation [72.10931780019297]
  Existing watermarking algorithms are vulnerable to paraphrase attacks because of their token-level design. We propose SemStamp, a robust sentence-level semantic watermarking algorithm based on locality-sensitive hashing (LSH) Experimental results show that our novel semantic watermark algorithm is not only more robust than the previous state-of-the-art method on both common and bigram paraphrase attacks, but also is better at preserving the quality of generation.
  arXiv  Detail & Related papers  (2023-10-06T03:33:42Z)
• Towards Codable Watermarking for Injecting Multi-bits Information to LLMs [86.86436777626959]
  Large language models (LLMs) generate texts with increasing fluency and realism. Existing watermarking methods are encoding-inefficient and cannot flexibly meet the diverse information encoding needs. We propose Codable Text Watermarking for LLMs (CTWL) that allows text watermarks to carry multi-bit customizable information.
  arXiv  Detail & Related papers  (2023-07-29T14:11:15Z)
• Watermarking Text Generated by Black-Box Language Models [103.52541557216766]
  A watermark-based method was proposed for white-box LLMs, allowing them to embed watermarks during text generation. A detection algorithm aware of the list can identify the watermarked text. We develop a watermarking framework for black-box language model usage scenarios.
  arXiv  Detail & Related papers  (2023-05-14T07:37:33Z)
• Stealing the Decoding Algorithms of Language Models [56.369946232765656]
  A key component of generating text from modern language models (LM) is the selection and tuning of decoding algorithms. In this work, we show, for the first time, that an adversary with typical API access to an LM can steal the type and hyper parameters of its decoding algorithms. Our attack is effective against popular LMs used in text generation APIs, including GPT-2, GPT-3 and GPT-Neo.
  arXiv  Detail & Related papers  (2023-03-08T17:15:58Z)

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.