Semantic Watermarking with Order-Robust Detection over Sub-sentence Units
Cryptography and SecurityArtificial IntelligenceComputation and Language
Summary
The authors study how semantic watermarks—hidden markers tied to sentence meaning—can be removed by attackers who slightly change the text without altering its meaning, such as by rewording or rearranging sentences. They introduce a new attack called embedding displacement attack (EDA) that effectively removes these watermarks by exploiting how edits change the underlying sentence embeddings used for detection. To make watermarks more robust, the authors propose k-SwordStamp, a method that detects watermarks using smaller sub-sentence parts to resist restructuring attacks better. Their tests show k-SwordStamp is more resilient to attacks like EDA, especially when the attacker does not have access to secret information. The authors also share their code for further research.
Abdulrahman Diaa, Jonathan Petit, Florian Kerschbaum
Abstract
Semantic watermarks tie the mark to sentence meaning rather than token choices, promising robustness to content-preserving edits. However, the detector only observes attacker-supplied text, which can be reworded, reordered, or resegmented to evade detection without content loss. Rewording, reordering, and resegmentation all cause embedding displacement: detection tests embeddings different from those selected during watermarking and can therefore lose the mark. Our adaptive embedding displacement attack (EDA) admits all three edits under a single objective that maximizes this displacement. It uses a public paraphraser and surrogate encoder without access to the provider's generator or secret key. At a 5% false-positive rate (FPR) and content-preservation threshold $\bar{q}=90\%$, EDA successfully removes the mark on between 32.6% and 47.9% of documents across four schemes, the highest among the tested attacks. Therefore, EDA evaluates the schemes' robustness more thoroughly than passive paraphrasing. To address these vulnerabilities, we design (k)-SwordStamp: semantic watermarks with order-robust detection over sub-sentence units, reducing sensitivity to attacker-chosen structure at a small quality cost. Against k-SwordStamp, the strongest no-box attack we test is an EDA variant adapted to its design, with a 10.8% attack-success rate. A stronger EDA with access to the provider's detector and secret key reaches a 39.7% attack-success rate, compared with 65.5% on k-SemStamp. Our code is available at https://github.com/D-Diaa/SwordStamp.