arXiv CS open access

Pin It on Anyone: Certified Targeted Displacement of Multi-Bit LLM Watermarks Without the Key

Paweł Batorski et al. · arxiv_cs

arXiv CS · Papers

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Pin It on Anyone: Certified Targeted Displacement of Multi-Bit LLM Watermarks Without the Key Paweł Batorski1

Przemysław Spurek2,3

1 Heinrich Heine University Düsseldorf

2 Jagiellonian University

Attacker

arXiv:2610.18359v1 [cs.CR] 13 Oct 2026

Abstract

Multi-bit watermarking embeds a message, typically an account identifier, into LLM output so that harmful text can be traced to its origin. We show an attack technique that allows to alter the watermarking message. This allows to, for example, exchange the embedded account ID to an arbitrary different one. The attacker mainly needs access to a few accounts for generating LLM output and model logits, but crucially not the secret key used to watermark. The attacker then rewrites the text, keeping its meaning, so that the watermarking message decoder recovers the watermarking message embedded by the attacker. We are, to our knowledge, the first to propose such an attack, which we call a targeted displacement. Theoretically, we present upper and lower bounds on the probability of our attack succeeding. This bound depends on the number of accounts the attacker has access to, the length of the message and some characteristics of the given text. Our attack can succeed whenever we can bound the ambiguity of the generated text well enough. Empirically, we test our attack technique against five watermarking methods and four LLMs. Attack success tracks our predicted bounds, allowing us to alter watermarking messages in almost all cases with high accuracy, given enough accounts. Our code can be found at https://github.com/Batorskq/PinIt.

Paul Swoboda1

Victim

3 IDEAS Research Institute

I have a few accounts on a watermarked LLM. I want to spread fake news and pin it on any user I choose! Watermarked generation r

r Watermarked

Thanks for the update. Let’s meet on Friday to go over the report.

0 1 1 0 1 0 1 0

Watermarked generation r

0 0 1 1

Displacement attack! Attacker’s paraphraser Rewrite to

Æ 1 1 0 1

1 1 0 1

Decoder

1 1 0 1

Attacker’s accounts

target ID ≈ same

meaning

r Watermarked

The mayor secretly took a bribe to approve the new stadium.

0 1 1 0

Decoder

Compare tokens with message bits 0110 1010 0011

r Watermarked

A bribe was secretly accepted by the mayor to approve the new stadium.

1 1 0 1

Decoder

any target ID

Figure 1: Targeted displacement of a multi-bit watermark. The provider embeds each account’s identifier into generated text, and a decoder recovers it to attribute a text. Text from the attacker’s own accounts is traced back to the attacker. By comparing the tokens its accounts favor with their known message bits, the attacker learns the hidden watermark structure without the key and paraphrases its text, keeping the meaning, so that the decoder outputs any identifier of the attacker’s choice, here that of an innocent user.

of its own and without the secret key, it rewrites a text that carries a source message m, keeping its semantics, so that the decoder reads a chosen target message m′ , such as the identifier of a third user. We call this targeted displacement. Obviously, such a watermarking attack can have serious security and privacy implications, when pinning harmful or sensitive text on an innocent party. Prior attacks remove the watermark (Krishna et al., 2023; Zhang et al., 2024) or spoof its presence (Jovanović et al., 2024; Gu et al., 2024; Pang et al., 2024; Jiang et al., 2025). They hence change whether the text is recognized as watermarked or not. That a multi-bit watermark might be steered

Introduction

Watermarks let a provider recognize text that its language model generated (Kirchenbauer et al., 2023). Multi-bit watermarks also hide a message in the text, typically the identifier of the account that requested it, so that a decoder holding the secret key can attribute a harmful text to its account (Fernandez et al., 2023; Yoo et al., 2024; Qu et al., 2025; Li et al., 2024; Jiang et al., 2025; Xu et al., 2026). We show that an attacker can effectively alter the watermark message (Figure 1). With a few accounts 1

toward a specific user was anticipated (Jovanović et al., 2024; Gloaguen et al., 2025b) and stated as a security goal (Qu et al., 2025), but no known attack, to our knowledge, was able to alter an underlying watermarking message. We develop the first such attack and a theory of what any such attack can achieve. We study attacks on so called distortion-based watermarking methods, which include popular green-list and red-list methods (Kirchenbauer et al., 2023, 2024; Zhao et al., 2024; Lee et al., 2024; Liu et al., 2024b; Lu et al., 2024) and their multi-bit variants (Fernandez et al., 2023; Yoo et al., 2024; Wang et al., 2024; Qu et al., 2025). Such schemes make the generator favor, at each step, a subset of the vocabulary that depends on the message and the secret key. The decoder checks how consistently a text follows the subsets of each candidate message. The attacker cannot compute these subsets without the key, but a few accounts whose messages are known can reveal enough information about the favored subset. When comparing an account’s next-token distribution with the base model, we see which tokens are favored, and comparing accounts with one another shows the tokens the target message m′ would favor. A paraphraser restricted to these tokens then rewrites the text (Figure 2). Not every target message is reachable however: when the accounts are too few or their underlying watermark messages are too similar, several targets look the same to the attacker. For such cases we prove an upper bound on the efficacy of any possible attacker. Additionally, we provide lower bounds for our attacker: For any target message m′ can compute a certificate, without access to the key, for a lower bound on the probability that the decoder will decode m′ . We evaluate the attack on five published watermarking methods using four LLMs (Section 4). Our contributions are the following.

marking methods and four LLMs, confirm the bound, show which schemes fall to one account, to multiple colluding accounts, or resist, and measure the price in fidelity for generating watermarked text with a target message.

Related Work

Multi-bit watermarks. Zero-bit watermarks bias the next-token distribution toward a keyed token set (Chen et al., 2024; Huo et al., 2024; Kirchenbauer et al., 2023, 2024; Lee et al., 2024; Liu et al., 2024b; Liu and Bu, 2024; Lu et al., 2024; Wang et al., 2025; Zhao et al., 2024), sample from it without distortion (Chen et al., 2025b; Christ et al., 2024; Fu et al., 2024; Golowich and Moitra, 2024; He et al., 2025; Hu et al., 2024; Mao et al., 2025; Tsur et al., 2025; Wu et al., 2024; Zhao et al., 2025), or select among drafts (Giboulot and Furon, 2024; Hou et al., 2024). They only detect presence. Multi-bit watermarks, like linguistic steganography (Shen et al., 2020; Ziegler et al., 2019), hide a message, typically a user identifier. CycleShift cyclically shifts one keyed set by the message (Fernandez et al., 2023), MPAC gives each context a message position and a vocabulary coloring (Yoo et al., 2024), RSBH spreads a Reed–Solomon codeword over public segments (Qu et al., 2025), DepthW keys a depth permutation by the whole code (Li et al., 2024), StealthInk reweights a keyed permutation without distortion (Jiang et al., 2025), and XMark suppresses keyed vocabulary quarters within public blocks (Xu et al., 2026). Other schemes edit or paraphrase the text (Lau et al., 2024; Xu et al., 2025; Yang et al., 2022; Yoo et al., 2023), balance, stack, or symmetrize partitions (Feng et al., 2025; Park et al., 2026; Wang et al., 2024; Zhu et al., 2026), correct, verify, or layer the payload (Chen et al., 2026; Kim et al., 2026; Li et al., 2026), personalize it (An et al., 2026c; Yu et al., 2025), or serve diffusion LMs, agents, and code models (Huang and Wan, 2026; Huang et al., 2026b; Yang et al., 2026; Zhang et al., 2025). Attribution has been formalized (Jiang et al., 2026; Song and Shahabi, 2026), and CertMark certifies the decoded message (Batorski et al., 2026). These works protect the message against erasure by edits and paraphrases. We ask which messages an attacker can make the decoder read.

• To our knowledge, we develop the first attack on a multi-bit watermarking method that can inject arbitrary target messages without access to the key. Its three steps depend on the scheme. • We give upper bounds on attack success for any attack method on multi-bit watermarking schemes and a lower bound that certifies the probability of attack success for our method. We exactly characterize in closed form reachable target messages.

Attacks on watermarks. Paraphrasing, editing, translation, and ensembling remove watermarks (Cheng et al., 2025a,b; Diaa et al., 2025; Harel-

• We evaluate the attack on five published water2

with high probability that DK (y) = m. The attacker’s goal is as follows: For a target message m′ ∈ M, the attacker outputs text ŷ = A(y, m′ , OM ) such that (i) the decoder will output m′ as watermarking message and (ii) the rewritten text ŷ is semantically close to the original text y and (iii) OM contains all the information the attacker has at his disposal. First, the attacker has access to a number of accounts with messages

Canada et al., 2025; He et al., 2024; Huang et al., 2025, 2026a; Hwang et al., 2026; Krishna et al., 2023; Pan et al., 2025; Rastogi and Pruthi, 2024; Wu et al., 2026b; Zhang et al., 2024), benchmarks compare schemes (Pan et al., 2024; Tu et al., 2024; Wu et al., 2026a), and queries reveal whether and how a model is watermarked (Gloaguen et al., 2025a; Liu et al., 2025). Closer to us, stealing estimates a zero-bit scheme’s keyed sets from queries (Chen et al., 2025a; Jovanović et al., 2024; Wu and Chandrasekaran, 2024) and distillation copies a watermark into another model (An et al., 2026a; Gu et al., 2024; Sander et al., 2024), so that an attacker can scrub it or spoof it on any text. Robustness alone permits piggyback spoofing (Pang et al., 2024). Defenses harden watermarks against spoofing or detect it (An et al., 2025, 2026b; Gloaguen et al., 2025b; Liu et al., 2024a; Shen et al., 2025; Zhou et al., 2024), and image watermarks can likewise be forged or overwritten (Dong et al., 2025; Müller et al., 2025; Saberi et al., 2024; Senthuran et al., 2026; Souček et al., 2025; Yang et al., 2024). A zero-bit spoof forges one verdict, whereas spoofing a multi-bit watermark could incriminate a specific user (Gloaguen et al., 2025b), and we study this attack. Combining outputs under several keys removes a watermark (Pang et al., 2024; Wu et al., 2026b). Our attacker combines accounts under one key to forge a message, and our symmetry bound limits it as impossibility and trade-off results limit the defender (Pratihar and Mukhopadhyay, 2026; Zhang et al., 2024). The rewrite steers a paraphraser toward a token set, as in lexically constrained and controlled decoding (Dathathri et al., 2020; Hu et al., 2019; Kajiwara, 2019; Liu et al., 2021; Lu et al., 2021; Mudgal et al., 2024; Qin et al., 2022; Yang and Klein, 2021), also used to obfuscate authorship (Fisher et al., 2024).

M = (m(1) , . . . , m(n) ) ∈ Mn ,

n ≥ 1, (1)

so he can generate text for pK,m(1) , . . ., pK,m(n) . Furthermore, the attacker has access to the base model, the tokenizer, the watermarking scheme, and relevant hyperparameters (decoding temperature, etc.) but has no access to the secret key K nor to the decoder for retrieving the watermark message from text. The threat is direct for open-weight models, where every user of a watermarked service can download the base model. For closed models it becomes an insider threat. Distortion Watermarking. We study distortion watermarks, which, for a fixed key, embed the message by changing the model’s next-token distribution (Kirchenbauer et al., 2023). When generating text y, at every position t the method takes the last ℓ tokens (the context length) of y, i.e. c = yt−ℓ:t . Together with the key K, the message m ∈ M, the green list of tokens is computed: Gm K (c) ⊆ V,

(2)

The green list is used as follows: (P1) generation under message m replaces the base distribution p(· | c) by pK,m (·|c) = Φ p(· | c), Gm (c) for a fixed, key-independent rule K Φ, and

Method

(P2) the decoder recomputes the green lists for all messages m ∈ M and chooses the message that maximizes the probability of having generated the watermarked text y, i.e. m ∈ arg max m̃ ∈ MpK,m̃ (y).

We study targeted displacement: rewriting a text that carries a watermark message m so that the decoder instead recovers the target message m′ . We first state the attacker’s objective and describe the watermarks we study.

The rule Φ usually shifts probability toward the green list. Alternatively, some schemes such as XMark suppress the green list set instead. We can also express this by taking Gm K (c) to be the complement of the original green set (Appendix A). For simplicity, for a controlled account i with known (i) message m(i) , we write Gi (c) := Gm K (c).

Let M = {0, 1}L be

Watermarking (Attacks). the message space. Let pK,m be the next-token distribution for encoding watermarked text with message m and secret key K. Typically m will be the account identifier of the person generating text. For text y ∼ pK,m the decoder DK will output 3

´ Attacker’s goal: rewrite the watermarked text 1

Recover the accounts’ sets

, keeping its meaning, so that the decoder reads a chosen m′ = 1 1 0 1

Synthesize the target’s set

² attacker’s accounts

î target m′

0110

1101

1010

query at context c

probability shift vs. base model

without the secret key.

Rewrite and certify

r source y

chosen by the attacker yes

Gi (c)

target unambiguous?

per account

; otherwise bounded: Pr[success] ≤ 1/N (M, m′ )

N (M, m′ ) = 1

≈ same meaning

′ Gm K (c)

rewrite ŷ

Æ paraphraser, ′ next token in Gm K (c)

attacker-side certificate

1101

decoder reads m′

Figure 2: Overview of targeted displacement. The attacker wants to rewrite a text that carries watermark message m, keeping its meaning, so that the decoder attributes it to a chosen message m′ , without the secret key. It controls accounts with known messages and, at every context used by the rewrite, compares an account’s next-token distribution with the base model to recover the account’s green list (step 1). The recovered green lists are turned into the target’s green list. This succeeds exactly when the target’s relative bits are constant within every twin class; otherwise the ambiguity bound of Theorem 1 caps the success probability (step 2). A paraphraser rewrites the source under a token-level constraint toward the target’s set, and the attacker certifies the rewrite from its own posterior without the key (step 3), so that the provider’s decoder reads the target message. Only step 2 depends on the watermark scheme.

Gm K (c) = {v ∈ V : CK (c, v) = mJK (c) }.

πK (c)

color 0

.22

selected bit

green list

Gm K (c) = {a, c, e} Gm K ′ (c) = {a, c, e}

πK (c)

a c e

b d f

JK (c) = 1 m1 = 0

πK ′ (c)

b d f

a c e

JK ′ (c) = 2 m2 = 1

a b c d e f

b d f

green list

JK (c) = 1 (i)

.27

.26

.14

Gi (c) = {a, c, e}

= 0

.18 .05

p: base model

.17 .11 .09

.03 − log Z i

qi : account i

θi

−1.35

ℓi (v) > θi

Gi (c) = {a, c, e}

Figure 4: Recovering an account’s set for MPAC at one context c. Top: the key colors the vocabulary and selects position 1, where account i’s message has bit 0, so generation boosts Gi (c) = {a, c, e}. The attacker sees none of this. Bottom: the attacker queries the account and the base model at c. By the public rule (P1), every token of the hidden set has its probability multiplied by eδ before renormalization, so the log-ratio ℓi (v) = log qi (v) − log p(v) takes only two values, δ − log Zi inside the set and P − log Zi outside it, here with Zi = 1 + (eδ − 1) v∈Gi (c) p(v) = 3.9. The midpoint θi separates them and returns {a, c, e} exactly, without the key. The position JK (c) and the name of the color stay hidden. Appendix A gives the rule for every scheme.

(3)

the attacker does not know K. However, for all the used watermarking methods function Φ is simple and we can obtain Gi (c) analytically. For example, for MPAC Φ increases the probability for all tokens in Gi (c) and reduces them for the complement. Hence Gi (c) = {v ∈ V : p(v|c) < pi (v|c)}. We present a general inversion approach that computes Gi (c) consistent with arbitrary Φ and give analytic inversion formulas for every used watermarking method in Appendix A.

m Gm K (c) = GK ′ (c) = {a, c, e}

Figure 3: Different hidden permutations and selections can induce the same observable green list set.

3.1

a c e

selected bit

still hidden: JK (c), color name

ATTACKER’S VIEW probability shift

color 1

.07

known message m = 0 1

color 1

color 0

ATTACKER’S VIEW (P1): qi ∝ p eδ1{v∈Gi (c)} , δ = 2 ℓi (v) = log qi (v) − log p(v) next-token probabilities at c .42 +0.65 δ − log Zi

The attacker has no access to the key, hence cannot compute the permutation πK (c), nor message position JK or hidden color CK . It observes only the resulting probability shift. Figure 3 shows why Gm K (c) is therefore the relevant object. HIDDEN FROM THE ATTACKER

account i: m(i) = 0 1

HIDDEN FROM THE ATTACKER

Green-List Gm K Construction. The watermarking method uses key K and context c to compute a pseudorandom permutation πK (c) of the vocabulary and splits the permuted tokens into two halves. This assigns every token v a hidden color CK (c, v) ∈ {0, 1}. The key also determines a message position JK (c) ∈ [L]. For message m, the green list is computed as those tokens whose color agrees with the message m at position JK (c), namely

Attack

Recovering Gi (c). Fix any context c. Let p(· | c) be the base model’s next-token distribution, and let pi (· | c) := pK,m(i) (· | c) be the observable distribution of controlled account i. For general rules Φ, the true green list set Gi (c) is unknown, since

Recovering green list of target m′ . The attacker controls n accounts and, at context c, holds their 4

TWIN CLASSES j m(1) m(2) xj

green lists G1 (c), . . . , Gn (c). We detail below how the attacker uses them to compute the target set ′ Gm K (c). Recall that in (3) the key assigns c the position j = JK (c), which the attacker does not know. It knows, however, that Gi (c) is the class (i) of tokens with color mj , and that the two color classes partition V. Two accounts therefore have the same green list at c exactly when their messages have the same bit at the hidden position, Gi (c) = Gi′ (c) ⇐⇒

(i) (i′ ) mj = mj ,

m′ rj

2 1 0 1 1

3 1 1 0 0

4 0 0 0 1

equal xj

same rj

CONTEXT c: THE SETS DIFFER

G1 (c)

a b c d e f

G2 (c)

a b c d e f

Ta = {1, 2}: x = 1, r = 0 ′ ⇒ Gm K (c) = G1 (c) Tb = {3, 4}: x = 0, r = 1 ′ ⇒ Gm K (c) = V \ G1 (c) hidden: j = JK (c) ∈ Ta (2)

(1)

G2 (c) ̸= G1 (c) ⇔ mj ̸= mj ⇒ x = 1, so T (c) = Ta and rTa = 0 Gm K (c) = G1 (c) = {a, c, e} ′

CONTEXT c′ : THE SETS AGREE

G1 (c′ )

a b c d e f

G2 (c )

a b c d e f

′

(4)

hidden: j ′ = JK (c′ ) ∈ Tb (2)

(1)

G2 (c′ ) = G1 (c′ ) ⇔ mj ′ = mj ′

⇒ x = 0, so T (c′ ) = Tb and rTb = 1 ′ ′ Gm K (c ) = V \ G1 (c ) = {b, c, e} ′

