Edit Distance Robust Watermarks via Indexing Pseudorandom Codes

Authors: noah  golowich
ankur  moitra
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 09:05:40

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.

Main paper: 
 introduction: 
 The rapid increase in AI-generated content represents a 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 AI-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 is watermarking schemes, which are procedures that embed hidden patterns in AI-produced content using a secret key. Watermarking schemes allow a 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 a number of recently proposed watermarking schemes, taking both a theoretical perspective (e.g., [CGZ24, CG24, Zam24, FGJ + 23]) as well as a more empirical one (e.g., [KGW + 23, KGW + 24, KTHL23]), a crucial challenge that remains elusive is that of ensuring the watermark be robust to adversaries which can modify the generated content. A watermarking scheme is of little use if it is too easy to change the model's output so as to remove the watermark. On the other hand, a sufficiently resourceful adversary can simply train their own unwatermarked model. Thus it is necessary to strike a balance in terms of the power of adversaries to 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 a constant fraction of i.i.d. deletions under additional stochasticity assumptions on the language model. Our results therefore represent progress towards the overarching goal of constructing watermarking schemes which are robust to resource-limited adversaries.We consider the task of watermarking the output of a language model Model, which is simply defined as a mapping from a sequence of tokens t 1 , . . . , t i-1 to a distribution over the next token. 1 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 + 24]) in addition to text. As this paper is theoretical in nature, we work only with this abstraction of an autoregressive model, keeping in mind that single tokens could represent, e.g., sequences of letters [SHB16] or discretized patches of an image [YLK + 22, RvdOV19]. 2A 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 computationally 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 distortionfreeness [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 watermarked, with high probability (over the generation of the secret key). • Edit-Robustness: 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 is to achieve the notion of edit-robustness given above. Robustness, broadly 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 (e.g., [CGZ24] ) can handle a subconstant fraction of edits. However, we argue that the right notion of adversary is that which makes a constant fraction of edits: there is a relatively low bar for a malicious adversary attempting to remove the watermark by changing the text at a 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 a 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] .The only prior work in the literature which obtains watermarking schemes with provable robustness guarantees against such "constant-rate" attacks was [CG24] , which constructed watermarking schemes robust to a 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] . 3Finally, 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 wellmotivated by an extensive line of work on edit distance (e.g., [OR07, AKO10, AO11, AN20], 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 in 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 editdistance perturbations on strings: for instance, mutations of DNA 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.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.1). Then for any security parameter λ ∈ N, there is a watermarking scheme over an alphabet of size poly(λ) for model outputs of length poly(λ), which is sound, undetectable with respect to algorithms running in time poly(λ), and robust to a 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 a security parameter λ, 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(λ); 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, 4and 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 it can only produce a 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 λ. 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, YLK + 22]; second, in practice one could use various heuristics to increase the number of tokens, such as 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 to constructing good codes is via concatenation, which combine an outer code with large alphabet together with an inner code that encodes individual symbols of the large alphabet using a smaller alphabet. Theorem 1.1 (as well as 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.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 watermarking schemes robust to i.i.d. random (i.e., non-adversarial) subsitutions and deletions. Roughly speaking, a pseuorandom code is an error-correcting code equipped with a secret key used for encoding and decoding, which looks random to any polynomial-time algorithm that does not hold a secret key. We establish the following ingredients pertaining to PRCs:• First, we design a a PRC over the binary alphabet which is robust to a 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 a generic reduction which converts any PRC over a larger alphabet robust to substitutions, insertions, and deletions to a watermarking scheme with analogous robustness properties (Theorem E.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 to obtain a guarantee analogous to Theorem 1.1 but under the (qualitatively stronger) cryptographic assumptions of [CG24] .In order to handle deletions, [CG24] uses a type of PRC they call a 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 a PRC to a 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.i.d., [CG24] need to assume that the language model is equivalent to a BSC. Our use of indexing PRCs avoids this significant shortcoming. 
