We describe a scheme for watermarking natural language text by embedding small portions of the watermark bit string in the
syntactic structure of a number of selected sentences in the text, with both the selection and embedding keyed (via quadratic
residue) to a large prime number. Meaning-preserving transformations of sentences of the text (e.g., translation to another
natural language) cannot damage the watermark. Meaning-modifying transformations have a probability, of damaging the watermark,
proportional to the watermark length over the number of sentences. Having the key is all that is required for reading the
watermark. The approach is best suited for longish meaning-rather than style-oriented ”expository” texts (e.g., reports, directives,
manuals, etc.), of which governments and industry produce in abundance and which need protection more frequently than fiction
or poetry, which are not so tolerant of the small meaning-preserving syntactic changes that the scheme implements.
Portions of this work were supported by Grant EIA-9903545 from the National Science Foundation, and by sponsors of the Center
for Education and Research in Information Assurance and Security.