Edit Distance Robust Watermarks via Indexing Pseudorandom Codes

Thank you for your positive comments. Regarding your comments on presentation: we will adjust our exposition accordingly. Regarding local weak PRFs, we do not know of a formal reduction showing that public-key cryptography implies local weak PRFs. We will adjust the discussion to add some additional background from reference [30] (Impagliazzo, 1995) on the meaning of the five worlds (which is somewhat informal, as mentioned on p.3 of Impagliazzo's paper).

Question 1: Yes, the locality requirement is incompatible with strong PRFs which give the adversary query access, since $\log(n)$-juntas can be learned in poly(n) time (See [BL97] below). Roughly speaking, the idea of this result is that for a $\log(n)$-junta $F(\cdot)$, an adversary finds x,y so that $F(x) \neq F(y)$, then queries vertices on a path in the hypercube between x and y, which yields at least 1 of the $\log(n)$ influential coordinates. It then recurses to find all influential coordinates. It can then learn $F$ by trying all possible n combinations of the $\log(n)$ influential coordinates.

[BL97] "A. Blum and P. Langley. Selection of relevant features and examples in machine learning, 1997"

Question 2: $\ell_2$ perturbations could be reasonable, though it is unclear if local PRFs can be used to achieve robustness to such perturbations. This is an interesting direction for future work.

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 your review.

Many of the weaknesses and limitations you mention relate to the lack of implementation and experiments. We want to emphasize that developing a fully practical watermarking scheme for immediate use in LLMs is not the point of this paper. Rather, the purpose is to lay the theoretical foundations for a technique to achieve edit-distance robust undetectable watermarking (for which there are not yet any practical schemes), and that additional work is needed to make our scheme fully practical.

Question 1: The computational cost of generating each next token for our watermarking scheme is linear in the alphabet size of the LLM. Note that it takes linear in alphabet size time to even generate non-watermarked output. We expect that the actual empirical (constant factor) blowup in computational cost will be quite small due to the relative simplicity of our procedure. That being said, we remark that our scheme requires a large alphabet size, which poses challenges for a direct implementation of it on existing LLMs; see the response to Question 1 of Reviewer YwkB for further details on this point.

Question 2: If the paraphrase attack produces text which is close to the original in edit distance (i.e., if it is not an overly aggressive paraphrasing), then our scheme would still detect paraphrased watermarked text. To deal with a translation attack, one could augment our detection algorithm to translate its input text into many common languages and output True if any of the resulting translations is detected as watermarked. This would overcome the translation attack assuming that translating a string x from one language to another and back leads to a string x' which is close to x in edit distance, which we expect to be a reasonable assumption.

Question 3: Thank you for pointing out the papers on watermark stealing attacks. While ruling out such attacks is beyond the scope of our paper, we are hopeful that our PRCs and watermarking schemes (as well as those of [Christ & Gunn, 2024]) are resistant to such attacks. Roughly speaking, we believe that it might be possible to show this using the relatively strong cryptographic properties of local weak PRFs (or, in the case of [Christ & Gunn, 2024], the relatively strong cryptographic properties of the noisy parity problem). Establishing such robustness to stealing attacks is an interesting direction for future work, even for the case of subsitution PRCs as in [Christ & Gunn, 2024].

Thank you for your helpful comments.

Minor questions:

• Eq. (2): Yes, dimension of $s$ should be $\ell(\lambda)$. And yes, we forgot an "=1" in the second term.
• Line 217: $\widetilde{Adv}^G$ refers to the output of the algorithm Adv (which is a 0 or 1) when, each time Adv decides to query G, it receives $(x, G(x))$ for a uniformly random $x$.
• Line 222: Thanks, we will clarify that the oracle returns just the output of the function $F_s(x) \in \{0,1\}$ (though of course Adv knows the random input $x$ as well).
• Line 244: Yes, should be $z \sim$.

Questions:

1. Using techniques from our theoretical watermarking scheme to develop a practical implementation for use with LLMs is an important direction for future work. The main limitation of our present theoretical results which may complicate a practical implementation is as follows: The alphabet size $|\Sigma(\lambda)|$ is required to grow exponentially in the inverse of the parameter $\alpha$ (see the statement of Theorem E.2). In turn, the parameter $\alpha$ is proportional to the entropy rate of the text needed to guarantee substring robustness (see Definition 2.6 and the setting of $\beta_\lambda(\ell) = O(\alpha \cdot \ell)$ in Theorem E.2). For typical LLMs, the alphabet size is likely smaller than our required value of $|\Sigma(\lambda)|$ given the entropy rates observed empirically in natural language. 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.

2. It sounds like you are asking about using watermarking for public attribution. It is indeed correct that the same "Detect" function cannot be used for both (a) detecting watermarked output robustly, and (b) as a sort of signature scheme to attribute text to a certain language model. Section 7.4 of [Christ & Gunn, 2024] proposes a solution to this dilemma by constructing watermarking schemes with "unforgeable public attribution": their scheme has an Attribution function, which is not robust and indicates when a portion of its input text is copied verbatim from the model, as well as a Detect function, which is robust and indicates when a portion of its input is edit-distance near to a string output by the model. The key point is that a "True" output of Detect should not be interpreted as attributing the text to the model.

Thank you for your review.

Question 1: Using techniques from our theoretical watermarking scheme to develop a practical implementation for use with LLMs is an important direction for future work. The main limitation of our present theoretical results which may complicate a practical implementation is as follows: The alphabet size $|\Sigma(\lambda)|$ is required to grow exponentially in the inverse of the parameter $\alpha$ (see the statement of Theorem E.2). In turn, the parameter $\alpha$ is proportional to the entropy rate of the text needed to guarantee substring robustness (see Definition 2.6 and the setting of $\beta_\lambda(\ell) = O(\alpha \cdot \ell)$ in Theorem E.2). For typical LLMs, the alphabet size is likely smaller than our required value of $|\Sigma(\lambda)|$ given the entropy rates observed empirically in natural language.

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.

Question 2: Modulo the limitations discussed in Question 1, our watermarking scheme is very efficient (and comparable to, e.g., that of [Christ & Gunn, 2024]). In particular, the computational cost of generating each next token is linear in the alphabet size of the LLM. Note that it takes linear in alphabet size time to even generate non-watermarked output.

Question 3: Yes, there is a joint tradeoff between undetectability, robustness, and blocklength of the watermark, even for substitution PRCs (i.e., Theorem 3.2), which then carries over to our edit-distance robust PRCs, as in Lemma D.8. The precise tradeoff is reflected in Equation (3) in the proof of Theorem 3.2: we show in the proof that the blocklength parameter $N(\lambda)$ to achieve a fixed undetectability guarantee must grow exponentially in $\log(1/(1-2p))$ through its dependence on $m(\lambda)$. In other words, keeping the block length fixed, taking $p \to 1/2$ will lead to a weaker undetectability guarantee. This does not manifest itself in the theorem statements since we always think of $p$ as a constant and so values of $p$ closer to $1/2$ result in a polynomially weaker undetectability guarantee for fixed blocklength, which is insignificant compared to the superpolynomial guarantee of undetectability (and we do not distinguish between different polynomials). We remark that the results of [Christ & Gunn, 2024] have essentially the same tradeoff; please see the end of Section E.1 for further discussion on this point.

Question 4: The main challenge lies in handling the tension between the fact that in many large-scale NLP tasks, the entropy rate is relatively low and the resulting alphabet size that our results require would be too large compared to the number of tokens. We believe that there are promising techniques which will be able to alleviate these limitations in future work for practical applications; see Question 1 for more details.