Edit Distance Robust Watermarks via Indexing Pseudorandom Codes
Authors: Noah Golowich
Ankur Moitra
Venue: NeurIPS 2024 poster (2024)
Keywords: Watermarking
pseudorandom codes
language models
Primary area: learning_theory
TL;DR: We introduce the first undetectable watermarking schemes for language models with robustness to adversarial substitutions, insertions and deletions.

Abstract: Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees. We aim for watermarks which satisfy: (a) undetectability, a cryptographic notion introduced by Christ, Gunn, & Zamir (2023) which stipulates that it is computationally hard to distinguish watermarked language model outputs from the model's actual output distribution; and (b) robustness to channels which introduce a constant fraction of adversarial insertions, substitutions, and deletions to the watermarked text. Earlier schemes could only handle stochastic substitutions and deletions, and thus we are aiming for a more natural and appealing robustness guarantee that holds with respect to edit distance.
  Our main result is a watermarking scheme which achieves both (a) and (b) when the alphabet size for the language model is allowed to grow as a polynomial in the security parameter. To derive such a scheme, we follow an approach introduced by Christ & Gunn (2024), which proceeds via first constructing pseudorandom codes satisfying undetectability and robustness properties analogous to those above; our codes have the additional benefit of relying on weaker computational assumptions than used in previous work.   Then we show that there is a generic transformation from such codes over large alphabets to watermarking schemes for arbitrary language models.

Edit Distance Robust Watermarks for Language Models
Noah Golowich nzg@mit. edu MIT
Ankur Moitra moitra@mit edu MIT
Abstract
Motivated by the problem of detecting Al-generated text, we consider the problem of watermarking the output of language models with provable guarantees. We aim for watermarks which satisfy: (a) undetectabiliry, a cryptographic notion intro- duced in [CGZ24] which stipulates that it is computationally hard to distinguish watermarked language model outputs from the model's 's actual output distribution; and (b) robustness channels which introduce constant fraction of adversarial insertions, substitutions, and deletions to the watermarked text. Earlier schemes could only handle stochastic substitutions and deletions, and thus are aiming for more natural and appealing robustness guarantee that holds with respect to edit distance.
Our main result is a watermarking scheme which achieves both undetectability and robustness edits when the alphabet size for the language model is allowed to grow as a polynomial in the security parameter. To derive such a scheme, we follow approach introduced in [CG24], which proceeds via first constructing pseudorandom codes satisfying undetectability and robustness properties analogous those above; our key idea is handle adversarial insertions and deletions by interpreting the symbols as indices into the codeword, which we call indexing pseudorandom codes. Additionally, assumptions than used in previous work. Then we show that there is generic transformation from such codes over large alphabets to watermarking schemes for arbitrary language models.
codes rely weaker computational
Introduction
The rapid increase in Al-generated content represents significant challenge for numerous societal institutions, ranging from education to social media. For instance, the ability of large language models such as GPT-4 to generate long bodies of text such as essays raises the possibility of increasing amounts of plagiarism, and the proliferation of Al-generated text, images, and videos on social media presents challenges regarding large-scale manipulation of online audiences. An important tool at our disposal in preventing the misuse of such content watermarking schemes, which are procedures that embed hidden patterns in Al-produced content using secret key. Watermarking schemes allow detection algorithm with the aid of the secret key to determine with high probability that the content was produced by the AI model. They do so without noticeably altering the content from the perspective of any algorithm not possessing the secret key.
Despite number of recently proposed watermarking schemes, taking both a theoretical perspective (e.g.. [CG724, CG24, 7am24, FGJ+23]) as well as a more empirical one (e.g., [KGW+23, KGW+24, KTHL223)), crucial challenge that remains elusive is that of ensuring the watermark be robust to
adversaries which can modify the generated content. watermarking scheme is of little use if too easy to change the model's output so to remove the watermark. On the other hand, sufficiently
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

