Abstract
Natural language watermarking often struggles with the trade-off between embedding capacity and linguistic precision. This paper presents a novel approach that targets "uncertainty cues"—words such as might, probably, or suggest—for synonym substitution. By restricting paraphrasing to this specific, closed class of words, the authors achieve near-perfect grammatical and semantic precision, ensuring the hidden watermark remains undetectable to human readers while maintaining a reasonable embedding capacity for long-form documents.
Introduction
Digital text watermarking involves embedding a secret message within a document to authenticate its source or trace its origin. A common technique is synonym substitution, where words are replaced with synonyms to encode binary data. However, natural language is highly context-dependent. "Open-vocabulary" approaches often result in awkward phrasing or shifts in meaning, which are unacceptable in precision-oriented watermarking tasks. This research addresses this by focusing on a highly constrained class of words: uncertainty cues. These words express epistemic modality or hypotheses without altering the core factual propositions of a sentence.
Methods
The proposed pipeline detects and paraphrases uncertainty cues through three main stages:
- Watermark Encoding via Parity: Text is divided into blocks. Words are assigned bit values (0 or 1), and a block's secret bit is determined by the parity of the sum of its words' bits. To flip a bit, the system swaps one word with a synonym of the opposite bit value.
- Uncertainty Detection: A Maximum Entropy (Maxent) classifier identifies uncertainty cues while disambiguating context (e.g., distinguishing "appear" as an uncertainty marker versus a physical event). It utilizes shallow features like lexical n-grams and POS tags for cross-domain robustness.
- Closed-Class Paraphrasing: The system uses a curated dictionary of 29 frequent uncertainty cues mapped to safe substitutes.
Datasets and Evaluation
The authors utilized a multi-domain dataset annotated for uncertainty cues, comprising Wikipedia articles (20,756 sentences), Newswire articles (3,123 sentences), and biological scientific texts (19,473 sentences). Models were evaluated in a cross-domain setting to simulate real-world performance on unfamiliar text styles.
Key Results
The "closed-class" approach demonstrated exceptional precision across all domains. As shown in the results table below, precision reached 89.46% on Wikipedia and nearly 99% on scientific texts. While this focus on precision limits capacity—embedding roughly one bit every 7 to 14 sentences—it ensures the watermark is virtually indistinguishable from the original text.
Conclusion and Future Work
Targeting "extra-propositional" meaning through uncertainty cues allows for watermarking that preserves the original author's intent. The genius of using uncertainty cues is that they modify the likelihood of an event, not the event itself. Changing "The committee may vote" to "The committee might vote" leaves the core proposition entirely untouched.
Future work includes combining this method with syntactic reordering (e.g., changing "John and Mary" to "Mary and John") and expanding the closed-class approach to other word classes, such as opinion expressions, to increase overall bit capacity without sacrificing linguistic quality.
Summary updated