preliminaries: 
 We begin with the definition of a pseudorandom code (PRC), as introduced in [CG24] . A pseudorandom code is defined over an alphabet Σ, which is simply a 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 a security parameter λ ∈ N; as λ is increased, the amount of security afforded by the PRC also increases. A function f : N → R ≥0 is called negligible if for any C > 0, there exists λ 0 so that f (λ) ≤ λ -C for all λ > λ 0 . We use negl(λ) to denote a negligible function, whose precise value can change from line to line.Given an alphabet Σ, a channel is a mapping E which associates to any x ∈ Σ a distribution E(x) over Σ . With slight abuse of notation, we will often let E(x) denote a random variable y drawn from E(x): for instance, when we write a statement of the form "with probability 1 -negl(n), D Ham (x, E(x)) ≤ pn", we mean that D Ham (x, y) ≤ pn with probability 1 -negl(n) 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. A 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 a secret key, Encode uses the secret key to "encrypt" a message, and Decode uses the secret key to "decode" a string. If the string passed to Decode is the output of Encode, perhaps with a 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 algorithms (undetectability), and Decode should almost always fail when given any fixed string (i.e., not an output of Encode) as input. These definitions are formalized below: Definition 2.1 (Secret-key Pseudorandom code (PRC)). Let λ ∈ N denote a security parameter, and suppose that for each λ ∈ N an associated alphabet Σ(λ) is given. Moreover, suppose that for each λ, a collection E (λ) of channels E : Σ(λ) → ∆(Σ(λ) ) is given. A secret-key pseudorandom code (PRC) with robustness to E is a triple of probabilistic polynomial-time algorithms (KeyGen, Encode, Decode) satisfying the following:• For some functions n, k, sk : N → N, for all λ ∈ N, we have KeyGen(1 λ ) ∈ {0, 1} sk (λ) , Encode : λ) , and Decode :{1 λ } × {0, 1} sk (λ) × Σ k(λ) → Σ n({1 λ } × {0, 1} sk (λ) × Σ → Σ k(λ) ∪ {⊥}.• For any λ ∈ N and message m ∈ Σ k(λ) , the code is robust to any channel E ∈ E (λ), which means that:Pr sk←KeyGen(1 λ ) Decode(1 λ , sk, E(x)) = m | x ← Encode(1 λ , sk, m) ≥ 1 -negl(λ).Moreover, for any fixed y ∈ Σ , the code is sound, which means that:Pr sk←KeyGen(1 λ ) Decode(1 λ , sk, y) =⊥ ≥ 1 -negl(λ).• The code is undetectable which means that: for any λ ∈ N for any probabilistic polynomial-time adversary Adv,EQUATIONwhere U denotes an oracle which responds with a freshly drawn uniformly random string in Σ n(λ) on each call (to any input).The block length of the PRC is defined to be n(λ). For all of our pseudorandom codes, we will have n(λ), k(λ), sk (λ) ≤ poly(λ). Moreover, we take as a convention that n(λ) ≥ λ for all λ (this may be ensured without loss of generality by rescaling n(λ)). Our focus will primarily be on 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 k(λ) = 0 for all λ, i.e., the only possible message is m = ∅.[CG24, Section 6] shows a generic reduction that converts any zero-bit PRC into a general PRC with constant rate, meaning that k(λ)/n(λ) = Ω(1). 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 (Substitution-bounded). For p ∈ (0, 1), a channel E over alphabet Σ is p-substitutionbounded if for any n ∈ N, y ∈ Σ n , for z ∼ E(y), D Ham (y, z) ≤ pn holds almost surely.Definition 2.4 (Edit-bounded channel). Fix an alphabet Σ together with p ∈ (0, 1). A channel E over Σ is defined to be p-edit-bounded if for any x ∈ Σ with n := |x|, y ∼ E(x) may be obtained from x by applying a total of at most pn substitutions, insertions, and deletions, almost surely. Moreover, there exists a probabilistic polynomial-time algorithm which, given x, outputs a sample y ∼ E(x).5 3 Secret-key substitution PRCs from weaker assumptionsIn 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.e., in the context of Impagliazzo'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 in "Minicrypt", though we are not aware of a 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 x.Definition 3.1 (Weak PRF family). Fix functions (λ), n(λ) : N → N of a security parameter λ, and a collection of functions {F s : {0, 1} n(λ) → {0, 1}}, indexed by s ∈ {0, 1} (λ) , for λ ∈ N.We say that the collection {F s } s is a 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 thatEQUATIONwhere Adv, for a mapping G : {0, 1} n(λ) → {0, 1} means that Adv can make calls to the function G, and for each call receives a tuple (x, G), for x ∼ Unif({0, 1} n ). (In particular, the tilde refers to the fact that Adv can only call G(x) on a uniformly chosen x.) Moreover, F Unif : {0, 1} n → {0, 1} denotes a uniformly random function. We will often refer to the function G that Adv can make queries to as the oracle Adv has access to. Given q ∈ [0, 1/2), we say that {F s } s is a weak PRF family with noise level q if (2) holds where each call to F s (•) by Adv returns F s (x) ⊕ e where x ∼ Unif({0, 1}) n and e ∼ Ber(q).Our new construction of PRCs is based off of local (weak) PRFs, which are PRFs for which the output depends on a small number of input bits. Definition 3.2 (Local function family). Let τ ∈ N. A family of functions {F s : {0, 1} n → {0, 1}} indexed by s is defined to be τ -local if for each s, F s (x) only depends on at most τ bits of x, i.e., for each s there are distinct indices j 1 , . . . , j τ ∈ [n] together with a function G s : {0, 1} τ → {0, 1} so that F s (x) = G s (x j1 , . . . , x jτ ) for all x ∈ {0, 1} n .Our main computational assumption is the existence of a weak PRF family which is τ -local for τ of logarithmic size: Assumption 3.1 (Local Weak PRFs). For some functions (λ), n(λ), τ (λ) : N → N with (λ), n(λ) ≤ poly(λ) and τ (λ) ≤ log n(λ), there exists a weak PRF family {F s : {0, 1} n(λ) → {0, 1}} s∈{0,1} (λ) for some noise level q < 1/2 which is τ (λ)-local, for each λ ∈ N.In Appendix C.2, we discuss how Assumption 3.1 follows from standard average-case hardness assumptions, notably the hardness of learning log(n)-juntas over Unif({0, 1} n ). As specific examples, either hardness of the log(n)-sparse noisy parity problem [FGKP09, BFJ + 94, GRV11, Val15] or hardness of weakly learning a 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 a 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, q] = (KeyGen, Encode, Decode) as follows. The construction depends on some parameters N (λ), m(λ) ≤ poly(λ), specified in (3):• KeyGen(1 λ ) chooses a function in F (indexed by s) together with a uniformly random z ∼ Unif({0, 1} N (λ) ) and a uniform permutation π : [N (λ)] → [N (λ)], and returns sk = (s, z, π).• Encode(1 λ , (s, z, π), ∅) draws m(λ) uniformly random elements of {0, 1} n(λ) , x 1 , . . . , x m(λ) , applies F s to each of them and flips the result with probability q to obtain bits (w 1 , . . . , w m(λ) ), and perturbs the concatenation ((x i , w i )) i∈[m(λ)] according to z, π as on Line 9.• Decode(1 λ , (s, z, π), y) first "unperturbs" y to obtain a string ((x i , w i )) i∈[m(λ)] as in Encode, and then outputs ∅ if m(λ) j=1 1{w j = F s (x j )} is above a threshold; otherwise, it outputs ⊥.Theorem 3.2. Given p, q < 1/2 and a function family F together with noise level q satisfying Assumption 3.1, then PRF-PRC[F, p, q] (Algorithm 2) is a zero-bit binary-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. 
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 substitution-bounded channels. Suppose we are given a PRC PRC Sub with block length n(λ) over the binary alphabet which is robust to any (1/2 -p 0 )-bounded substitution channel, for p 0 ∈ (0, 1/2). Given a parameter ρ ≥ 1, we construct an indexing PRC, PRC Idx [PRC Sub , ρ] (in Algorithm 1), which is robust to any p-edit-bounded channel, where the parameter p depends on p 0 , ρ in a manner that will be explained below. The code PRC Idx [PRC Sub , ρ] has polynomially large alphabet Σ(λ) := [q(λ)], where q(λ) = ρ • n(λ). We denote the block length of PRC Idx [PRC Sub , ρ] by m(λ) (which is defined to be ln(2) • n(λ) ) to distinguish it from the block length n(λ) of PRC Sub . • The Encode(1 λ , (sk, ψ), m) function calls the encoding method Encode Sub for PRC Sub , which yields a string y 0 ∈ {0, 1} n(λ) . It then chooses a string y ∈ [n(λ)] m(λ) 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 0 := {i ∈ [n(λ)] : y 0 i = 1} of indices at which y 0 has a "1". The precise way in which the sets Unique(y) and S 0 differ is determined by the function PerturbDifference in Algorithm 1, and is needed to ensure that the output of Encode(1 λ , sk, m) is indistinguishable from the uniform distribution over [n(λ)] m(λ) (i.e., that the PRC is undetectable). Finally, Encode returns a string z ∈ [q(λ)] m(λ) where each coordinate z j is a uniformly random pre-image of y j under ψ.• The Decode(1 λ , (sk, ψ), z) function calls the substitution PRC decode function, Decode Sub , on the string y ∈ {0, 1} n(λ) which has a 1 in position i ∈ [n(λ)] if and only if i ∈ Unique(ψ(z)).For future reference, we denote this string by y = D ψ (z), i.e., D ψ (z) i = 1{i ∈ Unique(ψ(z))}. Define sk ← KeyGen Sub (1 λ ). Set y 0 ← Encode Sub (1 λ , sk, m) ∈ {0, 1} n(λ) .Set y ← PerturbDifference(n(λ), m(λ), y 0 ).For each j ∈ [m(λ)], choose z j ∼ Unif({a : ψ(a) = y j }).return z = (z 1 , . . . , z m(λ) ). Define y := ψ(z) = (ψ(z 1 ), . . . , ψ(z m(λ) )).12: Define y ∈ {0, 1} n by y i = 1{i ∈ Unique(y)}.return Decode Sub (1 λ , sk, y ). Set S 0 := {i ∈ [n] : y 0 i = 1}.Sample y 1 ∼ Unif([n] m ).Set S 1 := Unique(y 1 ) ⊂ [n].18:if |S 0 \S 1 | ≥ |S 1 \S 0 | then 19:Let σ : S 1 \S 0 → S 0 \S 1 denote a uniformly random injective mapping.For each a ∈ S 1 \S 0 , let y be formed by replacing each instance of a in y 1 with σ(a).else 22:Let τ : S 0 \S 1 → S 1 \S 0 denote a uniformly random injective mapping.For each a ∈ S 0 \S 1 , let y be formed by replacing each instance of τ (a) in y 1 with a.24:return y.Unfortunately, such a result does not have sufficiently good robustness for our application to watermarking. As will be discussed in Section 5, our procedure which watermarks a language model Model by "embedding" a codeword z of a PRC in a sequence of text output by Model introduces a fraction 1 -α of errors to z, all of which are substitutions. Here α is some constant which is related to the entropy rate of Model. Using the naive approach above, we are constrained to a rate of substitutions p bounded as p < 1/4, thus forcing 1 -α < 1/4 and so disallowing all but high entropy rates.To compensate, we make use of the fact that the randomly chosen mapping ψ : [q(λ)] → [n(λ)] maps multiple (namely, ρ) symbols in [q(λ)] to each symbol in [n(λ)], when performing decoding. In particular, consider any fixed channel E over the alphabet [q(λ)]. For simplicity in our overview here, we assume that E is deterministic (so that it is specified by a mapping E : [q(λ)] m → [q(λ)] for each m ∈ N), though essentially the same argument works for randomized E. Consider a codeword z ∈ [q(λ)] m(λ) which is output by Encode(1 λ , (sk, ψ), m). By undetectability of the code, with high probability over Encode, we will have that |Unique(ψ(z))| ≈ n(λ)/2 ± O( n(λ)), since by our choice of m(λ) = n(λ) • ln(2) , a uniformly random string z ∼ Unif([q(λ)] m(λ) ) satisfies |Unique(ψ(z))| ≈ n(λ)/2 ± O( n(λ)) with high probability. 6Supposing that E is promised to make at most a fraction 1 -p of edits, then z := E(z) shares at least p • m(λ) symbols with z. Let us suppose for simplicity here that z ∈ [q(λ)] m(λ) , so that the insertions and deletions of E are balanced (a slight modification of the argument handles the general case). Of the remaining (1 -p) • m(λ) symbols of z , by the random choice of ψ and since |Unique(ψ(z))| ≈ n(λ)/2, each one is roughly equally likely to map (under ψ) to an element in Unique(ψ(z)) as to an element in [n(λ)]\Unique(ψ(z)). Thus, in going from the set Unique(ψ(z)) to the set Unique(ψ(z )), we should expect to change at most roughly (1 -p) • n(λ)/2 elements. This intuition is made precise in the following lemma:Lemma 4.2 (Informal version of Lemma D.7). Given a channel E as above which makes a (1 -p)fraction of edits (i.e., substitutions, insertions, and deletions), with 1 -negl(λ) probability over the draw of of (sk, ψ) ← KeyGen(1 λ ) and z ← Encode(1 λ , (sk, ψ), m) we can bound the set difference between Unique(ψ(z)), Unique(ψ(E(z))) as follows:|∆(Unique(ψ(z)), Unique(ψ(E(z)))| ≤ (1 -Ω(p)) • n(λ).Since 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 of ψ), we need to use Dobrushin's concentration inequality (Theorem F.3) for data with limited dependencies. Roughly speaking, this inequality comes into play because the sets ψ -1 (1), . . . , ψ -1 (n(λ)) ⊂ [q(λ)] are not fully independent (since, e.g., they must be disjoint). Nevertheless, we may bound their dependencies, assuming that n(λ) is sufficiently large as compared to ρ. 
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 a 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, we need the notion of empirical entropy: given a token sequence t ∈ Σ L and i, j ∈ [L], the empirical entropy of Model on the subsequence [i, j] isH [i:j] e (t, Model) := -log Pr t i:j ∼Model(•|t1:i-1) (t i:j = t i:j | t 1:i-1 ),where the probability is over a sequence that is 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 t i:j is "far from being deterministic" under Model given the prefix t 1:i-1 .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 watermarked text is passed through a channel inducing a bounded number of edits, then the watermark will still be detected. More precisely, for a function β : N → N, a watermarking procedure W = (Setup, Wat, Detect) over an alphabet Σ is β-substring robust to a channel E ifPr sk←Setup(1 λ ) t←Wat(1 λ ,sk),t ←E(t) ∃i, s.t. Detect(1 λ , sk, t ) = False and H [i:i+ -1] e (t) ≥ β( ) • ln |Σ| ≤ negl(λ).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 definition of substring-robustness. Our main result of this section shows that a PRC with robustness to edit-bounded channels yields a watermarking scheme with substring-robustness to edit-bounded channels:Theorem 5.1 (Informal version of Theorem E.1). Let α ∈ (0, 1) be a given constant. Suppose PRC, defined over alphabet Σ PRC , has block length n and is robust to any (1 -α 16 )-edit-bounded channel. Further suppose Model is a language model over alphabet Σ satisfying |Σ| ≥ ( 8 α |Σ PRC |) 2/α . Then there is a watermarking scheme W[PRC, Model] (Algorithm 3) which is sound, undetectable, and β( )-substring robust to any α 2 48 -edit-bounded channel, for β( ) := 8n + 6α .Theorem 5.1 establishes that, as long as the entropy from a substring of generated text is roughly a Ω(α)-fraction of the maximum possible entropy, then a constant (O(α 2 )) fraction of edits to that substring cannot remove the watermark. We remark that this constant fraction of edits cannot be impoved to beyond an α-fraction (as is evident from the example in Footnote 4). The proof of Theorem 5.1 builds off of the reduction of [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, we 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 W[PRC, Model] of Theorem 5.1. The main limitation of our present theoretical results which may complicate a practical implementation is as follows: The alphabet size |Σ(λ)| is required to grow exponentially in the inverse of the parameter α (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 β λ ( ) α • in Theorem E.2). For typical LLMs, the alphabet size is likely smaller than our required value of |Σ(λ)| given the entropy rates observed empirically in natural language. On 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.Watermarking has a long history, dating back to the work of [TTI05, ARC + 01, ARH + 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 a 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 a text segment is noticeably higher than 1 2 . 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 k 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. [KTHL23] introduced a notion called distortion-freeness, which posits that a single text sample from the watermarked model is distributed identically to a single sample from the true model. [KTHL23] construct watermarking schemes satisfying distortionfreeness, with nontrivial edit-robustness guarantees: their watermarks have robustness to a 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).7 [HCW + 24, WHZH23] also developed a similar approach to [KTHL23] .[CGZ24] defined the stronger notion of undetectability (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. [CGZ24] constructed the first provably undetectable watermark by using a similar technique to [AK22, KGW + 23] with the modification that they dynamically adjust the parameter k denoting the length of text used to seed the pseudorandom 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 [FGJ + 23], which concentrated on schemes with public attribution.It is natural to wonder: why should one should prefer undetectable watermarking schemes over distortion-free ones? The simplest reason is that, as a requirement on generative models, distortionfreeness is very weak, as illustrated in the below example.Example A.1 (Distortion-freeness). Consider the alphabet Σ = {0, 1} and suppose that Model is the uniformly random distribution on outputs t ∈ {0, 1} n , for some n ∈ N. Consider the watermarking scheme which draws a key sk ∼ Unif({0, 1} n ) 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 it is clearly not undetectable).Example A.1 indicates that distortion-free watermarks may suffer from insufficient diversity in model outputs: in Example A.1 there is no variation whatsoever in the outputs. The distortion-free schemes of [KTHL23] are only slightly better on this front: they sample a long random key sk and then generate a 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 a repeat answer after only len(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 a more compelling argument for adopting watermarking in the first place. Watermarking is just one of many technologies that can be built into AI 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 output, the result will be essentially the same, means that the addition of a 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) AI model and generate content from it. Therefore, we view robust watermarking as targeted more at "honest" or "lazy" adversaries who are making edits to either improve the quality of content without explicitly trying to remove a watermark (e.g., for AI-generated news articles) or have very few resources to remove the watermark (e.g., a student asking an LLM to 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 + 24a, LB24, CBD + 24, KGW + 24]).Error-correcting codes for insertions and deletions. A recent line of work (e.g., [GL16, BGH17, GW17, HS21a, HS21b]) has focused on developing error-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 a 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 a 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 easier to align a 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 to construct such codes that are pseudorandom.A language model Model over alphabet Σ which, for any positive integer i, takes as input a sequence of tokens t 1:i-1 = (t 1 , . . . , t i-1 ) already output by the model and produces a distribution Model(t i = • | t 1:i-1 ) ∈ ∆(Σ), representing the distribution of the next token, conditioned on t 1:i-1 . We assume that Model is computationally efficient, meaning that it runs in time poly(i, log |Σ|). We also assume that there is some token END ∈ Σ representing the end of the model's response. As a matter of convention, we assume that all subsequent tokens after a END token are also END (i.e., Model(END | t 1:i-1 ) = 1 if some t j for j < i is END). Given a language model Model, we introduce the notation Model: given any sequence t 1:i-1 ∈ Σ i-1 (which may be the empty sequence) and m > 0, the distribution Model(t i:i+m-1 = • | t 1:i-1 ) ∈ Σ m is defined as follows: we sequentially generate t i , . . . , t i+m-1 , where for each 0 ≤ j < m, t j is distributed as Model(t j = • | t 1:j-1 ). In the case i = 1 (i.e., t 1:i-1 = ∅), then we denote an output of Model as t ∼ Model.An intuitive requirement on Model that allows for watermarking is that outputs of Model must be highentropy; indeed, a model that outputs a deterministic sequence of text is 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 t ∈ Σ L , and i, j ∈ t, we define the empirical entropy of Model for t on subsequence [i, j] to be:H [i:j] e (t, Model) := -log Model(t i:j | t 1:i-1 ).By definition of Model, we have -log Model(t i:j | t 1:i-1 ) = -log Pr t∼Model ( ti:j = t i:j | t1:i-1 = t 1:i-1 ). When Model is clear from context, we typically drop Model from the notation, so that H Our main goal in this paper is to construct a watermarking scheme for Model, which is a tuple W = (Setup, Wat, Detect) of probabilistic polynomial-time algorithms with the following semantics:[i:j] e (t) := H [i:j] e (t,• Setup(1 λ ) takes as input a security parameter λ ∈ N and outputs a secret key sk.• Wat(1 λ , sk) takes as input λ, sk and outputs a sequence t = t 1:L ∈ Σ L , for some L ∈ N.• Detect(1 λ , sk, t) takes as input a sequence t ∈ Σ for some ∈ 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 λ ∈ 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 λ. Formally, we consider a language model family indexed by λ, (Model(λ)) λ∈N , where the alphabet for Model(λ) is denoted by Σ(λ). Our watermarking procedure should produce a string in Σ(λ) which is computationally indistinguishable from an output of Model(λ). In 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 λ, we assume that the length of an output t ∼ Model(λ) is bounded by L max (λ), where L max (λ) is some function growing as poly(λ).9 When the value of λ is clear from context, we drop the argument λ and simply write Model, Σ. Definition B.2 (Soundness, Undetectability, E -Robustness). Consider a language model family Model(λ) together with a watermarking scheme W = (Setup, Wat, Detect). We define the following properties of W:• W is sound if for all λ ∈ N and t ∈ Σ ≤Lmax(λ) , Pr sk←Setup(1 λ ) Detect(1 λ , sk, t) = True ≤negl(λ).• W is undetectable if for all λ ∈ N and any probabilistic polynomial time algorithm Dist,Pr Dist Model (1 λ ) = 1 -Pr Dist Wat(1 λ ,sk) (1 λ ) = 1 ≤ negl(λ),where Dist O means that Dist can make repeated calls to O, which generate a sample from the corresponding distribution (either t ∼ Model or t ∼ Wat(1 λ , sk)).• Fix some family of channels (E (λ)) λ∈N , where each E (λ) is a collection of channels E : Σ(λ) → ∆(Σ(λ) ), and a family of functions β λ : N → N. Then W is defined to be β-substring robust to the family (E (λ)) λ if for each λ ∈ N, and each channelE ∈ E (λ), Pr sk←Setup(1 λ ) t←Wat(1 λ ,sk),t ←E(t) ∃i, j ∈ [L max (λ)] s.t. Detect(1 λ , sk, t ) = False and H [i:j) e (t) ≥ β λ (j -i) • ln |Σ(λ)| ≤ negl(λ).Above, we use the convention that t is to be interpreted as an element of Σ Lmax(λ) 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 it through an channel E, then the output of the channel is still detected as watermarked with high probability.Given n ∈ N together with a mapping π : [n] → [n] and a string x = (x 1 , . . . , x n ) ∈ Σ n , we write π • x := (x π(1) , . . . , x π(n) ) ∈ Σ n . Given a mapping φ : X → Y for (finite) sets X , Y and a distribution P ∈ ∆(X ), we let φ • P ∈ ∆(Y) be the push-forward distribution for φ, i.e., (φ • P )(y) = P (φ -1 (y)).Given a mapping ψ : X → Y for finite sets X , Y, we let ψ(X ) := {ψ(x) : x ∈ X } ⊂ Y, and for any Y ⊂ Y, ψ -1 (Y ) := {x ∈ X : ψ(x) ∈ Y }. Finally, for a tuple x = (x 1 , . . . , x n ) ∈ X n , we let ψ(x) := (ψ(x 1 ), . . . , ψ(x n )) ∈ Y n .For y ∈ Σ N and J = (j 1 , . . . , j t ), we let y J ∈ Σ t denote the vector y J := (y j1 , . . . , y jt ). Given a set S, m ∈ N, and a string y ∈ S m , we define Unique(y) := {y i : i ∈ [m]} ⊂ S, i.e., Unique(y) is the set of distinct elements of y.In this section, we discuss several standard conjectures on 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 ∈ N, we are given a class F n of boolean functions indexed by strings s ∈ {0, 1} (n) , for some function :N → N; write F n = {F s : {0, 1} n → {0, 1}} s∈{0,1} (n) . Given q ∈ [0, 1/2), we say that F = (F n ) n is ( (n), δ(n))-PAC learnable with noise level q if there is a poly(n)-time algorithm Alg which, for some m(n) ∈ N, takes as input a dataset D = ((x i , y i )) i∈[m(n)] and X ∈ {0, 1} n ,1 -δ over s ∼ Unif({0, 1} (n) ), x i ∼ Unif({0, 1} n ), y i = F s (x i ) (i ∈ [m(n)]): Pr X∼Unif({0,1} n ) Alg((x i , y i ) i∈[m(n)] , X) = F s (X) ≤ .Proposition C.1. Suppose that a family of functions F = (F n ) n∈N is not (1/3, 1/3)-PAC learnable with noise level q ∈ [0, 1/2) (per Definition C.1). Then, with n(λ) = λ, the family of functions (F n(λ) ) λ is a weak PRF with noise level q (per Definition 3.1).Proposition C.1 is essentially folklore (see, e.g., [BR17] ), but we provide a proof sketch for completeness:Proof sketch of Proposition C.1. Suppose that a polynomial-time adversary Adv satisfiesE s∼{0,1} n(λ) Adv Fs(•) (1 n(λ) ) = 1 -E F Unif Adv F Unif (1 n(λ) ) ≥ λ -O(1) ,where F Unif : {0, 1} n → {0, 1} denotes a uniformly random function. Suppose that Adv makes at most m(λ) queries to its oracle (eitherF s (•) or F Unif ). Consider the algorithm which re- ceives m(n) samples (x i , y i ) with x i ∼ Unif({0, 1} n ), y i = F s (x i ) for an unknown s together with X ∼ Unif({0, 1} n(λ) ), chooses a uniformly random index m ∈ [m(λ) -1],and then runs Adv with the oracle responses given by (((x i , y i )) i∈[m ] , (X, b), (x j , y j ) j∈[m +2,n(λ)] ), where x j ∼ Unif({0, 1} n ), y j ∼ Unif({0, 1}) for j ≥ m + 2, for each value of b ∈ {0, 1}. By a hybrid argument, for some b ∈ {0, 1}, this algorithm must have λ -O(1) advantage at predicting F s (X). A standard boosting argument [FS95] then establishes the existence of a polynomial-time algorithm that (1/3, 1/3)-PAC learns the family F.By Proposition C.1, either of the two assumptions below implies Assumption 3.1:Assumption C.2 (Sparse noisy parity). There is no polynomial-time algorithm which (1/3, 1/3)-PAC learns the family (F n ) n of log(n)-sparse parities with noise level q = 1/3, i.e.,F n = {F s (x) = i∈[n] x i s i : s ∈ {0, 1} n , s 1 = log(n)}.It is straightforward to see (using a hybrid argument) [Blu03] that Assumption C.2 is equivalent to the assumption that there is no polynomial-time algorithm which identifies the hidden log(n)-sparse string s ∈ {0, 1} n with constant probability.There is no polynomial-time algorithm which (1/3, 1/3)-PAC learns the family (G n ) n defined below, with noise level q = 0:G n = G S1,S2 (x) = Maj(x i : i ∈ S 1 ) ⊕ i∈S1 x i | S 1 , S 2 ⊂ [n] are disjoint subsets of size log(n)/2 .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 G S1,S2 with constant probability. We remark that [FGKP09, Theorem 3] shows that an algorithm which learns log(n)-sparse parities at noise level 1 2 -O(1/n) implies the existence of an algorithm which learns (noiseless) log(n)-juntas (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)-sparse noisy parities with noise level q = 1/2 -O(1). Thus, even given the reduction of [FGKP09] , Assumption C.3 does not appear to imply Assumption C.2.Weakly substitution-bounded 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 a channel E over an alphabetΣ is p-weakly-substitution-bounded if for any n ∈ N, Pr y∼Unif(Σ n ),z∼E(y) (D Ham (y, z) > pn) ≤ negl(n).Noise sensitivity. For x ∈ {0, 1} n , we let N ρ (x) ∈ ∆({0, 1} n ) denote the distribution over y, where y i = x i with probability 1/2+ρ/2 (and y i = 1-x i with probability 1/2-ρ/2), independently for each i. Note that y ∼ N 1-2δ (x) is generated by flipping each bit of x with probability δ. DefineNS δ [f ] := Pr x∼Unif({0,1} n ),y∼N 1-2δ (x) (f (x) = f (y)). Also write W i [f ] = S⊂[n],|S|=i f (S) 2 . Lemma C.4 (Theorem 2.49 of [ODo14]). For any f : {0, 1} n → {-1, 1}, we have NS δ [f ] = 1 2 n i=0 (1 -(1 -2δ) i ) • W i [f ]. Corollary C.5. For any f : {0, 1} n → {0, 1}, we have NS δ [f ] = 1 2 - n i=0 φ i • (1 -2δ) i , for some φ 0 , . . . , φ n ≥ 0 satisfying φ 0 + • • • + φ n = 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} n → {-1, 1} satisfies n i=0 W i [f ] = 1. C.3 Proof of Theorem 3.2Proof 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[F, p, q] uses Assumption 3.1: if undetectability failed to hold as witnessed by some adversary Adv, then we could construct 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, ∅) (i.e., if the channel E does nothing to its input). Indeed, the tuples (x i , w i ) (for i ∈ [m(λ)]) computed in Line 11 of Decode are exactly equal to (x i , F s (x i ) ⊕ e i ). As long as the noise rate q of e i is bounded away from 1/2, the statistic W computed in Decode will be larger than m(λ)/2 + ln(m(λ)) m(λ) with all but negligible probability, as desired.Algorithm 2 PRF-PRC[F, p, q]: Generic PRF-based PRC Require: Weak PRF family F = (F λ ) λ , where F λ = {F s : {0, 1} n(λ) → {0, 1}} indexed by s ∈ {0, 1} (λ) , parameters p, q ∈ (0, 1). Functions n(λ), (λ), m(λ), N (λ) :N → N satisfying N (λ) ≥ (n(λ) + 1)m(λ), 1: function KeyGen(1 λ ) 2:Sample s ∼ Unif({0, 1} (λ) ) and z ∼ Unif({0, 1} N (λ) .Let π : [N (λ)] → [N (λ)] be a uniformly random permutation.Return sk := (s, z, π).5: function Encode(1 λ , sk = (s, z, π), ∅) 6: Sample x 1 , . . . , x m(λ) ∼ Unif({0, 1} n(λ)) and e 1 , . . . , e m(λ) ∼ Ber(q).Sample r ∼ Unif({0, 1} N (λ)-(n(λ)+1)m(λ) ).Define a := ((x 1 , F s (x 1 ) ⊕ e 1 ), . . . , (x m(λ) , F s (x m(λ) ) ⊕ e m(λ) ), r).return the string π • (a ⊕ z). Let x 1 , . . . , x m(λ) ∈ {0, 1} n(λ) and w 1 , . . . , w m(λ) ∈ {0, 1} be defined by((x 1 , w 1 ), . . . , (x m(λ) , w m(λ) )) = ((π -1 • y) ⊕ z) 1:(n(λ)+1)m(λ) .12:Let W := m(λ) j=1 1{w j = F s (x j )}. 13: If W > m(λ) 2 + ln(m(λ)) m(λ), return ∅; otherwise, return ⊥.Now what if y is drawn from E(y 0 ), for y 0 ← Encode(1 λ , sk, ∅), for some p-bounded substitution channel E? Then the tuples computed in Line 11 of Decode may be written as(x i , w i ) (for i ∈ [m(λ)]), where (x i , w i ) are "perturbed" versions of (x i , w i ), wherex i ∼ Unif({0, 1} n(λ) ), w i = F s (x i) ⊕ e i are as computed in Encode. Although the channel E may introduce substitutions in an adversarial fashion (i.e., it may not introduce substitutions at each position independently with probability p), by virtue of the fact that the output string of Encode is π •(a⊕z) for uniformly random z ∈ {0, 1} N (λ) , π : [N (λ)] → [N (λ)], we can show that (x i , w i ) is close to being distributed by perturbing each bit of (x i , w i ) independently with some probability p ≤ p. The proof of this fact uses an approximation of a Hypergeometric distribution with a Binomial distribution: roughly speaking, the permutation π allows us to "pick out", for each i, a uniformly random subset of n(λ) + 1 positions corresponding to (x i , w i ), out of N (λ) total positions of the string y. Of these, p • N (λ) ≤ p • N (λ) are changed by E, and as long as N (λ) n(λ), applying E thus has nearly the same effect as changing each of the n(λ) + 1 positions of (x i , w i ) independently with probability p .Given the above, we then use the fact that if x i ∼ Unif({0, 1} n(λ) ) and x i is formed by flipping each bit of x i with probability p ≤ p, then Pr[F s (x i ) = F s (x i )] ≥ 1 2 + (1 -2p) τ ≥ 1 2 + (1 -2p) log n(λ). 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 F s (•) is τ -local for some τ ≤ log(n(λ)). Note that (1 -2p) log n(λ) ≥ n(λ) -Ωp(1) ; thus, as long as m(λ) is a large enough polynomial in n(λ), we can show that the statistic m(λ) i=1 1{w i = F s (x i )} 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 (x i , e i , x i , w i ) may not be independent across different i. Thus, to ensure concentration of the sum m(λ) i=1 1{w i = F s (x i )} 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 (λ) is sufficiently large.Formal proof. Suppose that we are given some p < 1/2 together with a weak PRF family F = {F s : {0, 1} n(λ) → {0, 1}} λ∈N,s∈{0,1} (λ) with noise level q < 1/2 which verifies Assumption 3.1, i.e., for some function τ (λ) ≤ log n(λ), the family is τ (λ)-local. We consider the construction PRF-PRC[F, p, q] in Algorithm 2. We let the functions n(λ), (λ) be as given by the PRF family F, and chooseEQUATIONwhere C 0 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 to p-weaklysubstitution-bounded channels: we do so in Lemma C.6, Lemma C.7, Lemma C.8, respectively, below.Lemma C.6 (Soundness). For any function family F = {F s } s on {0, 1} n(λ) indexed by s ∈ {0, 1} (λ) , and p, q ∈ (0, 1), PRF-PRC[F, p, q] is sound.Proof. Fix λ ∈ N, and write n = n(λ), = (λ), m = m(λ), N = N (λ). Fix any y ∈ {0, 1} N . Let x 1 , . . . , x m ∈ {0, 1} n , w 1 , . . . , w m ∈ {0, 1} be defined as in Decode(1 λ , sk, y), i.e., ((x 1 , w 1 ), . . . ,(x m , w m )) = ((π -1 • y) ⊕ z) 1:(n+1)m, where sk = (s, z, π). Since π, z are uniformly random in their respective domains, it follows that W = m j=1 1{w j = F s (x j )} is distributed as Bin(m, 1/2) for any fixed s, meaning that, for any δ ∈ (0, 1), Pr z,π (W > m/2 + m log 1/δ) ≤ δ.Choosing δ = 2 -log 2 m ≤ negl(λ) yields that Pr sk←KeyGen(1 λ ) (W > m/2+log(m) √ m) ≤ negl(λ), as desired.Lemma C.7 (Undetectability). Fix p, q ∈ [0, 1/2). Suppose that F = {F s } s is a weak PRF on {0, 1} n(λ) with noise level q (Definition 3.1), indexed by s ∈ {0, 1} (λ) . Then PRF-PRC[F, p, q] is undetectable.Proof. Fix λ ∈ N, and write n = n(λ), = (λ), m = m(λ), N = N (λ). Consider any probabilistic polynomial-time adversary Adv. Let sk = (s, z, π) ← KeyGen(1 λ ) denote the secret key for the PRC. Suppose that the adversary makes a total of Q queries to Encode(1 λ , sk, ∅); its view consists ofEQUATIONfor some constant c > 0, then we could construct an adversary Adv which violates security of F s (namely, Definition 3.1), as follows: Adv makes Qm calls to F s (•) on random inputs, which gives it samples (x(i) j , F s (x (i) j ) ⊕ e (i) j ) for j ∈ [m], i ∈ [Q],draws a uniformly random permutation π : [N ] → [N ] and a uniformly random string z ∈ {0, 1} N , and outputs the result of Adv given the Q tuples y (i) := π • (((x(i) 1 , F s (x (i) 1 ) ⊕ e (i) 1 ), . . . , (x (i) m , F s (x (i) m ) ⊕ e (i) m ), r (i) ) ⊕ z), where r (i) are uniformly random strings of length N -(n + 1)m (for i ∈ [Q]). Note that if the mQ calls made by Adv were generated by a random function, then the strings y (i) are uniformly random in {0, 1} N , conditioned on the event that x(i) j are all distinct, for j ∈ [m], i ∈ [Q]. The probability that all x (i) jare distinct is at least 1 -mQ/2 n ≥ 1 -negl(λ), meaning that, by (4), Adv achieves advantage λ -cnegl(λ) on distinguishing a random element of the family {F s } s from a uniformly random function, thus contradicting the security of F.Given N, t ∈ N, let J N,t denote the distribution of t-tuples J = (j 1 , . . . , j t ) where j 1 , . . . , j t are drawn uniformly from [N ] without replacement.Lemma C.8 (Robustness). Fix p, q ∈ [0, 1/2), and that F = {F s } s∈{0,1} (λ) ,λ∈N is a τ (λ)-local function family. Then PRF-PRC[Fp, q] is robust to any p-weakly-substitution-bounded channel.Proof. Fix λ ∈ N, and write n = n(λ), = (λ), m = m(λ), N = N (λ). Let E be a pweakly-substitution-bounded channel over {0, 1}. Given x j , e j (j ∈ [m]) drawn as in Line 6 of Algorithm 2 and a uniformly random string r ∼ Unif({0, 1} N -(n+1)m ), consider the string a := ((x 1 , F s (x 1 ) ⊕ e 1 ), . . . , (x m , F s (x m ) ⊕ e m ), r), and note that the output of Encode(1 λ , sk, ∅) given that x 1 , . . . , x m , e 1 , . . . , e m , r are sampled is ȳ := π • (a ⊕ z). Given v ∈ {0, 1} n , we let, with slight abuse of notation, E(v) ∈ {0, 1} n denote a random variable drawn from the eponymous distribution E(v) ∈ ∆({0, 1} n ). We haveu := (π -1 • E(ȳ)) ⊕ z = π -1 • E(π • (a ⊕ z)) ⊕ z =π -1 • ((π • z) ⊕ E((π • a) ⊕ (π • z))) .Since z and π are chosen uniformly at random in their respective domains and independent of a, it follows that the distribution of u is the same as the distribution ofu := π -1 • ((π • a) ⊕ v ⊕ E(v)) = a ⊕ (π -1 • (v ⊕ E(v))),where v ∼ Unif({0, 1} n ) is uniformly at random and independent of π, a. (In particular, we have used the reparametrization that setsv := (π • a) ⊕ (π • z). ) Let us unpack (π -1 • (v ⊕ E(v))) 1:(n+1)m = ((x 1 , w 1 ), . . . , (x m , w m )), where x j ∈ {0, 1} m , w j ∈ {0, 1} for j ∈ [m]. Note that the distribution of the statistic W computed in Decode(1 λ , sk, E(ȳ)) is exactly the distribution of m j=1 1{w j ⊕ e j ⊕ F s (x j ) = F s (x j ⊕ x j )}.(5) By our assumption that the family F s is τ -local, for each s ∈ {0, 1} there is someJ s ∈ [n] τ and G s : {0, 1} τ → {0, 1} so that F s (x) = G s (x Js ) for all x ∈ {0, 1} n . Define t = τ + 1 and G s : {0, 1} t → {0, 1} by G s (x) = G s (x 1 , . . . , x t-1 ) ⊕ x t .For each j ∈ [m] and fixed s ∈ {0, 1} , we have thatEQUATIONwhere the probability is taken over x j ∼ Unif({0, 1} n ), e j ∼ Ber(q), z ∼ Unif({0, 1} n ), the uniformly random permutation π, and the randomness in E (which together determine w j , x j ). We now apply Lemma C.9 to the function (z 1 , . . . , z t ) → 1{G s ((x j ) Js , 0) = G s ((z 1 , . . . , z t-1 ) ⊕ (x j ) Js , z t )}.Note that, for fixed v, E(v), since π is chosen uniformly at random (and independent of v, E(v), a), the distribution of ((x j ) Js , w j ) is exactly the distribution of y J for J ∼ J N,t , for y = v ⊕ E(v). Let us write p(y) := wt(y)/N , for y ∈ {0, 1} N . Thus, for any fixed s, we haveEQUATIONwhere the first inequality uses Lemma C.9, the fourth equality uses the fact that x j ∼ Unif({0, 1} n ) independently of v, E(v) and the definition of noise sensitivity, the second equality uses Corollary C.5, and the final inequality uses the fact that wt(v ⊕ E(v)) ≤ pN with probability 1 -negl(N ) since the marginal distribution of v is Unif({0, 1} n ) and E is p-weakly-substitution-bounded. Since we have2t √ N -t + negl(N ) ≤ 1 4 • (1 -2p) τ +1by our choice of N in (3) (which ensures that, as long as C 0 is sufficiently large N ≥ C 0 • (1 -2p) -4 log(n) , and in particular that N -t ≥ 16t(1 -2p) -τ -1 as long as the security parameter λ is sufficiently large) , it follows from Eqs. ( 6) and (7) that for each j ∈ [m], for sufficiently large λ,EQUATIONFinally, 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 j ∈ [m], define Γ j = (x j , e j , w j , x j ). Let P Γ1,...,Γm denote the joint law of (Γ 1 , . . . , Γ m ), and P Γi|Γ-i denote the conditional law of Γ i conditioned on Γ -i . For any distinct i, j ∈ [m], we have thatEQUATIONS := {π -1 ((a -1)(n + 1) + b) : a ∈ [m]\{i}, b ∈ [n + 1]}, the distribution of Γ i = (x i , e i , w i , x i) is given as follows:x i ∼ Unif({0, 1} n ), e i ∼ Ber(q), and (w i , x i ) is distributed (independently of x i , e i ) as a tuple of n + 1 distinct elements of v ⊕ E(v) which are not indexed by coordinates in S. Moreover, changing the value of x j , e j , and {π -1 ((j -1)(n + 1) + b) : b ∈ [n + 1]} changes only n + 1 elements of S, so by Lemma C.10 with k = n + 1 and the data processing inequality for total variation distance, changes the conditional distribution of (w i , x i ) by at most (n+1) 2 N -m(n+1) .Thus j∈[m]\{i} I j→i (Γ 1:m ) ≤ m(n+1) 2 N -m(n+1) ≤ 1/2 and i∈[m]\{j} I j→i (Γ 1:m ) ≤ m(n+1) 2 N -m(n+1) ≤ 1/2 since we have chosen N = 3m(n + 1) 2 in (3). It then follows from Theorem F.3 that for any δ > 0, with probability 1 -δ over the draw of Γ 1:m ,W = m j=1 1{w j ⊕ e j ⊕ F s (x j ) = F s (x j ⊕ x j )} ≥ m j=1Pr(w j ⊕ e j ⊕ F s (x j ) = F s (x j ⊕ x j )) -4m ln(2/δ).(9) Choosing δ = 2 exp(-ln 2 (m)) ≤ negl(m) ≤ negl(λ), and combining Eqs. (8) and (9) and the choice of m in (3), we see that as long as the constant C 0 in (3) is sufficiently large,Pr W ≥ m 2 + ln(m) √ m ≥ Pr W ≥ m 2 + m • (1 -2q)(1 -2p) τ +1 /4 -ln(m) √ 4m ≥ 1 -δ.(In particular, we have used that our choice of m ensures that m• (1 -2q)(1 -2p) τ +1 /4 ≥ 3 ln(m) √ m.) Since Decode(1 λ , sk, y) outputs ∅ exactly when W ≥ m 2 + log(m)√ m, we have established robustness, as desired.Lemma C.9. Fix N, k ∈ N and let y ∈ {0, 1} N be given with wt(y) = k. Fix t ∈ N, and let f : {0, 1} t → {0, 1} be a given function. ThenE J∼J N,t [f (y J )] -E x∼Ber(k/N ) t [f (x)] ≤ 2t √ N -t .Proof. It suffices to upper bound the total variation distance between the distribution of y J and the distribution of x ∼ Ber(k/N ) t . By symmetry, this total variation distance is the total variation distance between Bin(t, k/N ) and Hyp(N, k, t), where Hyp denotes the hypergeometric distribution (so that, in particular, W ∼ Hyp(N, k, t) satisfiesPr(W = w) = ( k w )( N -k t-w ) ( N t )). By [RS23, Theorem 1] (restated in Lemma G.2), this total variation distance is bounded above by 2t √ N -t .replaced with the string ỹ0 defined by ỹ0 π(i) := y 0 i , i ∈ [n], and the sample y 1 in Line 16 is replaced with the string ỹ1 defined by ỹ1i := π(y 1 σ(i) ), i ∈ [m].The distribution of the sets S 0 , S 1 ⊂ [n] under this modified procedure is exactly the distribution of π(S 0 ), π(S 1 ) when S 0 , S 1 are drawn according to the original procedure. Thus, the probability of observing z under the original execution of PerturbDifference is the same as the probability of observing z under this modified execution of PerturbDifference.It follows from the two previous paragraphs that each string in [n] m has equal probability of being output by PerturbDifference(n, m, y 0 ), under y 0 ∼ Unif([n] m ), as desired.Lemma D.3 (Undetectability). Let PRC Sub = (KeyGen Sub , Encode Sub , Decode Sub ) be a PRC for substitutions. Then the PRC PRC Idx [PRC Sub ] in Algorithm 1 is undetectable.Proof. Fix λ ∈ N, and let us write q := q(λ), n := n(λ). Consider any ψ :[q] → [n] which satisfies |ψ -1 (j)| = q/n for each j ∈ [n].Given a string y 0 ∈ {0, 1} n , let E ψ (y 0 ) ∈ [q] n denote the random variable which is the output of the following procedure: given y 0 , let y ← PerturbDifference(n, m, y 0 ), then sample z ∈ [q] m as on Line 8 of Algorithm 1 (using ψ), and output the resulting string z.Claim D.4. For any fixed ψ as above, the distribution of E ψ (y 0 ), for y 0 ∼ Unif({0, 1} n ), is uniform on [q] m . Proof. By Lemma D.2, the distribution of y ← PerturbDifference(n, m, y 0 ) is uniform on [n] m . Since |ψ -1 (j)| = q/n for each j ∈ [n], it follows that the distribution of the output string z is uniform on [q] m . Now consider any probabilistic polynomial-time adversary Adv, and suppose thatPr (sk,ψ)←KeyGen(1 λ ) Adv Encode(1 λ ,(sk,ψ),•) (1 λ ) = 1 -Pr U Adv U (1 λ ) = 1 = ν(λ)for some function ν : N → R ≥0 . We construct an adversary Adv for the substitution PRC PRC Sub , as follows: Adv first generates ψ : [q] → [n] conditioned on |ψ -1 (j)| = q/n for each j ∈ [n]. Adv then simulates Adv, where each time Adv calls its oracle O(m) for some message m, Adv performs the following. It calls y 0 ← O (m) (using its oracle O which is either a random oracle or Encode Sub (1 λ , sk, m)), then applies y ← PerturbDifference(n, m, y 0 ), samples z j ∼ Unif({a : ψ(a) = y j }) for each j ∈ [m], and then uses z as the simulated output for O(m). By definition of Encode in Algorithm 1, the adversary Adv faithfully simulates the execution of Adv Encode(1 λ ,sk,m) when the oracle O (•) for Adv is Encode Sub (1 λ , sk, •). When the oracle O for Adv is a random oracle U (i.e., which outputs a uniformly random string y 0 ∼ Unif({0, 1} n )), then Claim D.4 ensures that the adversary Adv generates a uniformly random string in [q] m . Thus, we have thatPr sk←KeyGen Sub (1 λ ) (Adv ) Encode Sub (1 λ ,sk,•) (1 λ ) = 1 -Pr U (Adv ) U (1 λ ) = 1 = ν(λ),and since PRC Sub is undetectable, we have ν(λ) = negl(λ), meaning that which implies that PRC Idx [PRC Sub ] is undetectable.Next, we will establish several lemmas in the aim of showing robustness of PRC Idx [PRC Sub , ρ]. 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 is a sufficiently large constant C D.5 ≥ 1 so that the following holds. Fix positive integers n, m with m = n • ln(2) and ∈ (0, 1) so that n ≥ C D.5 ln 2 (1/ )/ 2 . For z ∈ [n] m , write D(z) ∈ {0, 1} n to be the string D(z) i := 1{i ∈ Unique(z)}. Then Pry 0 ∼Unif({0,1} n ) z←PerturbDifference(n,m,y 0 ) D Ham (y 0 , D(z)) ≥ n ≤ 1 -negl(n).Proof. Given y 0 , let S 0 = {i ∈ [n] : y 0 i = 1} be defined as in Line 15 of PerturbDifference. By a Chernoff bound, for any δ ∈ (0, 1), PrEQUATIONNow consider y 1 ∼ Unif([n] m ) and S 1 = Unique(y 1 ) as in Lines 15 and 16 of PerturbDifference.By our choice of m, n and Lemma D.6 with q = n, y 1 is typical with probability1 -negl(m) ≥ 1 -negl(n), which implies that |S 1 | -n 2 ≤ 2 √ m ln(m) + 1.Combining this fact with (10) and choosing δ = 2 exp(-ln 2 (n)) ≤ negl(n) gives that Pry 0 ∼Unif({0,1} n ),y 1 ∼Unif([n] m ) |S 0 | -|S 1 | ≥ n ≤ Pr y 0 ∼Unif({0,1} n ),y 1 ∼Unif([n] m ) |S 0 | -|S 1 | ≥ 2 √ m ln(m) + 1 + √ n ln(n) ≤ negl(n),where we have used that n ≥ 3 Definition D.1 (Typical string). Fix q, m ∈ N. A string z ∈ [q] m is defined to be typical if the following inequalities hold:√ n ln(n) + 1 ≥ 2 √ m ln(m) + 1 + √ n ln(n)q • (1 -exp(-m/q)) -2 √ m ln m ≤ |Unique(z)| ≤ q • (1 -exp(-m/q)) + 2 √ m ln m.Lemma D.6. Suppose that q ≥ √ m/ ln(m). With probability 1 -negl(m), a uniformly random string z ∼ Unif([q] m ) is typical.Proof. Consider a string z ∈ [q] m , and defineF 1 (z) := |Unique ≥1 (z)| = q a=1 1{|{i ∈ [m] : z i = a}| ≥ 1}.Note that F 1 satisfies the bounded differences property with constants c i = 1, for each i ∈ [m]. Note also thatE z∼Unif([q] m ) [F 1 (z)] = q • 1 - j-1 k=0 m k • q -k • (1 -1/q) m-k = q •   m k=j m k • q -k • (1 -1/q) m-k   .We have that E[F 1 (z)] = q • (1 -(1 -1/q) m ), and using the bounds exp(-1/q) ≥ 1 -1/q ≥ exp(-1/q -1/q 2 ) for q ≥ 1, we conclude thatq • (1 -exp(-m/q)) ≤ E[F 1 (z)] ≤ q • (1 -exp(-m/q -m/q 2 )) ≤ q • (1 -exp(-m/q)) + m/q.By Theorem F.1, for any δ ∈ (0, 1), we have that with probability 1 -δ over z ∼ Unif([q] m ),|E[F 1 (z)] -F 1 (z)| ≤ m ln(2/δ).Choose δ = 2 exp(-ln 2 (m)) (so that δ ≤ negl(m)), and note that our assumption that q ≥ √ m/ ln m gives that m/q ≤ m ln(2/δ). Combining the two displays above gives that with probability 1 -negl(m) over z ∼ Unif([q] m ), we haveq • (1 -exp(-m/q)) -2 √ m ln m ≤ F 1 (z) ≤ q • (1 -exp(-m/q)) + 2 √ m ln m.Given integers n < q so that q/n ∈ N, let P ptn n,q denote the uniform distribution over mappings ψ : [q] → [n] conditioned on the event that |ψ -1 (j)| = q/n for each j ∈ [n]. For sets S, T ⊂ Ω, define ∆(S, T ) := (S\T ) ∪ (T \S).Lemma D.7. There is a constant C D.7 > 0 so that the following holds. Consider n, ρ, q ∈ N satisfying q/ρ = n, let Z 1 , Z 2 ⊂ [q] be given, and writeZ := Z 1 ∩ Z 2 . Define Z := |Z|, Z 1 := |Z 1 |, Z 2 := |Z 2 |,and suppose that 0 ≤ ≤ p ≤ 1/10 are given so thatEQUATIONThenPr ψ∼P ptn n,q |∆(ψ(Z 1 ), ψ(Z 2 ))| ≥ n • 1 2 - p 5 + 23 ≤ negl(n).Proof. The fact that 2/ ≤ ρ and max{Z 1 /n, Z 2 /n} ≤ 2 implies that max{Z 1 /ρ, Z 2 /ρ} ≤ n.1 := exp(-Z 1 /n), ζ 2 := exp(-Z 2 /n) so that ζ 1 ∈ [(1 -)/2, 1/2 + ] and ζ 2 ∈ [(1 -)/4, 1].Note that the mapping ψ : [q] → [n] is specified by the random variablesψ -1 (1), ψ -1 (2), . . . , ψ -1 (n) ⊂ [q]. Let us define F (ψ) := |∆(ψ(Z 1 ), ψ(Z 2 ))| = n i=1 1{i ∈ ∆(ψ(Z 1 ), ψ(Z 2 ))} = n i=1 G(ψ -1 (i); Z 1 , Z 2 ),whereG(T ; Z 1 , Z 2 ) ∈ {0, 1} (for some T ⊂ [q]) is defined to be equal to 1 if and only if either (a)T ∩ Z 1 = ∅ but T ∩ Z 2 = ∅ or (b) T ∩ Z 2 = ∅ but T ∩ Z 1 = ∅.Step 1: Bounding the expectation of F . Fix any i ∈ [n], and note that ψ -1 (i) ⊂ [q] is a uniformly random subset of size ρ. Note thatEQUATIONBy Lemma D.9, we have PrEQUATIONandEQUATIONwhere we have used the fact that, conditioned on ψ -1 (i) ∩ Z 2 = ∅, ψ -1 (i) is distributed as a uniformly random subset of [q]\Z 2 , which has size q -Z 2 . Moreover, the third inequality above uses the upper bound Z 2 /ρ ≤ n and the lower bound Z ≥ pn in (11), the fourth inequality uses the upper bound Z 1 /n ≤ 2 from (11), and the remaining inequalities simplify and use the fact that , p ∈ (0, 1/10) and 8/ρ ≤ .Using Eqs. ( 12) to ( 14) together with a symmetrical argument to bound Pr(ψ -1 (i)∩Z 2 = ∅, ψ -1 (i)∩ Z 1 = ∅),10 we see that, for each i ∈ [n],E ψ∼P ptn n,q [G(ψ -1 (i); Z 1 , Z 2 )] ≤ζ 2 • ((1 -ζ 1 ) -pζ 1 + 10 ) + ζ 1 • ((1 -ζ 2 ) -pζ 2 + 10 ) ≤ζ 1 + ζ 2 -2ζ 1 ζ 2 (1 + p) + 20 ≤ 1 2 + + ζ 2 -(1 -)ζ 2 • (1 + p) + 20 = 1 2 + + ζ 2 -ζ 2 (1 -) • p + 20 ≤ 1 2 - p 5 + 22 ,where the second inequality uses that ζ 1 , ζ 2 ≤ 1, the third inequality uses thatζ 1 ∈ [(1-)/2, 1/2+ ],and the final inequality uses thatEQUATION)Step 2: Concentration of F to its expectation. Consider any subset H ⊂ [n] of size H 0 := |H| satisfying 4ρH 0 ≤ n, and define F H (ψ) := i∈H G(ψ -1 (i); Z 1 , Z 2 ). Note that F H satisfies the bounded differences property with respect to the random variables ψ -1 (i), i ∈ H, with constants c i = 1 for each i ∈ H. For any distinct i, j ∈ H, we haveEQUATIONwhere we use ψ -1 | H\{i,j} to denote the collection of tuples (k, ψ -1 (k)) for k ∈ H\{i, j}. In ( 16), the probability is over ψ -1 (i), whose conditional distribution is that of a uniformly random subset of [q]\(ψ -1 (j) ∪ (ψ -1 (H\{i, j}))) of size ρ. The second inequality above uses Lemma D.9, and the second-to-last inequality uses the fact that q -H 0 ρ + 1 > q -H 0 ρ ≥ q/2, since 2H 0 ρ ≤ q by assumption, and the final inequality uses that q ≥ 4ρ 2 H 0 , by assumption.The above chain of inequalities (17) guarantees that I j→i (ψ -1 | H ) ≤ 1/(2H 0 ) for all i, j ∈ H with i = j. By Theorem F.3, it follows that for any δ ∈ (0, 1), PrEQUATION)Write H := C1 ln 2 n 2 , for a sufficiently large constant C 1 to be specified below. Note that 4ρ(H +1) ≤ n as long as n ≥ 8C1ρ ln 2 n 2 , which in turn, since ρ ≤ n 1/4 , holds when n ≥ C/ 3 for a sufficiently large constant C (chosen as a function of C 1 ). Let H 1 , . . . , H n/H denote a partition of [n] for which |H j | ∈ {H, H + 1}. Since 4ρ(H + 1) ≤ n, we may apply (18) to each H j and use a union bound, which yieldsEQUATION) Choosing δ = 2 exp(-ln 2 (n)) ≤ negl(n) gives that n 4 ln(2/δ)/ √ H ≤ 2n ln(n)/ √ H ≤ n,as long as the constant C 1 is chosen sufficiently large. Combining Eqs. ( 15) and ( 19) yields that with probability 1 -negl(n) over the draw of ψ ∼ P ptn n,q , F (ψ) ≤ n • 1 2 -p 5 + 23 , which yields the claimed bound.We are ready to show robustness of our PRC PRC Idx [PRC Sub ] to edit-bounded channels (Definition 2.4). Lemma D.8 (Robustness). There are some constants C D.8 , C rob ≥ 1 so that the following holds. Consider any ρ > 1 and security parameter λ ∈ N satisfying n(λ) ≥ C D.8 ρ 4 , and p 0 ∈ (C D.8 /ρ, 1/(10C rob )) and any (1 -C rob p 0 )-edit-bounded channel E. Then for any PRC PRC Sub which is robust to (1/2 -p 0 )-substitution-bounded channels, the PRC PRC Idx [PRC Sub , ρ] in Algorithm 1 is robust to E.Proof of Lemma D.8. Fix λ ∈ N, and write n := n(λ), q := q(λ), m := m(λ), so that p 0 > C D.8 /ρ ≥ 1/ρ. Fix any z ∈ [q] m which is typical (per Definition D.1), and consider any z ∈ [q] m which can be obtained form z via a total of at most (1 -C rob • p 0 ) • m substitutions, insertions, and deletions (which has probability 1 over z ∼ E(z) since E is (1 -C rob p 0 )-edit-bounded. Write Z := Unique(z) ∩ Unique(z ), i.e., Z denotes those entries of z which are preserved in z . Since z is typical and m/q ≤ m/(nρ) ≤ 1/ρ, we have that|Unique(z)| ≥ q • (1 -exp(-m/q)) -2 √ m ln m (20) ≥ q • (m/q -(m/q) 2 ) -2 √ m ln m ≥ m • (1 -1/ρ) -2 √ m ln m,where the second inequality uses the fact that exp(-x)≤ 1 -x + x 2 for x ∈ [0, 1]. Since the requirements n ≥ C D.8 ρ 4 and m = ln(2) • n ensure that that 2 √ m ln(m) ≤ m/ρ (as long as C D.8 is large enough), we have that |Unique(z)| ≥ m • (1 -2/ρ). Note also that it is immediate that |Unique(z)| ≤ m.Step 1: Using Lemma D.7. Since z is obtained from z via at most 1 -C rob p 0 insertions, deletions, and substitutions, we have|Z| ≥ |Unique(z)| -m • (1 -C rob p 0 ) ≥ m • (C rob p 0 -2/ρ).We also have that |Unique(z )| ≤ 2m. We now apply Lemma D.7 withZ 1 = Unique(z), Z 2 = Unique(z ), = p 0 , p = C rob -2 2 • p 0 .We must verify that the preconditions (11) are satisfied: first, we check that, as long asC D.8 ≥ 8, 8 = 8 p 0 < 8ρ C D.8 ≤ ρ ≤ n 1/4 ,where the final inequality follows from our choice of n ≥ ρ 4 . Next, we have|Unique(z)| ∈ [m • (1 -2/ρ), m] ⊂ [(ln(2) -) • n, (ln(2) + ) • n],where we have used that m = ln(2) • n and the fact that 2/ρ < p 0 = and n = np 0 ≥ 1. Similarly, we haveEQUATION)as long as C D.8 is chosen sufficiently large. Thus, all constraints of Lemma D.7 are satisfied. Given ψ : [q] → [n] and z ∈ [q] , define D ψ (z) ∈ {0, 1} n to be the vector defined byD ψ (z) i := 1{i ∈ Unique(ψ(z))}.Then Lemma D.7 gives that PrEQUATION)As long as C rob ≥ 300, we have1 2 - p 5 + 23 ≤ 1 2 - C rob -2 10 • p 0 + 23p 0 ≤ 1 2 -5p 0 .Step 2: Averaging over z. Let us consider the following "idealized" variant of Encode(1 λ , (sk, ψ), m), which we denote by Encode (1 λ , ψ) (as the output of the below procedure does not depend on sk or m):1. Sample y ∼ Unif([n] m ). 2. For each j ∈ [m], choose z j ∼ Unif({z : ψ(z) = y j }), so that z j ∈ [q].3. return z = (z 1 , . . . , z m ).For any fixed z ∈ [q] m , note that Pr(Encode (1 λ , ψ) = z) = q -m , and in particular does not depend on ψ: this holds since each element z j of z is drawn independently from the distribution which first draws y j ∼ Unif([n]) and then draws z j ∼ Unif({z :ψ(z) = y j }); since |ψ -1 (a)| = q/n for each a ∈ [n], this distribution is simply Unif([q]). Let Q denote the joint distribution of (y, ψ, z, z ), where y ∼ Unif([n] m ), ψ ∼ P ptn n,q , z is generated from y, ψ as in the above procedure Encode (1 λ , ψ), and z ∼ E(z). For any z 0 ∈ [q] m , it follows that the conditional distribution (under Q) of ψ given z = z 0 is P ptn n,q . Since ψ and z are conditionally independent given z, we have furthermore that for any z 0 , z 0 ∈ [q] m , the conditional distribution (under Q) of ψ given z = z 0 , z = z 0 is P ptn n,q . Thus, by ( 22), if z 0 is typical and z 0 can be obtained from z 0 with at most (1 -C rob p 0 ) • m subsitutions, insertions, and deletions, thenPr Q D Ham (D ψ (z), D ψ (z )) ≥ n • 1 2 -5p 0 | z = z 0 , z = z 0 ≤ negl(n).Since z is typical with probability 1 -negl(n) under Q (by Lemma D.6) and and z can be obtained from z using at most (1 -C rob p 0 ) • m substitutions, insertions, and deletions with probability 1 under Q, it follows that in factEQUATION)Step 3: using pseudorandomness. Let Q denote the joint distribution of (y, ψ, z, z ) where y is distributed as the random variable y defined in Line 7 of Algorithm 1, ψ ∼ P ptn n,q , z is distributed as the random variable z defined in Line 8 of Algorithm 1 given the value of ψ and y (i.e., z j ∼ Unif({a : ψ(a) = y j })), and z ∼ E(z). Using the fact a sample from E(•) may be produced by a probabilistic polynomial-time algorithm together with Lemmas D.2 and D.3, we have thatEQUATIONIn more detail, to 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 y 0 ← Encode Sub (1 λ , sk, m) from a uniformly random string y 0 ∼ Unif({0, 1} n ), as follows: we first generate y ← PerturbDifference(n, m, y 0 ) (as in Line 7 of Algorithm 1, then sample ψ ∼ P ptn n,q , then sample z ∈ [q] m by z j ∼ Unif({a : ψ(a) = y j }) for j ∈ [m], then sample z ∼ E(z), and finally evaluate D Ham (D ψ (z), D ψ (z )). In the event that y 0 ← Encode Sub (1 λ , sk, m), then the resulting distribution of (y, ψ, z, z ) is Q, and in the event that y 0 ∼ Unif({0, 1} n ), Lemma D.2 gives that the induced distribution over y is Unif([n] m ) and thus the resulting distribution of (y, ψ, z, z ) is Q. Thus we would get a contradiction to Lemma D.3.Step 4: Wrapping up. We have from Eqs. ( 23) and ( 24) thatEQUATION)By our construction of the distribution Q, D ψ (z) = y with probability 1 under Q. Moreover, we have thatEQUATIONwhere Ēψ : {0, 1} n → {0, 1} n denotes the (random) channel which, given y 0 ∈ {0, 1} n , first applies the procedure in Lines 7 and 8 of Algorithm 1 to generate z ∈ [q] m from y 0 , and then outputs D ψ (z ) for z ∼ E(z). For future reference we let this distribution over (y 0 , z) where sk ∼ KeyGen Sub (1 λ ), y 0 ← Encode Sub (1 λ , sk, m) be denoted by R. The first equality in the display above uses that the output of Decode(1 λ , (sk, ψ), z ) is given by Decode Sub (1 λ , sk, D ψ (z )). The second equality uses the definition of Encode(1 λ , (sk, ψ), m) in Algorithm 1. Finally, the inequality follows since the PRC PRC Sub is robust to (1/2-p 0 )-substitution bounded channels together with Lemma G.1 and the fact that with probability 1 -negl(λ) over the draw of ψ ∼ P ptn n,q , sk ∼ KeyGen Sub (1 λ ), y 0 ← Encode Sub (1 λ , sk, m), and z ∼ Ēψ (y 0 ), we have D Ham (z , y 0 ) ≤ (1/2 -p 0 ) • n. This fact follows from the following observations:• By Lemma D.5 and undetectability of PRC Sub , for any ψ, with probability 1 -negl(n)negl(λ) ≥ 1 -negl(λ) over (y 0 , z) ∼ R, we have D Ham (y 0 , D ψ (z)) ≤ p 0 n. (In particular, Lemma D.5 ensures that D Ham (y 0 , D ψ (z)) ≤ p 0 n when y 0 ∼ Unif({0, 1}) n and then z is generated from y 0 as in Lines 7 and 8 of Algorithm 1, and undetectability of PRC Sub ensures that this also holds when instead y 0 ∼ Encode Sub (1 λ , sk, m).) Here we have also used the fact that ψ(z) is the output string y of PerturbDifference(n(λ), m(λ), y 0 ) (defined in Line 7), together with the fact that n ≥ C D.5 ln 2 (1/ )/ 2 by ( 21), as long as the constant C D.8 is chosen sufficiently large.• By (25) together with the fact that the distribution of (ψ, z, z ) where ψ ∼ P ptn n,q , z ∼ R, and z ∼ E(z) is exactly the marginal distribution of (ψ, z, z ) ∼ Q, we have that D Ham (D ψ (z), D ψ (z )) ≤ 1 2 -3p 0 with probability 1 -negl(n) ≥ 1 -negl(λ). • Combining the two points above, we see that with probability 1 -negl(λ) over sk ∼ KeyGen Sub (1 λ ), y 0 ∼ Encode Sub (1 λ , sk, m), ψ ∼ P ptn n,q , z ∼ Ēψ (y 0 ), D Ham (y 0 , z ) ≤ (1/2 -p 0 ) • n, as desired.Summarizing, we have established (26), which yields the desired robustness guarantee.Remark D.2 (Removing computational efficiency of channel). Though the proof of Lemma D.8 uses the fact that (per Definition 2.4), the channel E 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 Sub is in fact (1/2 -p 0 )-weakly substitution bounded (per Definition C.2), then the proof of Lemma D.8 can be modified as follows to remove the assumption that E is computationally efficient: instead of showing that with probability 1 -negl(λ) over the draw of y 0 ← Encode Sub (1 λ , sk, m) and z ∼ Ēψ (y 0 ), we have D Ham (z , y 0 ) ≤ (1/2 -p 0 ) • n and using Lemma G.1, we would show that D Ham (z , y 0 ) ≤ (1/2 -p 0 ) • n with probability 1 -negl(λ) when instead y 0 ← Unif({0, 1} n ), which would imply that Ēψ is (1/2 -p 0 )-weakly robust. This latter argument avoids us to avoid needing to reason about the distribution of y 0 ← Encode Sub (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, ρ ∈ N and a subset Z ⊂ [N ] with Z := |Z|, and suppose Z ≤ N -ρ. Let T ⊂ [N ] be a uniformly random subset of size ρ. ThenPr(Z ∩ T = ∅) = 1 - Z N • • • 1 - Z N -ρ + 1 ∈ exp - ρZ N -ρ - ρZ 2 (N -ρ) 2 , exp - ρZ N .Proof. We may choose T by selecting its elements without replacement from [N ]. After i elements of T (not intersecting Z) have been chosen, the i + 1th element of T is distributed uniformly over a set of size N -i, of which Z elements belong to Z. This establishes the equality. To see the following containment, we use the fact that exp(-x) ≥ 1 -x ≥ exp(-x -x 2 ) for all x ∈ [0, 1].E Watermarks from PRCs over larger alphabets E.1 Overview of the algorithm and guaranteeIn 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 to 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 we are given a zero-bit pseudorandom code, PRC, with block length n(λ) over an alphabet Σ PRC (λ), with |Σ PRC (λ)| ≥ n(λ), 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 a family of language models (Model(λ)) λ∈N over alphabet (Σ(λ)) λ∈N with |Σ(λ)| ≥ |Σ PRC (λ)|, we construct a watermarking scheme W[PRC, Model] (Algorithm 3), as the following tuple of algorithms (Setup, Wat, Detect):• Setup(1 λ ) produces a pair sk Wat = (sk, φ) as the secret key of W. Here sk is a secret key generated from PRC.KeyGen(λ), and φ : Σ(λ) → Σ PRC (λ) is chosen uniformly at random, which can be interpreted as a hash function. • Wat(1 λ , (sk, φ)) generates a sequence of tokens t 1 , t 2 , . . . in blocks of length n(λ), in the following manner: for each block of length n(λ), we sample a codeword x ← PRC.Encode(1 λ , sk) (Line 13), and at each position i, we consider the pushforward distribution pi := φ • Model(t i = • | t 1:i-1 ) ∈ ∆(Σ PRC (λ))of the next token under the hash function φ (Line 15 of the subroutine EmbedChar). If pi puts enough mass on the corresponding token of the codeword x (denoted by x j in Algorithm 3), then we let the output token of Wat at position i be a uniformly random token which hashes to x j (Lines 16 and 21). Otherwise, we sample the output token of Wat at position i in a 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 x is drawn from a 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 a sequence t = t 1: ∈ Σ(λ) of (potentially watermarked) text. It searches through all contiguous substrings of t, denoted t i:j and checks whether (φ(t i ), . . . , φ(t j )) decodes to ∅ under PRC.Decode. If so, it returns True (and otherwise False).In the below theorem, we suppose that PRC is a zero-bit PRC with block length n(λ) over alphabet Σ PRC (λ), satisfying |Σ PRC (λ)| ≥ n(λ). Furthermore, we suppose that (Model(λ)) λ∈N is a family of language models defined over alphabet Σ(λ). Theorem E.1 (Watermarking from PRCs). Suppose that p, α ∈ (0, 1) are given, that PRC, Model(λ) are as described above and satisfy |Σ(λ)| ≥ ( 8 α |Σ PRC (λ)|) 2/α , and that PRC satisfies robustness to any (1 -α 8 + 3p α )-edit-bounded channel. Then the watermarking scheme W[PRC, Model] (Algorithm 3) is sound, undetectable, and β λ ( )-substring robust to any p-edit-bounded channel, where β λ ( ) := 8n(λ) + 6α .Theorem E.1 shows that for any constant α, we can detect the watermark as long as the entropy rate of the model's text is at least Ω(α) and as long as the fraction of errors (adversarial deletions/insertions) introduced to the watermarked text is at most O(α 2 ). This latter statement follows since there are PRCs robust to (1 -α 8 + 3p α )-edit-bounded channels for p = O(α 2 ). In turn, the alphabet Σ(λ) of the language model needs to have size roughly |Σ PRC (λ)| 2/α , which is a polynomial in |Σ PRC (λ) as long as α is a constant. By combining Theorems 3.2, 4.1 and E.1 we can show our main theorem, which guarantees substringrobust watermarking schemes for edit-bounded channels under the existence of local weak PRFs (Assumption 3.1). To simplify notation, given constants α, q > 0 together with a function family F consisting of binary-valued functions on {0, 1} n(λ) , let us defineEQUATIONwhere C 0 , C rob ≥ 1 are the constants from Theorem 4.1. In words, W comp [F, q, α] chains together the PRCs in Algorithms 1 and 2 and the watermarking scheme in Algorithm 3. Theorem E.2 (Main theorem). There are absolute constants c, C 1 , C 2 > 0 so that the following holds. Fix any α > 0. Suppose there exists a function family F, consisting of binary-valued functions on {0, 1} n(λ) , which is a log n(λ)-local weak PRF for some noise level q ∈ [0, 1/2), per Assumption 3.1. Then for any language model family Model(λ) over alphabets Σ(λ), the watermarking schemeEQUATION)) is sound, undetectable, and β λ ( )-substring robust to any cα 2 -edit-bounded channel, as long as:β λ ( ) := 6α + 8 • n(λ) C1 log 1 α , |Σ(λ)| ≥ n(λ) C2 1 α log 1 α .Notice that the exponent of n(λ) in the -independent term of β λ ( ) depends on α, 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) we can construct a polynomially-more efficient watermarking scheme W = (Setup , Wat , Detect ) as follows. The algorithms Setup , Wat , Detect , given a security parameter λ, call the corresponding Setup, Wat, Detect algorithms with security parameter λ α , for some α < 1. Since any function which is negl(λ α ) is also negl(λ) and an algorithm running in time poly(λ) is also poly(λ α ), the new scheme W is sound, undetectable, and substring robust if W is. Moreover, its various parameters (e.g., |Σ(λ)|) 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 λ α as opposed to λ) is weaker than that of W, though only by a polynomial.Indeed, the approach of [CG24] implicity suffers from the same n(λ) O(log 1/α) dependence in their substring-robustness function β( ), though it is not explicitly stated as such since they essentially already scale down the security parameter. In particular, the sparsity parameter t in [CG24, Lemmas4 & 5] is required to be O log n log 1 1 2 -p(where p < 1/2 denotes the rate of substitutions for the purpose of evaluating robustness; one can think of 1 2 -p as being roughly comparable to α 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 t . To formally reason about polynomial-sized differences in the parameters, we would need to make fine-grained average case hardness assumptions, a direction we do not pursue in the present work.Fix a security parameter λ ∈ 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 an output x of PRC.Encode and changes some of the tokens to produce its output t. (Technically, we view it as a channel over Σ PRC by applying the hash function φ to the output t of Wat.) Our goal is to show that for a codeword x ∈ Σ n PRC , Wat makes at most (1 -Ω(α)) • n substitutions if the empirical entropy of the generated text derived from x (i.e., the output of the channel) is at least Ω(α • n • log |Σ|). In such a case, we say that the "empirical entropy rate" of the generated text is Ω(α).The key technical difference between our watermarking procedure and that of [CG24] is the introduction of the hash function φ. Let us first see what goes wrong without such a φ, i.e., if Σ = Σ PRC and φ is the identity map. Suppose that for each i,Model(t i = • | t 1:i-1 ) is uniform over a fixed subset Σ ⊂ Σ of size |Σ | = |Σ| α .Then with high probability the output of Model will have empirical entropy rate Ω(α). However, a codeword x produced by PRC will only have the property that a roughly |Σ| α-1 fraction of its tokens belong to Σ . Thus, the procedure in Algorithm 3 will only be able to maintain roughly a |Σ| α-1 fraction of tokens of x (i.e., the if statement on Line 16 will only succeed with probability |Σ| α-1 ), and thus the error rate of the corresponding substitution channel will be roughly 1 -|Σ| α-1 = 1 -o(1), since |Σ| ≥ n. This error rate is too large, since our pseudorandom codes (even over large alphabets) can only correct a 1 -p fraction of errors, for any constant p > 0.To circumvent this issue, we make the following observation: if the entropy of the distributionp i := Model(t i = • | t 1:i-1 ) ∈ ∆(Σ) is at least α • ln |Σ|, then, if Σ is sufficiently large compared to Σ PRC (roughly |Σ| ≥ |Σ PRC | Ω(1/α) ), then for a uniformly random hash function φ : Σ → Σ PRC , the pushforward distribution pi = φ • p i ∈ ∆(Σ PRC ) will be "close to uniform" in the folloing sense: At least an Ω(α) fraction of the mass of pi will be on tokens σ ∈ Σ PRC for which pi (σ) ≤ 1/|Σ PRC |. This claim is proven formally in Lemma E.3, and may be seen as a consequence of concentration of measure. Since each such token σ occurs with probability roughly 1/|Σ| under a codeword output by the PRC (by undetectability), altogether such tokens account for a probability Ω(α) event under which the condition on Line 16 of Algorithm 3 will evaluate to true. Thus, at least a fraction Ω(α) of the tokens will not be substituted, as desired. This idea (together with the application of various concentration inequalities) allows us to ensure that the substitution channel induced by Wat introduces a fraction 1 -Ω(α) of errors.Next, the p-edit bounded channel referred to in the statement of Theorem E.1 introduces an additional p fraction of errors in the sequence of watermarked text. However, because an output of Wat consists of a sequence of text t consisting of multiple (say M ) consecutive codewords of PRC (each of block length n), 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 • M n errors in those same αM blocks, meaning that the effective rate of (edit) errors in those αM blocks is in fact pM n αM n = p/α. Thus, we need the PRC to in fact be robust to (1-Ω(α)+O(p/α))-edit-bounded 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.Algorithm 3 displays our watermarking procedure W[PRC, Model], given a pseudorandom code PRC over alphabet Σ PRC (λ) and a family of language models (Model(λ)) λ∈N over alphabet Σ(λ). Whenever the security parameter λ is clear from context, we drop the argument λ, i.e., write Σ PRC , Σ, Model. To aid in the analysis, given a language model Model over alphabet Σ, an alphabet Σ PRC for the PRC, and a mapping φ : Σ → Σ PRC , we define an embedding channel x → E φ Emb (x; t 1:i-1 ) for each choice of i ∈ N and t 1:i-1 ∈ Σ i-1 , which maps x ∈ Σ n PRC to some (random) string E φ Emb (x; t 1:i-1 ) ∈ Σ n (as the input and output alphabets are different, our use of the term "channel" is a slight abuse of terminology). Given x ∈ Σ n PRC and t 1:i-1 ∈ Σ i-1 , E φ Emb (x; t 1:i-1 ) performs the following for 1 ≤ j ≤ n: for p j = Model(t j+i-1 = • | t 1:j+i-2 ), it generates t j+i-1 ← EmbedChar(x j , p j , φ). (If some token t j+i-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(1 λ , (sk, φ), φ) of Algorithm 3. x ← PRC.Encode(1 λ , sk).x ∈ Σ n PRC 7:i ← 1, j ← 1.while END ∈ {t 1 , . . . , t i-1 } do 9:p i ← Model(t i = • | t 1 , . . . , t i-1 ). p i ∈ ∆(Σ)10:t i ← EmbedChar(x j , p i , φ).11:i ← i + 1, j ← j + 1.12:if j > n(λ) then 13: j ← 1, x ← PRC.Encode(1 λ , sk).14: function EmbedChar(x j , p i , φ)x j ∈ Σ PRC , p i ∈ ∆(Σ), φ : Σ → Σ PRC 15: pi ← φ • p i . pi ∈ ∆(Σ PRC ) 16: if Ber(min{1, |Σ PRC (λ)| • pi (x j )}) = 1 then 17: Set y i ← x j . y i ∈ Σ PRC 18: else 19:Sample y i ∼ q i , where q i (σ) ∝ pi (σ) - return True.return False.Next, define Q ∈ ∆(Σ) by := 1{σ∈T }•P (σ)P (T ), and let U denote the uniform distribution on Σ . For any subset S ⊂ Σ , by Hoeffding's inequality we have thatPr φ (|φ • Q(S) -U(S)| ≥ ) = Pr φ U(S) - σ∈Σ Q(σ) • 1{φ(σ) ∈ S} ≥ ≤ 2 exp - 2 2 σ∈Σ Q(σ) 2 ,where the randomness is over the draw of a uniformly random function φ : Σ → Σ PRC . Using that σ∈Σ Q(σ) 2 ≤ max σ∈Σ Q(σ) ≤ η P (T ) ≤ η•2 ln |Σ| H(P ) together with a union bound over all subsets S ⊂ Σ ,11 we see thatPr φ (d TV (U, φ • Q) ≥ ) ≤ 2 |Σ | • exp -2 2 • H(P ) η • 2 ln |Σ| ≤ 2 |Σ |--2 •H(P )•exp(H(P )/2) ln |Σ| .Under the event that d TV (U, φ • Q) ≤ , we have that σ ∈Σ min{1/|Σ |, φ • Q(σ )} ≥ 1 -, and thus, since φ • P ≥ P (T )• (φ • Q) pointwise, σ ∈Σ min{1/|Σ |, φ • P (σ )} ≥ P (T ) • (1 -).The conclusion of the lemma follows by setting = 1/2.Lemma E.4. Fix any φ : Σ → Σ PRC , and i, n ∈ N. The distribution of E φ Emb (x; t 1:i-1 ), for x ∼ Unif(Σ n PRC ), is exactly the distribution of Model(t i:i+n-1 = • | t 1:i-1 ).Proof. We use induction on j ∈ [i, i + n -1]. Fix any j ∈ [i, i + n -1] together with a sequence t 1:j-1 ∈ Σ j-1 . Let p j ∈ ∆(Σ) denote the distribution of t j ∼ E φ Emb (x; t 1:i-1 ) j-i+1 | t i:j-1 , i.e., the distribution of the j -i + 1th token of the output E φ Emb (x; t 1:i-1 ), conditioned on t i:j-1 . Let p j denote Model(t j = • | t 1:j-1 ); we wish to show that p j = p j .By Line 21 of Algorithm 3, it suffices to show that φ • p j = φ • p j . To do so, write pj := φ • p j (i.e., the quantity computed in Line 15 of Algorithm 3), and write ρ j := d TV (p j , Unif(Σ PRC )) = σ∈Σ PRC [p j (σ) -1/|Σ PRC |] + , so that ρ j = 1 -σ∈Σ PRC min{p j (σ), 1/|Σ PRC |}. By definition, for each σ ∈ Σ PRC , we haveφ • p j (σ) = 1 |Σ PRC | • min{1, |Σ PRC | • pj (σ)} + ρ j • [p j (σ) -1/|Σ PRC |] + ρ j pj (σ),as desired.Given integers a, b ∈ N with a < b, a mapping φ : Σ → Σ , and a sequence t = t 1:b ∈ Σ b , we define the spread of the sequence with respect to φ to beEQUATIONwhereP i (σ) := Model(t i = σ | t 1:i-1 ).Additionally, we define the mean entropy for the sequence t ∈ Σ b in the interval [a : b) to beH [a:b) m (t) := b-1 i=a H(Model(t i = • | t 1:i-1 )) = b-1 i=a E[H i e (t) | t 1:i-1 ].Lemma E.5. For any integers a < b, we have that EQUATIONφ S φ,[a:b) (t) ≥ α • (b -a) 4 ≥ 1 -(b -a) • 2 -1 8 α|Σ| α .Next, Lemma E.5 gives that (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 ∈ [L], let p i ∈ ∆(Σ) denote the distribution Model(t i = • | t 1 , . . . , t i-1 ), which is itself a random variable (depending on t 1 , . . . , t i-1 ). Fori ∈ [a, b -1], let Z i ∼ Ber(min{1, |Σ PRC | • (φ • p i )(x i-a+1)}) be the random variable used in the definition of E φ Emb (x a:b-1 ; t 1:a-1 ) (i.e., corresponding to Line 16 of Algorithm 3). Note that the output t a:b-1 = E φ Emb (x a:b-1 ; t 1:a-1 ) of the embedding channel satisfies φ(t i-a+1 ) = x i-a+1 ifEQUATION)For each i ∈ [a, b -1], note that E x∼Unif(Σ L PRC ) [Z i | φ, t 1:i-1 , Z 1:i-1 ] = σ∈Σ PRC 1 |Σ PRC | • min{1, |Σ PRC | • (φ • p i )(σ)},and using the definition of the spread in (28) with Σ = Σ PRC , we see thatb-1 i=a E x∼Unif(Σ L PRC ) [Z i | φ, t 1:i-1 , Z 1:i-1 ] = b-1 i=a σ∈Σ PRC min 1 |Σ PRC | , (φ • p i )(σ) = S φ,[a:b) (t).By Theorem F.2, for any fixed φ and for any δ ∈ (0, 1), with probability 1 -δ over the draw of .EQUATIONLemma E.8 (Substring robustness of the watermark). Suppose that p, α ∈ (0, 1) are given, and PRC is zero-bit PRC with block length n(λ) over alphabet Σ PRC (λ), satisfying |Σ PRC (λ)| ≥ n(λ). Suppose further that PRC is robust to any (1 -α 8 + 3p α )-edit-bounded channel. Let Model(λ) be defined over some alphabet Σ(λ) satisfying |Σ(λ)| ≥ ( 8 α |Σ PRC (λ)|) 2/α . Then the watermarking scheme W[PRC, Model] (defined in Algorithm 3) is β λ ( )-substring robust to any p-edit-bounded channel E, where β λ ( ) = 8n(λ) + 6α .Proof. For convenience we write p 1 := α/8, p 0 := 3p/α; then PRC is robust to any (1 -p 1 + p 0 )bounded channel. Let λ denote the security parameter for the given PRC. We will show that for all i, j ∈[L max (λ)], Pr (sk,φ)←Setup(1 λ ) t←Wat(1 λ ,(sk,φ)),t ←E(t) Detect(1 λ , (sk, φ), t ) = False and H [i:j) e (t) ≥ β λ (j -i) • ln |Σ(λ)| ≤ negl(λ).(37) Using (37), the fact that L max (λ) ≤ poly(λ), and a union bound over all possible choices of i, j will yield the desired claim of β λ ( )-substring robustness. To establish (37), fix λ ∈ N, and set Model = Model(λ), n = n(λ), Σ = Σ(λ), Σ PRC = Σ PRC (λ), as well as i, j ∈ [L max (λ)]; we argue in two parts:Step 1: defining channels. Let us write := j -i and let a 1 < a 2 < • • • < a h be the indices in [i, j -1] denoting the start positions of blocks for the PRC in the execution of Wat(1 λ , (sk, φ)) (in particular, a 1 , . . . , a h are simply the integers in [i, j -1] congruent to 1 (mod n)). We will write t := E(t i:j-1 ) to denote the output of the edit-bounded channel E given t i:j-1 as input. Since E is p 0 -edit-bounded, we have len(t ) ≤ := (1 + p 0 ) • . Given a mapping φ : Σ → Σ PRC , we let F φ (x, t) (given x ∈ Σ L PRC , t ∈ Σ L ) denote the joint distribution over random variables(y g,b,b ) g∈[h-1],b,b ∈[ ]: b -b∈[n(1-p0),n(1+p0)], defined as follows:• It draws t ∼ E(t i:j-1 ).• For each choice of g, b, b as above, it lets y g,b,b to be either: Next, given φ, g, b, b as above, we let E φ g,b,b be the channel which, given as input a string x ∈ Σ n PRC , performs the following operations:• First, it generates (sk, φ) ∼ Setup(1 λ ), and generates t ∼ Wat(1 λ , (sk, φ)), with the following modification: when generating output for the block starting at index a g , instead of using a fresh output of PRC.Encode(1 λ , sk), it uses the given input string x. Let x 1 , . . . , x Lmax(λ)/n(λ) ∈ Σ n PRC denote the codewords (output by PRC.Encode(1 λ , sk)) used in the Wat procedure, so that in particular x ag = x. Write x = (x 1 , . . . , x Lmax(λ)/n(λ) ).• Then, it samples from the marginal y g,b,b ∼ F φ (x, t) and outputs φ(y g,b,b ). Claim E.9. For any g ∈[h -1], b, b ∈ [ ], and φ : Σ → Σ PRC , the channel E φ g,b,b is (1 -p 1 + p 0 )- edit-bounded.Proof. It is immediate from the definition of E φ g,b,b and F φ that, almost surely, for a sample y g,b,b ∼ F φ (x, t), φ(y g,b,b ) can be obtained from x via a sequence of at most (1 -p 1 + p 0 )n substitutions, insertions, and deletions.Finally, an output of E φ g,b,b can be sampled in polynomial time: here we use that t ∼ Wat(1 λ , (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 b:b -1 ) above) can be obtained from another string (namely, x ag:ag+1-1 above) via a sequence of a given number (i.e., (1 -p 1 + p 0 )n) substitutions, insertions, and deletions.EQUATIONWe emphasize that the notation x 1 , x 2 , . . . ← PRC.Encode(1 λ , sk), t ∼ E φ Emb (x; ∅) means that PRC.Encode(1 λ , sk) is called repeatedly to produce strings x 1 , x 2 , . . . ∈ Σ n PRC , and the concatenated string x = (x 1 , x 2 , . . . , x Lmax(λ)/n(λ) ) is used as input to the embedding channel E φ Emb (x; ∅). Notice that this procedure is identical to Wat(1 λ , (sk, φ)), meaning that the distribution of the output string t is identical to the output distribution of Wat(1 λ , (sk, φ)).Proof of Claim E.10. Let A denote the event that H [ag:ag+1) e (t) ≤ 4αn ln |Σ| or D Ham (x ag:ag+1-1 , φ(t ag:ag+1-1 )) ≤ n • (1 -α/8). We have that 32•ln 4 (n) n ≤ α as long as n = n(λ) ≥ Ω(1/α), which holds for all λ greater than a sufficiently large constant depending on α (and it is sufficient for us to only consider such λ as the claimed failure probability is negl(λ)). Thus, we may apply Lemma E.7 with a = i, b = j, Σ = Σ PRC ; doing so, we see that if φ : Σ → Σ PRC is drawn uniformly and x ∼ Unif(Σ Lmax(λ) ), the event A occurs with probability1 -negl(n) -n • 2 -1 8 α|Σ| α ≥ 1 -negl(λ) -n • 2 -1 8 α|Σ| α(here we have used n ≥ λ). Since a draw of t ∼ E φ Emb (x; ∅) may be implemented in polynomial time (as we have assumed that Model is computationally efficient), and since H [ag:ag+1) e (t), D Ham (x ag:ag+1-1 , φ(t ag:ag+1-1 )) can be computed in polynomial time, it follows that A must occur with probability 1 -negl(λ) -n • 2 -1 8 α|Σ| α when x 1 , x 2 , . . . , x Lmax(λ)/n(λ) ← PRC.Encode(1 λ , sk). (Otherwise, we could violate undetectability of PRC by generating codewords x 1 , x 2 , . . . from the encoding oracle O, representing either PRC.Encode or a random oracle, and checking whether A occurs.) Finally, we remark that n• 2 -1 8 α|Σ| α ≤ negl(n) ≤ negl(λ) by our requirement that |Σ| α ≥ |Σ PRC | ≥ n.Since the channel E is p-edit-bounded, for most values of g ∈ [h -1] indexing full blocks of t i:j-1 , there must be some b, b so that t b:b -1 can be obtained from t ag:ag+1-1 by at most O(pn) insertions and deletions; this is formalized in the below claim: Claim E.11. Fix any C ≥ 1 and suppose h ≥ 2. For any string t i:j-1 ∈ Σ , there are at least(h -1) • (1 -1/C) values of g ∈ [h -1] so that there exist b, b ∈ [ ]for which t b:b -1 can be obtained from t ag:ag+1-1 by applying at most 3Cp • n substitutions, insertions, and deletions (where we have t = E(t i:j-1 )).Proof of Claim E.11. For each g ∈ [h -1] and t i:j-1 ∈ Σ , the edit-bounded channel E sends the substring t ag:ag+1-1 to some substring t bg:bg+1-1 of the (possibly random) channel output t = E(t i:j-1 ). (In particular, b g denotes the index in t of the first token in t ag:ag+1-1 which is not deleted by E, or, if all of t ag:ag+1-1 is deleted, the index in t of the first token following t ag+1-1 which is not deleted by E.) Note that b g is a function of t i:j-1 ; we omit this dependence from the notation to avoid clutter. Fix t i:j-1 and t = E(t i:j-1 ). For each g ∈ [h -1], let e g denote the number of substitutions, insertions, and deletions applied by E to obtain t bg:bg+1-1 from t ag:ag+1-1 . Since E is p-editbounded, we haveh-1 g=1 e g ≤ p ≤ p • (h + 1)n. Therefore, at least (h -1) • (1 -1/C) values of g ∈ [h -1] satisfy e g ≤ C h-1 • p(h + 1)n ≤ 3Cp • n, as desired.Step 2: using robustness of the PRC. Since each channel E φ g,b,b (for any φ :EQUATIONNote that the distribution of y ∼ E φ g,b,b (x), for x ← PRC.Encode(1 λ , sk), is the same as the marginal distribution of φ(y g,b,b ) ∼ F φ (x, t), for x 1 , x 2 , . . . ← PRC.Encode(1 λ , sk), x := (x 1 , . . . , x Lmax(λ)/n(λ) ), t ∼ E φ Emb (x; ∅). Therefore, using (39) together with a union bound over the (polynomially many) choices of g, b, b , we see thatEQUATIONFor any i ∈ [L max (λ)], by Lemma E.5 with a = i, b = i + n, there is some event B i that occurs with probability 1 -negl( ) ≥ 1 -negl(λ) under t ← Model so that, under B i ,H [i:i+n) e (t) ≤ 3 2 H [i:i+n) m (t) + 8 ln |Σ| • ln 4 (n) ≤ 3 2 n ln |Σ| + 8 ln |Σ| • ln 4 (n) ≤ 2n ln |Σ|,where the final inequality holds as long as λ is chosen sufficiently large so that n(λ) ≥ 20 ln 4 (n(λ)). By undetectability of PRC, Lemma E.4, and efficiency of Model, the event B i also holds with probability 1 -negl(λ) under the distribution of t specified in (38 A holds with probability 1 -negl(λ).Under the event A ∩ B (which occurs with probability 1 -negl(λ)), one of the following must be the case:• There are at least α • (h -1) + 2 values of g ∈ [h -1] so that D Ham (x ag:ag+1-1 , φ(t ag:ag+1-1 )) ≤ n • (1 -α/8); let this event be denoted C 1 .• It holds that H[i:j) e ≤ 8n ln |Σ| + 6α ln |Σ|; let this event be denoted C 2 .Indeed, under A ∩ B, if C 1 does not occur, then we must have that C 2 occurs since we would have:H [i:j) e =H [i:a1) e (t) + H [a h :j) e (t) + h-1 g=1 H [ag:ag+1) e (t) ≤4n ln |Σ| + ( α • (h -1) + 2) • 2n ln |Σ| + (h -1 -α • (h -1) -1) • 4αn ln |Σ| ≤8n ln |Σ| + 2α ln |Σ| + 4α ln |Σ| = 8n ln |Σ| + 6α ln |Σ|,where the first inequality uses that A ∩ B occurs and the second inequality uses the fact that (h -1)n ≤ .Note that if h < 2, under the event B, the event C 2 occurs.Next, if h ≥ 2, by Claim E.11 with C = 1/α, for any string t i:j-1 ∈ Σ , with probability 1 over t ∼ E(t i:j-1 ), there are at least (h -1) • (1 -α) values of g ∈ [h -1] so that there exist b, b ∈ [ ] for which t b:b -1 can be obtained from t ag:ag+1-1 by applying at most 3 α • pn substitutions, insertions and deletions. Note that α• (h -1) + 2 + (h -1) • (1 -α) > h -1. Thus, under the event A ∩ B ∩ C 1 , there is some value of g ∈ [h -1] and b , b ∈ [ ] so that D Ham (x ag :ag +1-1 , φ(t ag :ag +1-1 )) ≤ n • (1 -α/8) = n • (1 -p 1 )and t b :b -1 can be obtained from t ag :ag +1-1 by applying at most p 0 n = 3 α • pn substitutions, insertions and deletions. By definition of F φ (x, t), we may couple a draw of (y g,b,b ) g,b,b ∼ F φ (x, t) to this distribution over (x, t, t ) so that under the event A∩B∩C 1 that (g , b , b ) as above exist, we have yg ,b ,b = t b :b -1 .Let the event of (40) (which holds with probability 1 -negl(λ)) be denoted by D. Then, if h ≥ 2, under the event A ∩ B ∩ D ∩ C 1 , g , b , b are well-defined as above, and so we have that PRC.Decode(1 λ , sk, φ(t g ,b ,b )) =⊥, and in particular, that Detect(1 λ , (sk, φ), t ) = True. Under the event A ∩ B ∩ D ∩ C 2 ⊂ C 2 (which must occur under the event B if h < 2), we have that H 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 t ∈ Σ , for some ≤ L max (λ)/n(λ) . We wish to show that Pr (sk,φ)←Setup(1 λ ) Detect(1 λ , (sk, φ), t) =⊥ ≤ negl(λ).(41)By definition of Detect (in Algorithm 3), Detect(1 λ , (sk, φ), t) =⊥ only if there are some i, j ∈ [ ] so that PRC.Decode(sk, φ(t i:j )) =⊥. Since PRC is sound, for each fixed choice of φ and i, j, Pr sk∼PRC.KeyGen(1 λ ) (PRC.Decode(sk, φ(t i:j )) =⊥) ≤ negl(λ).Taking expectation over φ (which is drawn independently from sk) and a union bound over i, j ≤ ≤ poly(λ), we see that (41) holds.Lemma E.13 (Undetectability of the watermark). For any PRC PRC, the watermarking scheme W[PRC] (defined in Algorithm 3) is undetectable.Proof. Suppose for the sake of contradiction that there is a polynomial-time adversary Adv so thatEQUATION)Using Adv, we can construct an adversary Adv to break the undetectability of PRC, as follows. Adv has access to an oracle O which is either PRC.Encode(1 λ , sk) (where sk ← PRC.KeyGen(1 λ )) or outputs a uniformly random string of length n(λ) at each call. Adv then draws φ : Σ → Σ PRC uniformly at random and simulates Adv, simulating each call to Wat(1 λ , (sk, φ)) as in Algorithm 3 but replacing each call to PRC.Encode(1 λ , sk) (Line 13 of Algorithm 3) with a call to O. In the case that O is PRC.Encode(1 λ , sk), then this procedure is exactly Adv 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 is exactly Adv Model . 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 to be able to evaluate Model(t i = • | t 1:i-1 ) (Line 9 of Algorithm 3), which is possible in polynomial time by assumption on Model (see Appendix B).Proof of Theorem E.2. Fix α > 0 together with a function family F which is a log n(λ)-local weak PRF for noise level q ∈ [0, 1/2), and a family of language models Model(λ) as in the theorem statement. Write p 0 := α 16C rob , where C rob is the constant from Theorem 4.1. By Theorem 3.2, PRC 1 := PRF-PRC[F, 1 2 -p 0 , q] is a zero-bit binary alphabet PRC with robustness to all ( 1 2 -p 0 )-bounded substitution channels. By definition in (3), the block length N (λ) of PRC 1 satisfies: N (λ) = O n(λ) 4 log(1/p0) • n(λ) 2 ≤ n(λ) O(log(1/p0)) . Fix a set X equipped with a sigma-algebra together with a positive integer n. Let P ∈ ∆(X n ) denote a distribution (where X n is equipped with the product sigma algebra). For X = (X 1 , . . . , X n ) ∼ P , we define the influence of X j on X i to be I j→i (X) := maxx-i-j ∈X n-2 xj ,x j ∈X d TV (P (X i = • | X -i-j = x -i-j , X j = x j ), P (X i = • | X -i-j = x -i-j , X j = x j )).(43)Definition F.1. Given a random variable X distributed according to some distribution P over X n , define the Dobrushin coefficient of X to be Lemma G.1. Suppose a PRC PRC = (KeyGen, Encode, Decode) is robust to any p-substitution-bounded channel.Then for any channel E satisfying Pr sk∼KeyGen(1 λ ),x←Encode(1 λ ,sk,m),y∼E(x) (D Ham (x, y) ≤ pn) ≥ 1 -negl(n), PRC is robust to E.Proof. Let E be the channel which samples y ∼ E(x), outputs y if D Ham (y, x) ≤ pn, and otherwise outputs x. By assumption PRC is robust to E . Moreover, we can construct a joint distribution of (sk, x, y, y ) where: (a) the marginal of (sk, x, y) is as follows: sk ∼ KeyGen(1 λ ), x ← Encode(1 λ , sk, m), y ∼ E(x); (b) the marginal of (sk, x, y ) is identical except that y ∼ E (x); (c) y = y with probability 1 -negl(λ). Then the robustness criterion for E yields that PRC is robust to E.Lemma G.2 (Theorem 1 of [RS23] ). For any positive integers t, k, N with k ≤ N and t ≤ N , it holds that d TV (Bin(t, k/N ), Hyp(N, k, t)) ≤ 2t √ N -t .For completeness, we provide the proof of Lemma G.2 below.Proof of Lemma G.2. Fix t, k, N as in the lemma statement and let P = Bin(t, k/N ) ∈ ∆({0, 1, . . . , t}) and Q = Hyp(N, k, t) ∈ ∆({0, 1, . . . , t}). Also write p = k/N . Then we have P(w) = t w • p w (1 -p) t-w andEQUATIONfor each 0 ≤ w ≤ t. By Pinsker's inequality, d TV (Q, P) ≤2 t w=0 Q(w) • ln Q(w) P(w)≤2 ln t-1 j=0 1 1 -j/N =2 t-1 j=0 ln 1 1 -j/N ≤2 t-1 j=0 j N -j ≤2 t 2 N -t ,where the second inequality uses (44), and the third inequality uses the fact that ln1 1-x ≤• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA]Justification: The paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).Note also that it is typically assumed that Model takes as input a prompt; for simplicity, we absorb such a prompt in the definition of 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.)In the setting of text, transforming a token sequence to readable text (i.e., sequences of 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 as part of the adversary for which our watermarks have robustness. See also [KGW + 23, Section 7] for related discussion on "tokenization attacks".We remark that, even for the case of substitutions, the result of[CG24] (Lemma 23 & Theorem 5 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 5] allows one to establish robustness a constant fraction of adversarial substitutions. However, entirely different techniques are needed to 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.The computational efficiency of E is only needed for our watermarking schemes. It is not necessary to obtain edit-robust PRCs; see Remark D.2Here we let ψ(z) := (ψ(z1), . . . , ψ(z m(λ) )).In particular, in order for [KTHL23, Lemma 2.6] to be nonvacuous, the parameter γ must be chosen so that γ > log k, which necessitates < 1/γ < 1/ log k, and k must grow faster than a constant for the probability in [KTHL23, Lemma 2.6] to decay to 0.Notice that undetectability is not strictly speaking stronger than distortion-freeness, since an 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-freeness "for all intents and purposes".This requirement appears to be implicit in[CG24], though it is not explicitly stated therein.Note that, though our assumptions on Z1, Z2 in the lemma statement are not symmetric, to derive (14) we only need the inequalities Z2/ρ ≤ n and Z1/n ≤ 2, which hold when the roles of Z1, Z2 are flipped.Technically, we only need to do a union bound over half of all subsets, since φ • Q and U are both probability measures; hence the multiplicative factor in front is 2 |Σ |-1 as opposed to 2 |Σ | .If b or b are outside the length bounds of t , then we let t b:b -1 denote the substring t min{b,len(t )}:min{b -1,len(t )} , which may be empty.(1/x)-1 for all x ∈ [0, 1]. 
 
 Appendix:  


Decision: 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).

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. Lack of real-world evaluation of the proposed approach.
2. Lack of efficiency comparison with the current watermarking framework.
3. Lack of discussion of trade-off between undetectability and robustness.
4. Lack of scalability.
questions: questions: 1. Have the authors considered evaluating the proposed method on real-world scenario to better understand its practical applicability?
2. How does the computational efficiency of the proposed method compare to existing watermarking framework?
3. 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？
4. What are the potential limitations or challenges in scaling the proposed method up for large-scale NLP tasks?
limitations: 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.
This 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?
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

