OriginMark: Mitigating Attacks in Distortion Free Watermarks

Distortion-free watermarking has emerged as a promising approach for establishing the provenance of large language model (LLM) outputs by preserving the original next-token distribution when averaged over watermark randomness. However, this guarantee does not directly characterize practical deployments, where a fixed secret key may be reused across many generation requests. We show that conditioning on a fixed key induces persistent, localized token-level distortions that form an observable watermark fingerprint. Exploiting this structure, we develop two black-box attacks requiring only sampled model outputs: a watermark identification attack that detects context-dependent watermarking and estimates its context width through controlled prefix perturbations, and a key-free spoofing attack that transfers inferred watermark-induced token preferences to a proxy language model without access to model logits, watermark keys, or detector feedback. Across seven open-weight models and three distortion-free watermarking schemes, these attacks expose substantial vulnerabilities under fixed-key deployment; we further observe a response pattern in two publicly accessible Gemini models consistent with context-dependent watermarking. To mitigate these vulnerabilities, we formalize randomized distortion-freeness, which requires the distribution averaged over a deployed key pool to exactly recover the original model distribution at every context, and introduce OriginMark, a watermarking scheme that realizes this property using only eight complementary keys. Experiments show that OriginMark reduces identification and spoofing signals to levels comparable to unwatermarked generation while preserving output diversity. At a 1% false-positive rate, OriginMark achieves a 77.3% detection rate at 400 tokens, outperforming the strongest evaluated attack-resistant baseline by 11.3%.