Synchronization-Free Algebraic Fingerprints for Large Language Models: From Autoregressive to Diffusion Models
Cryptography and SecurityInformation Theory
Summary
The authors propose a new way to watermark text generated by large language models so that the creator can be identified even if the text is edited or rearranged. Their method uses pairs of words to embed small pieces of a secret code based on a special polynomial, which makes the watermark resistant to changes like adding or removing words. They also analyze how well the watermark can be recovered despite errors and show it needs only a little extra data to remain reliable. This approach avoids problems with older methods that rely on fixed blocks of text and can handle both short and long secret identifiers.
Authors
Jaroslaw Janas, Josef Pieprzyk, Pawel Morawiecki
Abstract
Large Language Models (LLMs) have created an urgent need for reliable watermarking methods that enable attribution of generated text while remaining robust to editing and paraphrasing. We propose a novel synchronization-free watermarking scheme in which every watermark consists of a single binary congruence generated from a pair of neighbouring tokens. For each token pair, a cryptographic hash determines an evaluation point of a Reed--Solomon polynomial representing the secret identity, while the parity of the polynomial evaluation determines the watermark bit embedded into the second token of the pair. Since each congruence is self-contained and depends only on the local token pair, the proposed construction is naturally resistant to insertions, deletions, and token reordering. We analyse the recovery problem from an algebraic perspective, discuss several decoding algorithms suitable for different identity sizes, and model watermark corruption as a Binary Symmetric Channel. The analysis shows that reliable recovery requires only a small redundancy even for relatively high token corruption rates. Unlike existing block-based watermarking schemes, the proposed method avoids synchronization problems while providing a flexible framework for embedding both short and long secret identities.