1. 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.

1. 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.

1. 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.

**Minor:**
- 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}}$.
- line 217: Output of $\widetilde{\mathrm{Adv}}^G$ is undefined
- 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.
- line 244: Should $z \in$ be $z \sim$?
questions: questions: - Are there any barriers to instantiating the proposed watermarking scheme? 
- Is edit distance robustness sometimes undesirable for watermarking?
limitations: limitations: Yes, limitations are discussed on p. 3.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The theoretical nature of the work might pose challenges in practical implementation, especially concerning the scalability and efficiency of the proposed watermarking scheme.
2. 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. 
3. 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.
questions: 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?
2. How does the proposed scheme perform against paraphrase and translation attacks?
3. 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?
[1] N. Jovanović, R. Staab, and M. Vechev, “Watermark Stealing in Large Language Models.” http://arxiv.org/abs/2402.19361
[2] Q. Wu and V. Chandrasekaran, “Bypassing LLM Watermarks with Color-Aware Substitutions.” http://arxiv.org/abs/2403.14719
[3] Z. Zhang et al., “Large Language Model Watermark Stealing With Mixed Integer Programming.” http://arxiv.org/abs/2405.19677
limitations: 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.
2. The requirement for a large alphabet size might necessitate modifications in existing tokenization schemes, posing a barrier to seamless integration.
3. 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.
4. 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.
paper_summary: paper_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$.