resourceful adversary can simply train their own unwatermarked model. Thus it is necessary to strike a balance in terms of the power of adversaries which a watermarking scheme enjoys robustness. In this paper, we give the first watermarking schemes with provable robustness to adversaries that make a constant fraction of arbitrary substitutions, insertions, and deletions to the output. This is a substantial improvement over previous schemes [CG24), which could only tolerate a constant fraction of adversarial substitutions or constant fraction of i.i.d. deletions under additional stochasticity assumptions the language model. Our results therefore represent progress towards the overarching goal of constructing watermarking schemes which are robust to resource-limited adversaries.
1.1 Setup: watermarking schemes
We consider the task of watermarking the output of a language model Model, which is simply defined as mapping from a sequence of tokens t1,-..; 44-1 to a distribution over the next token.' Though we use the terminology "language model" and "text" throughout the paper, our framework can be used to model a host of autoregressive models including those for generation of images, audio, and videos (e.g., [YXK*22, TJY+ in addition to text. As this paper is theoretical in nature, we work only with this abstraction of an autoregressive model, keeping mind that single tokens could represent, e.g., sequences of letters [SHB16) or discretized patches of an image [YLK 22, RvdOV19].
watermarking scheme W for Model consists of a tuple of efficient algorithms.
W (Setup, Wat, Detect)
where Setup generates a secret key at random, Wat uses Model and the secret key to produce a sequence of text with a watermark embedded in it, and Detect uses the secret key to determine whether a given sequence of text is watermarked. Moreover, Detect has no knowledge of Model. W should satisfy the following three properties:
Undetectability | /CGZ24]: Text generated from the watermarking protocol Wat should be compu- tationally indistinguishable to text generated by the true model Model, to any polynomial-time algorithm which can repeatedly query either Wat or Model. (Other notions, namely distortion- freeness [KTHL23], have been considered in place of undetectability, but are significantly weaker; see Example A.1.)
Soundness: Any fixed sequence of text (not produced by Wat) should not be detected as water- marked, with high probability (over the generation of the secret key).
AdditRooustnesss A sequence which can be obtained by calling the watermarking procedure Wat and then making a constant fraction of adversarial edits (i.e., substitutions, insertions, and deletions) to its output will still be detected as watermarked by Detect with high probability.
Whereas several existing watermarking schemes achieve undetectability and soundness, the main contribution of our work construed, has long been recognized as essential for constructing useful watermarking schemes [ARC+01, ARH + 02], yet nearly all of the existing provable guarantees on watermarking do not yield robustness to any constant fraction of edits. We remark that some works (c.g.. [CGZ24]) can handle a subconstant fraction of edits. However, we argue that the right notion of adversary that which makes constant fraction of edits: there is relatively low bar for malicious adversary attempting to remove the watermark by changing the text at constant rate while avoiding significant quality degradations, such as randomly replacing 5% of words with a synonym. Moreover, even if an adversary is not actively trying to remove a watermark, it is reasonable to expect that an "honest" editor who is merely trying to improve the text's quality will introduce edits at constant rate. The lens of coding theory provides further motivation for recovering from such channels that introduce a constant fraction of errors: doing so is a longstanding gold standard in the field [GRS19].
achieve the notion of edit-robustness given above. Robustness, broadly
'Note also that it is typically assumed that Model takes as input prompt: for simplicity, we absorb such a prompt in the definition Model, which technically introduces a different model for each possible prompt. Nothing in our results changes if we instead explicitly allow Model to take as input a prompt. (In particular, our watermarking detection algorithms do not assume any knowledge of Model, and therefore of the prompt.)
Inn the setting text, transforming a token sequence to readable text (i.e., sequences letters) and then back to tokens may not necessarily recover the original token sequence. Any errors induced via this transformation would likely be of small edit distance, and therefore we incorporate them part of the adversary for which our watermarks have robustness. See also [KGW*23 Section for related discussion "tokenization attacks".

---

The only prior work in the literature which obtains watermarking schemes with provable robust- ness guarantees against such "constant-rate" attacks was [CG24]. which constructed watermarking schemes robust to constant fraction of deletions and substitutions. Moreover, in order to handle any deletions at all, [CG24] needs to assume that: (a) the deletions and substitutions are made independently at each position with some fixed probability; and (b) the language model is equivalent to a binary symmetric channel in a certain sense, a strong assumption which is contradicted by decades of study in linguistics, which posit that earlier words strongly influence the distribution of subsequent words [Bib09].*
Finally, we emphasize that the task of obtaining robustness against adversaries that can make a constant fraction of insertions, deletions, and substitutions, as opposed to merely substitutions, is well- motivated by an extensive line of work on edit distance (e.g.. [OR07, AKO10, AO11, AN20J, amongst many others). The edit distance between two strings is the minimum number of insertions, deletions, and substitutions needed to transform one string into the other. Edit distance has found numerous applications areas ranging from computational biology to information retrieval [Nav01]. This fundamental role of edit distance results from the fact that many natural processes induce small edit- distance perturbations on strings: for instance, mutations of DÑA can involve insertions or deletions as well as substitutions, as do the changes people typically make to documents. Procedures that make such changes therefore represent a reasonable adversary in our present setting of watermarking.
1.2
Main result
Our main result states that watermarking schemes with all of the aforementioned properties exist under a standard cryptographic assumption:
Theorem 1.1 (Informal version of Theorem E.2). Suppose that local weak PRFs exist (per Assumption 3. Then for any security parameter X E N, there is a watermarking scheme over an alphabet of size poly(>) for model outputs of length poly(X), which is sound, undetectable with respect to algorithuss running in time (A)y()), and robust to constant fraction of substitutions, insertions, and deletions when the sequence of generated text has "entropy rate" " at least some constant.
As is typical in cryptographic settings, the guarantee of Theorem 1.1 involves security parameter X, which controls the power of a distinguishing algorithm (in the context of undetectability) as well as the failure probability of soundness and edit-robustness (which are negl(A); see the formal version in Appendix E). The requirement that the sequence of generated text have constant entropy rate (meaning that on average, the tokens are generated from conditional distributions which have entropy at least a constant fraction of the maximum possible entropy) is easily seen to be necessary," and lower bounds on the entropy are standard amongst essentially all watermarking schemes, even without any robustness requirement [CGZ24, FGJ 23, CG24, Zam24]. Indeed, watermarking a near-deterministic language model is impossible since can only produce small number of outputs; the entropy assumption quantifies the extent to which the language model is near-deterministic.
One potential limitation of Theorem 1.1 is the requirement that the alphabet size of the language model (i.e., number of tokens) grow as a polynomial in A. This limitation is mitigated by the following observations: first, in many domains, the number of tokens used by existing (or future) tokenizers may already be quite large, i.e., at least in the thousands [SHB16, 16, YLK +22]; second, in practice one could use various heuristies to increase the number of tokens, such by grouping together consecutive sequences of tokens to create larger alphabets of "mega-tokens". Finally, again invoking the language of coding theory, a common approach constructing good codes via concatenation, which combine an outer code with large alphabet together with an inner code that encodes individual symbols of the large alphabet using smaller alphabet. Theorem 1.1 (as well Theorem 4.1, discussed below) could play the role of the outer code in such a concatenation strategy for watermarking schemes; finding the analogue of an inner code to decrease the alphabet size represents an important direction for future work.
3 We remark that, even for the case of substitutions, the result of [CG24] (Lemma 23 & Theorem within) only states robustness against i.i.d. substitutions, i.e., a binary symmetric channel. Nevertheless, a straightforward modification to the proof of [CG24, Theorem 5J allows one to establish robustness a constant fraction of adversarial substitutions. However, entirely different techniques are needed handle the case where insertions and deletions are also allowed.
'If only an o(1) fraction of tokens have nonzero entropy, then an adversary could simply replace those tokens with any fixed token and thus remove all entropy.
3

---

Roadmap of techniques. The proof of Theorem 1.1 proceeds via constructing new pseudorandom codes (PRCs), which are cryptographic objects originally introduced by [CG24] to derive water- marking schemes robust to i.i.d. random (i.e., non-adversarial) subsitutions and deletions. Roughly speaking, a pseuorandom code an error-correcting code equipped with a secret key used for encod- ing and decoding, which looks random to any polynomial-time algorithm that does not hold secret key. We establish the following ingredients pertaining to PRCs:
First, we design PRC over the binary alphabet which is robust to constant fraction of adversarial substitutions, under Assumption 3.1 ( (Theorem 3.2; see Section 3). This assumption is, qualitatively speaking, weaker than the cryptographic assumptions in [CG24].
Next, we give a generic reduction which, given any PRC over the binary alphabet robust to substitutions, yields a PRC over a polynomial-sized alphabet robust to any constant fraction of substitutions, insertions, and deletions (Theorem 4.1; see Section 4). A central idea in this latter PRC is to interpret symbols of the larger alphabet as indices into codewords of the former PRC; hence, we call it an indexing PRC.
Finally, we establish generic reduction which converts any PRC over larger alphabet robust to substitutions, insertions, and deletions to watermarking scheme with analogous robustness properties (Theorem 1, ; see Section 5).
Theorem 1.1 follows by composing the components above. These components have the advantage of being modular in nature, meaning that one could, for instance, plug in the substitution PRCs of [CG24] in place of the first item obtain guarantee analogous to Theorem 1.1 but under the (qualitatively stronger) cryptographic assumptions of [CG24].
In order to handle deletions, [CG24] uses type of PRC they call majority code. This code is only robust when the substitutions and deletions are made in an i.i.d. manner. In their reduction that converts PRC to watermarking scheme, the language model may induce certain errors on the PRC codewords. Since these errors may not be correctable by the majority code unless they are assumed to be i..d., [CG24] need to assume that the language model is equivalent to a BSC. Our use of indexing PRCs avoids this significant shortcoming.
2 Preliminaries
We begin with the definition of a pseudorandom code (PRC), as introduced in [CG24]. A pseu- dorandom code is defined over an alphabet Σ, which is simply finite set. We denote the set of all finite-length strings over Σ by Σ*. As is typical when defining cryptographic primitives, our pseudorandom codes depend on security parameler À E N; as À is increased, the amount of security afforded by the PRC also increases. A function f N - Rgo is called negligible if for any C > O, there exists An so that f(A) < X-C for all X > An We use (A)) to denote a negligible function, whose precise value can change from line to line.
Given an alphabet Σ, channel a mapping which associates to any x E Σ' a distribution (x)) over Σt. With slight abuse of notation, we will often let Exx denote random variable y drawn from (xx): for instance, when we write a statement of the form "with probability 1 - nn).
DHam (I, {x)) S prt", we mean that Dam (I. S pm with probability 1 - ne) over y E(x).
We primarily focus on secret key PRCs for simplicitity: our arguments (in particular, those regarding edit-robust PRCs) apply identically to the case of public-key PRCs [CG24, Definition 2]. though for simplicity we focus solely on secret-key PRCs. secret-key PRC may be viewed as a variant of a secret-key encryption scheme in which the ciphertext enjoys certain robustness properties to adversarial perturbations. Formally, a PRC is specified by functions KeyGen, Encode, Decode, which behave as follows: KeyGen outputs secret key, Encode uses the secret key to "'ncrypt"' message, and Decode uses the secret key to "decode" a string. the string passed to Decode is the output of Encode, perhaps with bounded number of adversarial perturbations. then Decode should output the message originally passed to Encode (robustness). Outputs of Encode should also look random to polynomial-time time algorithms (undetectabilitt), and Decode should almost always fail when given any fixed string (i.c., not an output of Encode) as input. These definitions are formalized below:
Definition 2.1 (Secret-key Pseudorandom code (PRC)). Let E N denote a security parameter, and suppose that for each À E N an associated alphabet (A) is given. Moreover, suppose that

---

for each A, collection (A) of channels & Σ(A) - ((E())) is given. A secret-key pseudo- random code (PRC) with robustness to is triple of probabilistic polynomial time algorithms (KeyGen, Encode, Decode) satisfying the following:
For some functions n, kt Lsk N N, for all À N, we have KeyGen 12) {0, 1) Encode
[1A} {0, 13 x E)(A) Σ)(A), and Decode {1²} x {0, 1J (( x E* E)(A) (1}.
For any E and message m E y the code is robust to any channel E &(),, which means that:
Pr skr (1)G (Decode(1*, sk, E(x) m Encode sk, m)) nAg
Moreover, for any fixed y E E*, the code is sound, which means that:
Pr skt (1
(Decode(1* ,k,, =1) 2 1 - nA)
The code is undetectable which means that: for any E N for any probabilistic polynomial-time adversary Adv.
(Adv 1a (1²)) skt skt- KeyGen(1AA))
(1²) (()))===]] (A), (1)
=1)
Pr ske (ee--Kyy)en11))
Pr
where U denotes an oracle which responds with freshly drawn uniformly random string in )*(A) on each call (to any input).
The block length of the PRC is defined to be n(A). For all of our pseudorandom codes, we will have (A), k(A), (xx (A) I poly(A). Moreover, we take as a convention that (²A) 2 À for all (this may be ensured without loss of generality by rescaling n())). Our focus will primarily be zero-bit PRCs, which are particularly useful for watermarking language model outputs.
Definition 2.2 (Zero-bit PRC). A zero-bit PRC is one for which (:)) = 0 for all X, i.e. the only possible message is 0.
[CG24, Section 6] shows a generic reduction that converts any zero-bi bit PRC into general PRC with constant rate, meaning that (A))/n(A) 12) We remark that the same reduction can be applied to our PRCs with edit robustness, though we do not pursue this direction further in this paper.
Definition 2.3 (Substiuution-buuneee) For E (0, 1), channel & over alphabet is p-substitution- bounded for any n E N, y E", for E(y). DHam (y, 2) $ pn holds almost surely.
Definition 2.4 (Edit-bounded channel). Fix an alphabet Σ together with p (0, 1). A channel & over E(x) may be obtained from r by applying a total of most pn substitutions, insertions, and deletions, almost surely. Moreover, there exists probabilistic polynomial-timg algorithm which, given x, outputs a sample {(x)
defined to be p-edii-boundeer if for any E E* with n == |<||
3 Secret-key substitution PRCs from weaker assumptions
In this section, we discuss a new construction of binary PRCs for substitution channels. Though such PRCs were also obtained by [CG24], the codes in [CG24] relied on relatively strong average-case hardness assumptions, in the sense that they imply the existence of public-key cryptography (i.c., in the context of Impagliazzo's 's Five Worlds [Imp95], they imply primitives in "Cryptomania"), In contrast, our construction relies only on the hardness of the existence of a family of pseudorandom functions that enjoys a certain locality property; such an assumption is generally believed to be weaker than the ones in [CG24], in the sense that it is only known to yield cryptographic primitives "Minicrypt", though we are not aware of formal separation.
We first recall the definition of pseudorandom function (PRF) families, which are PRF families for which the adversary can only query the pseudorandom function at a uniformly random input æ.
'The computational efficiency of E is only needed for our watermarking schemes. It is not necessary to obtain adit-robust PRCs; see Remark D.2
5

---

Definition 3.1 (Weak PRF family). Fix functions {(A), (a)) - N of a security parameter A, and a collection of functions {Fa, {0, 1)m()) - [0,11} indexed by E (0.1)(A), for À E N.
We say that the collection (F is weak pseudorandom function family (weak PRF) if for every probabilistic polynomial-time algorithm Adv which outputs a single bit (i.e., 0 or 1), it holds that
E (0.
Adv Fs() ((m())))
Adv
Fusit (1n(Al)]
S neg)(A),,
(2)
for mapping G: : {0, 1)m(A) + 10, 1/ means that Adv can make calls to the function G, and for each call receives a tuple (2. G). for x ~ Uni,((0,13"), (In particular, the tilde refers to the fact that Adv can only call ((rr) denotes a uniformly random function. We will often refer to the function G that Adv can make queries
where Adv G
uniformly chosen x.) Moreover, Funit [0,1)" - {0, 1}
to as the oracle Adv has access Given q [0, 1/2), we say that {Fs)s is weak PRF family with noise level if (2) holds where each call to (-) by Adv returns F3 (z) @ e where x ~ Unif([O, 1})" and Ber(g).
Our new construction of PRCs is based off of local (weak) PRFs, which are PRFs for which the output depends on small number of input bits.
Definition 3.2 (Local function family), Let T N. A family of functions {F, : 13" {0, indexed by s is defined to be 7-local if for each Fx( only depends on at most 7 bits of z, i.c. for each s there are distinct indices fı..... .i.....Jr Jr E [n] together with function G, : {0, 13" - {0. 1] so
that (x) = Gz(z),..... ................................ E.y) for all x E 1
Our main computational assumption is the existence of weak PRF family which is r-local for r of logarithmic size:
Assumption 3.1 (Local Weak PRFs). For some functions ((A), (()) : N + N with n(A) S poly(A) and T()) S log n(X), there exists a weak PRF family {Fa : {0, [0, +
{0. (000,poe for some noise level q < 1/2 which T(X)-local, for each X E N.
In Appendix C.2, we discuss how Assumption 3.1 follows from standard average-case hardness assumptions, notably the hardness of learning log(nt)-juntas over Unif( {0, 1 1)"). As specific exam- ples, either hardness of the log(n))sparse noisy parity problem [FGKP09, BFI+94, 94, GRVII, Val15] or hardness of weakly learning particular family of functions presented in [BFKL94] (see also [Blu03]) implies Assumption 3.1.
The PRC construction. Our construction of PRCs based on Assumption 3.1 is presented in Algorithm 2: given function family F satisfying Assumption 3.1 with noise level q together with some p < 1/2 representing the maximum fraction of substitutions to correct, we construct PRF-PRC[F,, p. = (KeyGen, Encode, Decode) as follows. The construction depends on some parameters N (A), m(A) S (oly(A), specified in (3):
KeyGen(1*) chooses a function in F (indexed by s) together with uniformly random ~ (n, 1} ((A) and a uniform permutation æ : [A]()] + [A)) and returns sk (s, 2, I))
Encode A, (s, 21 2), 0) draws m(() uniformly random elements of {0, 1}m(A), F1..... mm()) applies F3 to each of them and flips the result with probability q obtain bits (wi..... ())()) and perturbs the concatenation ((z,, (e)))=((((A)) according to 2, π as Line 9.
Decode(1*, ^ (s, 2, .)..) 3) first "unperturbs" y to obtain a string ((x;, ws) ws))se(((()) as in Encode, and then outputs 0 if Σソ= 1 1ww; Fx()))) is above a threshold; otherwise, it outputs 1.
Theorem 3.2. Given p.g < 1/2 and function family F together with noise level q satisfying Assumption 3.1, then PRF-PRC(F, p, q] (Algorithm 2) is a zero-bit alphabet secret-key PRC (per Definition 2.2) with robustness to all p-bounded substitution channels.
The proof of Theorem 3.2 is given in Appendix C.3.
4 From substitution PRCs to edit-robust PRCs
In this section, we discuss our construction of PRCs which are robust to edit-bounded channels. To do so, we reduce to PRCs robust to substiutioon-oundee channels. Suppose we are given PRC

---

PRCsub with block length n(x) over the binary alphabet which is robust to any (1/2 - pu) boundedd substitution channel, for Po (0, 1/2). Given a parameter p 2 1, we construct an indexing PRC. PRCia(PRCssad (in Algorithm 1), which is robust to any p-edit-bounded channel, where the parameter p depends on po. o manner that will be explained below. The code PRC1ax (PRCsub: p) has polynomially large alphabet Σ(A) == [g()),, where q()) p (A). We denote the block length of IRCidx(PRSsul p] by mAA) (which is defined to be [In(2) (A)7) to distinguish it from the block length (()) of PRC
Construction of PRC1 |PRCsub: pl. The idea behind PRC (PRCsuR: p| is simple: we interpret each symbol of (PRC p] as an index into a codeword of PRCsub- so that the existence of a symbol in a given codeword of PRCidx codeword for PRC as having a "1" in the position corresponding to that symbol. To ensure stronger robustness guarantees, it turns out to be necessary to introduce redundancy in the sense that for each integer j E [n[A]] (representing an index of a codeword of PRCsub), there are p different elements of [q()]] which correspond to index j. The choice of these P elements for each j is specified a mapping & [g{) + [x] with ( [ = p for all j. which is chosen randomly in the KeyGen function of PRC PRC p]. With this intuition in mind, we proceed to overview the individual KeyGen, Encode, Decode functions of (PRCsb. p. in Algorithm 1:
p) should be interpreted as the corresponding
The KeyGen(1>) function generates a secret key sk for PRC using KeyGensub. It also generates random function d as described above, and returns the tuple (sk, v)), which is the secret key for PRCix p).
The Encode(1> (sk, )) m) function calls the encoding method Encodesub for PRC which yields string yd E {0, 1)m"(A, It then chooses string E [n(A)] which has the property that the set of distinct elements of y, which we denote by Unique(y). has small set difference with the set S := {i E [n(A)] : y 1 of indices at which y has a "1". The precise way in which the sets Unique(y) and S differ determined by the function PerturbDifference in Algorithm 1, and is needed to ensure that the output of Encode(1>, sk, m) indistinguishable from the uniform distribution over mn))) (i.e., that the PRC is undetectable). Finally, Encode returns string 2 I(() where each coordinate 2, is uniformly random pre-image of y under sb.
The Decode(1>, (sk, v), 2) function calls the substitution PRC decode function, Decodesub, on the string y' E {0, 1 ja(A)) which has a in position [n{A)] if and only if i E (z))) For future reference, we denote this string by y' = (z),), i.e., (z); i E Unique (=))).
Theorem 4.1 below shows that PRCiax (PRC p] has robustness to any channel which makes large fraction (at most - CrobPo) of substitutions, insertions, and deletions.
Theorem 4.1. There are constants Co, Crob 2 1 so that the following holds. For any po (10Crab) and PRC PRC with block length n(X) which is robust to all (1/2 -u)ssutititutton bounneed channels, for any p 2 Co/Po. PRC PPRCdt p] (Algorithm 1) is a pseudorandom code over an alphabet size [p- n(X)] and block length at most n()),, which has robustness to any (1 CrobPa)- channel (per Definition 2.4).
Proof overview for Theorem 4.1. To prove Theorem 4.1, we need to establish the soundness, undetectability, and robustness of PPCsu, p). Soundness is an immediate consequence of soundness of PRCsub (Lemma D.2). Undetectability is likewise straightforward, using unde- tectability of PRCsub together with the fact that the output of PerturbDifference( m. y)). for 8d ~ Unif (f0, 1))", is uniform on [n] (Lemma D.2). The bulk of the proof consists in establishing robustness.
natural attempt to establish robustness would proceed as follows: given a string = E ()))))()))) (to be interpreted as an output of Encode(1>, (sk, m)). a single insertion or deletion in z can change at most one symbol of (2), and a single substitution in can change at most two symbols of (z). Thus, it straightforward to show statement of the following form: if PRCsub is (1/2 - (00-Po)--see subssitttiinn bounded and 2p < 1/2 -p., then PRC (PRCsub p] is robust to the class of p-edit-bounded channels. (Technically, some additional work is needed since the PerturbDifference function introduces some additional substitutions in the underlying binary codeword, though we ignore this detail for now since with an appropriate choice of parameters the number of such errors will be of lower order.)
7

---

Algorithm I Indexing PRC: PRCix(PRCSub/
Require: PRC for substitutions: (KeyGensub- Encodesub, Decodesub); together with functions n N + N, N N characterizing the block length and key length, respectively; parameter / 1. Functions m(A) = [ln(2) m(A)], g(A) = (A))
1: function KeyGen(1~)
2: Define sk KeyGensub (1*).
3: Let [q(A)] + [n())] be uniformly random function conditioned on | = p for
each j E [r((
4:
return (sk, 1²).
5: function Encode(1 (sk, 4), m)
6: Set y" -- Encodesub (1>, sk, m) {0, (0.1))(A)
7: Set y f- (erturtDDiferencce((())))) (A)
8: For each E [m()),, choose 2j Unif(fa: v(a) = =;²)).
9: return , . =m(A))
10: function Decode(1>, (sk, vi), 2)
11: Define : (=) (vb(21), (),,)..).,,, ..... (Zm(a)))
12:
Define y' E (0, 13"h by of = lii E Unique(y)).
13:
return Decodesub (1> sk,
14:
function PerturbDDifferenceenn, m,,"
15:
Set 5 = {i E [n] xf 1}.
16:
Sample y² Unif([n:')) ))
Set S = Unique(y") [n].
18:
if ( 2 | \ then
Let : 8 8 S denote a uniformly random injective mapping.
20:
For each E S let be formed by replacing each instance of a in y² with o(a).
21:
else
22:
Let : S + St) 8 denote a uniformly random injective mapping.
23:
For each E s let be formed by replacing each instance of r(a) in y with a.
24:
return y.
Unfortunately, such result does not have sufficiently good robustness for our application to termarking. As will discussed Section 5, our procedure which watermarks a language model Model by "embedding" codeword of PRC in sequence of text output by Model introduces a fraction 1 - a of errors to 2, all of which are substitutions. Here a is some constant which is related the entropy rate of Model. Using the naive approach above, are constrained to rate of substitutions bounded as < 1/4, thus forcing --a a < 1/4 and so disallowing all but high entropy rates.
To compensate, we make use the fact that the randomly chosen mapping v [q(A)] - [x() maps multiple (namely, p) symbols in [A)) each symbol in [n(A)], when performing decoding. In particular, consider any fixed channel over the alphabet (A()). For simplicity in our overview here,
assume that E is deterministic (so that it is specified by mapping & [q(A)] - [a())]* for each m E N), though essentially the same argument works for randomized E. Consider a codeword z (a(A)]m(A) which is output by Encode(1^, (sk, +),m), m). By undetectability of the code, with high probability over Encode, we will have that (nique((((2)) x n() + O /n(A)), since by our choice of m(X) = [n) l2(2), uniformly random string ă ~ Unif([q(A)]m((A) satisfies
(aique(()())) m()) O (()) with high probability.
'eer let (>x) (V(2)),.... (. (Zm((1))

---

Supposing that & is promised to make at most fraction 1 - p of edits, then x' == E(z) shares at least (A) symbols with 2. Let us suppose for simplicity here that x' E [o(A)] so that the insertions and deletions of are balanced (a slight modification of the argument handles the general case). Of the remaining (1 - p) mm()) symbols of z', by the random choice of z0 and since (Unique())(e R (2) each one roughly equally likely to map (under v) to an element in Unique( (b(2 as to an element in [n( (n))) Unique({b(z)), Thus, in going from the set Unique(ri(( to the set Unique(v (=)),, we should expect to change at most roughly (1 - p) m2) elements. This intuition is made precise in the following lemma:
Lemma 4.2 (Informal version of Lemma D.7). Given channel & as above which makes (1 -p)- fraction of edits (i.e., substitutions, insertions, and deletions), with 1 - negl(A) probability over the draw of of (sk, 1/) < KeyGen(1>) and < Encode(1>, (sk, 4), m) we can bound the set difference between Unique (z)), Unique (nique(((E(2))) (E(()))
follows:
A(Unique(((())) Unique((((E(3))) S (1 (())) m(A)
Since the Hamming distance DHam (D Dy is equal to the size of the set difference |A(Unique (z)). (nnque((<<=)))) we arrive at the conclusion that D (D, (x') x - [pp)) n(A)/2 with high probability over the draw of dà in KeyGen. Since Po can be cho- sen arbitrarily small, we have substitution PRCs SuC which can correct (1 -=p)))/ fraction of substitutions. Thus, obtain as a consequence that PRC (PRCsub: p] can correct (1 p) fraction of substitutions, insertions, and deletions.
The argument above omits many details, notably involving the high-probability event referenced in Lemma 4.2. To establish that such an event occurs with high probability (over the draw t)), we need to use Dobrushin's 's concentration inequality (Theorem F.3) for data with limited dependencies. Roughly speaking. this inequality comes into play because the sets & '()) (1)..... e (n(A)) C (n(((())) [A)]
not fully independent (since, e.g., they must be disjoint). Nevertheless, dependencies, assuming that n(A) is sufficiently large as compared to p.
may bound their
5 From large-alphabet PRCs to watermarking
In this section, we overview our reduction (stated in Theorem 5.1) that converts a PRC with robustness to channels making a bounded number of adversarial edits to a watermarking scheme with robustness to adversarial edits. At high level. this reduction uses rejection sampling at each step of the language model generation to make the output of the model align with a PRC codeword. To formally state the result, need the notion of empirical entropy: given token sequence E Σ and i, E [L). the empirical entropy of Model on the subsequence [ is
R (t, Model) == log
Pr the Model( (i)--1)
(t/.
Li: (1:0-1);
where the probability is over sequence that drawn, token by token, from the per-token distributions induced by Model (see Definition B.1 for discussion). The empirical entropy quantifies the degree to which the sequence tz:j "far from being deterministic" under Model given the prefix t1:-11
The watermarking schemes we derive from PRCs satisfy a stronger property known as substring robustness [CGZ24, CG24], which means that if any sufficiently high-entropy substring of water- marked text is passed through a channel inducing a bounded number of edits, then the watermark will still be detected. More precisely, for function N N, watermarking procedure W = (Setup, Wat, Detect) over an alphabet Σ is B-substring robust to a channel & if
Pr Ske-Setup(1>) t<-at(I>>sM) =(())
(3i,
S.t. s.t. DItect(I*, sk, t') False and H H1s++e-11 (()) 2 B()) In InnEE) < negl(A)).
We remark that the channel E is required to be non-adaptive in that it cannot depend on the particular draw of the secret key sk. Some details are omitted; see Definition B.2 for a completely formal Our main result of this section shows that a PRC with robustness
definition of substring-robustte to adit-bounded channels yields a watermarking scheme with rubstring-robustness to edit-bounded channels:

---

Theorem 5.1 (Informal version of Theorem E.1), Let a E (0,1) be given constant. Suppose PRC, defined over alphaber ΣPRC. has block length n. and is robust any (1 a --dde-bbbuudeed channel. Further suppose Model is a language model over alphabet E satisfying |>] 2 (a [PRCl)2/o. Then there is a watermarking scheme W[PRC, Model] (Algorithm 3) which is sound, undetectable, and -(u)-suustiing robust to any 48 -g-edi-bbounded channel, for ((E) == 8n + 6ol.
Theorem 5.1 establishes that, as long as the entropy from a substring of generated text is roughly a ((a))fraction of the maximum possible entropy, then a constant (O(a²) fraction of edits to that substring cannot remove the watermark. We remark that this constant fraction of edits cannot be impoved to beyond an a-fraction (as is evident from the example in Footnote 4). The proof of Theorem 5.1 builds off of the reduction [CG24], for which = ΣPRC = {0, 1]. Their reduction, however, breaks down in the setting when ΣPRC is no longer binary, and we introduce some new ideas (roughly, involving a hashing technique) to deal with the setting of larger alphabets. Details of the proof may be found in Appendix E. Finally, remark that by combining Theorems 3.2, 4.1 and 5.1, we obtain Theorem 1.1, which establishes the existence of edit-robust watermarking schemes under Assumption 3.1.
On implementation of the watermarking scheme. A natural question is how feasible it is to implement the watermarking scheme WIPRC, Model] of Theorem 5. The main limitation of our present theoretical results which may complicate practical implementation is follows: The alphabet size [>]) is required to grow exponentially the inverse of the parameter a (see the statement of Theorem E.2). In turn, the parameter is proportional to the entropy rate of the text needed to guarantee substring robustness (see Definition B.2 and the setting of Bx(() x a in Theorem E.2). For typical LLMs, the alphabet size is likely smaller than required value of [[()]] given the entropy rates observed empirically in natural language. On the other hand, we believe that future work aimed developing modifications of our watermarking scheme with eye towards practical implementation will be successful. One idea which seems promising is to simulate larger alphabet by grouping tokens together, and aim accordingly for slightly weaker robustness guarantee.
Acknowledgements
NG was supported by a Fannie & John Hertz Foundation Fellowship and NSF Graduate Fellowship. AM is supported in part by a Microsoft Trustworthy AI Grant, an ONR grant and a David and Lucile Packard Fellowship. We thank Gabe Schoenbach for helpful comments earlier draft of this work.
References
[AK22]
Scott Aaronson and Hendrik Kirchner, Watermarking gpt outputs, 2022. Available at https://wwaz http:///wwww.sstttrooeeeeee www.taaroosoonncccooo.oo wotp:///////alll////eerraaatat ppt.
[AKO10] Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Polylogarithmic approxi- mation for edit distance and the asymmetric query complexity, 2010.
[AN20]
Alexandr Andoni and Negev Shekel Nosatzki. Edit distance near-linear time: it's constant factor. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 990-1001, 2020.
[AO1I]
Alexandr Andoni and Krzysztof Onak. Approximating edit distance in near-linear time, 2011.
[ARC+OI] Mikhail J. Atallah, Victor Raskin, Michael Crogan, Christian Hempelmann, Florian Ker- schbaum, Dina Mohamed, and Sanket Naik. Natural language watermarking: Design, analysis, and proof-of-concept implementation. In Ira S. Moskowitz, editor, Informa- tion Hiding, pages 185-200, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.
[ARH+02] Mikhail J. Atallah, Victor Raskin, Christian F. Hempelmann, Mercan Topkara, Radu Sion, Umut Topkara, and Katrina F. Triezenberg. Natural language watermarking and tamperproofing. In Information Hiding, 2002.
10

---

[BF] 94]
Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC '94, page 253-262, New York, NY, USA, 1994. Association for Computing Machinery.
[BFKL94]
Avrim Blum, Merrick Furst, Michael Kearns, and Richard J. Lipton. Cryptographic primitives based on hard learning problems, Douglas R. Stinson, editor, Advances in Cryptology - CRYPTO 93, pages 278-291, Berlin, Heidelberg, 1994. Springer Berlin Heidelberg.
CRYPTO
[BGH17] Boris Bukh, Venkatesan Guruswami, and Johan Håstad. An improved bound on the fraction of correctable deletions. IEEE Transactions on Information Theory, 63(1):93- 103, 2017.
[Bib09]
Douglas Biber. 159 Corpus- Basud and Corpus-driven Analyses of Language Variation and Use. In The Oxford Handbook of Linguistic Analysis. Oxford University Press, 12 2009.
[Blu03]
Avrim Blum. Learning a function of relevant variables. In Bernhard Schölkopf and Manfred K. Warmuth, editors, Learning Theory and Kernel Machines, pages 731-733, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.
[BR17] Andrej Bogdanov and Alon Rosen. Pseudorandom functions: Three decades later. Cryptology ePrint Archive, Paper 2017/652, 2017. https://eprints iacr org/ 2017/652.
[CBD+24] Liang Chen, Yatao Bian, Yang Deng, Deng Cai, Shuaiyi Li, Peilin Zhao, and Kam fai Wong. Watme: Towards lossless watermarking through lexical redundancy, 2024.
[CG24] Miranda Christ and Sam Gunn. Pseudorandom error-correctin codes. In Proceedings of the 44th Annual International Cryptology Conference (CRYPTO). COLT, 2024.
[CGZ24] Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. In Proceedings of the 37th Annual Conference on Learning Theory (COLT), 2024.
[Cha16]
Sourav Chatterjee. Concentration inequalities with exchangeable pairs (ph.d. thesis), 2016.
[FGI+23] Jaiden Fairoze, Sanjam Garg, Somesh Jha, Saced Mahloujifar, Mohammad Mahmoody, and Mingyuan Wang. Publicly detectable watermarking for language models, 2023.
[FGKPO9] Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM Journal on Computing. 39(2):606-66 645, 2009.
[FKQR23] Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making, 2023.
[FS95]
Yoav Freund and Robert E. Schapire. desieion-theoretic generalization of on-line learning and an application to boosting. In Paul Vitányi, editor, Computational Learning Theory, pages 23-37, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg.
[GL16]
Venkatesan Guruswami and Ray Li. Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes, 2016.
[GLLH24]
Chenchen Gu, Xiang Lisa Li, Percy Liang, and Tatsunori Hashimoto. On the learnability of watermarks for language models. The Twelfth International Conference on Learning Representations, 2024.
[GRS19]
Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential Coding Theory. 2019.
[GRV11]
Elena Grigorescu, Lev Reyzin, and Santosh Vempala. On noise-tolerant learning of sparse parities and related problems. In Jyrki Kivinen, Csaba Szepesvári, Esko Ukkonen, and Thomas Zeugmann, editors, Algorithmic Learning Theory, pages 413-424 Berlin, Heidelberg, 2011. 1. Springer Berlin Heidelberg.
[GW17] Venkatesan Guruswami and Carol Wang. Deletion codes in the high- and high-rate regimes. IEEE Transactions on Information Theory, 63(4):1961-11700 2017.

---

[HCW 24] Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang. and Heng Huang. Unbiased watermark for large language models. In The Twelfth International Conference on Learning Representations, 2024.
[HS21a]
Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings and codes for insertions and deletions survey, 2021.
[HS21b] Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings: Codes for insertions and deletions approaching the singleton bound. J. ACM, 68(5). sep 2021.
[4ZZ*24] Baihe Huang, Hanlin Zhu, Banghua Zhu, Kannan Ramchandran, Michael I. Jordan, Jason D. Lee, and Jiantao Jiao. Towards optimal statistical watermarking, 2024.
[Imp95]
R. Impagliazzo. A personal view of average-case complexity. In Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, pages 134-147, 1995.
[KGW+23] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17061-17084. PMLR, 23-29 Jul 2023.
[KG John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models, 2024.
[KTHL23] Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-fre free watermarks for language models, 2023.
[LB24] Yepeng Liu and Yuheng Bu. Adaptive text watermark for large language models, 2024.
[LPH+244] Aiwei Liu, Leyi Pan, Xuming Hu, Shuang Li, Lijie Wen, Irwin King, and Philip S. Yu. An unforgeable publicly verifiable watermark for large language models. In The Twelfth International Conference on Learning Representations, 2024.
[LPH+24b] Aiwei Liu, Leyi Pan, Xuming Hu, Shiao Meng, and Lijie Wen. A semantic invariant robust watermark for large language models. The Twelfth International Conference on Learning Representations, 2024.
[Nav01]
Gonzalo Navarro. A guided tour to approximate string matching. ACM Comput. Surv., 33(1):31-88, mar 2001.
[ODo14]
Ryan ODonnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Rafail Ostrovsky and Yuval Rabani. Low distortion embeddings for edit distance. J. ACM, 54(5):23-es, oct 2007.
[OR07]
[PHZS24]
Qi Pang. Shengyuan Hu, Wenting Zheng, and Virginia Smith. Attacking IIm watermarks by exploiting their strengths, 2024.
[RS23]
Upul Rupassara and Bishnu Sedai. On the convergence of hypergeometric to binomial distributions. Computer and Information Science, 16: 16:15, 07 2023.
[RvdOV19] Ali Razavi, Aaron den Oord, and Oriol Vinyals. Generating diverse high-fidelity images with va-vae-2. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bun E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[SHB16]
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Katrin Erk and Noah A. Smith, editors, Proceedings of the 54th Annual Meeting of the Association for Computational Linguisties Vooluee 1: Long Papers), pages 1715-1725, Berlin, Germany, August 2016. Association for Computational Linguistics.
[2J Keyu Tian, Yi Jiang, Zehuan Yuan, Bingyue Peng, and Liwei Wang. Visual autoregres- sive modeling: Scalable image generation via next-scale prediction, 2024.
[TTI05]
Merean Topkara, Cuneyt M. Taskiran, and Edward J. Delp III. Natural language watermarking. volume 5681, pages 441-452. SPIE, 2005.
[Val15]
Gregory Valiant. Finding correlations subquadratic time, with applications to learning parities and the closest pair problem. J. ACM, 62(2), may 2015.
12

---

[WHZH23] Yihan Wu, Zhengmian Hu, Hongyang Zhang, and Heng Huang. Dipmark: A stealthy, efficient and resilient watermark for large language models, 2023.
[YLK Jiahui Yu, Xin Li, Jing Yu Koh, Han Zhang, Ruoming Pang, James Qin, Alexander Ku, Yuanzhong Xu, Jason Baldridge, and Yonghui Wu. Vector-quantized image modeling with improved VQGAN. In International Conference Learning Representations, 2022.
[YXK] 22] Jiahui Yu, Yuanzhong Xu. Jing Yu Koh, Thang Luong, Gunjan Baid, Zirui Wang. Vijay Vasudevan, Alexander Ku, Yinfci Yang. Bureu Karagol Ayan, Ben Hutchinson, Wei Han, Zarana Parekh, Xin Li, Han Zhang, Jason Baldridge, and Yonghui Wu. Scaling autoregressive models for content-rich text-to-image generation. Transactions on Machine Learning Research, 2022. Featured Certification.
[ZALW24]
Xuandong Zhao, Prabhanjan Vijendra Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for Al-generated text. In The Twelfth International Conference Learming Representations, 2024.
[Zam24]
Or Zamir. Excuse me, sir? your language model leaking (information), 2024.
[ZEF+23 23]
Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak. Watermarks in the sand: Impossibility strong watermarking for generative models, 2023.
13

---

A Additional related work
Watermarking has a long history, dating back to the work of [TT105, ARC+ 02]: generally speaking, these early works considered procedures which embed a watermark into a given text, by altering the text in some subtle way. Spurred by the remarkable abilities of generative models, in particular large language models (LLMs), there has been a recent resurgence of interest in watermarking. In contrast to the classical works, most recent works (including this paper) aim to embed the watermark in way that does not significantly alter the distribution of the generated content. This task is enabled by the autoregressive nature of LLMs, which generate each successive token using some fresh randomness.
Recent works [ZALW24, AK22, KGW+23] construct watermarking schemes by pereferentially generating certain tokens at each step of generation. For instance, [ZALW24] partitions tokens into two equal-sized sets, a "green set" and a "red set". It slightly increases the probabilities of green tokens while slightly decreasing the probabilities of red tokens. A watermark is then detected if the proportion of green tokens in text segment noticeably higher than 1.4 The works of [AK22, KGW+23] build on this protocol by generating the green and red sets at each position using a pseudorandom function seeded with a window of some number is of previous tokens. These schemes all introduce some degree of noticeable bias to the watermarked model's output, by increasing the probability of certain k-grams.
Distortion-freeness vs undetectability. [KTHL223 introduced a notion called distortioonfreeness, which posits that single text sample from the watermarked model is distributed identically to single sample from the true model. [KTHL23] construct watermarking schemes satisfying distortion- freeness, with nontrivial edit-robustness guarantees: their watermarks have robustness constant fraction of substitutions (Lemma 2.5 within), but only to a slightly sub-constant fraction of edits when insertions and deletions are also allowed (Lemma 2.6 within). [HCW+24, WHZH23] also developed a similar approach to [KTHL23]]
[CGZ24] defined the stronger notion of undefectabilityy (the focus of the present work), which requires that no computationally efficient algorithm which makes any number of queries to the language model can distinguish between the watermarked model and the original one. [CG724] constructed the first provably undetectable watermark by using a similar technique to [AK22, KGW 23] with the modification that they dynamically adjust the parameter & denoting the length of text used to seed the pscudorandom function. This dynamic adjustment ensures that the sequence of k tokens has sufficiently high entropy, which ensures undectability.' 8 Undetectable watermarking schemes were also constructed by [Zam24], which focused specifically on the application to steganography (see also [CG24] for robust steganography schemes), and [FG] [23], which concentrated on schemes with public altribution.
It is natural to wonder: why should one should prefer undeteciable watermarking schemes over distortion-free ones? The simplest reason is that, as requirement on generative models, distortion- freeness is very weak, as illustrated in the below example.
Example A.1 (Distostion-freeness).. Consider the alphabet Σ = {0, 1} and suppose that Model is the uniformly random distribution on outputs t E {0, 1)", for some n E N. Consider the watermarking scheme which draws a key sk (n0 1}") and at each call to Wat(sk), simply returns sk. This scheme is distortion-free since the distribution of sk is uniform, but has the property that once Wat is called once, the output of all future calls is determined (and so is clearly not undetectable).
Example A. indicates that distortion-free watermarks may suffer from insufficient diversity in model outputs: in Example A. there is no variation whatsoever in the outputs. The distortion-fiet schemes of [KTHL23] are only slightly better on this front: they sample long random key sk and then
II particular, in order for [KTHL223, Lemma 2.6] be nonvacuous, the parameter 7 must be chosen so that 7 >> log kt which necessitates ε < 1/7 < 1/ log k; and & must grow faster than a constant for the probability in [KTHL.23, Lemma 2.6] to decay to 0.
*Notice that undetectability is not strictly speaking stronger than distortion-frrenes, since undetectable watermarking scheme can perturb the distribution of even a single text sample output by the model, though only in a way that can not be detected by any computationally efficient algorithm. Since in practice, any downstream applications of language model outputs will proceed via computationally efficient algorithms, we view undetectability as stronger than distortion- "for all intents and purposes".
14

---

generate sequence of text from Model in a way that aims to be close to a random shift of sk. Having fixed the key sk, the output text from the scheme of [KTHL23] is a deterministic function of the shift, meaning that at most len(sk) distinct sequences of text can be generated altogether. Moreover, by the birthday paradox, one would expect to see repeat answer after only vlen(sk) calls. The effective number of distinct samples of the distribution of output text of [KTHL23] may be even smaller than len(sk), if different shifts of sk lead to similar text sequences (as they will for, e.g., the uniform Model in Example A.1).
Beyond avoiding the issue of insufficient diversity, the stronger guarantees afforded by undetectability offer more compelling argument for adopting watermarking in the first place. Watermarking is just one of many technologies that can be built into Al models to achieve better alignment with human values. Even if each of these degrades performance in minor but non-negligible ways, the aggregate impact of all of these additions could potentially potentially be substantial. The guarantee of undetectability, namely that no matter what efficient downstream algorithms are applied to the model's 's output, the result will be essentially the same, means that the addition of watermark can only be blamed for a negligible amount of the overall performance degradation.
Additional work on watermarking. [HZZ* 24] formulate a variant of the watermarking problem which is purely statistical in nature, and characterize the optimal rate of watermarking. [GLLH24] show that watermarking schemes can be learned, using a student-teacher framework. [KGW+23, CG24, PHZS24, ZEF+ 23] develop various attacks on watermarking schemes. Generally speaking, these attacks are relatively expensive in terms of calls to the language model (as in [CG24, PHZS24]) or an additional "quality oracle" (as in (ZEF+23)) Moreover, a sufficiently motivated adversary could simply train their own (unwatermarked) Al model and generate content from it. Therefore, we view robust watermarking as targeted more at "honest" or "lazy" adversaries who are making edits either improve the quality of content without explicitly trying to remove a watermark (e.g.. for Al Al-generated news articles) or have very few resources to remove the watermark (e.g., a student asking an LLM write their essay right before the deadline).
Finally, we remark that there is a sizeable body of work focusing on empirical approaches to watermarking (e.g.. [LPH* 24b, LPH LB24, CBD+24, KGW
Error-correcting codes for insertions and deletions. A recent line of work (e.g., [GL.1, BGH17, GW17, HS21a, HS21b]) has focused on developing enor-correcting codes for insertions and deletions. We remark that the idea of indexing is implicit in some of this work. One focus of these papers has been on obtaining codes which can correct constant fraction of insertions and deletions with smaller (e.g., constant-size) alphabets. A common technique for this task is that of of synchronization strings [HS21a, HS21b]: it proceeds by increasing the alphabet size by constant factor and attaching to each message character an "auxiliary character" coming from a so-called synchronization string, which has certain properties that make it casier to align noisy codeword with the clean codeword. Unfortunately, the same synchronization string must be used with each call to the encoding algorithm, which makes it unclear how construct such codes that pseudorandom.
B Additional preliminaries
B.1 Watermarking language models
language model Model over alphabet E which, for any positive integer i, takes as input sequence of tokens ti:1-1 = (t,,...,,4,) 4-11) already output by the model and produces a distribution Model(t, = ti:-1) E AEE), representing the distribution of the next token, conditioned t1--11 We assume that Model is computationally efficient, meaning that it runs in time poly(i, log [E)). We also assume that there is some token END Σ representing the end of the model's 's response. As matter of convention, we assume that all subsequent tokens after a END token are also END (i.e., Model(END ti: = 1 if some t; for j < i is END). Given a language model Model, we introduce the notation Model: given any sequence t1:-1 E 5 (which may be the empty sequence) and m > O. the distribution Model(t;i-m-1 = (1=-1) E Σm is defined as follows: we sequentially generate ....... f++m-1, where for each 0 S j < m, ty is distributed as Model(t, = (1.j-1). In the case i = 1 (i.c., t1=-1 0). then denote an output of Model as t Model.
15

---

An intuitive requirement on Model that allows for watermarking is that outputs of Model must be high- entropy; indeed, a model that outputs a deterministic sequence of text impossible to watermark, since the only distribution which is indistinguishable from its output is that same deterministic sequence of text. As we aim to measure the entropy of individual model outputs, we use the following notion of empirical entropy, following [CGZ24]:
Definition B.1 (Empirical entropy). Given a language model Model, a sequence E E", and we define the empirical entropy of Model for on subsequence [i,]] to be:
and i.j E t.
H iisl (t, Model) == log (odel (1:-1)).
By definition of Model, we have log (odel(te.) (1:s-1) = - log Pri-Moddi Model (tay = tay fis-1
t1=-1). When Model is clear from context, we typically drop Model from the notation, so that
H Ha (t) == # (t, Model), and moreover write (t) == (t, Model), H
H (t) == H (t).
Finally, note that from the chain rule of probability, H [ (t) -t) Eu= (t)
Our main goal in this paper is construct a watermarking scheme for Model, which is a tuple W (Setup, Wat, Detect) of probabilistic polynomial time algorithms with the following semanties:
Setup(1^) takes as input security parameter
and outputs a secret key sk.
Wat(1*, sk) takes as input X, sk and outputs a sequence t =ti.z E E4, for some L E N. Detect(1>, sk, t) takes input sequence E Σ' for some E N and outputs either True or False, denoting whether t is detected as being watermarked.
We next define the security properties we desire in our watermarks, in terms of a security parameter E N. Some of our results operate in the "large-alphabet" setting, meaning that the size of the alphabet for the language model can depend (polynomially) on A. Formally, we consider a language model family indexed by X, (Model(A)) where the alphabet for Model(A) is denoted by E(A). Our watermarking procedure should produce string in Σ(A)* which is computationally indistinguishable from an output of Model(A). order for us to establish a computational separation between the process of outputting watermarked text and an adversary running in time given by an arbitrarily large polynomial in X, we assume that the length of an output ~ Model(A) is bounded by (A), where Imma((A (A) some function growing as poly(A)." When the value of À is clear from context, we drop the argument À and simply write Model, E.
Definition B.2 (Soundness, Undetectability. & R-Robustness). Consider a language model family (Adel(A) together with a watermarking scheme W = (Setup, Wat, Detect). We define the following properties of W:
W is sound if for all X E N and t E
Pr ske S1
(Detect(1*, sk, t) = True) <neg
Wi is undetectable for all X N and any probabilistic polynomial time algorithm Dist, Pr (Dist Model
Modal (1^) 1) Pr (DistWar(1* War(1> sk) (1^) 1) < negl(A),
where D means that Dist can make repeated calls to O, which generate sample from the corresponding distribution (either ~ Model or ~ Wat(1> sk)).
Fix some family of channels (8())) where each & ((A) is a collection of channels E: Σ())* + A(E(A))), and family of functions 3x N + N. Then W is defined to be B-substring robust to the family (A)) if for each À E N, and each channel E 6(),
Pr ske- Setupp111
[i.j E [Lmax s.t. Detect(1*,, sk, t') = False and H! (t) 2 3x - i) In (n(2))) I negl(A).
(a-Wat11* (((())
Above, we use the convention that to be interpreted as an element of mm)) by padding it with instances of the terminal token END. Thus, substring robustness requires that if we choose any substring of length from the output of Wat and pass through an channel E, then the output of the channel is still detected as watermarked with high probability.
Thii requirement appears to be implicit in [CG24], though it is not explicitly stated therein.
16

---

B.2 Notation
Given n E together with a mapping π [n] + [n] and a string x = (2i,..., Fn) E E", we write ι o == (Ix(I):....) Zn(n)) l". Given mapping ø X + y for (finite) sets N and a distribution P E A()), we let o o P e A()) be the push-forward distribution for Φ, i.e., (& o P)(v) p( (( (v)).
Given a mapping 1/ X' + y for finite sets X.Y, we let (xx) :- (b(x) : x E 2 C V. and for any y" C. v0 (Y") = {x Ex : vx)) E V" Finally, for tuple (x1...... Fnn X let (2) = (v(z))
E
For Σ and J (Ju,..., je), we let yJ E E' denote the vector yJ == (U Bz ). Given set S. m e N. and a string y E S" we define Unique(y) == {y : i E [m]] C S, i.c. (nique is the set of distinct elements of y.
C Secret-key substitution PRCs
C.1 Hardness assumptions
In this section, we discuss several standard conjectures the hardness of PAC learning which imply Assumption 3.1. We first recall the definition of PAC learning with respect to the uniform distribution:
Definition C.1 (PAC learning for the uniform distribution). Suppose that for each n E N. we are given a class F, of boolean functions indexed by strings & E {0, 1) for some function L N - N; write Fr {F.: : 10" - {0. (00,))o) Given q E [0, 1/2), we say that J
in is (c(n), ((n)) learnable with noise level if there is poly(n)-time algorithm Alg which, for some m(n) E N, takes as input dataset D = ((zg, y1)) (e)))((())) and X E {0, 1)", and satisfies the following with probability 1 - 8 over ~ (ni 1)(6))) ). Unif((0, 1)*), F2(1)) (m(n)]):
Pr X=Unnif(O.13"")
(Alg((=,, (() X) * Fx(X)) S..
Proposition C.1. Suppose that a family of functions F= (Fr)nen is not (1/3, -PAC learnable with noise level q E [0, 1/2) (per Definition C.I). Then, with n(A) = X, the family of functions (Frts)x is a weak PRF with noise level q (per Definition 3.1).
Proposition C.I is essentially folklore (see, e.g., [BR17]), but we provide a proof sketch for complete- ness:
Proof sketch of Proposition C.I. Suppose that polynomial-time adversary Adv satisfies
Adv
F2(-) (Im(A))
EFust
Adv
Funif
(Im(Al)
2 2--0111
where Funir 10 + {0, 1} denotes uniformly random function. Suppose that Adv makes at most m()) queries to its oracle (either (-) or FUnit). Consider the algorithm which re- ceives mn)) samples (I,, with x, Unif ((0, 1)0m,,)),,,,,,)) = F, (2.) for an unknown s together with X Uni m)m())), chooses a uniformly random index m' E [m(() - I]. and then runs Adv with the oracle responses given by (((x,, ())mm)) (X, (zz, jem zy Unif 1)"), yj ~ Uni 1}) for 2 m' + 2, for each value of b E 1). By hybrid argument, for some b E {0, 1J. this algorithm must have X (01) advantage predicting (X). A standard boosting argument [FS95] then establishes the existence polynomial-ting algorithm that (1/3, 1/3)-PAC learns the family F.
where
By Proposition C. either of the two assumptions below implies Assumption 3.1:
Assumption C.2 (Sparse noisy parity). There is no polynomial-time algorithm which P33 learns the family (Fa), of log(n)-sparse parities with noise level q = 1/3, iee. Fn = (F,(x) = Die(n) D49; s e {0, 1 13"h ||s||1 = log(n)).
17

---

It is straightforward to see (using a hybrid argument) [Blu03] that Assumption C.2 is equivalent to the assumption that there is no polynomial-ting algorithm which identifies the hidden log(n) (n) -sparse string E {0, 3r with constant probability.
Assumption C.3 (IBFKL94), Section 2.3). There is no polymomial-time algorithm which (1/3, 1/3)- PAC learns the family (I defined below, with noise level q = 0:
In = [.CS..s. - Maj(a, E +
Iz S C [n|] are disjoint subsets of size log(n))2
iES,
Similarly to the case for Assumption C.2, Assumption C.3 is equivalent to the assumption that there is no polynomial-time algorithm which identifies the function Gs,,s, with constant probability. We remark that [FGKPO9. Theorem 3] shows that an algorithm which learns log(n) noise level 1 - (()/n) implies the existence of an algorithm which learns (noiseless) -njunnass (with both learning algorithms being over the uniform distribution). Notice, though, that Assumption C.2 assumes there is no efficient algorithm which learns log(n) -sparse noisy parities with noise level q bounded away from 1/2, which is stronger than assuming hardness of learning log(n) - noisy parities with noise level q = 1/2 - O(1). Thus, even given the reduction of [FGKPO9], Assumption C.3 does not appear to imply Assumption C.2.
parities at
C.2 Additional preliminaries
Weakly substitution- -obbuuduttio-bbuudeed channels. We will show that our PRCs are robust to a slightly more broad class of channels which are only guaranteed to introduce a bounded number of substitutions with high probability with respect to a uniformly random string from the channel's alphabet. The codes of [CG24] also enjoy robustness to such channels; thus, the robustness guarantee for our substitution codes is directly comparable to that of [CG24].
Definition C.2 (Weakly substitution bounded channel). We say that channel & over an alphahet E is pweeaky-ubbsiittioo--oomld if for any n E N, P (Dtam (v, 2) > pn) S neg)(n).
Noise sensitivity. For E 10, we let N₂(x) E A((0, denote the distribution over y. where y; v, with probability p/2 (and y4 = 1 1- with probability 1/2-p/2), independently for each i. Note that y ~ (z) is generated by flipping each bit of x with probability Define
[S.[]] =
(J(x) # [w)). Also write [ -sc(m)
Lemma C.4 (Theorem 2.49 of [ODo14]). For any : 10,1)" {-1,1}, we have NS.sf] EE= (1 (1 25 W']])
Corollary C.5. For any f (0. 13" + {0, 1). we have NS = -E di (1 28);, for some .o..... 0n 2 0 satisfying do + ... + on 1/2.
Proof. The corollary is an immediate consequence of Lemma C.4 applied to the mapping x +
2f(x) 1, together with the fact that any f : {0, 1)" + (-1,1} satisfies Ei= W*[[] =
C.3 Proof of Theorem 3.2
Proof overview. The proof of soundness Lemma C.6 is straightforward; see Appendix C.3 for details. The proof of undetectability (Lemma C.7) of PRF-PRC q] uses Assumption 3.1: undetectability failed to hold witnessed by some adversary Adv, then could construet an adversary which violates pseudorandomness of F (per (2)) by simulating Adv, using computational efficiency of Encode together with the PRF oracle to implement the oracle calls for Adv.
The bulk of the proof lies in establishing robustness to p-bounded substitution channels (Lemma C.8). Let us first make sure that Decode(1>, sk. y) returns @ with high probability if its input y is simply an output of Encode( 1^ sk, 0) (i.c., if the channel & does nothing to its input). Indeed, the tuples (a,, w:) (for E [m()) ())) computed in Line 11 of Decode are exactly equal to (z,, (x;) @ e,). As long as the noise rate 9 of e, is bounded away from 1/2, the statistic W computed in Decode will be larger than m(A//2 + In(m( / (A) with all but negligible probability, as desired.
18

---

Algorithm 2 PRF-PRC[F, P. g]: Generic PRF-based PRC
Require: Weak PRF family F (Fx)x. where Fx {Fs {0, ())1))()) + {0, 1}} indexed by 8 E {0, 1)(()) parameters p, E (0, 1). Functions m()), - N satisfying
((A) 2 (n(A) + 1)m()),
1: function KeyGen(1*)
2: Sample s ~ [f0 1)((a) and 2 ~ (10, 1)N(A)
3: Let π [AV [A] be uniformly random permutation.
4: Return sk = (8, 2,
5: function Encode(1>, = (8, 2, T),0)
6: Sample =1,,.,, (n0 1 1)m(A)) and 61, e1....; Ber(g).
7: Sample r (0, (00
8: Define a = [[ @ Be)), (Fm()), (Fm(()) @ em(2)).r).
9: return the string क (a + z).
10:
function Decode(1*, sk = (8, 2, π 7),9)
11:
Let ,
E (0. 1 1)m(A) and wi.-... (m(A)
10.13 be defined by
((I1, W1), .... (mm())) (m(()))) (( 1 o y) (m)())))
12:
Let W = Σラ= 1ww, F, (z;)).
13: If m()) + +nn(m(A)) return 0; otherwise, return I.
Now what if y is drawn from Ely"), for yd + Encode(1*,, , sk, 0). for some p-bounded substitution channel E? Then the tuples computed in Line 11 of Decode may be written as (z/, w/) (for e (m())), where (z', wx) are "perturbed" versions of (z,, wi), where I; ~ Uni 10 1}m(AA), w; = F. (zx) @ e are as computed in Encode. Although the channel & may introduce substitutions in an adversarial fashion (i.e., it may not introduce substitutions at each position independently with probability p), by virtue the fact that the output string of Encode π (a for uniformly random {0, 1))( . [N())] + [N]) we can show that (x/, w!) is close to being distributed by perturbing each bit of (æq, we independently with some probability p' S. p. The proof of this fact uses an approximation a Hypergeometric distribution with Binomial distribution: roughly speaking, the permutation π allows us to "pick out"" for each i, a uniformly random subset of ra()) +1 positions corresponding to (x4; w(), out of ((A) total positions of the string y. Of these, p' (N)) S p- (A)
changed by E, and as long ((A) >> n()), applying & thus has nearly the same effect as changing each of the (A) + positions of (x,, w:) independently with probability p'.
Given the above, we then use the fact that if x; (n0, 1 1)m(A)) and x is formed by flipping each bit of x, with probability p' S p. then (x;) = (x4)) 2 (1- 2p) 2 } + (1- 2p)) log (A). This is a basic consequence of the Fourier analytic expression for the noise sensitivity of Boolean functions (Lemma C.4), together with the fact that Fx(.) is r-local for some T S log(n Note that (1 2p) mA) 2 n(A) (R, thus, as long as mx)) large enough polynomial in n(A), we can show that the statistic Σm(A) [(w/- (z()) will be bounded away from m()//2, which implies that Decode returns ( with high probability.
One complication of the above argument comes from the fact that, due to the adversarial nature of the channel E, the random variables (I:,, (2,,,,,,2 C,,2%, wf) may not be independent across different i.
Thus, to ensure concentration of the sum Em(A) 1( = Fz(x))} to its mean, we use Dobrushin's concentration inequality for weakly dependent data (Theorem F.3) and bound the dependence of these random variables for different i using the fact that N(A) is sufficiently large.
Formal proof. Suppose that we are given some p < 1/2 together with a weak PRF family F= (F {0, 1) - f0, 1) (o) with noise level q < 1/2 which verifies Assumption i.., for some function r(A) I log n(),, the family -oA)-local. We consider the construction PRF-PRC[F, p. in Algorithm 2. We let the functions r2)),, ((A) be given by the PRF family F.
19

---

and choose m(A) Co (1 (1-2g) 2q) +4 -n(A) log 25
N(A) 3m(() (n(2) + 1)²,
(3)
where Co is a constant chosen sufficient large as specified in the proof below. By Definition 2.1, to prove Theorem 3.2, it suffices to establish soundness, undetectability, and robustness p-weakly- substitution-buundee channels: we do so in Lemma C.6, Lemma C.7, Lemma C.8, respectively, below.
Lemma C.6 (Soundness). For any function famity == {Fe)s on (0,1)*(A) indexed by {0, 1)((), and p.q E (0, 1). PRF-PRC[F, p, q] is sound.
Proof. Fix X N. and write n n()). ((A). m m()). N N(A). Fix any y (0. (0.13.. Let 2i,....,5m E (0, 1m wi:..... ..... Wm [0,1) be defined in Decode sk, y). i.e.,
((11, w1)....; (Tm; (m)) )- = ((TT oy) θ (n) where sk = (s, 2, r). Since π,, 2 are uniformly random in their respective domains, it follows that W = -j= [wj = F.1r)) is distributed as Bin(m, 1/2) for any fixed s, meaning that, for any d (0, 1), Pr, (W > m/2+ m log 1/6) S Choosing 5 = 2- log" < neg)(A) yields that Pr KeyGenn (W (W > m/2 log(m) Vm) S (A).
as desired.
Lemma C.7 (Undetectability). Fix p.q E [0, 1/2). Suppose that J = {Fa}s is weak PRF on (0, (0.1)alA) with noise level (Definition 3. 1), indexed by E 13 ((A)) undetectable.
() Then PRF-PRC[F, p. is
Proof. Fix À E N, and write n - r(A), = ( polynomial-tie time adversary Adv. Let sk = (s, x) t KeyGen(1~) denote the secret key for the PRC. Suppose that the adversary makes a total of Q queries to Encode(1^, ,kk 0): its view consists of Q uplees (((x)),
= NA). Consider any probabilistic
(3) F. (x @ el)),,... .....,, (am1) Fs (.(m)) @ em")) @ z), for i E [Q]. If Adv satisfies
Encode) (1>, sk. ( (1²)= =1) - Pr 2
=1) 2 2
Pr Ke-eKeGen(1A))
(4)
for some constant c > 0, then we could construct an adversary Adv' which violates security of F, (namely, Definition 3.1), as follows: Adv' makes Qm calls to F.).) on random inputs, which
gives it samples (xz)" (z())) ()) a e for j E [m], E [Q]. draws a uniformly random permutation
T: [N] + [N] and uniformly random string E {0. 1 and outputs the result of Adv given the Q tuples ( == π o (((z)) (x e e (8) )...., (x F& (amm @ (t) ) (()) @ 2). where y.(() are uniformly random strings of length N (m+ 1)m (for i E [Q). Note that if the mQ calls made by Adv' were generated by a random function, then the strings y are uniformly random in (0. 1 1
conditioned on the event that u are all distinct, for E [m]] i E [Q]. The probability that all zyy" are distinct is at least 1 - mQ/2" 2 1 - negl(A), meaning that, by (4), Adv' achieves advantage - negl(A) on distinguishing random element of the family {Fa). from a uniformly random function, thus contradicting the security of F.
Given N,t N, let JN.i denote the distribution of t-tuples J (f.....,je) where J1. . Ju drawn uniformly from [N] without replacement.
Lemma C.8 (Robustness). Fix p.q E [0, 1/2), and that F = (F.) (F.))e(0..) is a T (AA)-ooca function family. Then PRF-PRC[Fpp q] is robust to any opreaak-ssubsiiution-bbbeee channel.
Proof. Fix X N, and write n = n(A),e ((A), m N = N(A). Let E be p- weakly-substitution-bo -oundee channel over {0, 1}. Given I,, ej ( E [m] drawn as in Line of Algorithm 2 and a uniformly random string r ~ Unif (0. 13 1)N-(n+i)m), consider the string a = ((11, Fx(x1) ee) ......., (Im, (x ) @ em ))), ), and note that the output of Encode(1* sk, 0) given that I1, .... Zm, C1, .... em, sampled is = π (a e 2). Given v E {0, 1)"" we let.
20

---

with slight abuse of notation, E()) E {0, 1 denote random variable drawn from the eponymous
distribution (v)) E ( 1)) We have
(N E()) @ (n E(T o (a 2))) @
--- o ((T 2) E((T a ())2)))
Since 2 and ı are chosen uniformly at random in their respective domains and independent of a, follows that the distribution of u is the same the distribution of
u' := To ((TT o a) @ u i {())
@ (T (v @ {())))
where e ~ Unif 1)")) is uniformly at random and independent of π, (In particular, we have used the reparametrization that sets := (Λ a) @ (I o).
Let us unpack (T- o (u @ (()))))(((++)))) = ((11, wf).... (x/m w'm),, where 2j E (0, wy E {0, 1) for j E [m]. Note that the distribution of the statistic W computed in Decode sk, Eg)) is exactly the distribution of
Σ 1w De + F.(z)) = Fo @ 221) 1=1
(5)
By our assumption that the family F, is r-local, for each E {0, 1] there is some J, E [n]]
and G. : [0,1) + {0, 13 so that (x) = G,(aJ,) for all x E {0, 1]". Define = T + 1 and
G² (0. - 13 by (z) = GT
21-1) 24.
For Boreach j E [m] and fixed & E {0, 13 we have that
Pr (1o) tc, F, @ x)))
=(1 224 Pr (F,(2)) = w/ F,(2, e mz))) +g
=(1 - 224 Pr (C,)( ( @ (zz)) w/)) + (6)
where the probability is taken over 2j 10"") ej Ber(g). Unif( (0, 1 1)"), the uniformly random permutation n, and the randomness in & (which together determine w'j, r²y) We now apply Lemma C.9 to the function
24) + 1(G 0) = (( 21-1) @ (zz),,, 20)
Note that, for fixed v, E(v,, since is chosen uniformly at random (and independent of v, { a), the distribution of ((rr)),,, 2., w()) is exactly the distribution of yJ for J IN,,, for y = @ (vv). Let us write p(y)= = wt(y)/N, for E {0, 1N Thus, for any fixed 8, we have
Pr (G. 0) = (, @ (z)))s, w/))
Ey B E J~JNN [[GG,(())),,,00)) = (,, -C(((()),,))))))) e) 2,,0, y=uBE(e)
2t
> >B, 0
VN -
2t
-Ev,s(o) - -.
+ T.}
VN
-By,g(o) (p(v p(u -
G.((1,),,
21
VN-t
2t
-Er,e(e) [p(vo + 2p(v E())) (1 NS N (() [G.l)]
VN -t --22((00
1
1
2
2.,
p(u + E(v)) (1
2
+ 2
(1 -
2.
VN -1
1 1
2t
=Ey,g(e)
- + (1 - p(u + ((
2
2
VN=
1
2t
+
(1-2p) 2p1
N (N),
2
21

---

where the first inequality uses Lemma C.9, the fourth equality uses the fact that 2; Unif ( 1))) independently of v, E()) and the definition of noise sensitivity, the second equality uses Corollary C.5, and the final inequality uses the fact that wi(u @ {()) S pN with probability 1 - negl( N) since the marginal distribution of y Unif( {0, 1)") and & is w--eekly--ubbsitutionn-- -oordidoo--ouddd..... Since we have 2t VN-7 (N) Σ [ (1 2p)*+ +1 by our choice of N in (3) (which ensures that, as long Co is
sufficiently large N 2 Co (1 - 2p)-1 -log(n), and in particular that N t 2 16t 2p) - as long as the security parameter À is sufficiently large). it follows from Eqs. (6) and (7) that for each j E [m]. for sufficiently large X,
7 (1-)22tt) +
1 1 = - (11021)(11 -2p)++1
Pr(u) oe @ Fo(x,) F, (2,) 22)
2
(8)
Finally, we use Dobrushin's inequality to analyze the concentration of the sum (5); we utilize the notation of Appendix F.1 (in particular the influences defined in (43)). For each E [m]. define r = (In, ej, w zz)). Let Pr........ denote the joint law of .T,....,''. m. and Pr,j-_ denote the conditional law of T, conditioned on r- For any distinct i.j E [m.]. we have that
(n + 1)2
max (Tmm((imm) 7 i s.n0n
drv(Pr. (11. 7---)))))) (r.jr_ Thy 7-5 s N - m(n + 1)
since if, for any i E [m]. we condition on x Z-1, e-1, U (v). and S = for ((a (n +
6) E Im][i), b [n + 1]}. the distribution of r (z,, es, w/, x/) is given follows: ay ~ Unif((0, 1)"), 6 ~ Ber(g). and (w,, is distributed (independently of 2;, 6j) as a tuple of + 1 distinet elements of v @ E(v) which are not indexed by coordinates in S. Moreover, changing the value of Cj. and (() 1)(n + 1) + b) : be [n + 1]} changes only n + 1 elements of S, so by Lemma C.10 with l: = 1 and the data processing inequality for total variation distance, (n+1)²
changes the conditional distribution of (w), by at most N-m(n+1j
Thus Exeman (f S m[(++1]
N-m(n+1) 1/2 and EiEmI (T= 1:mm S m(x 1)
NNm(n++) S
1/2 since we have chosen N = 3mn(n + 1)² in (3). It then follows from Theorem E.3 that for any
ô > with probability 1 - over the draw of I 1:mm
W =
1w @ Be 1 Fz(1,) Fa 1 02 2 D
Pr(w', te, @ D Fo(z,) = Fo( @ 222))) - v 4m In (2/5)).
Choosing 8 = 2 2expp - (nn(m)) S negl(m) S (A), and combining Eqs. (8) and (9) and the choice of in (3), we see that as long as the constant Co in (3) is sufficiently large.
Pr W
2 + In(m)vm) 2 Pr ( 2
+ (1 21) 2p) 1 In(m) (4m)
8.
(In particular, we have used that our choice of m ensures that m (1 - 21 - 2p) +1/ > 3 (n(m))mm.) Since Decode(1>, sk, y) outputs @ exactly when W 2 m + log(mm) / /m, we have established robustness, as desired.
2
Lemma C.9. Fix N E N and let y 10,1 be given with wily) = k. Fix E N, and let f: [0 {0,1] 1} be a given function. Then
2t VN-1
[)~Jw,[f(ss)
Proof. It suffices to upper bound the total variation distance between the distribution of yJ and the distribution of x Ber (er(k/N)" By symmetry, this total variation distance is the total variation distance between Bin k/N) and Hyp(N, k, t), where Hyp denotes the hypergeometric distribution
(so that, in particular, W Hyp(N, (N, k. I) satisfies Pr(W =w)
By (RS23, Theorem
1] (restated in Lemma G.2), this total variation distance is bounded above by
21
'N-T
22

---

Lemma C.10. Let So. S₁ be sets size N so that |Sa n1 N - for some h < N. Letn < N be given. For E {0.1} let J, denote the distribution of a tuple J (i....... :n) of n elements of So drawn uniformly without replacement. Then (rv(J. J1) S nk
N-n'
Proof. For any tuple J all whose elements belong to So nSn (which we write as J C. So Si). we have [J] = (J) by symmetry. Thus we have
(N-k)
(N - k)... (N - - - +
div(Jo: FI) = Pr (J & Su n(;) = J-Jo
=
N... (N +1)
- n1 - k
nkb
<
5
N
N
D Insertion/Deletion PRCs from substitution PRCs
Suppose that PRCsub PRC which robust to (1/2 pp))-subsitutioo-bouie bounneed channels, for some po > O. Choose P 2CD a/ /po. where CD is the constant defined in Lemma D.8. Note that PRC (PRCsb p| (defined in Algorithm 1) has block length m(() == [T((): In(2)] and alphabet size |Σ = (A) = p r()) 2Cps nA)). Thus, to prove Theorem 4. suffices to show that PRC PuC p] satisfies undetectability (Lemma D.3), soundness (Lemma D.I), and robustness all (1 Po -dde---d-oddd channels (Lemma D.8), where Grob constant defined in
Lemma D.8.
Additional notation. Fix q, m E For integers j 2 1, we define Unique,()) == {a E [a] Hi y4 = a)l j), i.e. Unique, (v) is the set of elements a E [g] so that exactly j elements of y are equal a. Given j N. we define Uniquezi (v) Uッı Unique (v). Note that Uniquely) Unique-1(() (v).
Lemma D.1 (Soundness). Let PRCsub be PRC for substitutions. Then the PRC PRCidx(PRssa in Algorithm is sound.
Proof. Fix X E N, and consider E [{(A)]m(A), Define y' E {(,1) 1)m()) in Line 12 of Algorithm 1. Since PRCsub sound, we have
Pr
(Decode(1>, (sk, =1)= Pr (en.KeGGes..a11)
(Decodesu (1*, sk, sk,y') v/) =1) negl(A).
(sk, (
To establish undetectability, first need the following lemma which states that PerturbDifference((,, m,)") v²) outputs a uniformly random string in [n]m when its input y is uniform over {0, 1)"".
Lemma D.2. Given positive integers S n, the distribution of PerturbDifferencee(n. m, v.) (Algorithm 1), for 1 ~ Unif((0, ))m),, is exactly Uni"([
Proof. Suppose yd (ni 1) ~ "ni""(n]""), and write S = {i E [m]] yf = 1}. S
Unique(y' as in PerturbDifferrnce.
Given y E [m] denote its frequency mapping freq(y) f [m] - N20 by f(j) |Unique, for j E [m]. Note that freq(y") = freq(y) with probability 1, where y denotes the output string of PerturbDifference (this holds since the maps a, necessarily injective). Thus, the distribution of (req(y) is exactly the distribution of freq(u)) for y² "nif([n]"")
Next, we claim that any two strings z E [n]m with freq(2) = freq(2') have equal probability of being output by PerturbDifference. To see this, we may choose a permutation and σ [m] + [m] so that (T ((20(1) = 2 for i E [m]. Next, it is straightforward to see from the definition of PerturbDifference that the distribution of its output remains unchanged if its input y is
[n] - [n]
23

---

replaced with the string 1 defined by V7( := vp. i [m]] and the sample y' in Line 16 is replaced with the string ÿ' defined by iن == x)) i E [m]] The distribution of the sets 5 s C [n] under this modified procedure is exactly the distribution of (((*) when S are drawn according to the original procedure. Thus, the probability of observing 2 under the original execution of PerturbDifference is the same the probability of observing s' under this modified execution of PerturbDifference.
It follows from the two previous paragraphs that each string in [n] th has equal probability of being output by PerturbDiiference(n, m. g²),, under y Unif([)) ([n][)))))))))))){) as desired.
Lemma D.3 (Undetectabilityy. Let PRCsub (KeyGensub- Encodesub. Decodesub) be PRC.for substitutions. Then the PRC PRC in Algorithm is undetectable.
Proof. Fix x E N. and let write 9 == (A), == r²(). Consider any sb [g] - [n] which satisfies 1 (i) = q/ n for each j E [n].
Given a string 5 E {0. 1)", let (v)) E [4]" denote the random variable which is the output of the following procedure: given yP. let y + PerturbDifference(n, m, v"), then sample 2 E [g]" as on Line 8 of Algorithm I (using v and output the resulting string s.
Claim D.4. For any fixed ub as above, the distribution of Eg(y²), for for o ~ Unif((0, is uniform on [a] m
Proof. By Lemma D.2, the distribution of + PerturbDifference((,, m, y²) is uniform on [r]]". Since (p) [b] = g/n for each j [n]] it follows that the distribution of the output string uniform on [g]m..
Now consider any probabilistic polynomial adversary Adv, and suppose that
(Acoeec (sk, (1²) = ( - Pr (Adv" =
(1))=)))=(() =
Pr KeyGen)))))))(11
for some function v -> R20- We construct an adversary Adv' for the substitution PRC PRCSub as follows: Adv' first generates &i [q] + [m] conditioned on |e) = q/n for each j E [n], Adv' then simulates Adv, where each time Adv calls its oracle O(m) for some message m, Adv' performs the following. It calls yd + O' ('(m (using its oracle O' which is either random oracle or Encodesub(1) (1 sk, m)), then applies y PerturbDifference(( m. v²), samples 2j Uni (aa) = y5 for each j E [m]] and then uses = as the simulated output for O()). By definition of Encode Algorithm 1, the adversary Adv' faithfully simulates the execution of Adv E when the oracle ('(-) for Adv' is Encodesubl (1>, sk, When the oracle O' for Adv' is a random oracle U1 (i.e., which outputs a uniformly random string 3d ~ Unif( 1 })"),, then
Claim D.4 ensures that the adversary Adv' generates a uniformly random string [g]m.. Thus, we
have that
Encodesie (1 (t.,,kk))))))))) ( =1) Pr (IA)))((1>) =v(=)))
Pr skt ski- KeyGeesu
and since PRCsuh is undetectable, we have u()) neg!(A), meaning that which implies that PRC is undetectable.
D.I Lemmas for robustness
Next, we will establish several lemmas in the aim of showing robustness of PRC1 (PRCsub: p). The below lemma bounds the number of replacements PerturbDifference has to perform in Line 20 or Line 23 of Algorithm 1.
Lemma D.5. There a sufficiently large constant CD.s 2 so that the following holds. Fix positive integers n., with m [n- In(2)] and e E (0, 1) so that n 2 Cp.s (1/e)///e For [m]m
write (==) E (0. 1) to be the string D(z); == 1 E Unique(=))- Then
Pr ((..1) *+ Sr-PPrturbDfffeeeeneenn..m
(DHam (v D())) 2 en) s 1 neg(
24

---

Proof. Given v², let 8" = fi E [n]
vr 11 be defined as in Line 15 of PerturbDifference. By
Cheroff bound, for any 8 E (0, 1),
(15
n 2 2 (loo(2/6))
Pr (0,
S
(10)
Now consider y² (ni"([n]"")) and 8 Unique(y") ) in Lines 15 and 16 PerturbDifference. By our choice of m, and Lemma D.6 with n, y² is typical with probability 1 - neg((m) 2
1 - (n), which implies that ||S - 2 S 2/ (n(m) + 1. Combining this fact with (10) and
choosing 8
(n)) s nn) gives that
Pr (0 Unit(()))) (1|5)) |S 2 en)
S ))~Umt(((01))))))))) Unt((((((" (1|5)) - S 2 2/mln(mm) +1+ vnln(n) I negl(n),
where we have used that 2 3/nln(n)
2 (m + vn In(n) result of our
assumption that n > (2Is(1//s) for sufficiently large constant C. The conclusion of the lemma x² follows by noting that ||S - |8 DHam (1/ D(2) with probability 1.
m is defined to be typical if the Definition D.1 (Typical string). Fix q,m E N. A string E [1] following inequalities hold:
q- (1(1-es (1-exp(-m/u)) m In S [Unique(=) q . (1 exp(-m/q)) + 2 In
Lemma D.6. Suppose that q 2 /m/ In(m). With probability 1 neg((m), uniformly random string Unim([ is typical.
Proof. Consider a string [q]",, and define
F2( |Unique (+)
11]-=11t ullii [m] = a}l 1}.
a=1
Note that Fi satisfies the bounded differences property with constants e; for each E [m]. Note also that
Ep -q (1-
m
1 m
.....11 (1- 1//)m-h q
Σ kmj
9 k. 1/a) m-
q k
km
We have that [x)] q. (1 (1- (1 m/) and using the bounds exp(-1/g) 1/9 2
exp( - (100-119-10 - 1//"-1119)) for 2 1, we conclude that
q (1 exp(-m/g) E[Fi < . (1 (aa0-m//amm//))) s (1 exp(-mm/)) m/q.
By Theorem F.1, for any 8 (0, 1), we have that with probability 8 over Unif((g)'"))
[B) F (z)) < /m ln(2/)).
Choose = 2 eexp(-nn(mm) (so that 5 < (m)) and note that our assumption that 2 /m/ In gives that m/g S ln Combining the two displays above gives that with probability - negl(m) over 2 (nni(((gm))) we have
- expeeppmm/o0 - m/mmnn < Fi(2) $9 11-1111xppp (11-xp((-m/q)) + mm
Given integers n q so that q/n E N, let pptn denote the uniform distribution over mappings ub : [g] - [n] conditioned on the event that |bb -() = q/n for each j E [n]. For sets S c Ω define A(S, T) = (TV(S)
n.g
25

---

Lemma D.7. There is constant Cp.7 > 0 so that the following holds. Consider p. E N
satisfying q/p = n, let 2,, 22 [q] be given, and write Z == 2, n 2z. Define Z : 12], 21 == [21|, 7-2 = 12), and suppose that 0 v S S 10 are given so that
Z E (2((2) (2(
Z - 2lm(2) +, 2 pn,
CD. n N
S S SPS
1/,
e
(11)
Then
(A(((()) n. (1 -1- 23c )) < negl(n).
P
Pr Yiu Prup mn
Proof. The fact that 2/c S p and max ( 22/n] S 2 implies that max //, 72/D) I en.
Let us write Si == exp( - ///n), S2 = exp( - n2/n)= so that Si E [(1 <)/2, 1/2 + 6 and C2
(1-4)/4,1) 1].
Note that the mapping v (1) v (n) C [g].
[g]
[m| is specified by the random variables
Let define
F( = | P(u):=A(((())) (2))
Σ 1 A(EE)
Σ (0,
where G(T: 21, 2x) E (0. 13 (for some T C [g) is defined be equal if and only if either (a) Tnz 0 but Tn 2 = 0 or (b) T n Z, + 0 but T n Z, = 0.
Step 1: Bounding the expectation of F. Fix any E [n], and note that s (x) C [q] is uniformly random subset of size p. Note that
Pr (e) (4)
+ (i) 2. 0)
Wee Part pite
+ 0 3 (1) n 2, = 0). Pr Pr ( (1)
(v (i) ( Zg = 0).
(12)
By Lemma D.9, we have
Pr ( (1) = 0) s exp(-pZa/1) -epp (Z2/-//))) C2
(13)
N0w par m.4
and
Pr (xb 21) 1 (1) Zg = 0)
// pats
p(Zz - -)
p(Z1 2)
21 exp
q Zn p
(q Z/- p)
7
p73
$1 cxp
n - Ze/p - (g - Z2 - p)2
<1 exp (-(1 + 4e) 22) exp(p) exp(-Z2(1 (1((144))/(ppn)
<1 exp(In((1) 8c) exp(p) exp(-8/p)
21 G (1 + p)
96) S G (1 p). (1 96) (1 (1) PSi + 10c,
(14)
where we have used the fact that, conditioned on & .- (i) n 2g - 0. (i) is distributed as uniformly random subset of [g] Z2, which has size Zz. Moreover, the third inequality above
uses the upper bound Zz/p S and the lower bound 7 > pm in (11), the fourth inequality uses
the upper bound Zı /n S from (11), and the remaining inequalities simplify and use the fact that e,p (0, 1/10) and 8/P p < e.
26

---

Using Eqs. (12) to (14) together with symmetrical argument to bound 21 0), 10 we see that, for each [n].
* 0, の (i)n
E Pow [G (1); 21, 22)] S62 ((1 - (1) - pci + 10c) + Gi ((1 - (2) - P52 + 10c)
<(1 + (2 - 2[1 +p) + 20c
1
<
+
+ C2 -(1- (1 + + 20c
2
1
+
+c52 -Ca(1 -c) + 20
2
p + 22c,
2
5
where the second inequality uses that {1. C2 < 1, the third inequality uses that S1 E (11-e)2,1/2+td)
and the final inequality uses that (2 E [[1 c) 1]. It follows that
P - 22c
Barryy [F( 5 2
(15)
5
Step 2: Concentration of F to its expectation. Consider any subset H C [n] size Hg == [H] satisfying 4pHo I n, and define Fx(()) == EEe (0): 21, 22). Note that Fu satisfies the bounded differences property with respect to the random variables v (i), i E H. with constants
c = 1 for each E H. For any distinet i E H. we have
drv( (P (vb (
x (In 2/ (i),, Pptn (v (1)) = -.. (N0 1a
max v ((K)Cl)) (EM)(E)) V (1)
max
PRE (V)- n 1 (j) + 2 1
(16)
Ck) (EA)
" 1().v (1)c((
<1 1 q (Ho 1)p
1
9 Hop
<1 -1-(2 (1 2p/g)² - 200² /g S 1/(2H)),
(17)
where we use - 120,113, to denote the collection of tuples (k, (k)) for k E HM(..j In (16). the probability is over vb (2). whose conditional distribution is that of a uniformly random subset of (vb (() U "6- (H))), of size p. The second inequality above uses Lemma D.9, and the second-to-lase inequality uses the fact that Hop + 1 > Hop 2 g/2, since Hop S by assumption, and the final inequality uses that q 2 4p² Ho. by assumption.
The above chain of inequalities (17) guarantees that 1 (v 1xx S 1/(2H)) for all i,j E H with i + j. By Theorem F.3, it follows that for any ā E (0, 1),
Pr Neww
(Fx(()))
[x((1)] 2 v /4H, In(/0)) < 5. Pan
(18)
Write H == Cj In3 n for a sufficiently large constant C1 to be specified below. Note that 4p(H+1) < e²
n as long as n > &Cielann which in turn, since p S n/4 holds when n 2 C/e² for a sufficiently large constant C (chosen as a function of CD). Let H....., H|n/H] denote partition of [r] for which [Hy] E (H. H + +1. Since 4p(H + 1) S n, we may apply (18) to each Hj and use union bound, which yields
[F()) - E pmm [F(+)] n/41n(2/0) VH
nd < nō.
Pr Fi.g
(19)
Choosing 8 2 exp(p In (n)) I negl(n) gives that n 44/41n222 (n2/5)/ / H < 2n In(n)/ < en, as long as the constant C₁ is chosen sufficiently large. Combining Eqs. (15) and (19) yields that with
probability ne))(n) over the draw of to pptn F(B) v n ( F + 23c), which yields the claimed bound.
n.g
L
Note that, though our assumptions on Z1, Z2 in the lemma statement are not symmetric, to derive (14) we only need the inequalities Zz/p S and Zı /n 2, which hold when the roles of 2i, Ze are flipped.
27

---

D.2 Proof of robustness
We are ready to show robustness of our PRC PRC (PCCsbb to slit-bounded channels (Defini- tion 2.4).
Lemma D.8 (Robustness). There are some constants CD.s. Crob 2 1 so that the following holds. Consider any p > 1 and security parameter X E N satisfying n(A) 2 CD and Po E (CD&/p. 1/10Cr)b) and any (1 Crsspo)-edle edii-bounde channel E. Then for any PRC ---suuutiutioonoooaeeee chunnels, the PRC PRCix p)
PRC which is robust to (1/2
Algorithm is robust to
Proof of Lemma D.8. Fix X E N. and write := =m(A). := q(A), m == m(X), so that Po > Cps/p ppp22.22 2 1/p. Fix any 2 E [q] th which is typical (per Definition D.I), and consider any x' E [q] t which can be obtained form via total of at most (1 Crob -oo) substitutions, insertions, and deletions (which has probability 1 over ~ {() since is (1- CrobPu) (radP))-edi--buundee Write 2 := (n) n (nique(2'), i.c., Z denotes those entries of which are preserved in s'. Since is typical and m/9 S m/ (mp) - 1/p, p. we have that
[Unique(2)] 2 g (1 exp(-m/p))
mm
(20)
2 q. (m/q ))) 2/m m//mmmm 2 m (1-1/p) - 2//mmm,
where the second inequality uses the fact that exp(-x) S 1 x x
x²² for x E [0, 1]. Since the requirements 2 Cn.ap" and m [2n(2) -n] ensure that that 22mll((m Cn. is large enough), we have that [Unique(=)] 2 m - (1 - 2/p). Note also that it is immediate that [Unique==)] S m.
m/ p (as long as
Step 1: Using Lemma D.7. Since z' is obtained from 2 via at most 1 CrobPo insertions, delctions, and substitutions, we have | 2 [Unique[=]] . (1 CrabPo) m mm (CrabPo 2/p). We also have that (Unique (z))l s 2m. We now apply Lemma D.7 with
Crob -
2 = Unique(=), Z2 = Unique(='), e Po,
Po-
2
We must verify that the preconditions (11) are satisfied: first, we check that, as long as CD.s 2 8,
8
8p
sps n 1/4
Po CDs
where the final inequality follows from choice of n 2 p² Next, we have
[Unique[=]] E [m (1 2/p), m] C [(In()) <) n, (In(2) + c) n],
where we have used that m [ln(2) n2] and the fact that 2/p po = and ne npo 2 1. Similarly, we have
Unnique=z)) s 2m S (2In(2) + c)
C Next, we have |2| 2 m (CrobPo - 2/p) 2 (Croh 2)po m 2 2 Finally, we have that
pon pn, since m 2 n/2.
n nzp pt 2 (CD.s/Po)* (3Cps/e)** 2 CD.T/e²
(21)
as long as CD.s chosen sufficiently large. Thus, all constraints of Lemma D.7 are satisfied. Given wb [g) - [n]] and E [u]', define (=) E {0, 1) to be the vector defined by
(2);), i e Uni)ue()(=))}.
Then Lemma D.7 gives that
Pr P
DHam (Do(e))) 2 n.
P
+23c
+ 23c
2
+ +3c )) I neg)(n).
= Pr Pa
[(((nqqqe)))) (Uniqqel (2'))) 2 n
(22)
2
As long as Crob 2 300, we have
1 P
1
Crob
23c
<
10 Po + 23pp < 5po-
2 5
2
28

---

Step 2:
Averaging over 2. Let us consider the following "idealized" variant of Encode(1* (sk, v). m). which we denote by Encode (1 vb) (as the output of the below procedure does not depend on sk or m):
1. Sample y Uni
2. For each! j E [m]. choose 2, Unif([ xb(2) = 42}),, so that 2j E [q]-
3. return (m))
For any fixed & [g]m note that Pr(Encode (1^, A 2b) = 2) q and in particular does not depend on th this holds since each element 2j of a is drawn independently from the distribution which first draws Vj [[]] and then draws 2j ~ Unif(f= : v²(2) yj h); since (4)) = g/n for each a E [n]. this distribution simply (4]. Let Q denote the joint distribution (ı, 4h, 2, =,==) where y Unif([n]"") & Pptn. 2 is generated from y. as the above procedure Encode (1>, v)) and z' ~ 8(z). For any 2a [q]m follows that the conditional distribution (under Q) of & given = =0 is Pptn. Since d and z' are conditionally independent given 2, we have furthermore that for any 20. 2/1 E [ql"". the conditional distribution (under Q) of ab given 2 20, z' 2 is Pptn Thus, by (22). if zo is typical and z/6 can be obtained from zo with at most (1 CrobPo) m subsitutions, insertions, and deletions, then
( - 1
Pr DHam (Dp))
20, z' ==0 S neg)
Since is typical with probability 1 - (eg under Q (by Lemma D.6) and and 2' can be obtained from a using at most (1 CrobPo)) 17 substitutions, insertions, and deletions with probability under Q, follows that in fact
Pr (Dom( 2 n- - 5po S nng S negl(m).
(23)
Step 3: using pseudorandomness. Let Q denote the joint distribution of (g), 1b 2, 2') where y is distributed as the random variable y defined in Line 7 of Algorithm 1, 1/ ~ Pptn is distributed as the random variable defined in Line 8 of Algorithm 1 given the value of n.g and y (i.e., 2, ~ Unif(fa va(a) yj H),, and z' ~ E()). Using the fact a sample from E(-) may be produced by probabilistic polynomial algorithm together with Lemmas D.2 and D.3, we have that
DHam (Pt)) 2n 5po) )) (5-5p)) Q
(Dtm)(D())) n ( (2-5p0) 5po -5p)) Q
Pr
Pr
negl(n).
(24)
In more detail, arrive at (24), we reason as follows: if the difference in (24) were non-negligible. then we could distinguish in polynomial time between a sample yd + Encodesub (1^, sk, m) from uniformly random string 3d Unif( 1)"). as follows: we first generate y + PerturbDifference(n, m. m,)²) (as in Line 7 of Algorithm 1, then sample go n.g. then sample E [gl m by 2j Unif(fa (ba)) yi for [m], then sample 2' ~ E(2), and finally evaluate DHam THam(DD(s (z), (z))). In the event that yº < Encodesus (1*, sk, m), then the resulting distribution of (y, vh 2, 2²) is Q, and in the event that yd Unif( (0, 1)"), Lemma D.2 gives that the induced distribution over y is Unif([n]"") and thus the resulting distribution of (y, 1h 2, z²) is Q. Thus we would get contradiction to Lemma D.3.
Step 4: Wrapping up.
We have from Eqs. (23) and (24) that
Pr (D),()) 2 n -3pp )) < negl(m).
(25)
29

---

By our construction of the distribution Q, (2(2) y with probability 1 under Q. Moreover, we
have that
Pr (sk, v)) KeyGGe)))) (Decode(1*, v)), + Encode (1^, (sk, eb), m))
Pr (sk. 1)+ (eyGeee((())) (Decodesubl (1 sk, (E(()))) + m 2 + Encode L (sk, 2b), m))
Pr sk>-KeGensub (1 18),
(eeoodesubl (1 sk. (v + m yº Encodesubl (1x, sk, m)) S negl(
(26)
where E {0.1]" + {0, 11"H denotes the (random) channel which, given yº E {0, 13", first applies the procedure outputs (=') for z' ~ E(=). For future reference we let this distribution over (y"; =) where sk ~ KeyGensub (1ae), 1d + Encodeswus11. sk, m) be denoted by R. The first equality in the display above uses that the output of Decode(1>, > (sk, =') is given by Decodesub (1 sk, (=))) The second equality uses the definition of Encode(1> X (sk, r²). m) in Algorithm 1. Finally, the inequality follows since the PRC PRC robust to (1/2-
Lines 7 and of Algorithm I to generate = E [g] from y". and then
and the fact that with probability [o -ubstitutiosn bounded channels together with Lemma G.1 negl(A) over the draw of sb Petn sk KeyGensubl (1*),
y < Encodesub (1^, sk, m), and ~ (vx we have DHam (2', ,8) S (1/2 22 - po) n. This fact follows from the following observations:
By Lemma D.5 and undetectability of PRCsubr for any vh with probability negl(n) negl(A) 2 1 - negl(A) over (u", .)) ~ R. we have DHam(y' (v/: (z)) ) S pon. (In particular, Lemma D.5 ensures that DHam D.. I pon when yd ~ Unif((0, 1})" and then & is generated from yd as in Lines and 8 of Algorithm 1, and undetectabilityy of PRC ensures that this also holds when instead y" Encodesub (1 A sk, m).) Here we have also m(A), ((A))"")) 5²) (defined in Line 7), together with the fact that n 2 CD.5 (1/e)// by (21), as long as the constant
used the fact that (z() is the output string y of PerturtDiifferenee(((
CDss is chosen sufficiently large.
*
By (25) together with the fact that the distribution of (v), 2, z'=) where sb ~ Petn n.g²
R. and z' ~ E(2) is exactly the marginal distribution of (v), 2, 2') ~ Q. we have that DHam (2)(2), (z)) S -3p with probability 1 neg((n) 2 1 negl(A).
.
Combining the two points above, we see that with probability 1 negl(A) over sk ~ KeyGensus(1*), v" ~ Encodesas(1",,, sk, m). 1p ~ n.g. z' ~ (29),, DHam (1/2 Po) n. as desired.
(u (v", 2²) I
Summarizing, we have established (26), which yields the desired robustness guarantee.
Remark D.2 (Removing computational efficiency of chamnel). Though the proof of Lemma D.8 uses the fact that (per Definition 2.4), the channel & is sampleable in polynomial time (namely, in Step 3), this assumption is not necessary, in the following sense. If we make the slightly stronger assumpgion that PRC is in fact (1/2- po) -weelly substitution bounded (per Definition C.2), then the proof of Lemma D.8 can be modified as follows remove the assumption that E is computationally efficient: instead of showing that with probability 1 - neg over the draw of yd + Encodesub (1' (1^, sk, m) and z' ~ (z)), we have DHam (2', 3 ) S (1/2 Po) n and using Lemmn 1. we would show that DHam(2' (2',8") < (1/2 - Po) n2 with probability 1 neg)(A) when instead y < (ni ((0, 1}"), which would imply that & is (1/2- Po) -weklly robust. This latter argument avoids us to avoid needing to reason about the distribution of O +- Encodesub (1>,, sk, m). and so allows us to omit Step 3 in the proof of Lemma D.8. Moreover, we note that (as discussed in Appendix C.2) Theorem 3.2 in fact establishes the existence of PRCs robust to weakly substitution bounded channels (as do [CG24, Sections 5.3 & 5.4]).
Lemma D.9. Fix integers N, p E N and a subset Z C [N] with 2 == 12), and suppose Z S N Let T C [N] be a uniformly random subset of size p. Then
Pr(ZnT = 0) = -(1- Z N
-11
pZ
pZz
(_pZ pZ
N N --1+11
E
exp INN
(N - p).
,exp
N
30

---

Proof. We may choose T by selecting its elements without replacement from [N]. After elements of T (not intersecting 2) have been chosen, the + 1th element of is distributed uniformly over a set of size N - i, of which Z elements belong to 2. This establishes the equality. To see the following containment, we use the fact that exp(-x) 2 x 2 exp(-x -2)) for all x [0, 1].
E
Watermarks from PRCs over larger alphabets
E.1
Overview of the algorithm and guarantee
In this section, we discuss how to use any PRC with security parameter À and alphabet size poly()) to produce a watermarking scheme meeting the requirements of Definition B.2. The reduction of [CG24] for this task is limited the case where the PRC has a binary alphabet. To extend to the setting where the alphabet size of the PRC is larger, some new ideas are needed.
Suppose that alphabet (A). with [E]] 2 nn)), which is robust to a constant fraction of substitutions, insertions, and deletions (such a code is provided by Theorem 4.1). Given some constant and family of language models (Model()) (A) A over alphabet (E(A))xeN with [Σ(A]] 2 [ERRC(A), we construct watermarking scheme Wi[PRC, Model] (Algorithm 3), as the following tuple of algorithms (Setup, Wat, Detect):
given nero-bit pseudorandom code, PRC, with block length n(A) over an
Setup 11 produces a pair skwat = (sk, +)) as the secret key of W. Here sk a secret key generated from PRC. (RC.KeyGen(A) and Φ Σ(A) + EPRC(A) is chosen uniformly at random, which can be interpreted as a hash function.
Wat(1>, o)) generates a sequence of tokens tı, t2, in blocks of length n (A), in the fol- lowing manner: for each block of length raA),, we sample a codeword x + PRC. 1^, .k) (Line 13), and at each position i, we consider the pushforward distribution P. := e o Model(t, = -I 11ta-11) (EEpRC (A)) of the next token under the hash function é (Line 15 of the subroutine EmbedChar). If P. puts enough mass on the corresponding token of the codeword x (denoted by 2y in Algorithm 3), then we let the output token of Wat at position i be a uniformly random token which hashes to I, (Lines 16 and 21). Otherwise, we sample the output token of Wat at position i in way that will ensure it does not alter the conditional distribution of the ith token (Lines 19 and 21).
To obtain some intuition for the above procedure, it is straightforward to see that if the codewords x are actually uniformly random, then the output of this procedure is identical to the distribution Model (Lemma E.4). Thus, if i drawn from distribution computationally indistinguishable from random (as will be the case for the output of a PRC), it is simple to show that this procedure yields an undetectable watermark.
Detect(1>, İ (sk, Φ), t) functions as follows, given sequence t = the E Σ()) of (potentially watermarked) text. searches through all contiguous substrings of t, denoted tay and checks whether (d(t))...., ()tt)) decodes to & under PRC.Decode. If so, it returns True (and otherwise False).
In the below theorem, we suppose that PRC is zero-bit PRC with block length naA) over alphabet Eprc(A), satisfying [A)] 2 n()). Furthermore, we suppose that (Model(A))xen XeN a family of language models defined over alphabet Σ(A).
Theorem E. (Watermarking from PRCs). Suppose that p, E (0, 1) are given, that PRC, Model (A) are as described above and satisfy [{()] 2 ( (1]PPC())))2/ and that PRC satisfies robustness to any (1 a + -e)-edi- channel. Then the watermarking scheme WiPRC, Model] (Algo- rithm 3) is sound, undetectable, and 3x(1) subbstiig robust to any t-edit-boundee channel, where (x(() ;= (n) + 6al.
8
Theorem E. shows that for any constant a, we detect the watermark as long the entropy rate of the model's 's text at least l(a) and as long as the fraction of errors (adversarial deletions//nsertions) introduced the watermarked text is most O(a2). This latter statement follows since there
PRCs robust to (1 a + 3p) bounddd channels for p O(a?). In turn, the alphabet Σ(A) of the language model needs to have size roughly [EPPCC (A))/A) which is polynomial [APR((A) as long is a constant.
s
31

---

By combining Theorems 3.2, 4.1 and E.1 we can show our main theorem, which guarantees substring- robust watermarking schemes for edit-bounded channels under the existence of local weak PRFs (Assumption 3.1). To simplify notation, given constants a, > O together with function family F consisting of binary-valued functions on {0, 1)m(A), let us define
Wromp|FF Faommp(F,g.00 9. a)) = W PRC PRF-PRC
F.
a 16C 9
16CrobCu
Model
(27)
where Co, Grbb 21 1 are the constants from Theorem 4.1. In words, Wicomp [F. g, o] chains together the PRCs in Algorithms I and 2 and the watermarking scheme in Algorithm 3.
Theorem E.2 (Main theorem). There are absolute constants c, Ci, C2 > 0 so that the following holds. Fix any a > O. Suppose there exists a function family F, consisting of binary-valued functions on {0, 1Im(X), which is a log n(A)-local weak PRF for some noise level E [0, 1/2), per Assumption 3.1. Then for any language model family Model(A) over alphabets (A), the watermarking scheme
Wcamp[ [F, q. a] ((27)) is sound, undetectable, and Bx (()-subbstring robust to any ca2 -ed-eddi-Hee beditbbounded
channel, as long as:
(x = 6ol + 8 -n(A)
[E(A) 2 m(A) log
Notice that the exponent of n(A) in the É-independent term of (E) depends on a, as does the exponent of n()) in the size of [()). While is a constant (and so this only leads to a polynomial blowup), it would be desirable to come up with more efficient reductions. We remark, however, that this issue is quite subtle, since our criterion of undetectability (in Definitions 2.1 and B.2) is phrased with respect to any polynomial-time algorithm, meaning that given a watermarking scheme W = (Setup, Wat, Detect) can construct polymomially-mor efficient watermarking scheme W = (Setup', Wat', Detect') as follows. The algorithms Setup', Wat', Detect', given a security parameter X, call the corresponding Setup, Wat, Detect algorithms with security parameter X for some a < 1. Since any function which is negi(A") is also negl(A) and an algorithm running in time poly(A) is also poly(>"), the new scheme W" is sound, undetectable, and substring robust if W is. Moreover, its various parameters (e.g.. [E()]) will typically be smaller than those of W by a polynomial. Of course, the guarantee afforded by undetectability of W (due to its use of X as opposed to A) is weaker than that of W, though only by a polynomial.
Indeed, the approach of [CG24] implicity suffers from the same n (())0(lgg dependence in their substring-robustness robustness function (()), though it is not explicitly stated such since they essentially substring
already scale down the security parameter. In particular, the sparsity parameter in [CG24, Lemmas
4 & 5] is required to be O logn log
(where p < 1/2 denotes the rate of substitutions for the 7-p
purpose of evaluating robustness; one can think of _ - p as being roughly comparable to a in Theorem E.2). Moreover, there is an algorithm which can distinguish the PRCs in [CG24] from uniform strings which runs in time roughly n'. To formally reason about polynomial sidde differences in the parameters, would need to make fine-grained average case hardness assumptions, direction we do not pursue in the present work.
E.2 Proof overview for Theorem E.1
Fix security parameter À E N; we will drop the argument À in our notation for the proof overview. In the algorithm description above we discussed the idea behind undetectability of W, and the proof of soundness is immediate. Therefore we focus on the (substring) robustness claim. The high-level idea of the proof of robustness is to show that the procedure Wat can be viewed as a substitution channel which (repeatedly) takes as input output of PRC.Enc and changes some of the tokens to produce its output t. (Technically, we view it as a channel over EPRC by applying the hash function ø to the output t of Wat.) Our goal is to show that for a codeword x E MPRC. Wat makes at most (1 - )(a))) n substitutions if the empirical entropy of the generated text derived from x (i.e., the output of the channel) is at least 2(a log |E]). In such a case, we say that the "empirical entropy rate" of the generated text is ((a).
The key technical difference between our watermarking procedure and that of [CG24] is the introduc- tion of the hash function Φ. Let us first see what goes wrong without such a di i.e., if Σ = EPRC and é is the identity map. Suppose that for each i, Model(t, tta-1) is uniform over fixed subset
32

---

E' of size | entropy rate Q(a). However, a codeword z produced by PRC will only have the property that a roughly | fraction of its tokens belong to Σ'. Thus, the procedure in Algorithm 3 will only be able to maintain roughly& a |E]a=1 fraction of tokens of (i.e., the if statement on Line 16 will only succeed with probability (Σ(a-1), and thus the error rate of the corresponding substitution channel will be roughly 1 1 -->- = 11-10 o1),, since [2] 2 n. This error rate is too large, since our pseudorandom codes (even over large alphabets) can only correct 1 p fraction of errors, for any constant p > 0.
E Then with high probability the output of Model will have empirical
To circumvent this issue, we make the following observation: if the entropy of the distribution t1: E A(E) is at least a In |ا] then, if Σ is sufficiently large compared to EpRC (roughly |حح 2 [EpRC| (2(1/)), then for a uniformly random hash function & + EPRC, the pushforward distribution P3: = o pi E ((ERC)) will be "close to uniform" in the folloing sense: At least an (2aa) fraction of the mass of P; will be on tokens E ΣPRC for which Pe(a) I 1/|EPRc|- This claim is proven formally in Lemma E.3, and may be seen as consequence of concentration of measure. Since each such token a occurs with probability roughly 1/|Σ) under a codeword output by the PRC (by undetectability). altogether such tokens account for probability Q(aa) event under which the condition on Line 16 of Algorithm 3 will evaluate to true. Thus, at least a fraction ((x)) of the tokens will not be substituted, as desired. This idea (together with the application of various concentration incqualities) allows us to ensure that the substitution channel induced by Wat introduces fraction 1 - {aa)) of errors.
P: := Model(tt
Next, the p-edit bounded channel referred to in the statement of Theorem E. introduces an additional p fraction of errors in the sequence of watermarked text. However, because an output of Wat consists of sequence of text consisting of multiple (say M) consecutive codewords of PRC (each of block length rt), we run into the following issue: suppose that all of the entropy of t is concentrated in M of the codeword blocks. Also suppose that the p-edit bounded channel concetrates all of its p Mn errors in those same aM blocks, meaning that the effective rate of (edit) errors in those a.M blocks is in fact pMnn = p/a. Thus, we need the PRC to in fact be robust to (1 - ((a) + -eep/aa)-ddiibboooooo a.
channels in order to detect the watermark. It is straightforward to see that the aforementioned scenario is worst possible, meaning that such robustness is in fact sufficient. Full details of the proof may be found in Appendix E.3.
E.3
Formal algorithm and guarantee
Algorithm 3 displays our watermarking procedure W/RRC, Model], given a pseudorandom code PRC over alphabet (A) and family of language models (Model A)n over alphabet E()). When- ever the security parameter À is clear from context, we drop the argument X, i.c., write EPRC, Σ, Model. To aid in the analysis, given a language model Model over alphabet Σ, alphabet EPRC for the PRC, and mapping o Σ- > ΣPRC, we define embedding channel x + EEmb (1=-)) for each choice i E N and t E - which maps x E PC to some (random) string Emb (1:t) E "n (as the input and output alphabets are different, of terminology). Given x EPRe and tisi-1 1 E E Emmb (1;; t1:--1 performs the following for 1 S j S n: for P5 Model(ty+i-1 = - t1:)- it generates t-+-i1 + EmbedChar(zs; (a Pj. Φ). (If some token tj+1-1 is the terminal token END, then all remaining tokens are also the terminal token END.) Note that this is exactly the procedure in Lines 9 and 10 for steps i through i + n - 1 of Wat (sk, Φ), o) of Algorithm 3.
use of the term "channel" is slight abuse
Lemma E.3. Suppose E, E' are finite alphabets, and P E A(E) is fixed. Let o: E + E' be uniformly random function. Then
Pr
min Σ L''Es'
2o P(o))
H(P)
2 1 21-2 2
HCP) (PP2
41
Σ
4 ز
Proof. Define 1) = exp(H(P))2}- Set T = (a E P(a) S n) Note that H(P) < P(T) ||
P(ENT) H(P)/2, meaning that P(T) > 2lm E
H(P)
Writing M == [T], we have M 2 2 E
H(P)
33

---

Algorithm 3 Watermarking from PRCs for general alphabets: WiPRC, Model]
Require: Pseudorandom code PRC with security parameter À over alphabet EpRC = EPRC and block length n()), Model over alphabet (A)), maximum length of model text Lmax(A).
1: function Set
2: sk < PRC.KeyGen(11))
3: Let E((A) (A) be chosen uniformly randomly.
4: return (sk, Φ).
5: function Wat(1*, (sk, 6))
6:
PPCC..nnooe sk). 1,1,j+ 1.
D D PRR
7:
8: while END & {t1 ,t....., 1 do
9:
p: + Model(t; = ti, ti
P A(E)
10:
- EmbedChar(zj.PPrr Ø). i 1,j + 1
12:
if > (A) then
13:
j 1. PRC.nncde(L1
function Embed(Cha((z,,,,.o))
D Daj E EPRC. Dt A(E). o: Σ EPRC
15:
Pi +- 2 p:.
b pr E A(EpRC)
16:
if Ber(min [I,|EPP((A]] (x(,)))) then
17:
Set y: + Dzz.
D yi E EPRC
18: else
Sample yi qi where q:()) x (p(()) FipRe]
20:
21:
Sample t; from the distribution of a ~ pt á(o)) = Yt.
22:
return t;
23:
function Detect(1>, A (sk, Φ), (tz...., .t). tz))
for i [C]. (i, min + n 1, { do PRC.Decdeesk,, return True.
25:
((,,)) #1 then
26:
27:
return False
Next, define Q E A(E) by Q(o) == 1/0E7)-P(o) P(T) and let U denote the uniform distribution on Σ'. For any subset S C V, by Hoeffding's inequality we have that
Pr (u(s) Σ0 160() ES} 2 2exp oEE
2ea E.ex
Pr (lo Q(8) - (()) > e) Pr &
(- "
Q(a)²
where the randomness is over the draw of uniformly random function ó Σ EPRC- Using that Eosy (² max.ex Q(a)= S PiT, S
7/21n [E] together with a union bound over all subsets H(P)
S C I. we see that
(222HH(P) H(P)
-22..
2 - HPP) www.e (XL(HLP)/2)
Pr (d 6o Q) 2 2 exp
S 2
n7 7.2 Σ
Under the event that dTv(Ul, 00 Q) e, we have that Eoess min (o ) > 1 e, and thus, since 6 P > P(T) (0o Q) pointwise, Er'ry min (1/1211/'11,/ P(o')) 2 P(T) (1 c). The conclusion of the lemma follows by setting c= 1/2.
TTechicallyy, only need to do union bound over half of all subsets, since do Q and 24 are both probability measures; hence the multiplicative factor in front is 2 E' opposed to 2
34

---

Lemma E.4. Fix any à : Σ + EPRC. and in E N. The distribution of E (2;t1=-1), for Unif((Tpc)). is exactly the distribution of Model(taitn-1
t1a-1).
Proof. We use induction on j E i 1]. Fix any j E [2, 1 n 1] together with a sequence i.c., the distribution of the j i 1th token of the output Emb (I;; (1)-),, conditioned 1. Let pj
t1:j-1 E y Let Pj E A denote the distribution of t, ~ EEb (z; ti 115--) t:j-1,
denote Model(t,
t::j-)): we wish show that pj = Pj.
By Line 21 of Algorithm 3, suffices to show that do o Pj = Φ pz. To do so, write Pj := $ o pj (i..., the quantity computed in Line 15 of Algorithm 3), and write Pj == dTv(2,, Unif(E =
EveLoRc (o) - 1/1[Ppcc]]++ that Pj LocEPRe (5 17,,1//1 1/[EPRC]] By definition, for each o E EPRC, we have
1 [EPPC]
(3( 1/ 1/|XPRclI+ pz(0),
Φop;(o)
min EpRcl SpRccl.//(00 [D)(o)) Pj
Pj
as desired.
Given integers a, E N with a < b, a mapping ó E + E', and a sequence t = t1:b E Ed, we define the spread of the sequence with respect to @ to be
b-1
gollabbi (t)
Σ
min
|Σ do P((0)..
(28)
DEE!
where Pa(o) == Model(t; = a t1:--1).
Additionally, we define the mean entropy for the sequence Eh in the interval [a b) to be
6-1
H lasb)) (t)
HMModel(t, = = -.
Σ E (t) tis-il.
Lemma E.5. For any integers we have that
3 (2 last)) (t) + In Σ
In 10-aa a) 2 H!!.:)(t)) (t) 2 -negl(b- a).
Pr to-Model
2
Proof. Let write H!!h (/:b)) (t) = - b-1
min (t), In | + In²(b a}}. For each i, we have that
Pr(H:(() - (t) 0) S Σ exp(- In Σ In (b- a)) = exp( In (b - a)).
(29)
By a union bound, it follows that Pr ( (t) H!! (t)) - (b a) exp( In in² bb- a)). Next, Theorem F.2 gives that, for any 8 > 0,
(abb)
Pr te-Model
(t)
3 Σ
E (t((t) tra-1] 4(I | + In² a)) lm 5d. (30)
Finally, since H!(()) S (t) with probability 1 each E (a, b), we have
E (t) ti:-1] < E(H:( t=:i-1] = H (t).
(31)
Combining Eqs. (29) (31) and choosing 8 exxp In2 (b- a)),
that with probability
1 2-b(6 a + 1). exp(- In² a)) 2 1 negl(b a). we have
3 6-1
H!a:b((t) S !1:0000) (t) S
Σ
(t)
[=--1] + 4(In ΣΣ| + In a)) In (2/6))
t=
3
5 H|abb
(t) + 8lm
|Σر In a).
2
35

---

Lemma E.6. Let alphabets E, E' be given, and let ø Σ + E' be uniformly random function. For
any integers a < and any a E [0, 1] satisfying |ا] 2 (>
2/a we have that
(| (3) (b-a) [E|+ In (b-a)
2 1-negl - a) - (b (6-w0) a) 2 _0/111
Pr ct-oodel
or g..la (1) 0-
Proof. Let fix any sequence EL For i E [r.], define P. ( by Pi(o) Model( (13-1).. ). By Lemma E.3, for each i E [a b), we have, over a random (uniform) draw of d that
Pr Σ min 6
H(PP)) 41m
21-2121 HLP (xP
where > is universal constant. Thus, for each index E [a, b 1] for which H(P:) (t) 2
In ES, we have
Pr Σ min O''
{ 1 |Σ' |
H(P:) 4 |
2 1 - 21 a/2
1 2-=-1/a/110 (32)
where the second inequality follows by our requirement that |>] 2 (1 2/a
For any sequence
t for which =/(=:)) (t) 2 2a (b a) In [ا], we must have that Eig (a #g(t)2a in (2] (m)() 2
a. (b 16-0l In E.. Thus, for any such t, (32) together with union bound gives that
Soh (t) 2 a (b - a)
2 1 (b- 20/1
Pr
4
Next, Lemma E.5 gives that
Pr te-Model
(H!a:b) (t) & 3a - (b a) In ΣΣ + 8
|
In In a) or H(a:b) 2 2a (b - a) In n 2
negl(b - a).
Combining the two above displays, see that
([loa) (1) (n)- (b-a)) or go. (1) (1) 101
21- 21-negl(b aa) - (b aa) - 2-/
Pr
te- d
Lemma E.7. Fix L N, alphabets M, MPRC, and integers a, [4]. Suppose [0, 1] satisfies 2
(b-o)) and |Σ] 2 2/1//// Then for Unif(E/RC) and ø E - EPRC drawn b-a
uniformly, it holds that
(b or Drun 1elta (b) (1-888) 2 negl(b a) - (b a) 2 1a/11"
Pr d.e 1im Model tasb-1 1 Emb 1
where we recall that ((ta:b-1) denotes the string (é(ta)...., ((to-1)))
Proof. For any fixed 6 E + ΣPRC and ti:-11 E Σ. Lemma E.4 gives that the distribution of (Za:b-1; -1: under Fa:b-1 Unif(Epre) is exactly the distribution of Model(ta.b-1 = t))--). Thus, by Lemma E.6 and the fact that (6 a) in E 8lm |Σ| Int(b a). have that
(t)):)(t) < 4a a) In Σ or (o).la:))()) 2 a (b a)
Pr
4
ti (odel((10)
tuib- Ei (1amb-13t1m-)) 11)
ml (b (b-a) 11|+8 In (b-
Pr 6,0
or (o)() (t) -د(h-a
1i 1 Model
laib-1 1 E (#a:b-1itt:ac
2 - ne - a) - (b- 2-
(33)
36

---

(To be precise, the first inequality above uses the lower bound on in the lemma statement and the second inequality uses Lemma E.6.) For each i E [L]. let p; E ( denote the distribution (t = t1 t...... ,i-1), which is itself random variable (depending on t,,...: 4-11). For i E [a, b - 1]. let Zu Ber(min EpRCi (ø pt) (:)(f=a+1))) be the random variable used in the definition of Emb (Iasb-1 tita-1) (i.e., corresponding to Line 16 of Algorithm 3). Note that the output t = Emb (Ta:b-1i 11:--) of the embedding channel satisfies o(t;-a+1) 2 2i-a+1 if Zi = for each E [a, - 1]. Therefore,
(Taub (te:bb-))
Σ Z.).
(34)
For each i E [a, b - 1]. note that
E Exw Ø, t1:1-1, Z1:-1]
min(1, [ipRII (o p.)(
MPRC
e
and using the definition of the spread in (28) with E'
EpRC, we see that
(00p))(1)= Sttllab)) (t).
L Unit 1Z4 o, t1:1 21,1
Σ
Σ
min [PRC
i=a E
By Theorem F.2, for any fixed @ and for any 8 (0, 1), with probability 1 5 over the draw of ( and Zí it holds that
t Model(. 0), x Unif Unif(EPRR). ta:b1
6-1 1
1 51b((a)b) (t) 4log(2/8).
Σ 2, 2
(35)
2
i=
Choose 5 = 2eep(plnnntt - a)) negl(b (b- a). In the event that Sd.(a:b) (t) > a.(b-a) and (35)
both hold, using the lower bound on a in the lemma statement together with (34), we see that
DHam (aa: ((ta:bt))) S (6 a) (b-a) a) + 4 4 a) S (b a) (1-a/8). (36)
4
Combining (33) and the fact that (35) holds with probability - negl(b b a) together with (36), we that
Pr tia Modal
(or (t) (b-aa
2 --gl(be a) (bb- - a) 2 2-1
faib-1 Eo Fim (Fai6- 11)
Lemma E.S (Substring robustness of the watermark). Suppose that a E (0, 1) are given, and PRC zero-bit PRC with block length n(X) over alphabet (A), satisfying [E)C((A]] 2 n()). Suppose further that PRC robust to any (1 + 3p) "")-edi-bbuunde houuded channel. Let Model(X) be
a
defined over some alphabet Σ(A) satisfying [Σ()] 2 (8 [EpRc(A))) Then the watermarking scheme WPRRC, Model] (defined in Algorithm 3) is 3x (()-suustgi robust any bedddd channel E, where (x( = 8n(A) + 6al.
Proof. For convenience write pı =x/8, Po = 3p/o; then PRC is robust any (1 11-p1 P1 pa)- bounded channel. Let denote the security parameter for the given PRC. We will show that for all i [Lmxx())
Pr Setuppp A (Detect(1*, (sk, Φ). t') False and H( 2 Bx(j - i) In (E(A)) < negl(A). te-Wat(1* (sk. ((())
(37)
Using (37), the fact that Lmax(A) < poly(A), and a union bound over all possible choices of i, will yield the desired claim of (ebsuuruggg robustness. To establish (37), fix À N, and set Model = Model(A), n n()), E(A), EPRC = EPRC(A), as well as i, E [Tmax (A)]; we argue
in two parts:
37

---

Step 1: defining channels. Let us write e j= i and let a1 < 02 < ..... be the indices in j 1] denoting the start positions of blocks for the PRC in the execution of Wat (sk, +)) (in particular, ....... 4h are simply the integers in j
congruent to (mod n)). We will write := E(t:g-1) to denote the output of the edit-bounded channel given 1:j-1 as input. Since E is po-edit-bounded, we have len(t') < l = [(1 + po) fj. Given mapping Φ Σ - EPRC- we let (z, (given E EPRC, t E Σd) denote the joint distribution over random variables (Vg,b,0) )ee(h-)nehhn)) (e((h-1),,,E((e))) &' -- (oo)) defined as follows:
It draws (t:.j-1).
For each choice of g: b, V' as above, it lets U9.5,6' to be either: (a) the substring t/ -1 if o(t) can be obtained from Tey:ay+1- via a sequence of most (1 Pi + po)m
subsitutions, insertions, and deletions, or (b) if not, any string satisfying o(y,.,,))
-0,:0,-1
Next, given o, 9. b, 6' as above, we let E 99..br be the channel which, given input string æ E 2PRC performs the following operations:
First, it generates (sk, o) ~ Setup(1*), and generates t ~ Wat(1>, (sk, o)), with the following modification: when generating output for the block starting index ag. instead of using fresh output of PRC.Encode(1*,, sk), it uses the given in- put string I. Let r'....,.'' (A//((AA E DR denote the codewords (output by PRC.Encode(1 sk)) used in the Wat procedure, so that in particular rh = x. Write H= = (x))
æ (A)/A(A()
Then, it samples from the marginal Un.b. (# and outputs (Vy,,.b))
Claim E.9. For any [h- - 1}, b, b E [e"), and Φ E + EpRC, the channel gg.. is (1 P1 po)- edit-bounded.
Proof. is immediate from the definition of & 9.,. and F that, almost surely, for a sample V9.6.0' (2, t), (( can be obtained from ø via a sequence of at most (1 P1 + po)n substitutions, insertions, and deletions.
Finally, an output of E can be sampled in polynomial time: here we use that ~ Wat(1A, (sk, Φ)) can be sampled in polynomial time (as Model is assumed to be computationally efficient), as well as the fact that it can be determined in polynomial time if one string (namely, ((t(,r==) above) can be obtained from another string (namely, Ia fa above) via a sequence of a given number (i.e., (1 - P1 + n)) substitutions, insertions, and deletions.
Claim E.10. For each E [h - 11, it holds that
H. " (1) or Diam aott -1 1,00 (o (1) 2 1 -A).
Pr (sk.d) Setup()) 3 Aomax (A)/m(())))1))))) + E
== (xt 2 (mmma(()//m2))))
to Em (a:0)
(38)
We emphasize that the notation x², xt,=?.... +- PRC.Encode(1 ,kk,, t Ed E 0) means that PRC. PRC.Encode(11 (1 ,sk) is called repeatedly to produce strings x! x² ....... E EpRc- and the concatenated string x (x xx. ..... (mmmm(A)))//(() is used as input to the embedding channel & (z; 0). Notice that this procedure is identical to Wat(1a, (sk, d)), meaning that the distribution of the output string t is identical to the output distribution of Wat(1 (sk, Ø)).
1f or are outside the length bounds t', then we let thow-1 denote the substring Emin (b.len(t') Jmmin( - )))en(())) which may be empty.
38

---

(t) (110((teaa S n (1 - a/8). We have that 32.In((n) S a as long as n(A) 2 ((1/a), which holds for all À greater than sufficiently large constant depending on a (and it is sufficient for us to only consider such À as the claimed failure probability is neg) Thus, we may apply Lemma E.7 with a = i, b, E' ΣpRC: doing so, we see that Φ: E EPRC is drawn uniformly and x (ni(( the event A occurs with probability 1 - --nee(()) n2. 2 --//E""" 2 negl(A) - n 2 --//== (here we have used 2 A). Since a draw tft~ Emb (z; 0) may be implemented in polynomial time (as we have assumed that Model com- Emb
Proof of Claim E.10. Let A denote the event that H!
4an In |
Damm (T Wogiay 1 1-1, (
1-11
putationally efficient), and since H. (! (t), DHmm (Ham(Fa:aa ((ta,;a0:= 11) can be computed in polynomial time, it follows that A must occur with probability - neg!(A) - n 2 - when x' r',x² .x?....,,2! E. [A] +- PRC.Encode(1*,, sk). (Otherwise, we could violate undetectability of PRC by generating codewords x², x²,=²2 from the encoding oracle O, representing either
PRC.Encode or random oracle, and checking whether A occurs.)
Finally, we remark that n n-2 2-///= < negl(n) < negl(A) A) by our requirement that |>| > |EPRR| n.
Since the channel & is p-edit-bounded, for most values of E 1h 1] indexing full blocks of t-j-1- there must be some 6, b' so that t/.8-11 can be obtained from taz: by most (pn) insertions and deletions; this is formalized in the below claim:
Claim E.11. Fix any C 2 1 and suppose 2 For any string t::j-1 E E', there are at least 1(h- - 1)-(3 (1 - 1/C)] values of 9 E h 1] so that there exist b, b' E [e") for which -1 can be obtained from t0,:0 by applying at most 3Cp n substinutions, insertions, and deletions (where have t' E(4,5-1))
Proof of Claim E. For each 9 E [h 1h-11 and Fij-1 E ΣS the edit-bounded channel & sends the substring fag00+111 to some substring b, of the (possibly random) channel output t'= E-E(tt 1) (In particular, by denotes the index in t' of the first token in 1- which is not deleted by E, or, if all of tup:a+41-1 is deleted, the index in t' of the first token following ta which is not deleted by E.) Note that by function of 4:j-1; 1: we omit this dependence from the notation to avoid clutter.
Fix 4--1 and t' E(taj-i)- For each g E [h 1). let eg denote the number of substitutions, insertions, and deletions applied by & to obtain 1 from ta.:9 Since is p-edit- bounded, we have - Eg S pl S p- (h + 1)n. Therefore, at least ( (1-1/C)] values of g E 1] satisfy eg S C p(h+ + 1)n= s 3Cp- n, as desired.
Step 2: using robustness of the PRC. Since each channel gd gg.b (for any o : E - EPRC, 9 [A- 1], b, E [e'] with b' - E [n(1 Po), n11 + po))) is (1 P1 Po)-bounded (by Claim E.9), it holds that
Pr (sk, ( ) mv-PRC, Encode() sk)
(PRC.Decode(1)) sk, y) *1) 2 negl(A)-
(39)
y--go S. (x)
Note that the distribution of ~ E.e (2), for x + PRC.Encodeie ,k), is the same as the marginal distribution of (Vgg,,1))
F0 t), for T2, + PRC.Encode(1", sk), x t Io E (x; 0). Therefore, using (39) together with a union bound over the (polynomially many) choices of g, b, we that
Pr
(Vg, b, PRC.Decode(1", sk, o(H) )) f1) 2 1- neg
(sk.d)+ - 1et
2a ar AAmax (A)/M(AA)) PRC. PRC. Encode(I sk) z (at (tt..//ammo/.///....m (A)x(())/(()))))) t- ( (2)()
(40)
39

---

For any i E [m by Lemma E.5 with a = i, i n. there is some event Bi that occurs with probability 1 - neg((e) (e) 2 1 negl(>) under <- Model so that, under B;,
Hl (t) - H ()) (t) + 8 E In - 2 In ز 8ln [ In (m) - 2n In [Σ]
2
where the final inequality holds as long as is chosen sufficiently large so that n²A) 2 20 (n()).. By undetectability of PRC, Lemma E.4, and efficiency of Model, the event B, also holds with probability 1 - -egl(A) under the distribution of t specified in (38), Let us write B Ba--n nBa n ... Bag thus, under B, we have
H (((i))(() 2n In |-],
H! S In | Vg [h - 11, H H( S 2n In [
Consider the distribution of (z, t,t²) where (x, are drawn specified in (38) and t' ~
E(tig-1). Let A denote the event that for all g E [A - 11. H H!. < 4a In |Σ] or
DitamFaa ( Φ ((taa:aaa1-1))) S n-(1-aa88)) by Claim E. and union bound over g E [h-1] A holds with probability 1 - (A).
Under the event An B (which occurs with probability (A)), one of the following must be the case:
* There are at least La (h - 1) + 2 values of
[h 1] so that DHam (Ta, mn (it (t S n (1 1--0 a/88; let this event be denoted C1.
It holds that ! < 8n In |ل]]| + 6al In [ let this event be denoted C2.
Indeed, under AnB, if C₁ does not occur, then we must have that C2 occurs since we would have:
h-1
( H(:d) -H! (t) + ( (t) +
Σ
H H 00 (t)
<n Σ + (Ia. (h- 1) 2) 2n In Σ + (h- - |a (h- 1)] 1) 4am In [Σ] <8nIn Σ + 2al In Σ + 4al In | = 8n In |X] + 6ad In [Σ].
where the first incquality uses that AnB B occurs and the second inequality uses the fact that (h - 1)m $ l.
Note that if h < 2, under the event B, the event C2 occurs.
Next, if h 2 2, by Claim E.11 with C = 1/a, for any string 4:--1 E Σ with probability 1 over t' ~ E(t.j-1). there are at least [(h 1). (1 a)] values of g E ih 1] so that there exist b,b' [("] for which t/.5-1 can be obtained from tag:agt1-1 by applying at most 3 pm
a
substitutions, insertions and deletions. Note that [a (h 1 11] + [(h 1).
a) h
Thus, under the event A n B n C2, there some value of g. E [h - -]] and b,. by E [e'] so that DHam : +1 ((ta, +1
be obtained from tay, 2 +1- by applying at most pon = 3 pm substitutions, insertions and deletions. By definition of F² t), we may couple a draw of W.....rrg,s.. ~ (2, t) to this distribution over (x,, t') that under the event AnBnC, that (g.. b, b()) above exist, we have bg.. th -1'
(1 a/8) n (1 pı) and t/
Let the event of (40) (which holds with probability 1 - nAg)(A)) be denoted by D. Then, if Z 2, under the event A n B n D n C1, Gx, b., by are well-defined above, and so we have that PRC.Decode(1* sk, étt 8. $L, and in particular, that Detect(1>, AA, (sk, Φ), t') = True. Under the event A n B o D n C2 C C2 (which must occur under the event B if h < 2), we have that H. (:)) (t) < 8n In Σ 6ae In Σ (x) In E Since (AnBn n (n) U (An 2
An AnBr D occurs with probability - negl(A), we have established (37).
Lemma E.12 (Soundness of the watermark). For any PRC PRC, the watermarking scheme W|PRC] (defined in Algorithm 3) is sound.
Proof. Fix any sequence E Σt, for some S [T-max (A)/n(A)) We wish to show that (Detect(1*, (sk, Φ). #1)= S neg!(A).
Pr Settp))))
(41)
40

---

By definition of Detect (in Algorithm 3), Detect(1*, (sk, 6).t) T only if there are some i, E [4] so that PeCoDecc sk, (t:;)) *L. Since PRC is sound, for each fixed choice of @ and i.j,
Pr Rkc-PRRCKKyGGm
(PRC.Decode(sk, o(tey)) *1) S neg
Taking expectation over ø (which is drawn independently from sk) and union bound over i.j < poly(A), we see that (41) holds.
Lemma E.13 (Undetectabilitty of the watermark), For any PRC PRC, the watermarking scheme W[PRC] (defined in Algorithm 3) undetectable.
Proof. Suppose for the sake of contradiction that there is a polynomial-time adversary Adv so that
Pr (Ady (1^) =1
Pr Se--Setup(1A))
(Adv Wat(1* .kk (1^) = =1) - poly(A)
(42)
Using Adv, we can construct an adversary Adv' to break the undetectability of PRC, as follows. Adv has access to an oracle O which either PRC.Encoder sk) (where sk < KeCCKKyGen(11)) or outputs a uniformly random string of length (A) at each call. Adv' then draws Ø Σ + DPRC uniformly at random and simulates Adv, simulating each call to Wat(1*, (sk, 6)) as in Algorithm but replacing each call to PRC.Encode(11 sk) (Line 13 of Algorithm 3) with a call to O. In the case that O is PRC.Encode L sk), then this procedure is exactly Wat(1 ( .sk), In the case that O outputs uniformly random strings in response to each call, then Lemma E.4 gives that this procedure exactly AddMede! Thus, (42) gives that Adv' can distinguish with inverse polynomial advantage between the two cases, a contradiction to undetectability of PRC. Note that in order to simulate Wat, Adv' needs be able evaluate Model(t, ti:--1 (Line of Algorithm 3), which is possible in polynomial time by assumption on Model (see Appendix B).
Proof of Theorem E.2. Fix a > 0 together with a function family F which is a log n m(A)-local weak PRF for noise level q E [0, 1/2), and family of language models Model(A) as in the theorem statement. Write Po == 16C.st where Crob is the constant from Theorem 4.1.
By Theorem 3.2, PRC; PRF-PRC[F, po: 9) is zero-bit binary alphabet PRC with robustness all ( - pu)-bounded substitution channels. By definition in (3), the block length ((A) of PRC; satisfies:
((A) 0 (1()))) ((A))) I n(A)
(()))((o())/)))
Next recall that Co, Grob 2 1 are the constants from Theorem 4.1. By Theorem 4.1, for Co/ PPo PRC2 == PRCiax(PRC, p] is zero-bit PRC with block length at most (A) and alphabet ΣpRC (A) of size EEpcc()) (A)l I Co. [[)]] which has robustness to any (1
channel. Since CrobPD 2 g + by our choice of po and since p S a² 222/55 /48 (which can be ensured by taking c = 1/48 in the theorem statement), PRC₂ is robust to any (1 + 32 -edit-bounded
channel.
Finally, by Theorem E. as long as [Σ()]| 2 ( (P))(())) the watermarking scheme W WIPRC,, Model] is sound, undetectable, and Bx (2) substtrng robust to any p-edit-bounded channel, for (f) == 6al + (N) < 6al + 6al+n (2)) Olog 1/po), To ensure that the lower bound on [Σ()] holds,
we note that
3/a
8
Co Po
2/a
I (n())o(d log log
which is bounded above by (a log C2 in the theorem statement is sufficiently large.
}Σ(A) (for sufficiently large X) as long as the constant
41

---

Technical tools: concentration inequalities
Theorem F.1 (MeDiarmid's inequality). Let sets Xi.... .,, Am equipped with sigma algebras be given,
and suppose f Xi x ... x Xm + R satisfies the bounded differences property, i.e. for each j E [m).
-(d)), S.j. cj.
max Z;EA, ViE villm),aeR
for some positive real numbers Gj. Then given independent random variables X; E 2; (1 [m]} holds that
-2c²
Pr Pr (I Xm) - B[f(X1, Xm)II 2)) 2exp
E &
Theorem F.2 (Corollary of Freedman's is inequality; Lemma A.3 of [FKQR23)). Let (Xt)eST be a sequence of random variables adapted to a filtration ((t))r If0 S X₁ S. R almost surely, then each of the below inequalities holds with probability 1- d:
Σ
X
E, [X.] 4R1n(2/8)
T
T
Σ
52
X,
8210(2
where [X,] denotes E[X, F(-]
F. Concentration with weakly dependent random variables
Fix a set X' equipped with a sigma-algebra together with a positive integer n. Let / E A(X") denote distribution (where X is equipped with the product sigma algebra). For X (Xi,..., Xn) P. we define the influence of Xj on X; to be
[==x())=
max drv = - | X, x/y)).
= x
R-1-JEX"
2,,0/EX
(43)
Definition F.1. Given a random variable X distributed according to some distribution P over X". define the Dobrushin coefficient of X to be
(X)) = max
max JE i
Σ 1 (X), max I se(n)
(X),
jzt
Theorem F.3 (Dobrushin's concentration inequality; e.g., Theorem 4.3 of [Cha16]), Let be distribution over X whose Dobrushin coefficient is Let f X + R be real-valued function satisfying the following bounded differences condition, for some constants C₁, ......, On 2
C 2n )=X"" ar EX [f 2(1) Scj.
Then for all E 0,
Pr. (((()))(((X)))) 2 S (- (1 (1- a) 2
( 1.
G Miscellaneous Lemmas
Lemma G.I. Suppose PRC PRC to any pssubsiiutioo--ouudeed channel. Pryke-KeGeen(1> Encode(1* ()(() DHam (x.,)) S pm) 2 negl(n), PRC
(KeyGen, Encode, Decode) robust
Then for any channel E satisfying robust
E.
42

---

Proof. Let E' be the channel which samples [x)). outputs if DHam (y. 2) I pn. and oth- erwise outputs z. By assumption PRC is robust Er. Moreover, we can construct joint distri- bution of (sk, v. v') where: (a) the marginal of (sk, x; y) is as follows: sk ~ KeyGen(1~), <-
Encode(1* X sk, m), E(r); (b) the marginal of (sk, 2, v is identical except that y/ ~ (x)); (c) y y' with probability (A). Then the robustness criterion for El yields that PRC robust to E.
Lemma G.2 (Theorem of [RS23]), For any positive integers t, k N with &s S N and t & N,
holds that (Bv(Bin(tt,))) k/N), Hyp(N, k. ()) VN-
For completeness, we provide the proof of Lemma G.2 below.
Proof of Lemma G.2. Fix k, N as in the lemma statement and let P Bin(t, k/N) A((O,I...., ,,) and Q = Hyp(N, t) E A((O, .t)). Also write = k/N. Then we have P(w) p= (1 - p) - and
NN
t
(N - k) ... (N - k - (t-ww) +1) k... w+
Q(w)
w
N... (N-(()
k
II 1 (1- pD--p-j/N)-In 10
5/k)
N
(1-0111
Then
Q w F(wr) (F)
1=0
(1 - p j/N) 11 (1-j/k)
1
(44)
(1 - p) j/N)
J/N
1=0
for each w S t. By Pinsker's inequality,
Q(w)
dTv(Q.P) $2
Σ Q(w)
P(w)
w==
1
In
J/N
j=0
1-1
In
1- j/N
1=0
H-1
Σ
N
j
1=0
12
V2
N -
where the second inequality uses (44), and the third inequality uses the fact that In - < (1/=)-
for all x E [0, 1].
43

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction give informal summaries of the results presented in the main body and appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed following Theorem 1.1.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
44

---

Justification:
Proofs are provided in the appendix, and the main computational assumption is stated as Assumption 3.1.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
45

---

Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
ponycccyl)) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips.co.. wwtpccccpppppppp.....eeeccc.cpee httpa//gggieeeeeeuuuubuiiiiiii /Cooeeeodeieeeeeeeeeeeeeee wwweeiissiiooooiioiioiioooooo (eiinnilccy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
46

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //te:r//n.u...///eee
Answer: [Yes]
Justification:
The paper is theoretical in nature and so any direct socictal impacts are limited.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Broader societal impacts are discussed in the introduction. Due to the theoreti- cal nature of our paper, any direct societal impacts are negligible.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
47

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
48

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
49


Reviews:
[{"review_id": "UKQLStSlmo", "reviewer": "Reviewer_YwkB", "summary": "The paper presents an innovative approach to embed an undetectable and robust watermark into AI-generated texts. The authors takes three main steps to reach the goal. They first design a robust pseudorandom code (PRC) over a binary alphabet, and then turn it into a polynomial-sized alphabet PRC robust to a fraction of edits. Finally, they bridge the PRC and the LLM watermark using some carefully designed mapping function to complement the whole watermarking system. The proposed approach is theoretically proved to be undetectable and robust to a constant fraction of edit attacks.", "questions": "1. Have the authors considered evaluating the proposed method on real-world scenario to better understand its practical applicability?\n2. How does the computational efficiency of the proposed method compare to existing watermarking framework?\n3. Is there a trade-off between undetectability and robustness? For example, in Lemma D.8, the robustness is achieved at very low $p_0$ (since $C_{\\text{rob}}$ should be a large constant value). Will undetectability be affected by low values of $p_0$? If the trade-off exists, how is the trade-off reflected in the theorems of the paper？\n4. What are the potential limitations or challenges in scaling the proposed method up for large-scale NLP tasks?", "limitations": "Lack of evaluation in real scenario: the authors did not show any experiment done on real LLM. Testing in the real world would provide a better assessment of the method's practical applicability and robustness. Adding some real example of watermarked AI-generated text will signify the problem of undetectability. Showing the real accuracy of detection will bridge the gap between the theory and the practice.\nThis paper considers \"constant-rate\" insertion/deletion/substitution attacker model, how about attackers who perform paraphrasing or adaptive attacks？Is the proposed method robust to them?", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses a critical need for theoretically robust LLM watermark.\nOriginality: Using a designed mapping function to bridge the gap between PRC and LLM watermark and proposing the theoretical robustness is innovative. \nQuality: The methodology is rigorously developed.\nClarity: The paper is well-structured and the writing is clear, making the complex concepts accessible.\nSignificance: The work has the potential to significantly impact the field of detecting AI-generated text.", "weaknesses": "1. Lack of real-world evaluation of the proposed approach.\n2. Lack of efficiency comparison with the current watermarking framework.\n3. Lack of discussion of trade-off between undetectability and robustness.\n4. Lack of scalability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. \n\nQuestion 1: Using techniques from our theoretical watermarking scheme to develop a practical implementation for use with LLMs is an important direction for future work. The main limitation of our present theoretical results which may complicate a practical implementation is as follows: The alphabet size $|\\Sigma(\\lambda)|$ is required to grow exponentially in the inverse of the parameter $\\alpha$ (see the statement of Theorem E.2). In turn, the parameter $\\alpha$ is proportional to the entropy rate of the text needed to guarantee substring robustness (see Definition 2.6 and the setting of $\\beta_\\lambda(\\ell) = O(\\alpha \\cdot \\ell)$ in Theorem E.2). For typical LLMs, the alphabet size is likely smaller than our required value of $|\\Sigma(\\lambda)|$ given the entropy rates observed empirically in natural language.\n\nOn the other hand, we believe that future work aimed at developing modifications of our watermarking scheme with an eye towards practical implementation will be successful. One idea which seems promising is to simulate a larger alphabet by grouping tokens together, and to aim accordingly for a slightly weaker robustness guarantee.\n\nQuestion 2: Modulo the limitations discussed in Question 1, our watermarking scheme is very efficient (and comparable to, e.g., that of [Christ & Gunn, 2024]). In particular, the computational cost of generating each next token is linear in the alphabet size of the LLM. Note that it takes linear in alphabet size time to even generate non-watermarked output.\n\nQuestion 3: Yes, there is a joint tradeoff between undetectability, robustness, and blocklength of the watermark, even for substitution PRCs (i.e., Theorem 3.2), which then carries over to our edit-distance robust PRCs, as in Lemma D.8. The precise tradeoff is reflected in Equation (3) in the proof of Theorem 3.2: we show in the proof that the blocklength parameter $N(\\lambda)$ to achieve a *fixed* undetectability guarantee must grow exponentially in $\\log(1/(1-2p))$ through its dependence on $m(\\lambda)$. In other words, keeping the block length fixed, taking $p \\to 1/2$ will lead to a weaker undetectability guarantee. This does not manifest itself in the theorem statements since we always think of $p$ as a constant and so values of $p$ closer to $1/2$ result in a polynomially weaker undetectability guarantee for fixed blocklength, which is insignificant compared to the superpolynomial guarantee of undetectability (and we do not distinguish between different polynomials). We remark that the results of [Christ & Gunn, 2024] have essentially the same tradeoff; please see the end of Section E.1 for further discussion on this point. \n\nQuestion 4: The main challenge lies in handling the tension between the fact that in many large-scale NLP tasks, the entropy rate is relatively low and the resulting alphabet size that our results require would be too large compared to the number of tokens. We believe that there are promising techniques which will be able to alleviate these limitations in future work for practical applications; see Question 1 for more details.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CvFWT1OvvM", "reviewer": "Reviewer_ab11", "summary": "This paper proposes a new pseudorandom code (PRC) called an _indexing PRC_ over a polynomially-sized alphabet that is robust to a constant number of adversarial edit corruptions (insertions, deletions or substitutions). It is constructed as a wrapper around a substitution-robust PRC, which has been studied in prior work. The paper also proposes a new substitution-robust PRC that relies on weaker cryptographic hardness assumptions than prior work. These cryptographic primitives are then used to construct a watermarking scheme for autoregressive models (e.g. LLMs), which is proven to satisfy three important properties: undetectability, soundness and edit robustness.", "questions": "- Are there any barriers to instantiating the proposed watermarking scheme? \n- Is edit distance robustness sometimes undesirable for watermarking?", "limitations": "Yes, limitations are discussed on p. 3.", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "**Originality and significance:**\nThe paper builds on recent work by Christ & Gunn (2024), who developed pseudorandom codes (PRCs) over binary alphabets that are robust to adversarial substitutions and limited deletions. This work makes several advances in PRCs, which enables an even more compelling application to watermarking of autoregressive models:\n- A new substitution-robust PRC is proposed based on local weak pseudorandom functions that follows from weaker average-case hardness assumptions than Christ & Gunn’s PRC\n- A new indexing PRC is proposed that is robust to a constant fraction of adversarial edits\n- The indexing PRC is used to develop a watermarking scheme for autoregressive models with large alphabets (whereas Christ & Gunn considered a model with a binary alphabet).\n\n**Clarity:** The authors have done a good job of distilling quite complex/technical work into 9 pages. Despite not having a background in cryptography, I found the paper reasonably accessible. I appreciated the summary of the main results on p. 3-4.", "weaknesses": "1. While the paper is motivated by watermarking of generative models, most of the paper’s contributions are in cryptography. Roughly two-thirds of the paper covers pseudorandom codes, while the final connection to watermarking (Section 5) consumes only half a page. I wonder whether another venue would be a better fit for the work – both in terms of the audience and the ability of reviewers to assess correctness.\n\n1. After having read the paper, it’s not clear to me whether the proposed watermarking scheme can be implemented in practice or not. I think the work is valuable whether the scheme is practical or not, however it’s important to be upfront about practical limitations (if there are any) to help guide future work.\n\n1. Related to the above point about practicality: there is no empirical evaluation of the watermarking scheme. This is not a major issue in my view, as the paper makes very strong theoretical contributions.\n\n1. I wonder whether edit robustness is a desirable property for a watermarking scheme. Consider the case of a vendor who is concerned about safety. An adversary could query the vendor’s model, receive safe watermarked output and then substantially edit the watermarked output to make it unsafe. The watermark is preserved in the unsafe output since it is edit robust, provided the number of edits falls below some threshold. This could be problematic for the vendor’s reputation, as the adversary can assert that the vendor’s model generated unsafe content.\n\n**Minor:**\n- eqn (2): Should the dimension of s be $\\ell(\\lambda)$ rather than $n(\\lambda)$? Inconsistency between two terms: one is an expectation over an indicator function, whereas the other is an expectation over the output of $\\widetilde{\\mathrm{Adv}}^{F_\\mathrm{Unif}}$.\n- line 217: Output of $\\widetilde{\\mathrm{Adv}}^G$ is undefined\n- line 222: Call to $F_s(\\cdot)$ returns a tuple in the space $\\\\{0, 1\\\\}^n \\times \\\\{0, 1\\\\}$, which conflicts with the return type given in line 214.\n- line 244: Should $z \\in$ be $z \\sim$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments.\n\nMinor questions:\n- Eq. (2): Yes, dimension of $s$ should be $\\ell(\\lambda)$. And yes, we forgot an \"=1\" in the second term.\n- Line 217: $\\widetilde{Adv}^G$ refers to the output of the algorithm Adv (which is a 0 or 1) when, each time Adv decides to query G, it receives $(x, G(x))$ for a uniformly random $x$.\n- Line 222: Thanks, we will clarify that the oracle returns just the output of the function $F_s(x) \\in \\{0,1\\}$ (though of course Adv knows the random input $x$ as well). \n- Line 244: Yes, should be $z \\sim$.\n\nQuestions: \n\n1. Using techniques from our theoretical watermarking scheme to develop a practical implementation for use with LLMs is an important direction for future work. The main limitation of our present theoretical results which may complicate a practical implementation is as follows: The alphabet size $|\\Sigma(\\lambda)|$ is required to grow exponentially in the inverse of the parameter $\\alpha$ (see the statement of Theorem E.2). In turn, the parameter $\\alpha$ is proportional to the entropy rate of the text needed to guarantee substring robustness (see Definition 2.6 and the setting of $\\beta_\\lambda(\\ell) = O(\\alpha \\cdot \\ell)$ in Theorem E.2). For typical LLMs, the alphabet size is likely smaller than our required value of $|\\Sigma(\\lambda)|$ given the entropy rates observed empirically in natural language.\nOn the other hand, we believe that future work aimed at developing modifications of our watermarking scheme with an eye towards practical implementation will be successful. One idea which seems promising is to simulate a larger alphabet by grouping tokens together, and to aim accordingly for a slightly weaker robustness guarantee.\n\n2. It sounds like you are asking about using watermarking for public attribution. It is indeed correct that the same \"Detect\" function cannot be used for both (a) detecting watermarked output robustly, and (b) as a sort of signature scheme to attribute text to a certain language model. Section 7.4 of [Christ & Gunn, 2024] proposes a solution to this dilemma by constructing watermarking schemes with \"unforgeable public attribution\": their scheme has an Attribution function, which is not robust and indicates when a portion of its input text is copied verbatim from the model, as well as a Detect function, which is robust and indicates when a portion of its input is edit-distance near to a string output by the model. The key point is that a \"True\" output of Detect should not be interpreted as attributing the text to the model.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8fa5jN0ly6", "reviewer": "Reviewer_zeWE", "summary": "This paper addresses the challenge of watermarking the outputs of language models with provable guarantees of undetectability and robustness to adversarial edits. The authors propose a novel watermarking scheme that maintains these properties even when subjected to a constant fraction of insertions, deletions, and substitutions. This work builds upon previous schemes that could handle only stochastic substitutions and deletions, thereby providing a more comprehensive solution. The key contribution is the development of pseudorandom codes (PRCs) that are robust against such edits, achieved through an indexing approach and relying on weaker computational assumptions. The paper demonstrates the theoretical foundations of this scheme and outlines its potential applications in preventing misuse of AI-generated content.", "questions": "1. What are the specific steps required to implement this watermarking scheme in existing language models, and how does it impact the model's performance in terms of speed and resource consumption?\n2. How does the proposed scheme perform against paraphrase and translation attacks?\n3. Watermark stealing attack has been proposed recently [1,2,3], which can infer the parameters of the watermarking scheme and remove the watermark from the text. How does the proposed scheme perform against watermark stealing attack?\n[1] N. Jovanović, R. Staab, and M. Vechev, “Watermark Stealing in Large Language Models.” http://arxiv.org/abs/2402.19361\n[2] Q. Wu and V. Chandrasekaran, “Bypassing LLM Watermarks with Color-Aware Substitutions.” http://arxiv.org/abs/2403.14719\n[3] Z. Zhang et al., “Large Language Model Watermark Stealing With Mixed Integer Programming.” http://arxiv.org/abs/2405.19677", "limitations": "1. The scheme's scalability to large-scale language models and extensive datasets remains untested, which might be a critical factor in practical applications.\n2. The requirement for a large alphabet size might necessitate modifications in existing tokenization schemes, posing a barrier to seamless integration.\n3. The effectiveness of the watermarking scheme is contingent upon the entropy rate of the generated text, which might not be uniformly high across different language models and applications.\n4. While the theoretical foundations are robust, empirical validation through extensive experimentation on various language models and datasets is needed to ascertain the scheme's practical efficacy and resilience to adversarial attacks.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper introduces a new watermarking scheme, which can handle a broader range of adversarial edits, including insertions and deletions.\n2. The authors provide a thorough theoretical analysis and proof of the robustness and undetectability of their proposed scheme, grounded in cryptographic principles.", "weaknesses": "1. The theoretical nature of the work might pose challenges in practical implementation, especially concerning the scalability and efficiency of the proposed watermarking scheme.\n2. The paper lacks empirical evaluation of the proposed watermarking scheme. Without experiment data, it is very hard to assess the effectiveness of the proposed method in realistic scenarios. \n3. The requirement for a constant entropy rate in the generated text might not be met by all language models, potentially limiting the scheme's effectiveness in low-entropy contexts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review.\n\nMany of the weaknesses and limitations you mention relate to the lack of implementation and experiments. We want to emphasize that developing a fully practical watermarking scheme for immediate use in LLMs is not the point of this paper. Rather, the purpose is to lay the theoretical foundations for a technique to achieve edit-distance robust undetectable watermarking (for which there are not yet any practical schemes), and that additional work is needed to make our scheme fully practical.\n\nQuestion 1: The computational cost of generating each next token for our watermarking scheme is linear in the alphabet size of the LLM. Note that it takes linear in alphabet size time to even generate non-watermarked output. We expect that the actual empirical (constant factor) blowup in computational cost will be quite small due to the relative simplicity of our procedure. That being said, we remark that our scheme requires a large alphabet size, which poses challenges for a direct implementation of it on existing LLMs; see the response to Question 1 of Reviewer YwkB for further details on this point. \n\nQuestion 2: If the paraphrase attack produces text which is close to the original in edit distance (i.e., if it is not an overly aggressive paraphrasing), then our scheme would still detect paraphrased watermarked text. To deal with a translation attack, one could augment our detection algorithm to translate its input text into many common languages and output True if any of the resulting translations is detected as watermarked. This would overcome the translation attack assuming that translating a string x from one language to another and back leads to a string x' which is close to x in edit distance, which we expect to be a reasonable assumption.\n\nQuestion 3: Thank you for pointing out the papers on watermark stealing attacks. While ruling out such attacks is beyond the scope of our paper, we are hopeful that our PRCs and watermarking schemes (as well as those of [Christ & Gunn, 2024]) are resistant to such attacks. Roughly speaking, we believe that it might be possible to show this using the relatively strong cryptographic properties of local weak PRFs (or, in the case of [Christ & Gunn, 2024], the relatively strong cryptographic properties of the noisy parity problem). Establishing such robustness to stealing attacks is an interesting direction for future work, even for the case of subsitution PRCs as in [Christ & Gunn, 2024].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y1RgmlVrD2", "reviewer": "Reviewer_Qm1S", "summary": "This paper constructs an LLM watermarking scheme which is robust to edit distance perturbations. The construction is carried out carefully in stages. The authors first construct pseudorandom codes (PRC) that are robust to constant fraction substitutions assuming the existence of local weak pseudorandom functions (PRF) (see below for an informal definition of PRFs). Here, PRCs refer to a keyed encoding and decoding scheme $(\\mathrm{Enc}_s, \\mathrm{Dec}_s)$ that satisfies the following three criteria. Note that for watermarking, the only “message” that needs to be encoded is “this model is watermarked”, which the authors denote by $\\emptyset$.\n\n1. **Undetectability.** For poly-time oracle Turing machines, the encoding oracle $\\mathrm{Enc}_s: {\\emptyset} \\to \\\\{0,1\\\\}^n$, which is a *random* function that outputs n-bit strings correlated with a *random* secret key s (unknown to the Turing machine), is indistinguishable from a random oracle that outputs purely random n-bit strings.\n2. **Soundness.** For any *fixed* n-bit string y, $\\Pr_{s}[\\mathrm{Dec}_s(y) = \\perp] \\ge 1-\\mathrm{negl}(n)$ (symbol representing NOT watermarked). In words, any fixed string is rejected by the decoder with all but negligible probability. Hence, a random n-bit string y drawn from the uniform distribution (and independently of the secret key s) will be rejected by $\\mathrm{Dec}_s$ with high probability.\n3. **Robustness.** Denoting by $\\mathcal{E} : \\\\{0,1\\\\}^n \\to \\\\{0,1\\\\}^n$ any corruption channel restricted to at most constant fraction substitutions. $\\Pr[ \\mathrm{Dec}_s(\\mathcal{E}(y)) = \\emptyset \\mid y \\leftarrow \\mathrm{Enc}_s(\\emptyset)] \\ge 1-\\mathrm{negl}(n)$.\n\nThe key property in this PRC construction is its robustness, which follows (non-trivially) from the use of local weak PRFs. Intuitively, *local* PRFs that depend only on log(n) bits are just the right primitives for constant-fraction perturbations. For example, if the string y is corrupted at random coordinates, most of the significant bits of the PRF evade corruption with high probability.\n\nHowever, the above PRC is only robust to substitution perturbations, not robust to edit distance perturbations. This brings us to their second stage, which is a generic transformation that takes the above PRC to *index* PRCs. The idea behind index PRCs is simple. Because corruption in edit distance can *delete* coordinates of the given string y, we need to repeat its content in some way to protect against deletions. Given a string, say 1001 one way to represent it is through the indices of its support, {1, 4}. After all, n-bit strings are in one-to-one correspondence with subsets of [n]. Thus, one can repeat the “contents” of the given string y, by cleverly storing and repeating the “indices” of y. Significantly expanding on this observation, the authors construct a PRC that is robust to constant fraction edit distance perturbations. The caveat, of interest to practitioners, is that this PRC requires the alphabet size to increase polynomially with the security parameter, a core parameter controlling undetectability (so quality of the watermarked model), soundness, and robustness.\n\nBased on their careful PRC constructions, the paper culminates by constructing a watermarking scheme for LLMs (i.e., general discrete autoregressive distributions) whose watermark can be robustly and reliably detected if the generated text contains a high empirical entropy substring.\n\n**Local pseudorandom functions.** Local PRFs are PRFs which depend only on few bits of the source randomness. That is, for each secret key s, there exists a support set $J \\subset [n]$ such that $F_s(x) = G_s(x_J)$, where $F_s : \\\\{0,1\\\\}^n \\to \\\\{0,1\\\\}$, and $G_s : \\\\{0,1\\\\}^\\ell \\to \\\\{0,1\\\\}$. For robustness against corruptions to a constant fraction of the coordinates, the authors require $\\ell = \\log n$. It seems that the locality requirement is incompatible with “strong” PRFs in which adversary (an oracle Turing machine that attempts to distinguish the PRF oracle and the random oracle) has query access. This is a non-issue in this work since the authors use weak PRFs, in which the adversary only has random sample access to the oracles.", "questions": "- It seems that the locality requirement is incompatible with “strong” PRFs in which adversary (an oracle Turing machine that attempts to distinguish the PRF oracle and the random oracle) has query access. For example, if an adversary has query access, then it can query the all zeros string and its 1-Hamming neighbors. Then, the adversary can decide that the unknown oracle is a PRF If the label bit is significantly insensitive to these 1-bit perturbations. Is this the right intuition?\n\n- Is there an object analogous to a local weak PRF for continuous domains? Local PRFs seem to be the right objects for countering \"sparse\" perturbation channels which affect only a few coordinates of the sample. What would be appropriate for perturbation channels in continuous domains (e.g., $\\ell_2$ bounded perturbations)?", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The contributions of this paper are significant both theoretically and practically. It is rare for a purely theoretical work, which is aesthetically and technically pleasing in its own right, to directly address an important practical problem of wide interest. I believe this paper has the potential to achieve award-worthy quality if its weaknesses are addressed.\n\n**Addresses a practically important ML question.** The widespread influence of LLMs like ChatGPT on our daily lives has raised numerous concerns and has spurred recent interest in watermarking schemes for LLMs. While there have been several recent works on LLM watermarking, this work is the first to achieve *constant fraction* edit-distance robust watermarking schemes with *reasonable* storage requirements for the secret key. Moreover, the authors achieve this by carefully constructing highly non-trivial theoretical objects (PRCs w.r.t. edit distance) which may have other exciting theoretical applications.\n\n**Technical novelty and significance.** The construction of PRCs based on local weak PRFs, and the generic transformation to index PRCs which are robust to edit distance perturbations is novel. In particular, the connection between PRCs and local weak PRFs seems to be novel, but they seem particularly well-suited for each other. Local weak PRFs are insensitive to perturbations in most coordinates of $(x, F_s(x))$, which is exactly what is needed for the robustness of PRCs.\n\nThe techniques involved in analyzing these schemes are non-trivial since the corruption channels can perturb *adversarially* (but restricted to at most p corruptions). Moreover, the test statistic which is used to test the existence of watermarks is a sum of (weakly) dependent terms to which standard concentration inequalities do not apply. The authors resolve such technical issues by designing the encoding scheme, using additional randomness, to mitigate the power of the perturbation adversary and using recently developed concentration inequalities that apply to weakly dependent random variables.", "weaknesses": "While the paper makes substantial technical contributions, its presentation falls short.\n\n- **Insufficiently polished exposition on application to LLM watermarking (Section 5).** While the paper does a great job in presenting the PRC constructions, the culminating application to LLM watermarking in Section 5 is presented in a very rushed way. The \"full detail\" presentation in Appendix E is hard to follow as well. The key issue seems to be the lack of separation between the high-level intuition and the technical complications, as well as the poor choice of notation. Theorem statements in cryptography often resemble an alphabet soup, so careful and clear notation is crucial. A few suggestions are:\n\n  1. Start Section 5 by explaining the basic idea that connects PRCs and watermarking schemes. The basic idea is that for each token generation, we first sample $y \\leftarrow \\Sigma$ from the PRC alphabet $\\Sigma$, and use rejection sampling with the condition $\\phi(v) = y$ to sample the next token $v$, where $\\phi : \\mathcal{V} \\to \\Sigma$ is a hash map.\n  2. In Algorithm 3, using $p_i$ to denote a *distribution* when $p_0$ and $p$ have already been used to denote constants in $(0,1)$ is confusing. Perhaps $\\mu_i$ might be less confusing?\n  3. The cluttered subscript notation under the $\\Pr$ sign is both misleading and hard to parse. It's misleading because it does not fully specify all the randomness. For example, in Eq. (1) (page 5, line 185) the randomness in $\\Pr$ not only depends on the $\\mathsf{sk} \\leftarrow \\mathsf{KeyGen}$, but also on the internal randomness of the \"adversary\". It might be less confusing to enumerate all elements of randomness as was done in Appendix C.3 (page 20, line 811). In addition, expressions like Eq. (37) in Claim E.10 are quite overwhelming.\n\n- **Lack of formal description of the perturbation channel.** There seem to be two unrelated \"adversaries\" to the watermarking scheme. The \"detection adversary\" which is a poly-time oracle Turing machine that attempts to detect the watermark, and the \"perturbation adversary\", i.e., the perturbation channel, which is a (potentially randomized) function that perturbs the generated text. It might be worth highlighting that the modeled perturbation channel is *static*. That is, the same (potentially randomized) function is applied to the generated text and robustness only holds w.r.t. this *static* adversary. This seems to be an important distinction since robustness against a *dynamic* perturbation adversary which interacts with the watermarking scheme over many rounds appears to be impossible, as the authors note (page 1, line 34-35).\n> *it is necessary to strike a balance in terms of the power of adversaries to which a watermarking scheme enjoys robustness*\n\n- **Contextualizing the local weak PRF assumption.** It's not clear to me why existence of local weak PRFs is weaker than the existence of public-key cryptography. Is there a formal reduction showing that public-key cryptography implies local weak PRFs? I don't think the current explanation based on Impagliazzo's worlds is adequate. Without context, it's unclear what being in Minicrypt or Cryptomania even means. Is there a single \"complete\" primitive that generates all cryptographic tools in each world? Do the worlds form a strictly increasing sequence (in set inclusion)?\n\n**Minor comments**\n- In Section 4, when introducing *indexing* PRCs, it might be helpful to include a diagram demonstrating the \"index\" encoding. For example, one can draw a diagram showing that 100101 maps to {1, 4, 6}.\n\n- The hyperref for \"Line 8\" in (page 6, line 248) is incorrect. It should link to Line 8 in Algorithm 2, not Algorithm 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive comments. Regarding your comments on presentation: we will adjust our exposition accordingly. Regarding local weak PRFs, we do not know of a formal reduction showing that public-key cryptography implies local weak PRFs. We will adjust the discussion to add some additional background from reference [30] (Impagliazzo, 1995) on the meaning of the five worlds (which is somewhat informal, as mentioned on p.3 of Impagliazzo's paper). \n\nQuestion 1: Yes, the locality requirement is incompatible with strong PRFs which give the adversary query access, since $\\log(n)$-juntas can be learned in poly(n) time (See [BL97] below). Roughly speaking, the idea of this result is that for a $\\log(n)$-junta $F(\\cdot)$, an adversary finds x,y so that $F(x) \\neq F(y)$, then queries vertices on a path in the hypercube between x and y, which yields at least 1 of the $\\log(n)$ influential coordinates. It then recurses to find all influential coordinates. It can then learn $F$ by trying all possible n combinations of the $\\log(n)$ influential coordinates.\n\n[BL97] \"A. Blum and P. Langley. Selection of relevant features and examples in machine learning, 1997\"\n\nQuestion 2: $\\ell_2$ perturbations could be reasonable, though it is unclear if local PRFs can be used to achieve robustness to such perturbations. This is an interesting direction for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a novel method to embed an undetectable and robust watermark into LLM-generated texts. The main idea is a new pseudorandom code (PRC) called an indexing PRC over a polynomially-sized alphabet that is robust to a constant number of adversarial edit corruptions (insertions, deletions, or substitutions). The PRC is then integrated into an LLM watermark using a carefully designed mapping. The authors further prove that the resulting watermark is w.h.p. undetectable and is robust to a constant fraction of edit attacks.

All the reviewers have agreed that the paper provides a novel set of contributions and a novel watermarking methodology. While I recommend the paper to be accepted, I would like to suggest to the authors to do their best to further address the comments/limitations raised by the reviewers (e.g. evaluation, scalability, etc -- please see the reviews).
Decision: Accept (poster)