Uncertainty Detection for Natural Language Watermarking

György Szarvas, Iryna GurevychIJCNLP 2013

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:

  1. 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.
  2. 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.
  3. Closed-Class Paraphrasing: The system uses a curated dictionary of 29 frequent uncertainty cues mapped to safe substitutes.
Table 1: Curated dictionary of uncertainty cues and their corresponding substitutions used for high-precision watermarking.

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.

Table 2: Performance metrics for the closed-class uncertainty detection across three domains, showing high precision and varying capacity.

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

BibTeX
@inproceedings{szarvas2013uncertainty,
  author = {György Szarvas and Iryna Gurevych},
  title = {{Uncertainty Detection for Natural Language Watermarking}},
  booktitle = {IJCNLP},
  year = {2013},
}
Figure