1. **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.
2. **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.
3. **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)$.

The 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.

However, 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.

Based 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.

**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.
strength_weakness: strength_weakness: While the paper makes substantial technical contributions, its presentation falls short.

- **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:

  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.
  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?
  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.

- **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).
> *it is necessary to strike a balance in terms of the power of adversaries to which a watermarking scheme enjoys robustness*

- **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)?

**Minor comments**
- 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}.

- The hyperref for "Line 8" in (page 6, line 248) is incorrect. It should link to Line 8 in Algorithm 2, not Algorithm 1.
questions: 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?

- 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: limitations: N/A

Comments: comment: We thank the authors for the response and decide to keep the score.
Thank you for answering my question. I would like to raise my score due to your solid theoretical analysis. However, I still believe that including empirical validation in your paper would enhance its overall strength.
Thank you! Yes, we will update the paper to address Q1 more explicitly.
Thank you for addressing my questions and being receptive. I am quite excited by the results and would be happy to see this paper accepted.

Additionally, I believe that the theoretical merits of this paper alone justify its acceptance. The proposed watermarking scheme is has negligible Type-1 error, *provably* robust in edit distance, and satisfies "undetectability", which means that the watermarked model is *computationally indistinguishable* from the original model. The fact that we can satisfy all three criteria (soundness, edit distance robustness, and undetectability) is already surprising and highly non-trivial.
Thank you for responding to my questions. I continue to advocate for acceptance, as the paper provides strong theoretical contributions, even though there are practical limitations. I recommend addressing Q1 more explicitly in the paper, as it's likely to be a concern for many in the NeurIPS community (three of the four reviewers asked about it).