and complementary sets otherwise. To relate these comparisons to positions, we take account 1 as the reference and define, for every message position j ∈ [L], its account signature xj = (xj,2 , . . . , xj,n ) ∈ {0, 1}n−1 , (i) (1) xj,i = mj + mj mod 2,

Ta 1 0 1 1 0

Figure 5: Building the set of the target m′ from twin classes. Top: two accounts with known messages, m(1) as the reference, and the signature xj that marks where m(2) differs from it. Positions with equal xj are twins, here Ta = {1, 2} and Tb = {3, 4}. The target m′ differs from the reference by rj , which is constant on each class, so every class fixes one choice between G1 (c) and its complement (6). Middle: at a context c the two accounts’ green lists differ, which by (4) means that their messages differ at the hidden position j = JK (c), so j ∈ Ta and the attacker boosts G1 (c). Bottom: at a context c′ the sets agree, so j ′ ∈ Tb and the attacker boosts the complement of G1 (c′ ). Neither step needs the position or the names of the colors. Bit 0 is green, bit 1 is orange, and the set to boost is blue.

(5)

so xj,i = 0 if account i has the same bit as the reference at position j, and xj,i = 1 if it has the opposite bit. The attacker computes every xj from the known messages, and by (4) the sets reveal the signature of the hidden position, xJK (c),i = 1{Gi (c) ̸= G1 (c)}. Positions j and j ′ are twins if xj = xj ′ . We write T for the resulting partition of [L] into twin classes and T (c) for the class of JK (c). Matching the observed signature against the known ones identifies T (c), but no comparison of sets can separate twins (Figure 5). (1) Let rj = (m′j + mj ) mod 2 be the target’s ′ bit relative to the reference. Since Gm K (c) is the class of tokens with color m′JK (c) , it equals G1 (c) if rJK (c) = 0 and V \ G1 (c) otherwise. If r is constant on every twin class, with value rT on class T , the attacker can make this choice from T (c) alone: ( G1 (c), rT (c) = 0, m′ GK (c) = (6) V \ G1 (c), rT (c) = 1.

for the paraphraser’s next-token distribution. The prompt never mentions the watermark, which enters only through the decoding rule below. At the watermark context z<t we have the green-list (m′ ) GK (z<t ). We use the hard bias sampler ( (m′ ) pt (v), v ∈ GK (z<t ) rt (v) ∝ . (7) 0, otherwise (m′ )

We apply (7) when Zt ≥ τ and GK (z<t ) contains an available token. Otherwise we retain the full vocabulary and use a soft bias sampler. Choose a δatk > 0 and let (m′ ) rt (v) ∝ pt (v) exp δatk 1{v ∈ GK (z<t } . (8)

The attacker never needs the hidden position or the name of either color. This covers 2|T | targets, one per choice of the values rT (all 2L when every position has a distinct signature). It remains to use these sets to steer the rewrite.

Thus τ = 0 forces a target-compatible token whenever possible, while larger τ leaves low-mass contexts closer to the paraphraser. The decoder relies on distinct context-token pairs for its efficacy. Since context-token pairs can repeat too often (recall that context-token pairs can reappear due to fixed context length ℓ), and constrained decoding tends to loop, we block repeated 4-grams (Paulus et al., 2018). Algorithm 1 in Appendix B lists the complete attack for binary MPAC.

Redirecting the decoded message to m′ . Let y be the source text. We will use a paraphraser model ppara , a chat model that is asked to rewrite y faithfully (Appendix D). Let z be the rewritten text and z<t the rewrite prefix at position t. We write pt (v) := ppara (v | y, z<t ) 5

THE REWRITE z AS THE SEQUENCE OF PAIRS (ct , zt ), ONE VOTE EACH t 9 3 5 6 7 8 1 2 4 c1 c2 c4 c1 c3 c5 c6 c2 c1 context ct token zt σ(ct , zt )

THE PAIRS GROUPED BY CONTEXT class T (c) Ta = {1, 2} c1 c2 c3 context c ′ Gm K (c)

{a,c,e}

σ(c, v)

a c e

Σv σ(c, v)

σ(c, v) = +1

{b,d,f}

b d a +1

Tb = {3, 4} c4 c5 c6

{a,c,e}

{b,c,e}

c b d

−1

σ(c, v) = −1

{a,d,f}

b c e

a d

(as above)

{a,d,f}

a d f

c1 occurs three times, at t = 1, 4, 9, with tokens a, c, e 15 16 17 14

−1

POSTERIOR DRAWS

σ(ct , z′t ) = +1 iff zt ∈ Gm K (ct ), else −1

CERTIFICATE

known: JK (c1 ) ∈ {1, 2}, hidden: 1 or 2 so ΠO draws J(c) ∼ Unif T (c), independently over c

margin Mj (J) = Σc: J(c)=j Σv σ(c, v) Mj (J) drawn J(c) E c1 c2 c3 c4 c5 c6 1 2 3 4 draw 1 1 2 1 3 4 4 +2 +1 +3 +5 ✓ draw 2 1 2 2 3 4 4 +3 0 +3 +5 × draw 3 1 1 1 3 4 4 +3 0 +3 +5 × draw 2: M2 (J) = 1 − 1 = 0, since c2 and c3 cancel draw 3: M2 (J) = 0, since no pair lands on j = 2

Cert(z, m′ | O) = PrJ∼ΠO [E] = 3/16 ≤ Pr[DK (z) = m′ | O] E: Mj (J) > 0 at every j

3/16: by hand in this example, Monte Carlo over J in practice

Figure 6: The certified attack on a rewrite z, for L = 4 with twin classes Ta = {1, 2} and Tb = {3, 4}. Top: z read as the sequence of pairs (ct , zt ), one vote each, with σ(ct , zt ) = +1 when zt lies in the recovered target green list ′ Gm K (ct ) and −1 otherwise. The context c1 occurs three times, at t = 1, 4, 9. Bottom left: the pairs grouped by context with the vote sum of each context. Bottom middle: the attacker knows JK (c1 ) ∈ {1, 2} but not whether it is 1 or 2, so ΠO draws the position of every context uniformly from its class, independently across contexts. Each draw gives the margins Mj (J), and E holds when every margin is positive. E fails when c3 cancels c2 (draw 2) or when no pair lands on position 2 (draw 3). Bottom right: the share of draws with E is the certificate, a lower bound on the probability that the decoder reads z as m′ . In this small example Pr[E] is computed by hand, 2/8 for Ta (positions of c1 and c2 differ and c3 joins c1 ) times 6/8 for Tb (not all three contexts on one position), whereas the experiments estimate it by Monte Carlo over draws of J.

3.2

Certification

The proof, including adaptive observations, attack randomness, and decoder ties, is given in Appendices K and L.

Upper bound on attack success. The comparisons in Section 3.1 reveal the twin class T (c) of the hidden position JK (c), but cannot distinguish the positions inside that class. Recall that (1) rj = (m′j + mj ) mod 2 records whether the target differs from the reference account at position j. For each twin class T , define X aT := rj . (9)

Remark 1. In Appendix K we present an elegant group-theoretic characterization of the twin sets and relate the group’s orbit to the ambiguity multiplicity. Attacker-side lower bound. Theorem 1 limits the success of any attack. Next, we will compute certificates that evaluate how good our attach has inserted the target watermark message m′ into the rewrite z. The decoder scores the distinct context– token pairs P(z) := {(zt−ℓ:t , zt ) : 1 ≤ t ≤ |z|}. Each context-token pair induces a hidden position JK (zt−ℓ:t ). For every (c, v) ∈ P(z), the attacker computes the twin class T (c) of JK (c), with T (c) := [L] if no class matched. Then we collect votes for estimating whether the next token v is in the target message green list or not.

j∈T

Thus aT is the number of positions in T at which the target differs from the reference. The attacker knows this number, but the observations do not identify which aT of the |T | hidden positions carry | those differences. There are |T aT possible placements. The choices combine across twin classes, giving the ambiguity multiplicity Y |T | ′ N (M, m ) := . (10) aT T ∈T

( +1, σ(c, v) := −1,

(m′ )

recovery shows v ∈ GK (c), otherwise. (12) Recall that the exact position of JK (c) inside T (c) stays hidden. We therefore define ΠO as the distribution that draws an assignment J uniform on T (c), independently across distinct contexts. We next define a margin Mj (J) that counts how often we have sampled from the green list as follows:

This count uses only the known account messages and the chosen target; it does not require the secret key. Theorem 1 (Targeting bound). Under the symmetry assumptions of Appendix K, every attack A against the distortion watermarking satisfies, for every target m′ , !−1 Y |T | Pr DK (A(O)) = m′ | O ≤ . aT T ∈T (11)

Mj (J) := 6

(c,v)∈P(z): J(c)=j σ(c, v).

(13)

L=8 L = 16 L = 32

exact match (%) exact match (%) exact match (%)

τ = 0, 4-gram block

MPAC 100 75 50 25 0 100 75 50 25 0 100 75 50 25 0

τ = 10

−3

upper-bound certificate (Thm. 1), shaded: ruled out

RSBH

lower-bound certificate (Thm. 2)

StealthInk

64 128

source, no rewrite

XMark

CycleShift

colluding accounts n

16 32

Figure 7: Exact-match success against the number of colluding accounts for five schemes and message lengths L ∈ {8, 16, 32} at 200 tokens per text, mean over the four generators Llama-2-7B, Llama-3.1-8B, Qwen3.5-4B, and Qwen3.5-9B (per-generator panels in Appendix G, 64-bit messages and other text lengths in Appendix H). Dashed: the upper-bound certificate, the mean scheme-specific symmetry bound over the drawn targets (shaded: ruled out), and the lower-bound certificate, the mean of (15) over the τ = 0 rewrites. Circles: the τ = 0 rule, band: its range over the generators. Diamonds: τ = 10−3 . Dotted: the decoder’s exact-match rate on the untouched source. CycleShift falls to a single account, so its panels show a random target from one account at n = 1, extended flat because any larger coalition can use one account, with the chunked variant of Appendix C at 32 bits. Its lower-bound certificate is zero for Llama-2-7B at 16 bits, whose vocabulary is smaller than the 216 shifts, so one account reveals only part of the keyed set.

Finally, E contains all realization of J for which we have a positive margin for every message position: E := J : Mj (J) > 0 for every j ∈ [L] . (14)

of C4 (Raffel et al., 2020), written by four generators, Llama-2-7B (Touvron et al., 2023), Llama3.1-8B (Grattafiori et al., 2024), Qwen3.5-4B, and Qwen3.5-9B (Qwen Team, 2026). The attacker uses the same model as chat model for rewriting. We measure attack efficacy by the exact-match rate, the fraction of rewrites whose decoded message equals the target, and by bit accuracy. We compare both metrics with the symmetry upper bound of Theorem 1 in the binary position–color case, with its scheme-specific counterpart otherwise, and with the attacker’s certificate (15). Appendix C gives the corpora, decoding settings, attack conditions, the formal definitions of every metric, and the implementation details.

Theorem 2 (Certificate validity). Under the posterior ΠO and any decoder DK Cert(z, m′ | O) := Pr [E] J∼ΠO

≤ Pr[DK (z) = m′ | O], (m′ )

with equality if GK

(15)

was recovered exactly.

The proof is given in Appendix M. We estimate the certificate by Monte Carlo over draws of J (Algorithm 2 in Appendix B), and it is zero when N (M, m′ ) > 1. Under the τ = 0 rule every σ is +1, so Mj (J) counts the pairs at j and E only asks that every position be covered. The fallback and soft rules also need positive margins. Theorem 3 (Appendix N) adds an analytic bound in terms of the true vote counts.

Steering MPAC across generators. Table 1 steers MPAC on all four generators, from the attacker’s own account and from enough colluding accounts to separate every message position. Both reach the target in almost every text, for 8- and 16-bit messages alike, while a paraphrase without watermark knowledge stays at chance. The rewrites keep the source’s topic and part of its wording but drift from its content. Targets that the theory declares unreachable are never decoded exactly (Figure 7). Appendix F reports the same table for the other four schemes (Table 4).

Experiments

Setup. We attack five published multi-bit schemes: MPAC (Yoo et al., 2024), RSBH (Qu et al., 2025), StealthInk (Jiang et al., 2025), XMark (Xu et al., 2026), and CycleShift (Fernandez et al., 2023). The watermarked texts are completions of prompts from the RealNewsLike subset 7

decoding accuracy (%) ↑ clean no attack own acc. → m̄ L

8 16 8 Llama-3.1-8B 16 8 Qwen3.5-4B 16 8 Qwen3.5-9B 16

96.5 93.5 98.0 94.8 99.0 93.6 98.4 95.8

50.2 49.2 49.2 49.4 48.0 50.2 52.5 50.0

100.0 100.0 100.0 100.0 100.0 99.7 100.0 99.8

100 100 100 100 100 96 100 97

Generator Llama-2-7B

fidelity to the source ↑

n accounts

BERTScore

BA EM

para. attack para. attack para.

100.0 99.9 100.0 99.9 100.0 99.6 100.0 99.9

100 99 100 99 100 96 100 98

0.89 0.90 0.90 0.90 0.90 0.90 0.91 0.91

0.84 0.84 0.86 0.87 0.86 0.86 0.86 0.86

ROUGE-L

0.48 0.48 0.39 0.40 0.43 0.42 0.46 0.45

0.32 0.32 0.28 0.29 0.30 0.29 0.29 0.29

LLM judge (1–5)

3.4 3.4 3.6 3.5 3.2 3.1 3.5 3.3

attack 2.7 2.9 3.1 3.2 2.5 2.3 2.7 2.5

Table 1: Steering binary MPAC on four generators. BA: bit accuracy of the decoded message to the attacker’s target, EM: exact-match rate, both in percent. Every cell averages the 100 watermarked texts of one generator and message length, each rewritten once per condition (800 sources and 2,400 rewrites in all). ↑: higher is better. Clean: BA of the watermarked source to its own message. No attack: the same paraphraser, with the same 4-gram block but no watermark knowledge, scored against a random target, i.e., chance. Own account: the attacker uses only its own account and targets the complement of its own message m̄. n accounts: n = 8 (L = 8) or n = 12 (L = 16) colluding accounts and a uniformly random target. Fidelity to the source, for the paraphrase without the attack (para.) and for the n-account rewrite (attack): BERTScore F1 and ROUGE-L F1 against the watermarked source, and the mean score of two LLM judges on a 1 to 5 scale (Appendix C).

Collusion across schemes. Figure 7 sweeps the number of colluding accounts for every scheme at 8, 16, and 32 bits. Success tracks the symmetry upper bound and meets it once the accounts make the target structurally reachable, so each scheme’s residual ambiguity decides how many accounts it withstands: CycleShift falls to a single account, MPAC and StealthInk once the accounts separate every message position or show every symbol value, XMark once every symbol value has appeared at every block, and RSBH only to coalitions large enough to cover its codeword symbols. Message length changes none of this up

to 16 bits. At 32 bits the bound still reaches one, but 200 tokens spread too few votes over each position for a reliable majority, so success falls short of the bound until the text grows (Appendix H), and 64-bit messages exceed what 200 tokens carry for every scheme. Across schemes, a paraphrase without watermark knowledge stays at chance. Empirical check of the certificate. Table 2 compares the certificate of every rewrite with whether the decoder read the target, under the forced rule and under the rule that leaves low-mass contexts to the paraphraser. A certificate of one is never wrong, a certificate of zero almost never sees the target decoded, and in between the certificate stays below the realized success for MPAC, RSBH, and StealthInk and matches it for XMark, so the attacker can treat it as the lower bound it claims to be and release only the rewrites it vouches for. The few conditions in which the mean certificate exceeds the realized success by more than its sampling error concentrate on XMark and RSBH, whose public positions leave the posterior only the unrevealed colors to draw.

certificate =1 Scheme

∈ (0, 1)

succ. ↑ cert. succ. succ. flagged ↓

rule τ = 0 MPAC RSBH StealthInk XMark

100 100 100 100

70 8 60 40

77 14 93 39

4 1 5 0

0/104 6/92 0/108 13/108

rule τ = 10−3 MPAC RSBH StealthInk XMark

100 100 100 100

63 12 43 35

68 19 69 33

2 3 2 0

0/129 3/92 2/108 13/108

Table 2: Certificate against realized success over all rewrites at 200 tokens under the τ = 0 and τ = 10−3 rules (9,200 to 12,900 rewrites per scheme and rule), grouped by certificate value: the success rate where the certificate is one, the mean certificate and the success rate where it lies strictly between zero and one, and the success rate where it is zero, in percent. Flagged: conditions (corpus and account setting) whose mean certificate exceeds the realized success by more than two standard errors. ↑ (↓): higher (lower) is better.

Conclusion

Targeted displacement is, to our knowledge, the first attack that steers a multi-bit LLM watermark to a chosen message without the key. On five published schemes its success meets the predicted upper bound once enough accounts collude. We argue that our attack can be successfully executed for insiders on closed source LLMs, with potential security implications, including identity theft. 8

Limitations

a provider which targets no attacker can reach. All experiments use public prompts, open-weight models, and accounts that we simulate locally, and no deployed service or real user was involved. We also acknowledge that appropriate safeguards and further evaluation are necessary to mitigate risks in real world applications.

The limitations of our paper are the assumptions of its threat model. Our attacker knows the watermarking scheme and its public hyperparameters but not the secret key. It has the unwatermarked base model and its tokenizer. It controls accounts whose embedded identifiers it knows, all watermarked under the provider’s single key, and it reads the next-token distributions of these accounts at the contexts of its rewrite. These assumptions are, however, standard in the watermarking literature. That the attacker knows everything except the key is Kerckhoffs’ principle, which the watermark stealing threat model adopts explicitly (Jovanović et al., 2024). Access to the unwatermarked distribution of the model is the available base responses setting of the same threat model and of its successors (Jovanović et al., 2024; Chen et al., 2025a), and it is the attacker against which stealthiness is argued (Jiang et al., 2025). Accounts with known identifiers are the spoofing adversary against which RSBH is argued secure (Qu et al., 2025), and a single provider key with the identifier as the message is how every scheme we study embeds it (Fernandez et al., 2023; Yoo et al., 2024; Qu et al., 2025; Jiang et al., 2025; Xu et al., 2026). Next-token log-probabilities are returned by public APIs and assumed by prior attacks (Pang et al., 2024; Chen et al., 2025a). Our attacker reads the full distribution, which idealizes the top-k entries that APIs return. A provider that hides account identifiers, keys the labeling per account, or withholds logprobabilities removes what the attacker reads, and we do not measure the query cost of sample access, under which the symmetry bound still holds.

References Hyeseon An, Shinwoo Park, Suyeon Woo, and Yo-Sub Han. 2026a. DITTO: A spoofing attack framework on watermarked LLMs via knowledge distillation. In Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), pages 4922–4936, Rabat, Morocco. Association for Computational Linguistics. Li An, Yujian Liu, Yepeng Liu, Yuheng Bu, Yang Zhang, and Shiyu Chang. 2026b. A reinforcement learning framework for robust and secure LLM watermarking. In Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), pages 7181–7198, Rabat, Morocco. Association for Computational Linguistics. Li An, Yujian Liu, Yepeng Liu, Yang Zhang, Yuheng Bu, and Shiyu Chang. 2025. Defending LLM watermarking against spoofing attacks with contrastive representation learning. In Second Conference on Language Modeling. Wenbo An, Lianwei Wu, and Zehao Wang. 2026c. IPMark: A sentence-level watermark for LLMs with hierarchical personalization and efficient detection. In Proceedings of the 43rd International Conference on Machine Learning. Paweł Batorski, Przemysław Spurek, and Paul Swoboda. 2026. CertMark: Distortion-free multi-bit watermarking with certified decoding. arXiv preprint arXiv:2609.33332.

Ethics Statement

Liang Chen, Yatao Bian, Yang Deng, Deng Cai, Shuaiyi Li, Peilin Zhao, and Kam-Fai Wong. 2024. WatME: Towards lossless watermarking through lexical redundancy. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 9166–9180, Bangkok, Thailand. Association for Computational Linguistics.

This work was conducted in accordance with the ACL Code of Ethics and the ACM Code of Ethics and Professional Conduct, and we have adhered to the rules throughout this research. We recognize that the attack we describe could be misused to make a watermark decoder attribute a harmful text to a user who did not write it, and that decoded identifiers may feed moderation or legal decisions. Our intention is to show providers and scheme designers that attribution by a multi-bit watermark can be displaced without the key, so that a decoded identifier is not treated as conclusive evidence on its own and so that future schemes are designed against this threat. The symmetry bound also tells

Ruibo Chen, Yihan Wu, Junfeng Guo, and Heng Huang. 2025a. De-mark: Watermark removal in large language models. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 9316–9333. PMLR. Ruibo Chen, Yihan Wu, Junfeng Guo, and Heng Huang. 2025b. Improved unbiased watermark for large language models. In Proceedings of the 63rd Annual

Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. 2023. Three bricks to consolidate watermarks for large language models. In 2023 IEEE International Workshop on Information Forensics and Security (WIFS), pages 1–6. IEEE.

Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 20587– 20601, Vienna, Austria. Association for Computational Linguistics. Xuyang Chen, Xiang Li, Yangxinyu Xie, and Qi Long. 2026. Selective disclosure watermarking for large language models. In Proceedings of the 43rd International Conference on Machine Learning.

Jillian Fisher, Ximing Lu, Jaehun Jung, Liwei Jiang, Zaid Harchaoui, and Yejin Choi. 2024. JAMDEC: Unsupervised authorship obfuscation using constrained decoding over small language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 1552–1581, Mexico City, Mexico. Association for Computational Linguistics.

Yixin Cheng, Hongcheng Guo, Yangming Li, and Leonid Sigal. 2025a. Revealing weaknesses in text watermarking through self-information rewrite attacks. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 9982–10009. PMLR.

Jiayi Fu, Xuandong Zhao, Ruihan Yang, Yuansen Zhang, Jiangjie Chen, and Yanghua Xiao. 2024. GumbelSoft: Diversified language model watermarking via the GumbelMax-trick. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5791– 5808, Bangkok, Thailand. Association for Computational Linguistics.

Yize Cheng, Vinu Sankar Sadasivan, Mehrdad Saberi, Shoumik Saha, and Soheil Feizi. 2025b. Adversarial paraphrasing: A universal attack for humanizing AIgenerated text. In Advances in Neural Information Processing Systems, volume 38. Miranda Christ, Sam Gunn, and Or Zamir. 2024. Undetectable watermarks for language models. In The Thirty Seventh Annual Conference on Learning Theory, pages 1125–1139. PMLR.

Eva Giboulot and Teddy Furon. 2024. WaterMax: Breaking the LLM watermark detectabilityrobustness-quality trade-off. In Advances in Neural Information Processing Systems, volume 37.

Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu. 2020. Plug and play language models: A simple approach to controlled text generation. In International Conference on Learning Representations.

Thibaud Gloaguen, Nikola Jovanović, Robin Staab, and Martin Vechev. 2025a. Black-box detection of language model watermarks. In The Thirteenth International Conference on Learning Representations. Thibaud Gloaguen, Nikola Jovanović, Robin Staab, and Martin Vechev. 2025b. Discovering spoofing attempts on language model watermarks. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 19562–19584. PMLR.

Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.

Noah Golowich and Ankur Moitra. 2024. Edit distance robust watermarks via indexing pseudorandom codes. In Advances in Neural Information Processing Systems, volume 37.

Abdulrahman Diaa, Toluwani Aremu, and Nils Lukas. 2025. Optimizing adaptive attacks against watermarks for language models. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 13546–13569. PMLR.

Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad AlDahle, et al. 2024. The Llama 3 herd of models. arXiv preprint arXiv:2407.21783.

Ziping Dong, Chao Shuai, Zhongjie Ba, Peng Cheng, Zhan Qin, Qinglong Wang, and Kui Ren. 2025. WMCopier: Forging invisible watermarks on arbitrary images. In Advances in Neural Information Processing Systems, volume 38.

Chenchen Gu, Xiang Lisa Li, Percy Liang, and Tatsunori Hashimoto. 2024. On the learnability of watermarks for language models. In The Twelfth International Conference on Learning Representations. Fabrice Y Harel-Canada, Boran Erol, Connor Choi, Jason Liu, Gary Jiarui Song, Nanyun Peng, and Amit Sahai. 2025. Sandcastles in the storm: Revisiting the (im)possibility of strong watermarking. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 29698–29735, Vienna, Austria. Association for Computational Linguistics.

Xiaoyan Feng, He Zhang, Yanjun Zhang, Leo Yu Zhang, and Shirui Pan. 2025. BiMark: Unbiased multilayer watermarking for large language models. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 17049–17067. PMLR.

Haiyun He, Yepeng Liu, Ziqiao Wang, Yongyi Mao, and Yuheng Bu. 2025. Theoretically grounded framework for LLM watermarking: A distribution-adaptive approach. In Advances in Neural Information Processing Systems, volume 38.

Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 9113–9126, Albuquerque, New Mexico. Association for Computational Linguistics. Baizhou Huang and Xiaojun Wan. 2026. From TDMA to CDMA: A multi-bit watermark for diffusion language models. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 37440– 37454, San Diego, California, United States. Association for Computational Linguistics.

Pengcheng He, Jianfeng Gao, and Weizhu Chen. 2023. DeBERTaV3: Improving DeBERTa using ELECTRA-style pre-training with gradientdisentangled embedding sharing. In The Eleventh International Conference on Learning Representations. Zhiwei He, Binglin Zhou, Hongkun Hao, Aiwei Liu, Xing Wang, Zhaopeng Tu, Zhuosheng Zhang, and Rui Wang. 2024. Can watermarks survive translation? on the cross-lingual consistency of text watermark for large language models. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 4115–4129, Bangkok, Thailand. Association for Computational Linguistics.

Hanbo Huang, Yiran Zhang, Hao Zheng, Xuan Gong, Yihan Li, Lin Liu, Zhuotao Liu, and Shiyu Liang. 2026a. RLCracker: Evaluating the worst-case vulnerability of LLM watermarks with adaptive RL attacks. In Proceedings of the 43rd International Conference on Machine Learning. Kaibo Huang, Jin Tan, Yukun Wei, Wanling Li, Zipei Zhang, Hui Tian, Zhongliang Yang, and Linna Zhou. 2026b. AgentMark: Utility-preserving behavioral watermarking for agents. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 12581– 12603, San Diego, California, United States. Association for Computational Linguistics.

Wassily Hoeffding. 1963. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020. The curious case of neural text degeneration. In International Conference on Learning Representations.

Mingjia Huo, Sai Ashish Somayajula, Youwei Liang, Ruisi Zhang, Farinaz Koushanfar, and Pengtao Xie. 2024. Token-specific watermarking with enhanced detectability and semantic coherence for large language models. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 20746–20767. PMLR.

Abe Hou, Jingyu Zhang, Tianxing He, Yichen Wang, Yung-Sung Chuang, Hongwei Wang, Lingfeng Shen, Benjamin Van Durme, Daniel Khashabi, and Yulia Tsvetkov. 2024. SemStamp: A semantic watermark with paraphrastic robustness for text generation. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 4067–4082, Mexico City, Mexico. Association for Computational Linguistics.

Jeongyeon Hwang, Sangdon Park, and Jungseul Ok. 2026. LLM watermark evasion via bias inversion. In Proceedings of the 43rd International Conference on Machine Learning.

J. Edward Hu, Huda Khayrallah, Ryan Culkin, Patrick Xia, Tongfei Chen, Matt Post, and Benjamin Van Durme. 2019. Improved lexically constrained decoding for translation and monolingual rewriting. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 839–850, Minneapolis, Minnesota. Association for Computational Linguistics.

Ya Jiang, Chuxiong Wu, Massieh Kordi Boroujeny, Brian Mark, and Kai Zeng. 2025. StealthInk: A multi-bit and stealthy watermark for large language models. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 27685–27709. PMLR. Zhengyuan Jiang, Moyang Guo, Yuepeng Hu, Yupu Wang, and Neil Zhenqiang Gong. 2026. Watermarkbased attribution of AI-generated content. In The Fourteenth International Conference on Learning Representations.

Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. 2024. Unbiased watermark for large language models. In The Twelfth International Conference on Learning Representations.

Nikola Jovanović, Robin Staab, and Martin Vechev. 2024. Watermark stealing in large language models. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 22570–22593. PMLR.

Baizhou Huang, Xiao Pu, and Xiaojun Wan. 2025. b4 : A black-box scrubbing attack on LLM watermarks. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for

Tomoyuki Kajiwara. 2019. Negative lexically constrained decoding for paraphrase generation. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 6047– 6052, Florence, Italy. Association for Computational Linguistics.

Liying Li, Yihan Bai, and Minhao Cheng. 2024. Where am I from? identifying origin of LLM-generated content. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 12218–12229, Miami, Florida, USA. Association for Computational Linguistics.

Joeun Kim, HoEun Kim, Dongsup Jin, and Young-Sik Kim. 2026. Block-wise codeword embedding for reliable multi-bit text watermarking. In Proceedings of the 43rd International Conference on Machine Learning.

Chin-Yew Lin. 2004. ROUGE: A package for automatic evaluation of summaries. In Text Summarization Branches Out, pages 74–81, Barcelona, Spain. Association for Computational Linguistics.

John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. 2023. A watermark for large language models. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17061–17084. PMLR.

Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang, WeiMing Chen, Wei-Chen Wang, Guangxuan Xiao, Xingyu Dang, Chuang Gan, and Song Han. 2024. AWQ: Activation-aware weight quantization for ondevice LLM compression and acceleration. In Proceedings of Machine Learning and Systems, volume 6.

John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. 2024. On the reliability of watermarks for large language models. In The Twelfth International Conference on Learning Representations.

Aiwei Liu, Sheng Guan, Yiming Liu, Leyi Pan, Yifei Zhang, Liancheng Fang, Lijie Wen, Philip S. Yu, and Xuming Hu. 2025. Can watermarked LLMs be identified by users via crafted prompts? In The Thirteenth International Conference on Learning Representations.

Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit Iyyer. 2023. Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense. In Advances in Neural Information Processing Systems, volume 36.

Aiwei Liu, Leyi Pan, Xuming Hu, Shuang Li, Lijie Wen, Irwin King, and Philip S. Yu. 2024a. An unforgeable publicly verifiable watermark for large language models. In The Twelfth International Conference on Learning Representations.

Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with PagedAttention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 611–626.

Aiwei Liu, Leyi Pan, Xuming Hu, Shiao Meng, and Lijie Wen. 2024b. A semantic invariant robust watermark for large language models. In The Twelfth International Conference on Learning Representations. Alisa Liu, Maarten Sap, Ximing Lu, Swabha Swayamdipta, Chandra Bhagavatula, Noah A. Smith, and Yejin Choi. 2021. DExperts: Decoding-time controlled text generation with experts and anti-experts. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 6691–6706, Online. Association for Computational Linguistics.

Gregory Kang Ruey Lau, Xinyuan Niu, Hieu Dao, Jiangwei Chen, Chuan-Sheng Foo, and Bryan Kian Hsiang Low. 2024. Waterfall: Scalable framework for robust text watermarking and provenance for LLMs. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 20432–20466, Miami, Florida, USA. Association for Computational Linguistics. Taehyun Lee, Seokhee Hong, Jaewoo Ahn, Ilgee Hong, Hwaran Lee, Sangdoo Yun, Jamin Shin, and Gunhee Kim. 2024. Who wrote this code? watermarking for code generation. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 4890–4911, Bangkok, Thailand. Association for Computational Linguistics.

Yepeng Liu and Yuheng Bu. 2024. Adaptive text watermark for large language models. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 30718–30737. PMLR. Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. 2021. NeuroLogic decoding: (un)supervised neural text generation with predicate logic constraints. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4288–4299, Online. Association for Computational Linguistics.

He Li, Xiaojun Chen, Jingcheng He, Zhendong Zhao, Shuguang Yuan, Xin Zhao, and Yunfei Yang. 2026. ARGH-Mark: Anchor-synchronized watermarking with Hamming correction for robust and qualitypreserving LLM attribution. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 37583–37590.

Yijian Lu, Aiwei Liu, Dianzhi Yu, Jingjing Li, and Irwin King. 2024. An entropy-based text watermarking detection method. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 11724– 11735, Bangkok, Thailand. Association for Computational Linguistics.

Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, and 2 others. 2019. PyTorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, volume 32.

Minjia Mao, Dongjun Wei, Zeyu Chen, Xiao Fang, and Michael Chau. 2025. Watermarking large language models: An unbiased and low-risk method. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 7939–7960, Vienna, Austria. Association for Computational Linguistics.

Romain Paulus, Caiming Xiong, and Richard Socher. 2018. A deep reinforced model for abstractive summarization. In International Conference on Learning Representations. Kuheli Pratihar and Debdeep Mukhopadhyay. 2026. Catch-22: On the fundamental tradeoff between detectability and robustness in LLM watermarking. In Proceedings of the 43rd International Conference on Machine Learning.

Sidharth Mudgal, Jong Lee, Harish Ganapathy, Yaguang Li, Tao Wang, Yanping Huang, Zhifeng Chen, HengTze Cheng, Michael Collins, Trevor Strohman, Jilin Chen, Alex Beutel, and Ahmad Beirami. 2024. Controlled decoding from language models. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 36486–36503. PMLR.

Lianhui Qin, Sean Welleck, Daniel Khashabi, and Yejin Choi. 2022. COLD decoding: Energy-based constrained text generation with Langevin dynamics. In Advances in Neural Information Processing Systems, volume 35, pages 9538–9551.

Andreas Müller, Denis Lukovnikov, Jonas Thietke, Asja Fischer, and Erwin Quiring. 2025. Black-box forgery attacks on semantic watermarks for diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 20937–20946.

Wenjie Qu, Wengrui Zheng, Tianyang Tao, Dong Yin, Yanze Jiang, Zhihua Tian, Wei Zou, Jinyuan Jia, and Jiaheng Zhang. 2025. Provably robust multi-bit watermarking for AI-generated text. In 34th USENIX Security Symposium, pages 201–220. USENIX Association.

Leyi Pan, Aiwei Liu, Zhiwei He, Zitian Gao, Xuandong Zhao, Yijian Lu, Binglin Zhou, Shuliang Liu, Xuming Hu, Lijie Wen, Irwin King, and Philip S. Yu. 2024. MarkLLM: An open-source toolkit for LLM watermarking. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 61–71, Miami, Florida, USA. Association for Computational Linguistics.

Qwen Team. 2024. Qwen2.5 technical report. arXiv preprint arXiv:2412.15115. Qwen Team. 2026. Qwen3.5: Towards native multimodal agents. https://qwen.ai/blog?id=qwen3. 5. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1–67.

Leyi Pan, Aiwei Liu, Shiyu Huang, Yijian Lu, Xuming Hu, Lijie Wen, Irwin King, and Philip S. Yu. 2025. Can LLM watermarks robustly prevent unauthorized knowledge distillation? In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 13228–13251, Vienna, Austria. Association for Computational Linguistics.

Saksham Rastogi and Danish Pruthi. 2024. Revisiting the robustness of watermarking to paraphrasing attacks. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 18100–18110, Miami, Florida, USA. Association for Computational Linguistics.

Qi Pang, Shengyuan Hu, Wenting Zheng, and Virginia Smith. 2024. No free lunch in LLM watermarking: Trade-offs in watermarking design choices. In Advances in Neural Information Processing Systems, volume 37.

Mehrdad Saberi, Vinu Sankar Sadasivan, Keivan Rezaei, Aounon Kumar, Atoosa Chegini, Wenxiao Wang, and Soheil Feizi. 2024. Robustness of AI-image detectors: Fundamental limits and practical attacks. In The Twelfth International Conference on Learning Representations.

Shinwoo Park, Hyejin Park, Hyeseon Ahn, and Yo-Sub Han. 2026. WaterMod: Modular token-rank partitioning for probability-balanced LLM watermarking. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 32683–32691.

Tom Sander, Pierre Fernandez, Alain Durmus, Matthijs Douze, and Teddy Furon. 2024. Watermarking makes language models radioactive. In Advances in Neural Information Processing Systems, volume 37.

Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor

Vithurabiman Senthuran, Yong Xiang, Iynkaran Natgunanathan, and Uthayasanker Thayasivam. 2026. The self-re-watermarking trap: From exploit to resilience. In The Fourteenth International Conference on Learning Representations.

Zongqi Wang, Tianle Gu, Baoyuan Wu, and Yujiu Yang. 2025. MorphMark: Flexible adaptive watermarking for large language models. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 4842–4860, Vienna, Austria. Association for Computational Linguistics.

Huanming Shen, Baizhou Huang, and Xiaojun Wan. 2025. Enhancing LLM watermark resilience against both scrubbing and spoofing attacks. In Advances in Neural Information Processing Systems, volume 38.

Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, and 3 others. 2020. Transformers: State-of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38–45. Association for Computational Linguistics.

Jiaming Shen, Heng Ji, and Jiawei Han. 2020. Nearimperceptible neural linguistic steganography via self-adjusting arithmetic coding. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 303–313, Online. Association for Computational Linguistics. Min Jae Song and Kameron Shahabi. 2026. Ideal attribution and faithful watermarks for language models. In Proceedings of the 43rd International Conference on Machine Learning.

Qilong Wu and Varun Chandrasekaran. 2024. Bypassing LLM watermarks with color-aware substitutions. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 8549–8581, Bangkok, Thailand. Association for Computational Linguistics.

Tomáš Souček, Sylvestre-Alvise Rebuffi, Pierre Fernandez, Nikola Jovanović, Hady Elsahar, Valeriu Lacatusu, Tuan Tran, and Alexandre Mourachko. 2025. Transferable black-box one-shot forging of watermarks via image preference models. In Advances in Neural Information Processing Systems, volume 38.

Yihan Wu, Xuehao Cui, Ruibo Chen, and Heng Huang. 2026a. Analyzing and evaluating unbiased language model watermark. In The Fourteenth International Conference on Learning Representations.

Erik F. Tjong Kim Sang and Fien De Meulder. 2003. Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition. In Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003, pages 142– 147.

Yihan Wu, Zhengmian Hu, Junfeng Guo, Hongyang Zhang, and Heng Huang. 2024. A resilient and accessible distribution-preserving watermark for large language models. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 53443–53470. PMLR.

Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288.

Zhihao Wu, Gracia Gong, Qinglin Zhu, Yudong Chen, and Runcong Zhao. 2026b. Linear ensembles wash away watermarks: On the fragility of distributional perturbations in LLMs. In Proceedings of the 43rd International Conference on Machine Learning.

Dor Tsur, Carol Long, Claudio Mayrink Verdun, Sajani Vithana, Hsiang Hsu, Richard Chen, Haim Permuter, and Flavio Calmon. 2025. HeavyWater and SimplexWater: Distortion-free LLM watermarks for low-entropy distributions. In Advances in Neural Information Processing Systems, volume 38.

Jiahao Xu, Rui Hu, Olivera Kotevska, and Zikai Zhang. 2026. XMark: Reliable multi-bit watermarking for LLM-generated texts. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 14747– 14763, San Diego, California, United States. Association for Computational Linguistics.

Shangqing Tu, Yuliang Sun, Yushi Bai, Jifan Yu, Lei Hou, and Juanzi Li. 2024. WaterBench: Towards holistic evaluation of watermarks for large language models. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1517–1542, Bangkok, Thailand. Association for Computational Linguistics.

Xiaojun Xu, Jinghan Jia, Yuanshun Yao, Yang Liu, and Hang Li. 2025. Robust multi-bit text watermark with LLM-based paraphrasers. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 69279–69292. PMLR.

Lean Wang, Wenkai Yang, Deli Chen, Hao Zhou, Yankai Lin, Fandong Meng, Jie Zhou, and Xu Sun. 2024. Towards codable watermarking for injecting multi-bits information to LLMs. In The Twelfth International Conference on Learning Representations.

Ke Yang, Dongyang Liang, Jing Yu, Shuguang Yuan, and Chi Chen. 2026. You can have a second chance: Unbiased and multi-bit watermarking for diffusion language models with regret-based remasking. In

Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. 2020. BERTScore: Evaluating text generation with BERT. In International Conference on Learning Representations.

Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 28141–28160, San Diego, California, United States. Association for Computational Linguistics.

Xuandong Zhao, Prabhanjan Ananth, Lei Li, and YuXiang Wang. 2024. Provable robust watermarking for AI-generated text. In The Twelfth International Conference on Learning Representations.

Kevin Yang and Dan Klein. 2021. FUDGE: Controlled text generation with future discriminators. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 3511–3535, Online. Association for Computational Linguistics.

Xuandong Zhao, Lei Li, and Yu-Xiang Wang. 2025. Permute-and-flip: An optimally stable and watermarkable decoder for LLMs. In The Thirteenth International Conference on Learning Representations.

Pei Yang, Hai Ci, Yiren Song, and Mike Zheng Shou. 2024. Can simple averaging defeat modern watermarks? In Advances in Neural Information Processing Systems, volume 37.

Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. 2023. Judging LLM-as-a-judge with MT-bench and chatbot arena. In Advances in Neural Information Processing Systems, Datasets and Benchmarks Track, volume 36.

Xi Yang, Jie Zhang, Kejiang Chen, Weiming Zhang, Zehua Ma, Feng Wang, and Nenghai Yu. 2022. Tracing text provenance via context-aware lexical substitution. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 11613–11621.

Tong Zhou, Xuandong Zhao, Xiaolin Xu, and Shaolei Ren. 2024. Bileve: Securing text provenance in large language models against spoofing with bi-level signature. In Advances in Neural Information Processing Systems, volume 37.

KiYoon Yoo, Wonhyuk Ahn, Jiho Jang, and Nojun Kwak. 2023. Robust multi-bit natural language watermarking through invariant features. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2092–2115, Toronto, Canada. Association for Computational Linguistics.

Junlin Zhu, Baizhou Huang, and Xiaojun Wan. 2026. QuantileMark: A message-symmetric multi-bit watermark for LLMs. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 6790–6806, San Diego, California, United States. Association for Computational Linguistics.

KiYoon Yoo, Wonhyuk Ahn, and Nojun Kwak. 2024. Advancing beyond identification: Multi-bit watermark for large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 4031–4055, Mexico City, Mexico. Association for Computational Linguistics.

Zachary Ziegler, Yuntian Deng, and Alexander Rush. 2019. Neural linguistic steganography. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 1210–1215, Hong Kong, China. Association for Computational Linguistics.

Zhuohao Yu, Xingru Jiang, Weizheng Gu, Yidong Wang, Qingsong Wen, Shikun Zhang, and Wei Ye. 2025. SAEMark: Steering personalized multilingual LLM watermarks with sparse autoencoders. In Advances in Neural Information Processing Systems, volume 38.

Explicit transformations and recovery rules

Boyu Zhang, Ping He, Tianyu Du, Xuhong Zhang, Lei Yun, Kingsum Chow, and Jianwei Yin. 2025. CLMTracing: Black-box user-level watermarking for code language model tracing. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 28974–28990, Suzhou, China. Association for Computational Linguistics.

This appendix instantiates the transformation Φ for every watermark studied in this paper. Fix a context c and abbreviate pv = p(v | c), qi,v = qi (v | c), and ℓi (v) = log qi,v − log pv . The equations below describe population distributions. Under sample access, qi is replaced by its empirical estimate.

Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak. 2024. Watermarks in the sand: Impossibility of strong watermarking for language models. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 58851–58880. PMLR.

General inversion. Given an arbitrary function Φ, recall that (P1) states pi (· | c) = Φ p(· | c), Gi (c) . (16) For some Φ inverting through it to compute Gi (c) given p and pi might not be possible. However, Φ 15

Consequently, a controlled account’s set Gi (c) is recovered directly by (20). The key, selected position, and absolute color name are not recovered by this operation.

defines which candidate sets are consistent with the observed distribution. Under exact distribution access, these candidates are Si (c) := S ⊆ V : Φ p(· | c), S = qi (· | c) = arg min dTV qi (· | c), Φ p(· | c), S ,

CycleShift. Let R = max(2L , |V|), let ⟨m⟩ ∈ [2L ] be the integer represented by the message, and let HK (c) ⊆ [R] be the keyed base set. The set associated with message m is the cyclic shift

S⊆V

(17) P where dTV (r, s) := 12 v∈V |r(v) − s(v)| is totalvariation distance. This inverts (P1): each scheme uses its own public Φ (Appendix A). If Si (c) is a singleton, it identifies Gi (c), and otherwise we constrain only memberships on which all candidates agree, replacing qi by its empirical estimate under sample access. Figure 4 works through the MPAC case: the log-ratio of the two distributions takes only two values, and the midpoint threshold between them returns the set exactly. By (P2), these memberships are the only way the key enters decoding, so controlling them suffices to control the decoder without recovering K.

Gm K (c) = {v ∈ V : (v + ⟨m⟩) mod R ∈ HK (c)}. Its transformation is again additive, m ΦCS p, Gm K (c) = Aδ p, GK (c) ,

HK (c) = {(v + ⟨m(i) ⟩) mod R : v ∈ Gi (c)}, ′

′ Gm K (c) = {v : (v + ⟨m ⟩) mod R ∈ HK (c)}. (25) If R > |V|, the account reveals only the coordinates of the extended set that are represented in the model vocabulary.

RSBH. Let Enc(m) = (a0 (m), . . . , ar−1 (m)) be the public Reed–Solomon codeword and let σ(c) ∈ [r] be the public segment selected by the context. For each context and symbol value a, the key determines a set HK,c,a ⊆ V. Hence

Aδ (p, S)v :=

(18)

u∈S

Gm K (c) = HK,c,aσ(c) (m) , m ΦRSBH p, Gm K (c) = Aδ p, GK (c) .

If qi = Aδ (p, Gi ), write Zi := Zδ (p, Gi ). Then ( δ − log Zi , v ∈ Gi , ℓi (v) = (19) − log Zi , v∈ / Gi . Thus the exact inversion rule is θi := 21 max ℓi (v) + min ℓi (v) , v

(20)

XMark. A message consists of B = L/2 symbols m1 , . . . , mB ∈ {0, 1, 2, 3} of two bits each. The block of a token is public: if c = (u, w) are the two preceding tokens, the block is σ(c) = (u + w) mod B. The key seeds two permutations of the vocabulary at c, each cut into four quarters, which give every token two quarter labels Q1K (c, v), Q2K (c, v) ∈ {0, 1, 2, 3}. Symbol s boosts the tokens that lie outside quarter s under both permutations, the dark set

This rule uses only the two observable distributions. The normalizer is common to every token and therefore need not be known. MPAC. At context c, the key selects a position JK (c) and a vocabulary coloring CK (c, ·). Writing VK,c,s := {v : CK (c, v) = s}, the messageconditioned set is (21)

Generation uses m ΦMPAC p, Gm K (c) = Aδ p, GK (c) .

(26)

Equation (20) therefore recovers, from account i, the set indexed by its codeword symbol aσ(c) (m(i) ). It does not reveal sets belonging to other symbol values. In the released construction, the set for symbol value 0 is generated without the secret multiplier and is therefore public as well.

Gi (c) = {v ∈ V : ℓi (v) > θi }.

Gm K (c) = VK,c,mJK (c) .

(24)

so (20) recovers Gi (c). When R = |V|, the controlled message also recovers the base set and every target set:

A shared additive transformation. MPAC, CycleShift, RSBH, and XMark use the same operation once their message-conditioned set has been constructed. For S ⊆ V and bias δ > 0, define pv exp(δ1{v ∈ S}) , Zδ (p, S) X Zδ (p, S) := 1 + eδ − 1 pu .

(23)

DK,c,s := {v : Q1K (c, v) ̸= s and Q2K (c, v) ̸= s}, (27)

(22) 16

which holds 9/16 of the vocabulary. Hence Gm K (c) = DK,c,mσ(c) , m ΦXM p, Gm K (c) = Aδ p, GK (c) .

The released cumulative reweighting is exactly Z Fr wI (x) dx. (31) ΦSI (p, πK (c), s)πr =

(28)

Fr−1

The selected part of the probability interval receives weight 0, its reflection about 1/2 receives weight 2, and their overlap and the remainder receive weight 1. Since a token in the selected chunk has its whole cumulative interval inside I, whereas every other token lies outside I, the exact membership implications are qi,v < pv =⇒ v ∈ Gi (c),

The decoder gives every scored token one vote for its quarter under the first permutation and, if that quarter differs, one for its quarter under the second, collects the votes per block, and outputs the symbol with the fewest votes. A token votes for s exactly when it lies outside DK,c,s , so the vote count of s at a block is the number of its tokens outside the dark set of s, and the decoder reads the key only through membership in the sets Gm K (c), as (P2) requires. The released code seeds the two permutations with fixed public constants, which we replace by a secret key and a second key derived from it. Equation (20) recovers from account i the (i) dark set DK,c,a of its symbol a = mσ(c) and hence its complement UK,c,a := V \ DK,c,a , the tokens that lie in quarter a under at least one permutation. It reveals neither the two quarters separately nor the dark sets of the other symbol values. Because the block is public, the sets of different accounts at the same context combine by symbol value. The target’s dark set at a context is available exactly when some account carries the target’s symbol s′ at that block, or when at most one symbol value is unseen there: if a and b are two known values other than s′ , a token in UK,c,a ∩ UK,c,b has one quarter equal to a and the other equal to b, so both differ from s′ and the token lies in DK,c,s′ . The implementation forces the tokens that lie in at least two known non-target unions, a subset of DK,c,s′ that is certain under every labeling consistent with the observations. When the target’s symbol is unseen and two or more symbol values are unseen at a block, these values are interchangeable in the attacker’s view, and the orbit of the target gains a factor equal to their number.

qi,v > pv =⇒ v ∈ / Gi (c), qi,v = pv =⇒ v is unresolved.

Thus this transformation generally reveals only part of Gi (c) and part of its complement. The implementation uses the numerically conservative log-ratio rules log(qi,v /pv ) < −5 for inside and log(qi,v /pv ) > 0.2 for outside, leaving the remainder unresolved. When applying (17) to this scheme, a candidate consists of a chunk together with a compatible ordering π, because the ordering affects the output probabilities.

Pseudocode of the attack on MPAC

Algorithm 1 lists the attack of Section 3 for binary MPAC, with the green-list recovery rule of Appendix A, and Algorithm 2 the certificate of Section 3.2. Both are written for one source text. The attacker queries its accounts and the base model at a context once and caches the recovered lists. With exact next-token distributions the log-ratio ℓi takes exactly two values at a context, so the midpoint threshold recovers Gi (c) exactly, and under sample access the empirical estimates of Appendix A take its place. The experiments use S = 1,000 draws for the certificate.

Experimental details

Corpora. Every corpus consists of 100 completions of C4 prompts (Raffel et al., 2020) with 200 tokens each, sampled at temperature 0.7 and top-p 0.9 (Holtzman et al., 2020) from the generator under one secret key and one attacker message, with binary MPAC (γ = 1/2, δ = 2). Message lengths are L ∈ {8, 16} in the tables and up to L = 64 in Figure 7. The released CycleShift code enumerates 2L shifts, so at 32 bits we run a chunked variant: four 8-bit blocks, the block chosen by the previous token, each a released CycleShift over the same secret set.

StealthInk. Here the exact transformation uses an ordered vocabulary partition, not only the selected chunk as an unordered set. Let πK (c) = (π1 , . . . , π|V| ) be the keyed permutation, split into contiguous chunks. If s = mJK (c) and the index interval of chunk s is {a + 1, . . . , b}, then Gm (29) K (c) = {πa+1 , . . . , πb }. Pr Put F0 = 0 and Fr = j=1 pπj , and let I = [Fa , Fb ] and I ⋆ = [1 − Fb , 1 − Fa ]. Define wI (x) := 1 + 1{x ∈ I ⋆ } − 1{x ∈ I}.

(32)

(30) 17

Algorithm 1 Targeted displacement attack on binary MPAC Require: source y, target m′ ∈ {0, 1}L , messages m(1) , . . . , m(n) of the controlled accounts, next-token access to the accounts qi (· | c) and to the base model p(· | c), paraphraser ppara , threshold τ , bias δatk Ensure: rewrite z 1: {twin classes and relative bits, from the messages alone (Section 3.1)} 2: for j = 1, . . . , L do n (i) (1) (1) 3: xj ← (mj + mj ) mod 2 i=2 and rj ← (m′j + mj ) mod 2 4: end for 5: T ← partition of [L] into classes of equal xj 6: for every class T ∈ T do 7: if rj is constant on T then 8: rT ← that value 9: else 10: rT ← rj for a uniformly random j ∈ T {ambiguous class, N (M, m′ ) > 1, success bounded by Theorem 1} 11: end if 12: end for 13: {constrained rewriting (Section 3.1)} 14: z ← () 15: for t = 1, 2, . . . until the paraphraser stops do 16: pt (·) ← ppara (· | y, z<t ), then pt (v) ← 0 for every v that would complete a 4-gram already in z<t 17: ct ← the watermark context of z<t (the previous token for MPAC), Bt ← TARGET L IST(ct ) P 18: if Bt ̸= ∅ and Zt := u∈Bt pt (u) ≥ τ then 19: sample zt ∼ rt with rt (v) = pt (v) 1{v ∈ Bt }/Zt (7) 20: else 21: sample zt ∼ rt with rt (v) ∝ pt (v) exp δatk 1{v ∈ Bt } (8) 22: end if 23: end for 24: return z 25: 26: procedure TARGET L IST(c) {the green list of m′ at c, (6)} 27: for i = 1, . . . , n do 28: ℓi (v) ← log qi (v | c) − log p(v | c) for all v ∈ V, θi ← 12 maxv ℓi (v) + minv ℓi (v) , Gi (c) ← {v : ℓi (v) > θi } 29: end for n 30: x(c) ← 1{Gi (c) ̸= G1 (c)} i=2 31: if x(c) = xj for some j ∈ [L] then 32: T (c) ← the class with signature x(c) 33: return G1 (c) if rT (c) = 0, else V \ G1 (c) 34: else 35: return ∅ {no class matches, the paraphraser alone decides this step} 36: end if

Attacker. The attacker rewrites each text with a chat model that shares the generator’s tokenizer (Llama-2-7B-chat, Llama-3.1-8B-Instruct, and the Qwen model itself with its reasoning mode disabled) and has distribution access to its accounts. The paraphraser samples at temperature 0.7 and top-p 0.9. We report the constrained rewriting rule of Section 3.1 with τ = 0, and the paraphraser additionally blocks repeated 4-grams, which keeps constrained decoding from collapsing into loops. Conditions: the own account with the target set to the complement m̄ or to a message one bit away, and n colluding accounts with a uniformly random target. Fact protection (used in the fidelity experiments of Appendix J) leaves a step unconstrained when the paraphraser’s top token has probability at least κ and ends the text, is whitespace, or continues a numeral, name, or negation copied from the source. Such a token may vote against the target,

and the certificate counts it as a rival vote. Metrics. Let ẑ be the rewrite of a source y against target m′ . Success, or exact match, is the fraction of texts with DK (ẑ) = m′ , and bit accuracy is the fraction of the target’s bits (symbols, for the 2-bit schemes) that the decoded message matches, both over the 100 texts of a corpus. The bound is the mean of the appropriate symmetry upper bound over the drawn targets; in the binary position–color case this is 1/N (M, m′ ) from Theorem 1. The certificate is the Monte Carlo estimate of the posterior quantity (15) (Table 2). Fidelity to the source uses BERTScore F1 (Zhang et al., 2020) and ROUGEL F1 (Lin, 2004) between ẑ and y. Two LLM judges (Zheng et al., 2023) from different families, Llama-3.3-70B-Instruct (Grattafiori et al., 2024) and Qwen2.5-72B-Instruct (Qwen Team, 2024), both in 4-bit AWQ (Lin et al., 2024) with greedy decoding, rate on a five-point scale how faithfully 18

Algorithm 2 Attacker-side certificate

NLI and NER scorers on one A40 (wall-clock costs in Appendix I). The code is Python 3.12 with PyTorch 2.11 (Paszke et al., 2019) and Transformers 5.10 (Wolf et al., 2020), except that the earliest Llama-2-7B MPAC runs at 8 and 16 bits with τ = 10−3 used PyTorch 2.4.1 and Transformers 4.45.2; the judges are served by vLLM 0.23 (Kwon et al., 2023). The generators are the Hugging Face checkpoints Llama-2-7b-hf, Llama-3.1-8B, Qwen3.5-4B, and Qwen3.5-9B, and the paraphrasers Llama-2-7b-chat-hf, Llama-3.1-8B-Instruct, and the two Qwen models themselves, so one copy of a Qwen model serves as generator, attacker’s base model, and paraphraser. Llama-2-7B generates in float16 and the other generators in bfloat16; during the attack every model runs in bfloat16, the Llama paraphrasers use eager attention, a guard replaces non-finite logits during rewriting (Llama-2-7B-chat produced NaNs in batched float16 generation), and the learner compares log-probabilities in float32. Corpora are sampled in batches of 10 prompts, truncated to 1,200 tokens and left-padded, with exactly T new tokens, top-k disabled, and a 5-gram repetition block (Paulus et al., 2018); the unwatermarked completion of a prompt reuses the sampling seed of its watermarked twin. Rewrites are sampled in batches of 8 with top-k disabled. The 4-gram block of Tables 1 and 4 and of Figure 7 is the no_repeat_ngram_size option of Transformers, which indexes the prompt as well, so a rewrite repeats no 4-gram of its source; the rewrite-only block of Appendix J is our own logits processor over the generated tokens. The watermarked API is simulated in-process: an oracle takes the generator’s logits at the attacker’s prefix, applies the watermark of the queried account (the δ bias of its set, or StealthInk’s reweighting), and returns the full log-softmax; the base-model forward pass is shared with the attacker’s own call and cached per prefix. For the additive schemes the learner classifies every token of the vocabulary by thresholding the log-ratio log pi (v | c) − log p(v | c), which equals δ 1{v ∈ Gi (c)} − log Z up to float32 rounding, at the midpoint of its range; StealthInk uses the closed-form rule of Appendix A. Learned sets are cached per context and account, and for MPAC accounts whose learned sets agree on at least 90 percent of the jointly resolved tokens form one twin class. Each corpus carries a pool of extra accounts with random messages (16 for MPAC at 8 and 16 bits, up to 128 for the longer messages and for the

Require: rewrite z, the classes T , relative bits rT , and procedure TARGET L IST of Algorithm 1, number of draws S Ensure: Cert(z, m′ | O) 1: if N (M, m′ ) > 1 then 2: return 0 3: end if 4: P(z) ← {(ct , zt ) : 1 ≤ t ≤ |z|} {distinct pairs} 5: for every distinct context c in P(z) do 6: T (c) ← the class matched in TARGET L IST(c), or [L] if none 7: σ(c, v) ← +1 if v ∈ TARGET L IST(c), else −1, for every (c, v) ∈ P(z) 8: end for 9: ok ← 0 10: for s = 1, . . . , S do 11: draw J(c) ∼ Unif T (c) independently for every distinct context c P 12: Mj (J) ← (c,v)∈P(z): J(c)=j σ(c, v) for j = 1, . . . , L 13: if Mj (J) > 0 for every j ∈ [L] then 14: ok ← ok + 1 15: end if 16: end for 17: return ok/S

ẑ keeps the facts, numbers, names, negations, and claims of y (5 for the same content, 3 when at least one fact is changed, invented, or lost, and 1 for different content). A DeBERTa-v3-large NLI model (He et al., 2023) gives support, the mean over the sentences of ẑ of the probability that y entails the sentence, and coverage, the mean over the sentences of y of the probability that ẑ entails the sentence. Facts kept is the fraction of the numeric expressions of y, with sign, currency, and magnitude word, and of its named entities, found by a BERT NER tagger trained on CoNLL-2003 (Devlin et al., 2019; Tjong Kim Sang and De Meulder, 2003), that ẑ reproduces verbatim (numbers up to spacing and equivalent percent and dollar notation). Neither extractor shares code with fact protection. The judges agree with each other (Spearman 0.78 over the rewrites and paraphrases, within one point on 97 percent of the pairs) and with NLI (0.64). For the other schemes, Table 4 reports BERTScore and perplexity under Llama-2-13B instead, since ROUGE-L and the judges were computed for the MPAC rewrites. Implementation details. Every generation, attack, and scoring job runs on one NVIDIA H100 (94 GB) or A40 (48 GB) of a Slurm cluster with 8 CPU cores and 64 GB of host memory (96 GB for the judges); the LLM judges run on two A40s with tensor parallelism and the 19

schemes with more positions); the n colluding accounts are the attacker’s own account and the first n − 1 accounts of one fixed random ordering of the pool, so the coalitions are nested in n, and the target of a text is drawn by a generator seeded with the condition, the global seed, and the text index, so a text faces the same target under every rewrite rule. The certificate (15) uses 1,000 Monte Carlo draws of the position assignment for MPAC, 300 for RSBH and StealthInk, and 200 for XMark, and is exact for CycleShift. Scheme parameters follow the released code: δ = 2 wherever a logit bias is added (StealthInk reweights without a bias), onetoken contexts except for XMark (two tokens) and StealthInk (three), and set fractions γ = 1/2 for MPAC and RSBH, 1/4 for CycleShift, and 9/16 for XMark. Our MPAC re-implementation draws the position and the color partition of a context from a PRNG seeded by a hash of key and context rather than from torch.randperm, so that generation and detection agree across devices; an 8-bit corpus generated with the released MPAC code and judged by its detector gives the same success rates as our re-implementation. The other schemes keep the seeding and decoding of their released code (Appendix A), with a secret key where the released code uses a fixed constant.

Paraphraser prompt

Every rewrite in the paper, the plain paraphrase included, is generated from the same two chat messages, and the rules of Section 3.1 change only the decoding. The source y is the watermarked completion alone, without the C4 prompt that produced it. System You are a careful editor. User Rewrite the following passage in your own words. Preserve every fact and the order of ideas, keep roughly the same length, and output only the rewritten passage with no preamble. Passage: ⟨watermarked text y⟩

Each paraphraser receives the two messages in its own chat template and writes the assistant turn. The template of Llama-3.1-8B-Instruct adds its default lines Cutting Knowledge Date: December 2023 and Today Date: 26 Jul 2024 to the system message, and for Qwen3.5 the reasoning mode is disabled, so the prompt ends with an empty reasoning block. The answer is sampled at temperature 0.7 and top-p 0.9 with 150 to 248 new tokens (the sources have 200), and the decoder scores it as generated, without post-processing.

Example rewrites

Table 3 shows two watermarked sources with their plain paraphrase and their attack rewrite under the τ = 0 rule of Table 1, both decoded to the target. Selection: among the 792 n-account rewrites that reached their target, we keep the 75 that both LLM judges score at least 4 (facts kept), leave out the Llama-2-7B-chat paraphraser, whose τ = 0 rewrites carry spelling and case corruption that the judges tolerate but perplexity (Table 4) does not, and show the two closest to the source by ROUGEL among the rest, at most one per generator. Over all 792 the ROUGE-L median is 0.29, and the examples score 0.40 and 0.51. The texts are shown as the judges and the metrics saw them, after the paraphraser’s chat preamble is removed.

BERTScore F1 uses bert-score 0.3.13 with RoBERTa-large and no baseline rescaling, ROUGE-L F1 uses rouge-score 0.1.2 with Porter stemming, and perplexity is that of Llama-2-13B in float16 given the last 3,000 characters of the prompt. The judges, Llama-3.3-70B-Instruct-AWQ and Qwen2.5-72B-Instruct-AWQ, generate at most 400 tokens in a 4,096-token context and answer with a JSON object holding a score and up to three changed facts; the score is read from the reply with a regular expression, and a reply without a score is dropped. The NLI model is DeBERTa-v3-largemnli-fever-anli-ling-wanli in float16 on pairs truncated to 512 tokens, with sentences split at terminal punctuation and kept when they have at least four words, and the NER tagger is bert-large-NER with simple entity aggregation. All randomness is seeded (seed 0 for the secret key, the messages, sampling, the attack, and the choice of accounts), and every reported cell is a single run over the 100 texts of its corpus.

Results for the other schemes

Table 4 gives, for every scheme at 8 bits and for each generator with the mean over the four, the clean decode rate, the bit accuracy and exact match of the plain paraphrase, of the own-account rewrite, and of the nmax -account rewrite, and the 20

Watermarked source

Paraphrase without the attack

Attack rewrite

Example 1. Qwen3.5-4B, L = 16, 12 colluding accounts. Target 1001000100100101, decoded 1001000100100101. Paraphrase / attack rewrite: judge 5.0 / 4.0, ROUGE-L 0.53 / 0.51, BERTScore 0.93 / 0.93. Google Music will continue to be free to Google Music remains free to download Users will still be able to download download in the U.S., but the service is within the U.S.; however, the service is Google Music for free from America. ending for free users across all European However, in every part Europe other shutting down for free users in all of except for Italy, free access to music is Europe, except for Italy. Apple Music, countries except Italy. Apple Music, now in beta testing, seems to be getting currently in beta, appears to combine the shutting down. best features of both worlds: it offers a Apple Music, which is now in beta, the best of all worlds. It offers a monthly streaming subscription similar appears to combine the best of both monthly subscription service like to Spotify and Google, while also options: a subscription service that Spotify and Google Music, but the works the type of Spotify and Google allowing users to purchase individual company is also offering an option to plus an option to purchase songs from tracks from the App store. For now, buy your music from the App Store. Apple Music is available exclusively for Apple Store. Apple Music is available for testing in the U.S. only for now and it will be testing in America, where beta users can Apple is available only for testing right available as an in-app purchase on both access it as an in-purchase on both iOS now in America. It is available as an on-the-floor, in-app store purchase to iOS and Mac for users in beta. So there devices and Mac computers. Consequently, mobile music consumers iOS and MAC users who participate in are a lot of choices for mobile music beta testing the service. consumers, and Google Music is a have numerous options, with Google So there are many options for mobile strong contender for those looking for a Music serving as a strong choice for those seeking a cloud-based music consumers and Google Music remains a cloud music experience. Does the very strong contender if people are “cloud music” label mean that it’s only experience. The term "cloud music" available on mobile devices? No. You does not imply the service is limited to searching out the best cloud-based can use the Google Music app on your mobile devices; users can stream via the music experience. app on iPhones and Android phones, as The label "cloud music" does not mean iPhone and Android. You can also well as through any web browser. it is only for mobile phones or tablets. access the service through a web You can utilize Google Music on an iOS browser. How much of your music is and Android phone, plus on the web. stored on your computer So much of your personal library stored on the personal computer. Example 2. Llama-3.1-8B, L = 16, 12 colluding accounts. Target 1100000001010101, decoded 1100000001010101. Paraphrase / attack rewrite: judge 4.0 / 4.0, ROUGE-L 0.41 / 0.40, BERTScore 0.91 / 0.89. They also collected money for those in The event featured fundraising efforts The demonstration featured fundraising struggle and leafleted with information. for those affected by conflict, as well as efforts for communities impacted by the distribution of informational leaflets. war. In conjunction, participants The event went on for two hours. The distributed leaflets with relevant speakers at the rally included a young The rally itself lasted for two hours. man from Afghanistan, who said, “The Speakers at the event included a young informational materials during the U.S. has been bombing my country for Afghan man, who emphasized that the two-hours-long protest. A speaker at the 16 years. We don’t want this war. We U.S.’s 16-year bombing campaign in his rally from Afghanistan expressed his don’t support this war. We support country has been met with opposition. country’s prolonged experience of peace, not war.” The speaker from the He stated that the Afghan people do not conflict, having been bombed by the U. Philippines, who is also a veteran of the support the ongoing war and instead S for nearly sixteen years. He U.S.’ wars there, said, “The people of advocate for peace. A speaker from the emphasized that the Afghan people’s opposition to war remains unwavering, the Philippines have been resisting the Phillipines, who has also experienced U.S. military involvement firsthand, with their desire for peaceful resolution U.S. for more than 120 years. The American imperialists have never been noted that the Phillipine people have being the primary stance. A veteran able to subjugate the Filipino people, been resisting U.S. influence for over from the U. s-affected Philippines also and they never will.” The IAC also set 120 years, with the U.S.-led imperialist shared his views at the rally. He up an anti-imperialist book table on efforts ultimately proving unsuccessful. highlighted the long history between the Wilshire Boulevard at the corner of The IAC set up an information table on U. and s the Philippine people, with Western. The table was staffed by IAC Wilhire Boulevard at Western Avenue, their resistance dating back over more a members who spoke to passers-by about where members engaged with passersby century. He confidently stated that the the U.S. war in Afghanistan, the U.S. about U.S. involvement in various U. could never subsume their people wars in Korea and the Philippines, and conflicts, including Afghanistan, Korea, under its control. The IAC set-up a book the U.S. attack on and the Phillipines. display on Wilhire Boulevard, at the intersection of Western. This display was staffed and monitored by IAC volunteers who spoke with on-looking passers-by, addressing the U. ’S involvement in conflicts in countries including Afghanistan, s Korea, s the U. the U. as and s the U, s the attack.

Table 3: Two example rewrites of binary MPAC under the τ = 0 rule of Table 1: the watermarked source, the same paraphraser without the attack, and the n-account attack rewrite that decoded to the target. Each example’s line gives the generator, the message length, the number of colluding accounts, the target and decoded messages, and the judge score, ROUGE-L and BERTScore of the paraphrase and of the attack rewrite. Selection as described in Appendix E.

BERTScore and perplexity of the rewrites. The paragraph on other schemes in Section 4 discusses the means.

continuations of a corpus.

Per-generator collusion curves

Figures 8 to 12 repeat the panels of Figure 7 for every generator separately, with the same rules and bound, and the MPAC figure adds the soft bias of (8).

Text length

Figure 13 repeats the sweep of Figure 7 for sources of 100, 200, and 400 tokens under the τ = 0 rule. The symmetry bound does not depend on the text length. What changes is how many tokens each message position receives. Up to 16 bits the three lengths give the same curves within a few points, except StealthInk at 16 bits and 100 tokens, where eight to 32 accounts reach 74 to 79 percent instead of 94 to 100. At 32 bits doubling the text to 400 tokens lifts the plateau of MPAC from 65 to 87 percent, StealthInk from 55 to 94, and XMark and RSBH to 100. At 64 bits no scheme carries its message through 200 tokens, untouched or rewritten (at most 23 percent, for XMark), and 400 tokens are still too few for MPAC (about 20 percent from 12 accounts on) and StealthInk (28 percent), while XMark reaches 82 to 85 percent, and the untouched watermarks decode none of these sources exactly.

Runtime

Every attack job rewrites the 100 texts of one corpus under every condition of its row in Figure 7 on a single NVIDIA H100 (94 GB), with the generator, the paraphraser, and the attacker’s copy of the base model loaded together and batches of 8 texts. The API is simulated locally with the generator itself, so the time includes the oracle’s own forward passes. Table 5 reports, for the settings run on the H100, the wall-clock time per rewritten text under the τ = 0 rule, including decoding, the certificate, and the learner’s queries. The τ = 10−3 rule costs the same. The dominant cost is one base-model forward pass per new context, so schemes whose context is longer than one token (XMark, StealthInk) query at almost every step, while MPAC, CycleShift, and RSBH reuse contexts. Queries is the number of oracle calls per rewritten text with a plan, one per context and account whose set the learner resolved, and corpus is the time to sample the 100 watermarked and 100 unwatermarked 22

Fidelity per generator

clean no attack own acc. → m̄ nmax accounts

perplexity ↓

BA ↑

BA ↑ BA ↑

MPAC (binary)

8 Llama-2-7B Llama-3.1-8B Qwen3.5-4B Qwen3.5-9B mean

96.5 98.0 99.0 98.4 98.0

50.2 49.2 48.0 52.5 50.0

100.0 100.0 100.0 100.0 100.0

100 100 100 100 100

100.0 100.0 100.0 100.0 100.0

100 100 100 100 100

0.89 0.90 0.90 0.91 0.90

0.84 0.86 0.86 0.86 0.86

4.9 4.4 5.8 5.4 5.1

41.7 19.8 23.5 24.3 27.3

StealthInk (binary)

8 Llama-2-7B Llama-3.1-8B Qwen3.5-4B Qwen3.5-9B mean

94.1 97.2 94.9 95.5 95.4

47.8 50.1 49.6 45.5 48.2

100.0 100.0 100.0 100.0 100.0

100 100 100 100 100

100.0 100.0 100.0 100.0 100.0

100 100 100 100 100

0.89 0.90 0.91 0.91 0.90

0.82 0.86 0.85 0.85 0.84

4.2 3.9 5.1 4.7 4.5

79.4 29.8 33.3 37.5 45.0

StealthInk (2-bit chunks)

16 Llama-2-7B Llama-3.1-8B Qwen3.5-4B Qwen3.5-9B mean

76.5 82.5 75.5 72.5 76.8

25.5 24.0 23.0 25.0 24.4

35.8 36.0 36.0 36.0 35.9

1 1 1 1 1

100.0 100.0 100.0 100.0 100.0

100 100 100 100 100

0.90 0.90 0.91 0.91 0.90

0.85 0.88 0.87 0.87 0.87

4.0 3.6 4.9 4.5 4.3

42.0 19.3 24.3 26.8 28.1

XMark (2-bit chunks)

16 Llama-2-7B Llama-3.1-8B Qwen3.5-4B Qwen3.5-9B mean

97.5 98.2 96.8 96.2 97.2

28.2 26.2 25.2 25.0 26.2

22.5 22.0 27.0 23.0 23.6

0 0 0 0 0

100.0 100.0 100.0 100.0 100.0

100 100 100 100 100

0.90 0.90 0.90 0.91 0.90

0.85 0.88 0.88 0.87 0.87

4.7 4.3 5.8 5.2 5.0

39.0 17.2 22.2 23.7 25.5

CycleShift

1 Llama-2-7B 99.5 Llama-3.1-8B 99.5 Qwen3.5-4B 97.2 Qwen3.5-9B 100.0 mean 99.1

52.6 51.0 50.0 51.9 51.4

100.0 100.0 100.0 100.0 100.0

100 100 100 100 100

100.0 100.0 100.0 100.0 100.0

100 100 100 100 100

0.90 0.90 0.90 0.91 0.90

0.79 0.83 0.82 0.82 0.82

5.0 117.9 4.7 41.6 6.1 29.1 5.7 38.3 5.4 56.7

RSBH

32 Llama-2-7B Llama-3.1-8B Qwen3.5-4B Qwen3.5-9B mean

47.9 49.8 52.2 52.1 50.5

38.6 45.6 44.8 45.8 43.7

0 0 0 0 0

97.6 96.6 96.8 95.1 96.5

93 90 91 86 90

0.89 0.90 0.91 0.91 0.90

0.85 0.87 0.87 0.87 0.86

4.7 4.3 5.7 5.3 5.0

Scheme

nmax Generator

97.0 97.8 97.2 98.9 97.7

EM ↑ BA ↑

BERTScore ↑

EM ↑ paraphrase attack source attack

38.3 17.2 20.5 22.2 24.5

Table 4: Steering other multi-bit schemes with 8-bit messages, per generator with the mean over the four generators. Same accuracy metrics as Table 1, with BERTScore and perplexity under Llama-2-13B (source and attack rewrite) as text metrics. ↑ (↓): higher (lower) is better. The colluding column uses the largest number of accounts run for each scheme, nmax , and for CycleShift a random target from the own account alone. CycleShift: the payload cyclically shifts one secret set, so one account reveals every payload’s set. RSBH: public segments and an RS(4,2) code over GF(16) whose released decoder falls back to the raw payload when decoding fails. XMark: public blocks from the two previous tokens and two keyed quarterings of the vocabulary, with the 2-bit symbol suppressing one quarter under both. StealthInk: the released 2-bit chunks, for which the accuracy columns report symbol accuracy over the four 2-bit positions, and a binary variant.

τ = 0, 4-gram block

exact match (%)

L=8 L = 16

source, no rewrite

orbit bound (Thm. 1), shaded: ruled out

−3

Llama-2-7B

exact match (%)

soft bias

τ = 10

Qwen3.5-4B

Qwen3.5-9B

Llama-3.1-8B

100 75 50 25 0 100 75 50 25 0

colluding accounts n

Figure 8: Binary MPAC: per-generator version of Figure 7. Triangles: the soft bias of (8).

−3

τ = 0, 4-gram block

τ = 10

L=8 L = 16

exact match (%)

Llama-2-7B

orbit bound (Thm. 1), shaded: ruled out

Qwen3.5-4B

Qwen3.5-9B

source, no rewrite

Llama-3.1-8B

100 75 50 25 0

colluding accounts n

Figure 9: RSBH: per-generator version of Figure 7. A target is reachable once at most one of its codeword symbols is uncovered by the accounts, which takes 32 accounts for 8-bit messages and 64 for 16-bit ones.

τ = 0, 4-gram block

L=8 L = 16

exact match (%)

Llama-2-7B

−3

τ = 10

orbit bound (Thm. 1), shaded: ruled out

Qwen3.5-4B

Qwen3.5-9B

source, no rewrite

Llama-3.1-8B

100 75 50 25 0

colluding accounts n

Figure 10: StealthInk with its released 2-bit symbols: per-generator version of Figure 7. A target becomes reachable once every one of its symbols has been seen at its position by some account.

−3

τ = 0, 4-gram block

τ = 10

L=8 L = 16

exact match (%)

Llama-2-7B

orbit bound (Thm. 1), shaded: ruled out

Qwen3.5-4B

source, no rewrite

Qwen3.5-9B

Llama-3.1-8B

100 75 50 25 0

colluding accounts n

Figure 11: XMark with its released 2-bit symbols: per-generator version of Figure 7. Blocks are public, so a target’s symbol at a block is reachable once some account carries it or only one symbol value is unseen there. −3

τ = 0, 4-gram block

τ = 10

L=8 L = 16

exact match (%)

Llama-2-7B

orbit bound (Thm. 1), shaded: ruled out

Qwen3.5-4B

source, no rewrite

Qwen3.5-9B

Llama-3.1-8B

100 75 50 25 0 m̄

d=1

d=4

rand

m̄

d=1

d=4

rand

m̄

d=1

d=4

rand

m̄

d=1

d=4

rand

m̄

d=1

d=4

rand

m̄

d=1

d=4

rand

m̄

d=1

d=4

rand

m̄

d=1

d=4

rand

100 75 50 25 0

target from the own account

Figure 12: CycleShift: per-generator version of Figure 7. Every target is reachable from the own account, so the panels show the complement m̄, targets one and four bits away from m, and a uniformly random one.

L=8 L = 16 L = 32

exact match (%) exact match (%) exact match (%)

T = 100

T = 200

MPAC 100 75 50 25 0 100 75 50 25 0 100 75 50 25 0

T = 400

orbit bound (Thm. 1), shaded: ruled out

RSBH

StealthInk

XMark

128

colluding accounts n

Figure 13: Exact-match success of the constrained rewrite (τ = 0, 4-gram block) against the number of colluding accounts for sources of T ∈ {100, 200, 400} tokens, rewrites of 0.75T to 1.24T tokens, mean over the four generators. Dashed: the mean symmetry bound, the same for every T . Shaded: ruled out. Figures 14 and 15 show the same runs in the layout of Figure 7.

L=8 L = 16

exact match (%) exact match (%)

τ = 0, 4-gram block

orbit bound (Thm. 1), shaded: ruled out

MPAC 100 75 50 25 0 100 75 50 25 0

RSBH

source, no rewrite

StealthInk

colluding accounts n

XMark

Figure 14: Figure 7 at 100 tokens per text (τ = 0 rule, since the τ = 10−3 rule and CycleShift were run at 200 tokens only). Dotted: the decoder’s exact-match rate on the untouched 100-token source.

L=8 L = 16 L = 32

exact match (%) exact match (%) exact match (%)

τ = 0, 4-gram block

orbit bound (Thm. 1), shaded: ruled out

MPAC 100 75 50 25 0 100 75 50 25 0 100 75 50 25 0

RSBH

source, no rewrite

StealthInk

XMark

128

colluding accounts n

Figure 15: Figure 7 at 400 tokens per text (τ = 0 rule, since the τ = 10−3 rule and CycleShift were run at 200 tokens only). Dotted: the decoder’s exact-match rate on the untouched 400-token source.

τ = 0 + 4-gram block

fact protection κ = 0.5 (filled), 0.2 τ=0 τ = 10−3 τ = 10−2

τ = 0 + 4-gram block

L = 16 τ=0

fidelity to the source (LLM judges, 1 to 5)

soft bias

paraphrase

same prompt

unrelated

soft bias

paraphrase

same prompt

τ = 10−2

40 20

fact protection κ = 0.5 (filled), 0.2 τ = 10−3

60 unrelated

exact target match (%)

100

L=8

fidelity to the source (LLM judges, 1 to 5)

Figure 16: Exact-match success against fidelity (mean of the two LLM judges) for the rewrite rules evaluated in this section, one panel per message length, mean over the four generators and over the own-account and n-account rewrites. Blue: the constrained rule from the soft bias to τ = 0. Squares: τ = 0 with either 4-gram block. Stars: τ = 0 with fact protection. Dashed lines: fidelity of the plain paraphrase, of an unwatermarked completion of the same prompt, and of an unrelated source.

Scheme

seconds per rewritten text ↓

queries ↓

corpus

Llama-2-7B

Llama-3.1-8B

Qwen3.5-4B

Qwen3.5-9B

per rewrite

(min)

MPAC

8 16 32 64 8 16 16 32 64

200 200 200 200 400 100 400 400 400

1 1 2 2 3 1 3 4 5

2 2 2 3 3 1 3 4 5

3 3 4 5 6 2 6 7 8

3 3 5 5 7 3 7 9 9

120 174 845 1555 276 177 513 1585 2751

3 3 2 2 5 1 5 5 4

RSBH

8 32 8 16 16 32

200 200 400 100 400 400

2 5 3 1 5 8

3 6 4 2 5 9

5 8 8 3 10 12

7 9 9 4 14 15

998 6520 1809 1444 4512 11364

5 4 7 2 7 7

StealthInk

16 32 64 8 8 16 16 32 64

200 200 200 100 400 100 400 400 400

4 4 5 2 8 2 9 9 11

4 4 6 2 8 2 9 9 11

14 14 16 6 32 7 33 32 37

15 14 16 7 46 7 38 37 39

3038 3008 6450 642 3326 1443 6172 6125 12529

3 3 3 3 6 2 6 6 5

XMark

16 32 64 8 16 16 32 64

200 200 200 400 100 400 400 400

2 2 2 4 1 4 4 4

9 9 9 15 5 16 16 17

9 9 9 18 5 17 18 18

146 156 154 302 80 263 280 275

3 3 3 6 2 6 6 6

CycleShift

8 32

200 200

1 1

3 2

25 29

3 3

Table 5: Wall-clock cost of the attack per rewritten text, in seconds on one H100, for the τ = 0 rule, the number of oracle queries per rewrite, and the corpus-generation time in minutes (mean over generators). ↓: lower is better. exact target match (%) ↑

facts kept ↑

own, 8 own, 16 n, 8 n, 16 judges ↑ NLI ↑ numbers entities

Generator

Text

Llama-2-7B

paraphrase τ = 0, block incl. source τ = 0, rewrite-only block + fact protection

100 100 100

100 100 90

100 100 100

99 99 93

4.21 2.76 2.76 3.10

0.74 0.51 0.50 0.59

0.85 0.07 0.08 0.66

0.83 0.21 0.24 0.56

Llama-3.1-8B paraphrase τ = 0, block incl. source τ = 0, rewrite-only block + fact protection

100 100 100

100 100 95

100 100 100

99 100 95

4.17 3.10 3.08 3.53

0.75 0.60 0.60 0.67

0.80 0.13 0.15 0.71

0.77 0.34 0.37 0.69

paraphrase τ = 0, block incl. source τ = 0, rewrite-only block + fact protection

100 100 98

96 94 88

100 100 98

96 97 89

4.32 2.26 2.29 2.90

0.79 0.48 0.48 0.61

0.72 0.05 0.06 0.60

0.85 0.32 0.34 0.66

paraphrase τ = 0, block incl. source τ = 0, rewrite-only block + fact protection

100 100 99

97 98 86

100 100 100

98 100 94

4.54 2.51 2.54 3.12

0.81 0.55 0.54 0.67

0.80 0.08 0.06 0.66

0.89 0.35 0.38 0.71

Qwen3.5-4B

Qwen3.5-9B

Table 6: Per-generator fidelity results for the plain paraphrase, the rule of Table 1 (τ = 0, 4-gram block over the whole input), the same rule with the block over the rewrite only, and the latter with fact protection (κ = 0.5). Judges: mean of the two LLM judges. NLI: mean of support and coverage. ↑: higher is better.

Relabelings and the general ambiguity bound

(A2) Observations through the controlled accounts. The transcript O records all queries and responses available to the attack. The accounts generate responses according to (P1), and the attack may choose accounts, contexts, prompts, and when to stop from its earlier observations. Exact next-token distributions are also allowed as responses. Sample responses use fresh sampling randomness independent of the key and of the attack’s private randomness, with the conditional token laws specified by (P1). All queries finish and the attack outputs a finite text almost surely. There is no additional key-dependent information outside O. The attack’s private random seed R, containing all of its random choices, is independent of K before observations are collected. Its output is A(O, R), and the notation A(O) in the theorem leaves R implicit.

The main text avoids group notation and states the binary count directly in Theorem 1. This appendix gives the general symmetry argument behind that result. It also makes explicit the assumptions on the hidden-key distribution and on the decoder’s treatment of labels, including ties. Let K be the key space and M the message space. A relabeling group (G, ◦) acts on both spaces: every g ∈ G induces maps ρK g : K → K and ρM : M → M. We write both as ρg (x) beg cause the argument identifies the space. With identity e and inverse g −1 , the action satisfies ρe (x) = x, ρg◦h (x) = ρg ρh (x) ,

(33)

ρ (m) Gρgg (K) (c) = Gm K (c).

(A3) Equivariant decoder. The decoder returns a message or an abstention symbol ⊥, and for every key k, text z, message b, and g ∈ H,

The first two identities hold for x ∈ K ∪ M and the last for every key, message, relabeling, and context. Thus renaming the hidden key structure and the message together leaves every green list unchanged. For the controlled messages M = (1) (n) (m , . . . , m ), define the relabelings that preserve all their public names by

Pr[Dρg (k) (z) = ρg (b)] = Pr[Dk (z) = b].

These probabilities are only over the decoder’s own fresh randomness, independent of the attack and of generation. For a deterministic decoder, this is the identity Dρg (k) (z) = ρg (Dk (z)). We extend the action by ρg (⊥) = ⊥.

HM := {g ∈ G : ρg (m(i) ) = m(i) for every i}. (34) The messages indistinguishable from a target m′ under these remaining symmetries form OrbHM (m′ ) := {ρg (m′ ) : g ∈ HM }.

Public model and sampling settings are fixed throughout, and independent public randomness can be included in R. Let

(35)

Appendix O gives concrete examples of a relabeling that remains in HM and one that the controlled messages exclude.

B := OrbH (m′ ),

(38)

1 . N

(39)

Pr[DK (A(O, R)) = m′ | O] ≤

The inequality holds almost surely in O. The probability includes the key, account sampling, attack randomness, and any decoder randomness. “Almost surely” means that the inequality may exclude observations in a set of total probability zero. In particular, it holds at every discrete observation o with Pr[O = o] > 0.

(A1) Invariant key prior. The key K has a probability distribution µ satisfying (g ∈ H)

N := |B| < ∞.

Then

Full symmetry statement for Theorem 1. Fix the controlled messages M = (m(1) , . . . , m(n) ), a target m′ , and a finite relabeling group satisfying (33). Write H := HM and assume the following.

µ(ρg (B)) = µ(B)

(37)

(36)

for every measurable set of keys B ⊆ K, where ρg (B) := {ρg (k) : k ∈ B}. Thus a set of keys and its relabeling have the same prior probability.

Proof. We first show that even the attack’s complete view, including its seed, leaves the key distribution invariant under H. We then show that the 28

decoder assigns equal conditional probabilities to every message in B, and sum those probabilities.

of this completion is pρg (k),m(i) (w)

Step 1: check the group operations used below. The action identities in (33) give, for any key or message x, ρg−1 (ρg (x)) = ρg−1 ◦g (x) = x, ρg (ρg−1 (x)) = ρg◦g−1 (x) = x.

(c)

(i) = Gm (c). k

(44) pk,m(i) (wt | ct (w<t ))

The first and last equalities are the autoregressive sampling rule, and the middle equality applies (43) to each factor. The identity includes zeroprobability sequences. If the response stops at an end token or a public length limit, the same stopping rule is applied to the same sequence, so the resulting response laws still agree. Step 3: preserve this equality under adaptive queries. Fix the private seed at R = r. Once this seed is fixed, each next query and the decision to stop are deterministic functions of the preceding transcript. Write Tj for the transcript after j queries, with T0 empty. For a possible preceding transcript t, denote the next query by qj (r, t). Denote its response distribution under key k by Qk (· | qj (r, t), t). Step 2 gives, for every response event F ,

Step 2: show that each account response is unchanged. Fix g ∈ H, a key k, an account i, and a context c. The stabilizer condition and (33) give ρ (m(i) )

pρg (k),m(i) (wt | ct (w<t ))

= pk,m(i) (w).

ρg◦h (m(i) ) = ρg (ρh (m(i) )) = ρg (m(i) ) = m(i) . (41) Hence g ◦ h ∈ H. If g ∈ H, applying ρg−1 to ρg (m(i) ) = m(i) gives ρg−1 (m(i) ) = m(i) , so g −1 ∈ H as well. This verifies that H is a subgroup. It also gives m′ = ρe (m′ ) ∈ B, so N ≥ 1 and division by N is valid.

(i)

t=1 T Y t=1

(40)

Thus ρg is a bijection with inverse ρg−1 . The identity fixes every controlled message, so e ∈ H. If g, h ∈ H, then for each i,

g Gm ρg (k) (c) = Gρg (k)

T Y

Qρg (k) (F | qj (r, t), t)

(42)

= Qk (F | qj (r, t), t).

(45)

For ordinary fresh sampling this kernel is the distribution from Step 2. Writing the history explicitly also accommodates repeated contexts and queries chosen using earlier responses. We do not require different queries to concern different contexts. We prove equality of transcript laws by induction on j. It holds at j = 0 because both transcripts are empty. Suppose it holds after j − 1 queries, and call the common law ηj−1 . For an event E of extended transcripts, the probability after the next query under key k is Z Z 1{(t, qj (r, t), a) ∈ E} (46) · Qk (da | qj (r, t), t) ηj−1 (dt).

The first equality uses ρg (m(i) ) = m(i) , and the second relabels the key and message together. By (P1), for every token v, (i) pρg (k),m(i) (v | c) = Φ p(· | c), Gm ρg (k) (c) (v) (i) = Φ p(· | c), Gm (c) (v) k = pk,m(i) (v | c). (43) Here Φ(p, S)(v) denotes the probability of v in the distribution returned by Φ. The base distribution and the rule Φ are the same in both experiments because they are key-independent. Consequently, a query returning the entire nexttoken distribution has exactly the same answer. A query sampling a token has the same answer distribution. For a completion w = (w1 , . . . , wT ), fix the query prompt and let ct (w<t ) be the context determined by that prompt and prefix. The probability

The expression under key ρg (k) has the same outer measure by the induction hypothesis, the same query because r, t are fixed, and the same inner measure by (45). The two probabilities are therefore equal, completing the induction. 29

Stopping causes no exception: at a fixed r, t, both experiments make the same stopping decision. Equivalently, append a fixed stop symbol at every subsequent round once the attack stops. The preceding induction then applies to these padded transcripts. Since termination occurs after finitely many queries almost surely, every event of final transcripts is the disjoint union of its parts with stopping times 0, 1, 2, . . .. Equality for each part gives equality for their sum. Thus, for every transcript event E, Pr[O ∈ E | K = ρg (k), R = r] = Pr[O ∈ E | K = k, R = r].

gives Pr[K ∈ ρg (B) | V = v] = Pr[K ∈ B | V = v]. (51) For general observations, including real-valued distribution responses, we use a regular conditional distribution µv (B) := Pr[K ∈ B | V = v]. To see why the same conclusion holds, let PV be the law of V and rewrite (50) as Z µv (ρg (B)) PV (dv) C Z (52) = µv (B) PV (dv).

(47)

This holds for every view event C. Two measurable functions with equal integrals over every event C are equal almost everywhere: otherwise, on an event where one exceeds the other by at least 1/j for some integer j ≥ 1, their integrals would differ. Applying this fact gives (51) almost surely in v. The key and observation spaces here are finite or countable products of discrete and real-valued spaces, on which these conditional distributions exist. Equality can first be imposed on a countable generating algebra of key events, then extended to all measurable events by uniqueness of probability measures. Since H is finite, one common set of views of probability one works for every g ∈ H. In particular, at each such view and for every bounded measurable function f of the key, Z Z f (ρg (k)) µv (dk) = f (k) µv (dk). (53)

This proves likelihood invariance for the whole adaptive experiment, including exact distribution responses, whose laws are point masses. Step 4: derive invariance of the conditional key distribution. Let V := (O, R) be the attack’s complete view, including the private seed. Although R and K are independent initially, they need not remain independent after conditioning on O. We therefore retain R in V . For an event C of complete views, put LC (k) := Pr[V ∈ C | K = k]. Let ν be the initial law of R and write Cr := {o : (o, r) ∈ C}. Independence before querying gives Z LC (k) = Pr[O ∈ Cr | K = k, R = r], ν(dr). (48) Equation (47) holds for each fixed seed, so integrating it against this same ν yields LC (ρg (k)) = LC (k).

Indeed, (51), applied to g −1 ∈ H, says that ρg (K) and K have the same conditional distribution. Expectations of the same function under equal distributions coincide.

(49)

For a set of keys B, the definition of conditional probability gives Z Pr[K ∈ ρg (B), V ∈ C] = LC (k) µ(dk) ρg (B) Z = LC (ρg (k)) µ(dk) ZB = LC (k) µ(dk)

Step 5: make the decoder’s symmetry explicit, including ties. For a fixed key and text, define the decoder probabilities dk (z, b) := Pr[Dk (z) = b].

(54)

If the decoder is deterministic, dk (z, b) is the indicator of Dk (z) = b. Assumption (A3) states that dρg (k) (z, ρg (b)) = dk (z, b). (55)

= Pr[K ∈ B, V ∈ C]. (50) The second line changes variables through the bijection ρg , and (A1) says that this change preserves µ. The third line uses (49). For a discrete view v with positive probability, set C = {v} in (50) and divide by Pr[V = v]. This

We explain how this condition follows for a common membership-based scoring rule, and why its tie rule matters. 30

For a fixed text z = (z1 , . . . , zT ), let ct be its scoring contexts and put T βk (z, b) := 1{zt ∈ Gbk (ct )} t=1 . (56)

instead the decoder abstains whenever there is a tie, both relabeled experiments abstain, since their tied sets have the same size. With ρg (⊥) = ⊥, this also satisfies (A3). A deterministic preference for the largest or smallest label need not do so. For other decoder architectures, (A3) is the condition required, since (P2) alone does not establish their tie behavior.

For each t, (33) gives ρ (b)

1{zt ∈ Gρgg (k) (ct )} = 1{zt ∈ Gbk (ct )}.

(57)

Equality at every coordinate gives βρg (k) (z, ρg (b)) = βk (z, b).

Step 6: show equality of conditional decoding probabilities. Fix a complete view v = (o, r) in the probability-one set from Step 4. The attack’s rewritten text

(58)

Suppose each candidate is evaluated by the same public function, sk (z, b) := s(z, βk (z, b)).

z := A(o, r)

(59)

is now fixed. Relabeling a key in its conditional distribution does not change o, r, or this text. For every message b, put

(60)

pv (b) := Pr[DK (A(O, R)) = b | V = v] Z (66) = dk (z, b) µv (dk).

Substitution then yields sρg (k) (z, ρg (b)) = sk (z, b).

The use of the same function for every candidate is part of this sufficient condition. A candidatedependent public preference is not justified by key access through memberships alone. For a maximizing decoder, write Ek (z) := arg max sk (z, b). b∈M

(65)

The second line averages the decoder’s probabilities over the conditional key distribution. It uses the fact that the decoder’s fresh randomness is independent of the view once its key and input are fixed. For any g ∈ H, compute

(61)

If b ∈ Ek (z), then sk (z, b) ≥ sk (z, a) for every a ∈ M. Equation (60) implies

Z pv (ρg (b)) =

sρg (k) (z, ρg (b)) ≥ sρg (k) (z, ρg (a))

for every a. (62) Because ρg is a bijection on messages, ρg (a) ranges over all candidates. Thus ρg (b) ∈ Eρg (k) (z). This proves one inclusion in Eρg (k) (z) = ρg (Ek (z)).

1{b ∈ Ek (z)} . |Ek (z)|

dρg (k) (z, ρg (b)) µv (dk)

(67)

Z =

dk (z, b) µv (dk)

= pv (b).

(63)

For the reverse inclusion, take b′ ∈ Eρg (k) (z) and apply the same argument to the key ρg (k) and the element g −1 . It gives ρg−1 (b′ ) ∈ Ek (z), hence b′ ∈ ρg (Ek (z)) as required. For a minimizing decoder, replace each score inequality above by ≤, and both inclusions follow in exactly the same way. If the extremum is unique, (63) relabels that unique output, proving (55). For a finite nonempty tied set, uniform tie breaking gives dk (z, b) =

dk (z, ρg (b)) µv (dk) Z

The first and last lines use (66). The second line applies (53) to the bounded function f (k) = dk (z, ρg (b)). The third line applies (55) at each key. Notice that the target is not relabeled in the actual attack. The calculation compares the probabilities of different decoder outputs for the same fixed text z. Step 7: sum over the distinct messages in the orbit. By definition of B, each b ∈ B has the form b = ρg (m′ ) for some g ∈ H. Substituting m′ for b in (67) therefore gives pv (b) = pv (m′ ) for every b ∈ B. There are N distinct messages in this set. The events that the decoder outputs each of these messages are pairwise disjoint: one decoder run

(64)

Equation (63) preserves membership in the tied set and its cardinality, so it again gives (55). If 31

returns at most one message. Consequently, X N pv (m′ ) = pv (b) b∈B

= Pr[DK (z) ∈ B | V = v]

same probability, so the relabeled pair is again uniform. The transformation acts separately at each context, preserving independence across contexts, and repeated contexts still read the same assignment. This proves invariance of the entire ideal key table. For a concrete finite-seed pseudorandom implementation, a uniform seed by itself does not prove that the induced table distribution has this exact symmetry. The information-theoretic conclusion above uses (A1).

(68)

≤ 1. We sum over distinct messages, not group elements: several relabelings can send m′ to the same message and must not be counted repeatedly. Dividing by N ≥ 1 proves Pr[DK (A(O, R)) = m′ | O, R] ≤

1 . N

Why the condition on ties cannot be dropped. Consider two-bit messages, a single controlled message (0, 1), and the relabeling

(69)

ρg (b1 , b2 ) = (1 − b2 , 1 − b1 ).

This inequality holds almost surely in (O, R). The inequality in (68) allows the decoder to output messages outside B or to abstain. Thus we have not assumed that its total probability on this orbit is one.

This is a position swap together with a flip at each position in the binary group described in the main text. It fixes (0, 1), so g ∈ H, but it interchanges (0, 0) and (1, 1). With one controlled message, a stabilizing relabeling has its color flips determined by its position permutation. There are just two position permutations here: the identity gives the identity relabeling, and the swap gives g. Therefore

Step 8: average over the attack’s private randomness. Let E := {DK (A(O, R)) = m′ } be the success event. Because conditioning on (O, R) includes conditioning on O, the law of iterated conditional expectation gives

OrbH ((1, 1)) = {(1, 1), (0, 0)}.

Pr[E | O] = E[1E | O]

(72)

On an empty text all vote counts are zero. A decoder that resolves every tied bit toward 1 returns (1, 1) for every key. Its success probability for that target is 1, exceeding the purported bound 1/2. The equivariance assumption excludes precisely this failure. The example concerns exact decoding, and it does not claim that an empty text passes watermark acceptance or preserves a source’s content.

= E[E[1E | O, R] | O] = E[Pr[E | O, R] | O] 1 O ≤E N 1 = . N

(71)

(70)

The inequality substitutes (69) and uses monotonicity of conditional expectation. The last equality holds because M and m′ are fixed, so their orbit size N is fixed. This averaging uses the actual conditional law of R given O, and it does not assume that the seed remains independent of the key after observation. Replacing N by its definition in (38) gives the claimed general bound.

Source texts and unlabelled observations. The attacker of Section 3 also observes the source y. To apply the theorem, include it in the observation: A(O, R) = A(y, m′ , OM , R). (73) Here the fixed target is left implicit on the left-hand side. If y is generated under a controlled message, Step 2 applies directly. If y is generated independently of the key and the account experiment, it also preserves the likelihood invariance. A source under a different unknown message requires an additional assumption, because simply not revealing its message does not imply symmetry. For example, let U = (U1 , . . . , Us ) be the unknown messages of all additional watermarked texts. Define the joint relabeling O = (y, OM ),

When the ideal-key assumption applies. Assumption (A1) is a distributional requirement, not a consequence of the algebraic identity (33) alone. In the binary position–color idealization, at each context the position is uniform on [L] and the balanced two-color partition is uniform, independently of that position and of the assignments at other contexts. A position permutation and per-position color flips define a bijection of the possible (position, partition) pairs. Each pair originally has the

(K, U ) 7−→ (ρg (K), ρg (U1 ), . . . , ρg (Us )). (74) 32

ties is bounded by 1/N . To transfer that bound to accepted outputs of the released decoder, one must establish that acceptance excludes all the relevant ties, and the presence of an acceptance threshold alone does not establish this. Finally, when N = 1 the bound is 1 and places no restriction on success. When N > 1, Step 7 identifies the obstruction: all N orbit messages have equal conditional decoding probability. The theorem supplies an upper bound, not an attack attaining it. In particular, a singleton orbit alone does not prove that a content-preserving successful rewrite exists.

Suppose their joint prior is invariant under this map for every g ∈ H. An invariant key prior with independent uniform Uj on a finite message space is one sufficient choice: the map permutes that message space, so it preserves each uniform distribution and their product. For each additional text, (33) gives ρ (u )

Gρgg (k)j (c) = Gk j (c).

(75)

Thus the response likelihood is invariant when key and hidden messages are relabeled together. Step 3 applies to this enlarged hidden state, and Step 4 gives invariance of its posterior. Taking a posterior event of the form {K ∈ B, U ∈ Ms } then gives invariance of the marginal posterior of K, since the full message space maps to itself. Steps 5–8 therefore prove the same bound conditional on all these observations. If an extra source message is known, it should instead be added to M , and the orbit recomputed under the resulting smaller stabilizer. An arbitrary fixed or nonuniform unknown source message is not covered without the stated joint symmetry.

We make the binary position–color setting of Section 3 explicit, verify that its relabelings form a group acting as (33) requires, determine the stabilizer HM of the controlled messages exactly, and count the orbit of the target. Throughout, (u + w) mod 2 denotes the sum of the bits u and w reduced modulo 2, so that (u + u) mod 2 = 0. Since (u+w) mod 2+z mod 2 = (u+w+z) mod 2, a reduction inside a longer sum may be postponed to the end, and we do so without comment. On bit vectors the reduction acts coordinatewise.

Content constraints, acceptance, and the meaning of the bound. The proof applies to every output text A(O, R), so restricting the attacker to content-preserving rewrites of y, as condition (ii) of its goal in Section 3 demands, cannot invalidate the upper bound when y is included in O as above. A deployment may also apply a keyed acceptance test AccK (z) ∈ {0, 1}, which decides whether a text is watermarked at all, before it attributes the text to the decoded message, and the attacker’s goal in Section 3 omits this test. The bound covers it nonetheless: for Z := A(O, R), Pr[DK (Z) = m′ , AccK (Z) = 1 | O] 1 ≤ Pr[DK (Z) = m′ | O] ≤ . N

Binary ambiguity count

Closed-form count.

Fix the following.

(S1) Messages, keys, and sets. The message space is M = {0, 1}L . A key K assigns to every context c a position JK (c) ∈ [L] and a coloring CK (c, ·) : V → {0, 1}, and the green list of message m at c is Gm K (c) = {v : CK (c, v) = mJK (c) }, as in (3). (S2) Relabelings. An element of G is a pair g = (σ, f ) of a permutation σ ∈ SL of the positions and a flip vector f ∈ {0, 1}L . It acts on messages and keys as follows, where the first line holds for every j ∈ [L],

(76)

The first inequality follows because the event on the first line is a subset of the exact-decoding event. It requires no symmetry of the acceptance rule when DK itself satisfies (A3). This is a bound on joint success and acceptance, not on the success probability conditional on acceptance. For a released decoder with a label-dependent tie rule, apply the theorem instead to the decoder that abstains whenever the relevant extremum is not unique. On texts without such ties the two decoders agree, so the joint event of exact success and no

ρg (m) σ(j) = (mj + fj ) mod 2, Jρg (K) (c) = σ JK (c) ,

Cρg (K) (c, v) = CK (c, v) + fJK (c) mod 2. (77) Thus the bit at position j moves to position σ(j) and is flipped exactly when fj = 1, and the key renames its positions by σ and exchanges the two color names at every context whose position j has fj = 1. The identity is e = (id, 0), and the product of g = (σg , f g ) 33

and h = (σh , f h ) is g ◦ h = σg ◦ σh , f g◦h , fjg◦h = fjh + fσgh (j) mod 2.

which is the action of g ◦ h on K. Hence ρg◦h = ρg ◦ ρh on messages and keys, and together with ρe = id these are the first two identities of (33). Every g = (σ, f ) has the inverse g −1 = (σ −1 , f ′ ) ′ with fσ(j) = fj , that is, fk′ = fσ−1 (k) . Indeed, by (78) the product g ◦ g −1 has permutation σ ◦ σ −1 = id and flips (fk′ + fσ−1 (k) ) mod 2 = 0 at every k, and g −1 ◦ g has permutation id and ′ flips (fj + fσ(j) ) mod 2 = 0 at every j, so both products equal e. The action on messages is faithful: if ρg (m) = m for every m, then m = 0 gives fj = [ρg (0)]σ(j) = 0 for every j, and then [ρg (m)]σ(j) = mj for every m forces σ(j) = j, as the unit vector m with a single one at position j shows. Therefore g 7→ ρg is an injective map from G to the bijections of {0, 1}L that sends ◦ to composition, e to the identity, and g −1 to the inverse, so ◦ inherits associativity from composition and (G, ◦) is a group. It has 2L L! elements and is therefore finite. Finally, for the last identity of (33) put j = JK (c). Then Jρg (K) (c) = σ(j), and by (77) the membership condition Cρg (K) (c, v) = [ρg (m)]σ(j) reads CK (c, v) + fj mod 2 = (mj + fj ) mod 2. (82) Adding the same bit fj to both sides of an equation modulo 2 does not change its solutions, so (82) holds exactly when CK (c, v) = mj . Hence

(78)

(S3) Signatures and twin classes. For the controlled messages M = (m(1) , . . . , m(n) ) and every position j, the account signature is (i) xj = (xj,2 , . . . , xj,n ) with xj,i = (mj + (1)

mj ) mod 2, as in (5). Positions with equal signatures are twins, T is the partition of [L] into twin classes, and for the target m′ the rel(1) ′ ative bits P are rj = (mj + mj ) mod 2, with aT = j∈T rj for T ∈ T . Then (G, ◦) is a finite group, the action (77) satisfies (33), and the orbit of m′ under the stabilizer HM of (34) has size Y |T | ′ | OrbHM (m )| = . (79) aT T ∈T

Proof. We first check that (77) is a group action with the equivariance property, so that the general bound of Appendix K applies. We then determine HM exactly, pass to coordinates relative to the reference message, and count. Step 1: verify the group action and the equivariance identity. The identity acts trivially: with e = (id, 0), (77) gives [ρe (m)]j = mj , Jρe (K) = JK , and Cρe (K) = CK , so ρe (x) = x for every message and key x. For the composition, fix g, h, and a message m. Applying (77) twice, ρg (ρh (m)) σg (σ (j)) h = ρh (m) σ (j) + fσgh (j) mod 2 h (80) = mj + fjh + fσgh (j) mod 2 = mj + fjg◦h mod 2,

ρ (m) Gρgg (K) (c) = v : Cρg (K) (c, v) = [ρg (m)]σ(j) = v : CK (c, v) = mj = Gm K (c). (83) By Step 1 of Appendix K, which used only the identities (33), every ρg is therefore a bijection with inverse ρg−1 , and HM is a subgroup of G. Step 2: determine the stabilizer. Let g = (σ, f ) ∈ G. By (77), ρg (m(i) ) = m(i) holds ex(i) actly when [ρg (m(i) )]σ(j) = mσ(j) for every j, that is, when

which is [ρg◦h (m)](σg ◦σh )(j) by (77) and (78). For a key, Jρg (ρh (K)) (c) = σg Jρh (K) (c) = σg σh (JK (c)) ,

(i)

(j ∈ [L]). (84)

We use (84) first for the reference account and then (1) for the others. For i = 1, adding mj to both sides of (84) modulo 2 and using (u + u) mod 2 = 0 (1) (1) gives fj = (mj + mσ(j) ) mod 2 for every j. Hence the flips of an element of HM are determined by its permutation, and we write (1) (1) fjσ := mj + mσ(j) mod 2 (j ∈ [L]). (85)

Cρg (ρh (K)) (c, v) = Cρh (K) (c, v) + fJg

(i)

(mj + fj ) mod 2 = mσ(j)

mod 2 = CK (c, v) + fJhK (c) + fσgh (JK (c)) mod 2 = CK (c, v) + fJg◦h mod 2, K (c) (81) ρh (K) (c)

For i ≥ 2, substitute f = f σ into (84) and add (1) mσ(j) to both sides modulo 2. By (85) and (u + u) mod 2 = 0, the left side becomes (i) (1) mj + fjσ + mσ(j) mod 2 (i) (1) = mj + mj mod 2 = xj,i ,

(u + u) mod 2 = 0, r(ρg (m′ )) σ(j) (1) = ρg (m′ ) σ(j) + mσ(j) mod 2 (1) = m′j + fjσ + mσ(j) mod 2 (1) = m′j + mj mod 2 = rj ,

(86)

and the right side becomes (1)

(i)

mσ(j) + mσ(j) mod 2 = xσ(j),i ,

that is, r(ρg (m′ )) = πσ (R): an element of the stabilizer moves the relative bits of the target along its permutation and flips none of them. Let O := {πσ (R) : σ ∈ ΣT }. Since r is a bijection and, by (89), σ ranges over ΣT as g ranges over HM ,

(87)

where both final equalities are the definition of the signatures in (S3). Adding the same bit to both sides of an equation modulo 2 is reversible, so for i ≥ 2 condition (84) is equivalent to xj,i = xσ(j),i . Requiring this for every i ∈ {2, . . . , n} says xσ(j) = xj , that is, σ(j) is a twin of j. Every step above is an equivalence, so we have shown

OrbHM (m′ ) = r−1 (O),

xσ(j) = xj for every j ∈ [L]. (88) Let ΣT be the set of permutations σ ∈ SL with xσ(j) = xj for every j. Such a σ maps every twin class T into itself, and since σ is injective and T is finite, σ(T ) = T . Thus σ restricts to a permutation σT of each class. Conversely, every family (σT )T ∈T of permutations σT ∈ S(T ) defines an element of ΣT by σ(j) = σT (j) for j ∈ T , because the classes partition [L] and σ(j) then has the signature of j. Identifying a permutation with its tuple of restrictions, we obtain Y

πσ (u) T = πσT u|T

(T ∈ T ).

(93)

Put OT := {πτ (R|T ) : τ ∈ S(T )}. We claim that O consists exactly of the vectors u with u|T ∈ OT for every T . If u = πσ (R) with σ ∈ ΣT , then (93) gives u|T = πσT (R|T ) ∈ OT for every T . Conversely, if u|T ∈ OT for every T , choose τT ∈ S(T ) with πτT (R|T ) = u|T , and let σ ∈ ΣT be the permutation with restrictions σT = τT , which exists by (89). Then (93) gives πσ (R)|T = u|T for every T , so πσ (R) = u and u ∈ O.QHence u 7→ (u|T )T ∈T maps O bijectively onto T OT , and Y |O| = |OT |. (94)

S(T ), (89)

T ∈T

| OrbHM (m′ )| = |O|. (92)

Step 4: decompose along the twin classes. Write u|T ∈ {0, 1}T for the restriction of a bit vector u to the coordinates in T . Because the classes partition [L], the map Qu 7→ (u|T )T ∈T is a bijection from {0, 1}L onto T {0, 1}T . For σ ∈ ΣT and k ∈ T we have σ −1 (k) ∈ T by Step 2, so (90) gives [πσ (u)]k = uσ−1 (k) = [πσT (u|T )]k , that is,

(σ, f ) ∈ HM ⇐⇒ f = f σ and

ΣT =

(91)

HM = {(σ, f ) : σ ∈ ΣT }, where the second line restates (88), and the map σ 7→ (σ, f σ ) is a bijection from ΣT onto HM .

T ∈T

Step 5: count within one twin class. Fix T ∈ T , put k = |T |, and let w⋆ = R|T , which has exactly aT coordinates equal to one by the definition of aT in (S3). We claim

Step 3: pass to coordinates relative to the reference message. For a message m define r(m) := (m + m(1) ) mod 2 coordinatewise, so that R := r(m′ ) = (r1 , . . . , rL ) is the vector of relative target bits of (S3). The map r is a bijection of {0, 1}L , since r(r(m)) = (m + m(1) + m(1) ) mod 2 = m. For σ ∈ SL and a bit vector u, let πσ (u) be the vector whose coordinates are those of u moved by σ, πσ (u) σ(j) := uj (j ∈ [L]). (90)

OT = w ∈ {0, 1}T : w has exactly aT ones . (95) Moving coordinates does not change how many of them equal one, so OT is contained in the right side. Conversely, let w have exactly aT ones, and let P = {j ∈ T : wj⋆ = 1} and Q = {j ∈ T : wj = 1}, two subsets of T with |P | = |Q| = aT and

Now let g = (σ, f σ ) ∈ HM . By (77), (85), and 35

hence |T \ P | = |T \ Q| = k − aT . Choose a bijection from P onto Q and a bijection from T \P onto T \ Q, and let τ be their union, a permutation of T . For j ∈ P , (90) gives [πτ (w⋆ )]τ (j) = wj⋆ = 1 with τ (j) ∈ Q, and for j ∈ T \ P it gives [πτ (w⋆ )]τ (j) = 0 with τ (j) ∈ / Q. Since τ is a bijection of T , the vector πτ (w⋆ ) equals one exactly on Q, so πτ (w⋆ ) = w and w ∈ OT . The right side of (95) is in bijection with the aT -element subsets of the k-element set T , so |T | |OT | = . (96) aT

on [L] across distinct contexts. The controlledaccount sets observed at c reveal the account signature xJK (c) , and therefore the twin class T (c), but not the position inside that class. The within-class symmetries proved in Appendix K assign equal posterior probability to every position in T (c). Independence across distinct contexts is preserved because the ideal key assigns them independently and the observations expose only their classes, and repeated occurrences of the same context share the same assignment. If no class was identified, the observation gives no position information and the posterior remains uniform on [L]. Consequently, the conditional law of the position map JK on the contexts of z is exactly ΠO . For a key K, define the true target vote of a scored pair by ( ′ +1, v ∈ Gm K (c), σK (c, v) := (98) ′ −1, v ∈ / Gm K (c).

Step 6: conclude. Substituting (96) into (94) and the result into (92) gives Y |T | ′ | OrbHM (m )| = |O| = , (97) aT T ∈T

which is (79). Together with (10), this identifies the main text’s N (M, m′ ) with the number of indistinguishable messages. As in Step 7 of Appendix K, the count is over distinct messages: several elements of HM may send m′ to the same message, which is why we counted the vectors in O rather than the permutations in ΣT . Substituting this identity into the general bound of Appendix K gives (11) and completes the proof of Theorem 1.

When the target set at c was recovered, the attacker’s vote σ(c, v) equals σK (c, v). When it was not recovered, the attacker sets σ(c, v) = −1, so in every case σ(c, v) ≤ σK (c, v). For the true assignment JK , let X MjK := σK (c, v)

Consequences used in themain text. For k ≥ 1 the binomial coefficient ka equals 1 exactly when a ∈ {0, k}, and a product of positive integers equals 1 exactly when every factor does. Hence the orbit is trivial if and only if aT ∈ {0, |T |} for every class, that is, if and only if the relative bits rj are constant on every twin class. Choosing this constant independently for each of the |T | classes gives 2|T | vectors r, and m′ = (r + m(1) ) mod 2 is a bijection between these vectors and the targets with a trivial orbit, so exactly 2|T | targets are reachable. When every position has a distinct signature, every class is a singleton and all 2L targets are reachable. Finally, (91) is the reason behind the construction (6): for a target with a trivial orbit, r takes a single value rT on each class, so the attacker needs only the class T (c) of a context to decide whether the target’s set at c is G1 (c) or its complement.

(99)

(100)

(c,v)∈P(z): JK (c)=j

be the decoder’s target margin at position j. Equations (99) and (100) give Mj (JK ) ≤ MjK

(j ∈ [L]).

(101)

Therefore, if E holds for the conservative tally, every position is covered and has MjK > 0. The strict-majority decoder must then output m′ at every position. Pointwise in the hidden key, 1{E(JK )} ≤ 1{DK (z) = m′ }.

(102)

Taking conditional expectations and using that JK | O ∼ ΠO yields Cert(z, m′ | O) = Pr [E] J∼ΠO

= Pr[E(JK ) | O]

(103)

≤ Pr[DK (z) = m′ | O], which proves the lower bound. If every target set used by z was recovered, then (99) is an equality for every pair. The strict-majority decoder outputs m′ exactly when every position is covered and has positive target margin, so (102) is also an equality. This proves the equality claim.

Proof of certificate validity

We prove Theorem 2 for a fixed observation O and rewrite z. In the ideal-key model, the hidden positions JK (c) are initially independent and uniform 36

The vote bound

(V3) Vote variables. Enumerate the pairs of position j as (cj,s , vj,s ) for s = 1, . . . , Nj , and put

The certificate of Section 3.2 evaluates the decoder’s vote tally exactly under the attacker’s posterior. The following bound complements it from the other side: it lower-bounds the success probability in terms of the true vote counts and vote biases, which the attacker cannot see, and explains why the constrained rule succeeds once enough contexts carry a target vote. We fix the setting with numbered assumptions, state the bound, and prove it in four steps: the vote probabilities of the two rewriting rules, the decoder’s success as an intersection of per-position majority events, Hoeffding’s inequality for each failure event, and a union bound over the positions.

Xj,s := 1{CK (cj,s , vj,s ) = m′j } ′

= 1{vj,s ∈ Gm K (cj,s )},

(105)

the two forms being equal by (3) because JK (cj,s ) = j. (V4) Independence and bias. Conditionally on the vote counts (Nj )j∈[L] , the variables Xj,s are independent, and there are numbers ρj > 1/2 with Pr[Xj,s = 1] ≥ ρj for every j and s. All probabilities below are conditional on (Nj )j∈[L] . Theorem 3 (Vote bound). Under (V1) to (V4), a pair drawn by (7) has Xj,s = 1 with certainty, a pair drawn by (8) at step t has Xj,s = 1 with probability qt eδatk /(qt eδatk + 1 − qt ), and

Setting. Fix a source y, a target m′ ∈ {0, 1}L , and a rewrite z = (z1 , . . . , zT ) of y produced by the rule of Section 3.1 for any threshold τ ≥ 0, with or without the 4-gram block, and assume the following.

′

Pr[DK (z) = m ] ≥ 1 −

(V1) Decoder. The decoder is the binary position– color decoder of (3). Let P(z) be the set of distinct context–token pairs (ct , zt ) of z, each pair counted once however often it occurs. Position j ∈ [L] receives the pairs with JK (c) = j, and for a color b ∈ {0, 1} its vote count is Vj (b) := # (c, v) ∈ P(z) :JK (c) = j,

L X

e−2Nj (ρj −1/2) .

j=1

(106) Proof. Step 1: compute the vote probabilities of the two rules. Let t be a step whose pair (ct , zt ) belongs to position j, so that JK (ct ) = j and Bt = ′ Gm K (ct ) by (V2). If zt is drawn from (7), then rt (v) = 0 for every v ∈ / Bt , so zt ∈ Bt with probability one and the pair’s vote variable equals ′ 1{zt ∈ Gm K (ct )} = 1. If zt is drawn from (8), then rt (v) = pt (v)eδatk /Zt for v ∈ Bt and rt (v) = pt (v)/Zt for v ∈ / Bt , with the normalizer X X Zt = pt (v)eδatk + pt (v) v∈Bt v ∈B / t (107) δatk = qt e + 1 − qt , P because v∈B / t pt (v) = 1 − qt . Summing rt over Bt ,

CK (c, v) = b , (104) so that Nj := Vj (0) + Vj (1) is the number of pairs at position j. The decoder outputs at position j the color b with Vj (b) > Vj (1 − b) whenever such a color exists, and DK (z) = m′ requires this output to be m′j at every position. (V2) Rewrite rule and recovered sets. The orbit of m′ is trivial and the attacker has re′ covered every target set Gm K (c) exactly, so that at every step t the target-compatible set ′ is Bt = Gm K (ct ), since the decoder of (V1) rewards membership in the target’s set. Token zt is drawn from the constrained distribution (7) when qt ≥ τ and Bt contains an available token, and otherwise from the soft bias (8), where pt is the paraphraser’s distribution at step t, after the 4-gram block has removed P its tokens if the block is in use, and qt = u∈Bt pt (u).

Pr[zt ∈ Bt ] =

qt eδatk , qt eδatk + 1 − qt

(108)

which is the stated probability. When the 4-gram block removes tokens, pt denotes the blocked and renormalized distribution, and both computations apply unchanged with its qt . Since eδatk > 1, the probability (108) exceeds qt , and it exceeds 1/2 exactly when qt eδatk > 1 − qt . Step 2: express the decoder’s success through the vote sums. Fix a position j and put Sj := 37

PNj

Step 4: combine theP positions. The union bound S L gives Pr[ j Fj ] ≤ j=1 Pr[Fj ], and inserting (115) into (111) yields

s=1 Xj,s . Every pair at position j has one of the two colors, so (104) and (105) give

Vj (m′j ) = Sj ,

Vj (1−m′j ) = Nj −Sj . (109)

′

By (V1), the decoder outputs m′j at position j whenever Vj (m′j ) > Vj (1 − m′j ), that is, whenever

Pr[DK (z) = m ] ≥ 1 −

(116) which is (106). The bound is informative only when the sum is below one, and it needs no assumption on how the decoder resolves ties, because Step 2 counted a tie as a failure.

(110)

If Nj = 0, then Sj = 0 and Fj is certain, which matches the fact that an empty position has no majority. If no Fj occurs, every position outputs m′j and DK (z) = m′ . Hence {DK (z) = m′ } ⊇

L \

Reading the bound. Under the rule with τ = 0 and every set recovered, Step 1 gives Xj,s = 1 for every pair, so = 1 is admissible and the P ρj−N bound reads 1− j e j /2 , a smooth relaxation of the exact statement that the decoder then succeeds as soon as every position receives a pair. Under the fallback (8), ρj can be taken as the smallest probability (108) over the fallback steps of position j, provided it exceeds 1/2, and the bound then says how many votes a position needs before its majority is reliable. The attacker cannot evaluate (106) itself, because it does not know the positions JK (c) and hence the counts Nj , which is why Section 3.2 certifies a rewrite from the posterior over the twin classes instead.

Fjc ,

j=1 L h[ i Pr[DK (z) = m′ ] ≥ 1 − Pr Fj .

(111)

j=1

The inclusion is an equality when the decoder never outputs m′j from a tie, which the strict majority rule of (V1) guarantees, but the inequality is all the proof needs. Step 3: bound each failure event by Hoeffding’s inequality. Hoeffding’s inequality (Hoeffding, 1963) states that for independent random Pvariables Y1 , . . . , YN with 0 ≤ Ys ≤ 1 and S = N s=1 Ys ,

(u > 0). (112) Fix j with Nj ≥ 1. By (V4) the Xj,s are independent, take values in {0, 1}, and satisfy E[Sj ] =

Pr[Xj,s = 1] ≥ Nj ρj .

(113) O.1

s=1

Common setup

Let the message space be M = {0, 1}3 and the vocabulary be V = {a, b, c, d}. At every context c, the key selects a message position JK (c) ∈ {1, 2, 3} and assigns each token a color CK (c, v) ∈ {0, 1}. The green list is

On Fj we have Sj ≤ Nj /2, so by (113) Sj −E[Sj ] ≤

Worked examples of relabelings and stabilizers

This appendix works through two relabelings of a binary position–color watermark. The first survives after the controlled-account messages are known and therefore lies in HM , while the second is a valid symmetry of the watermark, but is ruled out by those messages. Both are pure position relabelings: their per-position color-flip vector is zero.

2 Pr S − E[S] ≤ −u ≤ e−2u /N

Nj X

e−2Nj (ρj −1/2) ,

j=1

Sj > Nj − Sj , which is equivalent to Sj > Nj /2. Define the failure event Fj := {Sj ≤ Nj /2}.

L X

Nj 1 −Nj ρj = −Nj ρj − , (114) 2 2

and u := Nj (ρj − 1/2) is positive because ρj > 1/2. Applying (112) with N = Nj and this u, Pr[Fj ] ≤ Pr Sj − E[Sj ] ≤ −u (115) 2 2 ≤ e−2u /Nj = e−2Nj (ρj −1/2) .

Gm K (c) = {v ∈ V : CK (c, v) = mJK (c) }. (117) For a concrete context, suppose JK (c) = 2,

If Nj = 0, then Pr[Fj ] = 1 = e0 , so (115) holds for every position.

m = (0, 1, 1),

and let the token colors be 38

(118)

token v

CK (c, v)

Substituting this identity and the unchanged colors into (117) yields Cρg (K) (c,v) ρg (m) Gρg (K) (c) = v : = [ρg (m)]J (c)

The key reads mJK (c) = m2 = 1, so

ρg (K)

Gm K (c) = {v : CK (c, v) = 1} = {c, d}. (119)

= {v : CK (c, v) = mJK (c) } = Gm K (c).

Finally, suppose that the attacker controls two accounts with messages m(1) = (0, 1, 1),

m(2) = (1, 0, 0),

(126) Moreover, σg is its own inverse. Thus g is an invertible, set-preserving relabeling, so g ∈ G.

(120)

and write M = (m(1) , m(2) ). O.2

Step 5. Check the controlled messages. Both controlled messages are fixed because their second and third bits agree:

A relabeling retained by the stabilizer

Let g swap the names of positions 2 and 3. Write this permutation as σg (1) = 1,

σg (2) = 3,

σg (3) = 2. (121)

Step 1. Relabel the message. The bit formerly called position j must appear at the new position σg (j). Hence ρg (m) σg (j) = mj ,

ρg (m(i) )

1 2

(0, 1, 1) (1, 0, 0)

g∈G O.3

and

g ∈ HM .

(127)

A relabeling excluded by the stabilizer

Now let h swap the names of positions 1 and 2:

Step 2. Relabel the key. The key must follow the same renaming of positions, while the token colors remain unchanged:

Cρg (K) (c, v) = CK (c, v).

m(i)

Therefore ρg (m(i) ) = m(i) for every controlled account, which is exactly the stabilizer condition in (34). Consequently,

ρg (m1 , m2 , m3 ) = (m1 , m3 , m2 ). (122) For example, (0, 1, 0) becomes (0, 0, 1).

Jρg (K) (c) = σg (JK (c)),

account

σh (1) = 2,

σh (2) = 1,

σh (3) = 3. (128)

Step 1. Relabel the message. As before, the old bit mj is moved to position σh (j): ρh (m) σ (j) = mj ,

(123)

In the concrete context of (118), the new key therefore selects position 3.

ρh (m1 , m2 , m3 ) = (m2 , m1 , m3 ). (129)

Step 3. Check the concrete green list. Here ρg (m) = (0, 1, 1) and ρg (m) J = ρg (m) 3 ρg (K) (c) (124) = 1 = m2 .

Step 2. Relabel the key. Apply the same position renaming to the key and leave its colors unchanged: Jρh (K) (c) = σh (JK (c)), Cρh (K) (c, v) = CK (c, v).

The colors have not changed, so the relabeled system again selects {c, d}.

(130)

Thus, in the concrete context, the old choice JK (c) = 2 becomes Jρh (K) (c) = 1.

Step 4. Verify the relabeling for every key, message, and context. Fix arbitrary K, m, c and put j = JK (c). Equations (122)– (123) give ρg (m) J = ρg (m) σg (j) (c)

Step 3. Check the concrete green list. The message becomes ρh (m) = (1, 0, 1), but the new key reads ρh (m) J = ρ (m) h 1 ρh (K) (c) (131) = 1 = m2 .

ρg (K)

= mj = mJK (c) . (125) 39

The selected bit and token colors are therefore unchanged, so the green list is again {c, d}. Step 4. Verify the relabeling for every key, message, and context. For arbitrary K, m, c, put j = JK (c). Then ρh (m) J = ρ (m) h (c) σ (j) h

ρh (K)

= mj = mJK (c) . (132) Together with Cρh (K) (c, v) = CK (c, v), this gives, for every K, m, c, ρ (m)

Gρhh (K) (c) = Gm K (c)

(133)

The permutation σh is also its own inverse, so h is a valid relabeling and h ∈ G. Step 5. Check the controlled messages. This time neither controlled message is fixed: account

m(i)

ρh (m(i) )

1 2

(0, 1, 1) (1, 0, 0)

(1, 0, 1) (0, 1, 0)

Already ρh (m(1) ) ̸= m(1) , so h fails the defining condition of HM . Hence h∈G O.4

but

h∈ / HM .

(134)

What the two examples show map

position renaming

in G?

in HM ?

g h

2↔3 1↔2

yes yes

yes no

Thus G contains all valid symmetries of the watermark, whereas HM contains only those symmetries that the known controlled-account messages do not rule out. These examples use pure position permutations. The full binary position–color group also permits a position permutation combined with per-position color flips, and such a combination is a different group element. Therefore h ∈ / HM excludes the particular pure swap defined above, not every relabeling whose position component swaps 1 and 2.

Use of AI assistants

We used large language models to help polish the presentation and writing of this manuscript and to assist in drafting portions of the implementation code. All substantive research decisions and core technical contributions, however, were made by the authors. 40

Pin It on Anyone: Certified Targeted Displacement of Multi-Bit LLM Watermarks Without the Key

Analyze & explore related research in Conceptio

Related documents