Bileve: Securing Text Provenance in Large Language Models Against Spoofing with Bi-level Signature

Authors: tong  zhou
xuandong  zhao
u c berkeley
xiaolin  xu
shaolei  ren
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:38:27

Abstract: Text watermarks for large language models (LLMs) have been commonly used to identify the origins of machine-generated content, which is promising for assessing liability when combating deepfake or harmful content. While existing watermarking techniques typically prioritize robustness against removal attacks, unfortunately, they are vulnerable to spoofing attacks: malicious actors can subtly alter the meanings of LLM-generated responses or even forge harmful content, potentially misattributing blame to the LLM developer. To overcome this, we introduce a bi-level signature scheme, Bileve, which embeds fine-grained signature bits for integrity checks (mitigating spoofing attacks) as well as a coarse-grained signal to trace text sources when the signature is invalid (enhancing detectability) via a novel rank-based sampling strategy. Compared to conventional watermark detectors that only output binary results, Bileve can differentiate 5 scenarios during detection, reliably tracing text provenance and regulating LLMs. The experiments conducted on OPT-1.3B and LLaMA-7B demonstrate the effectiveness of Bileve in defeating spoofing attacks with enhanced detectability.

Main paper: 
 introduction: 
 Watermarks have been envisioned as a promising method to differentiate content generated by large language models (LLMs) from human [5, 11, 23, 13, 1, 4] . It involves injecting statistical signals into the token sampling process utilizing a secret watermark key. Subsequently, the one who knows the key can verify the content's origin by assessing the presence of the predefined signal through a statistical test. Current watermarking schemes primarily focus on user-side concerns, striving to achieve robustness against watermark removal attacks (i.e., perturb the generated text to remove the watermark), thereby combatting academic dishonesty and other deceptive practices.However, a critical vulnerability remains unaddressed in watermark design: spoofing attacks directed towards model owners. In these attacks, malicious actors attempt to falsely attribute content generated by humans or other models to the targeted model, with the aim of evading accountability 1 or damaging the model's reputation. A few recent works have identified two kinds of spoofing attacks targeting the LLM watermark by exploiting either its symmetric characteristic [6, 15] or learnability [8, 10] , as detailed in Sec. 2.3. Furthermore, we propose a new spoofing attack, named semantic manipulation, Table 1 : Comparison of different watermarking methods based on four desired properties.Robust Unforgeable Tamper-evident Transparent Kirchenbauer et al. [11] ✓ ✗ ✗ ✗ Zhao et al. [23] ✓ ✗ ✗ ✗ Kuditipudi et al. [13] ✓ ✗ ✗ ✗ Liu et al. [15] ✓ ✗ ✗ ✗ Fairoze et al. [6] ✗ ✓ ✓ ✓ which enables attackers to alter the sentiment of generated content with minimal token modifications, as described in Sec. 3.2. It assumes the most constrained capabilities of attackers, where they only have access to the victim model's detector. Due to the robustness of LLM watermarks against perturbations, this attack can manipulate the originally helpful content into something harmful or offensive without compromising the detectability of the watermark, thus successfully achieving spoofing attacks.Given the serious consequences of spoofing attacks, it is highly in demand to answer the question: How to avoid an LLM being wrongly blamed? To solve this problem, we aim to design a watermark for LLM, which focuses more on the model owners' side instead of only watermarking on the users' side. To reliably identify the provenance of machine-generated content while being able to defend against the above spoofing attacks, a signature should have the following properties:• Robust: The signature remains capable of tracing the source of machine-generated text even when subjected to certain perturbations, ensuring it is not overly fragile or easily rendered ineffective. • Unforgeable: The signature is inherently resistant to being learned given the components utilized in its detection. • Tamper-evident: It should be able to check the integrity of the generated content, showing reliable tampering evidence to safeguard the interests of model owners. • Transparent: It is detectable without needing access to generation secrets or relying on a black-box API, allowing independent, reliable verification.Despite the critical importance, achieving all desired properties in a single LLM watermark remains challenging, as even state-of-the-art (SOTA) designs cannot meet them all (see Tab. 1). Indeed, designing such a watermarking scheme involves a fundamental trade-off between defending against removal attacks and spoofing attacks. Specifically, being robust to removal attacks requires that the watermark's detectability remains unaffected by certain perturbations, while anti-spoofing demands sensitivity to perturbations to verify text integrity, distinguishing harmful content from genuine model output and tampered content.To overcome the above challenges, we propose Bileve, a novel sampling strategy by embedding a bi-level signature into generated tokens. At the coarse-grained level, we utilize statistical signals across the entire text to detect the presence of the watermark, ensuring robustness against perturbations. Concurrently, at the fine-grained level, we integrate content-dependent signature bits into each token to uphold content integrity, which leverages a digital signature scheme to ensure unforgeability, as the secret key required for watermark embedding will be securely held by model owners. This scheme enables transparent detection by allowing verification with a public key instead of embedding secrets, so independent parties can authenticate without proprietary details or a black-box API, ensuring reliable detection. And the tampering evidence will show when these two level detection results are not consistent.Our contributions are threefold: 1) We uncover an advanced spoofing attack that exploits the robustness of SOTA watermarking schemes; 2) We introduce Bileve, the first watermarking scheme to simultaneously ensure robustness and unforgeability by embedding a bi-level signature through a novel rank-based sampling strategy; 3) Bileve is capable of distinguishing five distinct scenarios during the detection phase, effectively defeating spoofing attacks and serving as a promising tool to regulate LLM safety mechanism.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: contributions are summarized in introduction Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
language model basics: 
 Let  denote a language model with a vocabulary  containing 𝐾 ∶= || tokens. To generate the next token 𝑤 𝑡 ,  will take prior tokens 𝑤 1∶𝑡-1 as the input and output a vector of logits 𝑙 (𝑡) , Table 2 : Three categories of spoofing attacks (ranked by attackers' capabilities from high to low).Exploited Vulnerabilities Attackers' Capabilities [6, 15] Symmetry Know the secret key for embedding watermarks [8, 10] Learnability Get access to the victim model and query it multiple times Our attack Robustness Only get access to the victim models' detector which is transformed into a probability distribution  (𝑡) = (𝑝 (𝑡) 1 , ..., 𝑝 (𝑡) 𝐾 ) via the softmax function. Then the sampling strategy is applied to determine how the model selects 𝑤 𝑡 based on  (𝑡) . One common sampling strategy is multinomial sampling, where  randomly selects the next token from  according to the probabilities 𝑝 (𝑡) 𝑘 assigned to each token. This process is repeated iteratively to generate a sequence of tokens.Watermarks for model-generated texts are used to identify the provenance of the text, ensuring accountability in cases where generated content needs to be traced back to a specific LLM. The existing watermark schemes rely on the specialized decoding algorithm to embed statistical signals into generated contents, then enabling watermark detection via computing p-value [1, 11, 23, 4, 13] . For instance, for generating the next token, one approach dynamically partitions the vocabulary into green and red lists based on its previous few tokens and a watermark key [11] , then increasing the logits of green tokens to enhance their chance of being selected. During detection, the watermark detection key is used to count the number of green tokens in the text, with the calculated z-statistic indicating the existence of the watermark. Moreover, Zhao et al. [23] simplify the scheme proposed in [11] by fixing the green-red list for each token, demonstrating that their watermark is twice as robust to edit as [11] . Furthermore, unlike modifying logits, a distortion-free watermark is proposed to preserve the original text distribution [13] . It leverages robust sequence alignment to align watermarked text to a watermark key sequence in the sampling phase, e.g., using exponential minimum sampling.However, these watermarking schemes only enable detection by individuals possessing the key, which doesn't facilitate transparent regulation. On one hand, making the key public is susceptible to attacks [15] . On the other hand, maintaining detection privately (e.g., via APIs) compromises reliability, as it functions as a black box, allowing the model owner to manipulate detection results.Spoofing attacks can fall into three categories based on the capability of attackers, and each of them exploits different vulnerabilities in SOTA watermarks, as summarized in Tab. 2. First, due to the watermark embedding and detection process sharing the same secret key (i.e., symmetric schemes), the semi-honest detector knowing the secret key can embed the watermark to any content. Such a vulnerability has been discussed in [6, 15] , where they design asymmetric watermarking schemes so that detection does not rely on the key used for embedding. Specifically, [6] proposes embedding watermarks using digital signature algorithms, ensuring that only model owners possess the secret key for watermark embedding while providing detectors with access to the public key for detection. However, it is easily broken once the message tokens are perturbed. Besides, it suggests using error-correcting encoding to improve robustness, which unfortunately would increase the risk of spoofing attacks and should not be adopted. Moreover, [15] employs two distinct neural networks for watermark embedding and detection, leveraging an asymmetric scheme for public detection.However, [15] is based on [11] and thus can be learned as studied in [8] , which is the second kind of spoofing attacks. In particular, [8] demonstrated that, by querying the victim model and collecting its watermarked samples, attackers can fine-tune an adversary model utilizing a sampling-based watermark distillation technique to learn the watermark (detailed in Appendix A). The fine-tuned adversary model can respond to any malicious requests, with the response containing the watermark of the victim model. Recently, an independent work also proposed attacks by exploiting watermark robustness [18] . Beyond techniques such as randomly inserting toxic tokens or modifying tokens to alter sentence accuracy, our attack leverages a reward model to guide targeted semantic manipulation. More importantly, while they suggest compromising watermark robustness to mitigate spoofing attacks, our work demonstrates how to achieve effective mitigation without sacrificing robustness.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: in discussion section Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
threat model: 
 Attackers' Objective. Given text generated by the victim LLM, attackers seek to alter the semantic meaning of the text with minimal changes, transitioning it from something helpful or neutral to harmful or offensive. Owing to the robustness of the existing watermarks, the watermark detector can still identify the presence of the watermark in the modified content. Consequently, the altered content erroneously attributes its origin to the victim model, potentially damaging the model's reputation.Attackers' Capability. Contrary to existing spoofing attacks, our approach assumes the strictest attacker capabilities, where the adversary only gains access to the watermark detector, as outlined in Tab. 2. These attackers lack knowledge of the secret key and are not required to query the victim LLM multiple times to acquire watermarked samples for training other adversary models. They may utilize public language models to enhance the efficiency of their attacks.We identify the dilemma of being robust and unforgeable. In particular, being robust indicates that the watermark should be preserved after perturbation, thus we can exploit this characteristic to design a novel spoofing attack. Specifically, attackers can query the victim model with harmless prompts, and then use basic word replacement techniques to change its semantic meaning to be toxic or harmful. Due to the robustness properties of LLM watermarks, the detectability will not be compromised if the portion of word replacement is low. Consequently, a detector cannot discern whether the content originated from the victim model or was manipulated by malicious actors. This highlights the limitation of current watermarks for auditing LLMs. By exploiting the above observation, we propose a novel spoofing attack. Let 𝑤 orig denote the original response of victim models, and 𝑤 att represent its manipulated version. The goal is to generate 𝑤 att that maximizes the change in sentiment while minimizing the Levenshtein distance between the original and manipulated responses. The problem can be formulated as follows:max 𝑤 att Δ𝑅 = 𝑅(𝑤 orig ) -𝑅(𝑤 att ), s. t. LD(𝑤 orig , 𝑤 att ) ≤ 𝜖𝑇 (1)Here, Δ𝑅 represents the sentiment change, defined as the difference between the reward scores (denoted by 𝑅(⋅)) of the original and manipulated responses obtained by the reward model. 2 A lower score of the reward model indicates less alignment with human feedback, such as a toxic response. The Levenshtein distance, denoted by LD(𝑡 1 , 𝑡 2 ), measures the minimum number of word edits required to transform text 𝑡 1 into text 𝑡 2 . 𝑇 is the length of 𝑤 orig and 𝜖 is the word edit budget. A trade-off exists in choosing 𝜖, wherein a larger value affords greater flexibility in manipulating the semantic meaning of 𝑤 orig , while a smaller value better preserves the detectability of the watermarks. To strike a balance, we opt for a larger 𝜖 to maximize semantic alteration and introduce a tuning factor 𝛼 ∈ (0, 1) to adjust 𝜖 in case the detectability is broken. Furthermore, instead of manually replacing the words in 𝑤 orig , attackers can simply leverage a powerful and accessible LLM (denoted as 𝑄) to execute such attacks efficiently. To enhance the generation quality while meeting the constraint, attackers can apply in-context learning by providing a few task demonstrations. We summarize the algorithm with more details of task demonstrations in Appendix B.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [NA] Justification: does not include theoretical resultsGuidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
proposed defense: 
 With the above attack, in conjunction with other existing spoofing attacks, we can recognize the vulnerability of current watermark schemes. This underscores the importance of designing secure schemes to defend against spoofing attacks and achieve all properties listed in Tab. We first extract the message-signature pair to conduct an integrity check using the public key. A statistical test is performed if necessary.% : urgent ⋮ ℎ(𝑤 # ) = 1 ℎ(𝑤 $ ) = 0 ℎ(𝑤 % ) = 0 ⋮ Message digestTo enable secure and reliable text attribution, we first examine the vulnerabilities exploited by attackers in conducting spoofing attacks, including symmetry, learnability, and robustness, as summarized in Tab. 2. In particular, previous methods embed the statistical signal into the generated texts [11, 23, 13, 1] , so as to identify the existence of a watermark during detection. Such statistical signal is consistent for every text, thus enabling the adversary model to learn the watermark rule can forge it. Therefore, to defend against spoofing attacks, we seek the opposite characteristics, i.e., asymmetric, unlearnable, and perturbation-sensitive, in the solution.We envision the digital signature as a promising solution as in [6] , where the scheme is defined as SLS = (𝖪𝖾𝗒𝖦𝖾𝗇, 𝖲𝗂𝗀𝗇, 𝖤𝗆𝖻𝖾𝖽, 𝖵𝖾𝗋𝗂𝖿 𝗒), where:• 𝖪𝖾𝗒𝖦𝖾𝗇 → (𝗌𝗄, 𝗉𝗄) outputs a public key pair (𝗌𝗄, 𝗉𝗄), where 𝗉𝗄 is public while 𝗌𝗄 is held by the owner of model .• 𝖲𝗂𝗀𝗇 𝗌𝗄 (𝐦) → 𝝈 uses 𝗌𝗄 to sign the digest of the message 𝐦 := 𝑤 1∶𝑚 via the hash function 𝐻 (e.g., MD5) and obtain the signature 𝝈 = 𝗌𝗄 × 𝐻(𝐦).• 𝖤𝗆𝖻𝖾𝖽(𝝈) → 𝑤 embeds signature into subsequent tokens following 𝑤 𝑚 , and outputs 𝑤 incorporating the message-signature pair (𝐦, 𝝈).• 𝖵𝖾𝗋𝗂𝖿 𝗒 𝗉𝗄 (𝑤) → {𝚝𝚛𝚞𝚎, 𝚏𝚊𝚕𝚜𝚎} extracts 𝝈 = 𝗌𝗄 × 𝐻(𝐦) from 𝑤 and verifies it using the public key 𝗉𝗄. If verification succeeds, it outputs 𝚝𝚛𝚞𝚎; otherwise, it outputs 𝚏𝚊𝚕𝚜𝚎.Unlike the digital signature methods, which typically attach signatures as metadata [20, 19] , SLS assigns the first few tokens as the message and uses the following tokens to carry the signatures. Specifically, the key idea of 𝖤𝗆𝖻𝖾𝖽 is to embed signature bits into tokens, ensuring that the block hashes to the corresponding signature bit (e.g., employing rejection sampling until the hash ℎ result matches the next signature bit). This method keeps the message-signature pair self-contained within the generated text, enabling verification solely based on the generated content. Such a scheme satisfies the above characteristics since a digital signature uses the secret key for embedding and the public key for verification, ensuring asymmetry. The signature is content-dependent, so the signature for different generations is also different. Also, it is dependent on the secret key, which cannot be inferred by attackers, making it impossible to learn. Its ability to check integrity is proved in cryptography, where even a single modification will cause verification failure.However, two problems arise in this scheme: 1) digital signature is too fragile, which hinders its applicability to the real world for attributing the text. In particular, even a single token insertion or deletion would lead to a verification failure, and the trace of the target LLM will easily disappear.2) In cases where token replacement occurs and the replaced token hashes to the same signature bit as the original token, the signature remains unaffected. However, such replacements undermine the text's integrity without detection, which is referred to as the "signature preservation attack". Apply  to prior tokens and sample 𝑤 𝑡 with Ξ 𝑡 involved (Eq. 2) 4: end for 5: Apply a hash function on 𝑤 1∶𝑚 to get the digest of message 6: Use 𝗌𝗄 to sign the digest to obtain the signature and convert it into a bit string 𝐵 7: for 𝑡 = 𝑚 + 1, ⋯ , 𝑚 + 𝑏 + 1 doApply  to prior tokens to get a score vector 𝑊 𝑅𝐴 (𝑡) over  9:{𝑤 𝑡,1 , ⋯ , 𝑤 𝑡,𝐾 } ← Sorted tokens based on their logits in descending order 10:for 𝑘 = 1 to 𝐾 do 11: if ℎ(𝑤 𝑡,𝑘 ) = 𝐵 𝑡-𝑚 then 12:𝑤 𝑡 ← 𝑤 𝑡,𝑘 ; break 13: end for 14: end forWe introduce Bileve, a bi-level signature scheme that improves upon the SLS in terms of detectability and security. At the fine-grained level, Bileve embeds the message-signature pair to verify content integrity, while the coarse-grained level incorporates a robust signal to boost detectability. Following [1, 13] , we design the signal as a random watermark key sequence 𝜉 ∼ Unif([0, 1] 𝐾 ). We propose a ranking-based sampling strategy to embed 𝜉 into generated tokens, where the objective is to let the randomness affect the sampling outcome but the selected token is also expected to have a large probability of preserving the generation quality.Generation. We propose a weighted rank addition (𝑊 𝑅𝐴) score for each token in  to rank the candidate tokens instead of ranking them based on probability like conventional methods [14] . In particular, given a probability vector 𝑝 of 𝑤 𝑡 and a pre-defined random sequence 𝜉 (both of dimension 𝐾), 𝑊 𝑅𝐴 is calculated by (we omit 𝑡 for simplicity):EQUATIONwhere R(𝑝 𝑘 ) and R(𝜉 𝑘 ) are the rank scores for 𝑘-th token based on 𝑝 and 𝜉, respectively, determined by their order when values are sorted in ascending order (e.g., if 𝑝 𝑘 is the smallest one in 𝑝, then R(𝑝 𝑘 ) is 0). Besides, by adjusting the hyperparameter 𝛾 (where 𝛾 < 1), we enhance the impact of higher probabilities while still allowing for randomness to affect the outcome. During generation, we rank token candidates by favoring larger 𝑊 𝑅𝐴 ( 1 in Fig. 1 ). When sampling tokens carrying signature bits, we incorporate an additional signature bit matching step by selecting the first candidate token that, through the hash function ℎ, maps to the predetermined signature bit ( 2 in Fig. 1 ).Besides, we enhance the diversity of generation by using the shift-generate algorithm [13] (detained in Appendix C). This involves pre-generating 𝑛 𝜉 sequences and iteratively decoding tokens using sequences Ξ = (𝜉 𝑑 , 𝜉 𝑑+1 , ..., 𝜉 𝑛 , 𝜉 0 , ..., 𝜉 𝑑-1 ), where 𝑑 ∈ [0, 𝑛) shifts with each new response generation. Such a shifting strategy ensures that  can generate diverse tokens even if their prefix tokens are the same, and iterative decoding ensures that generated tokens 𝑤 align well with Ξ. The rank-based sampling strategy with shift-generate is summarized in Alg. 1. Thus, although a signature preservation attack may maintain alignment with the signature, it is less likely to simultaneously align well with Ξ sequences, thereby effectively mitigating such attacks.Statistical Test. Following [13] , we define the alignment cost asEQUATIONIf the text 𝑤 generated by , Ξ 𝑡,𝑤 𝑡 will be large due to Eq. 2, then 𝑑 will be smaller compared to human-generated text or text from other models. Thus, we test 𝑤 𝑡 with random Ξ ′ for 𝑁 times, and got p-value as 1 𝑁+1 (1 +∑ 𝑁 𝑖=1 1{𝑑(𝑤, Ξ ′ ) ≤ 𝑑(𝑤, Ξ)})for the null hypothesis that 𝑤 is not generated by . Hence, a small p-value (e.g., <0.01 when 𝑁=100) indicates 𝑤 is high likely from . For checking the signature preservation attack, we run a local alignment, i.e., splitting 𝑤 into several segments, if the p-value for a certain segment is larger than the rest, then it indicates the token replacement happens in that segment with their associated signature bits unchanged. When signature validation fails, we run a global alignment test, with Eq. 2 enhanced by Levenshtein distance to be robust against insertion and deletion, as detailed in Appendix D.Detection. With detectors getting access to 𝗉𝗄, ℎ, and Ξ, they will apply two primary methods during detection: extracting the message-signature pair for integrity verification using the public key 𝗉𝗄, and conducting statistical tests. The verification process is described as follows: Step 1: Check the signature at a fine-grained level ( 1 in Fig. 1 ). If the signature is valid and model owners raise no doubts, verification is completed, and the text attribution is assigned to the target LLM (Case 1). Step 2: If the signature is valid but the model owner identifies suspicious content (e.g., potentially offensive material not in line with their model's safety mechanisms), they can conduct a local alignment test ( 2 in Fig. 1 ). Abnormal results suggest signature replacement (Case 2), while normal results suggest that there is a high chance that the safety mechanisms of target LLM require improvement (Case 3).Step 3: If the signature is invalid, examine the coarse-grained signal through a global alignment test ( 2 in Fig. 1 ). A small p-value serves as tampering evidence that the content originates from the targeted LLM but has been altered (Case 4). Otherwise, it suggests the text originates from a source other than the targeted LLM (Case 5). Overall, Bileve can differentiate 5 cases with the bi-level signature, reliably tracing the text provenance with mitigating spoofing attacks.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: include in experiment setup Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.  
experiments: 
 In this section, we evaluate our approach from multiple perspectives, including detectability, generation quality, and security. Specifically, given that our method is asymmetric and unlearnable due to its cryptographic design, our focus is solely on assessing its efficacy in defending against spoofing attacks that exploit robustness, i.e., semantic manipulation. Additionally, we demonstrate the effectiveness of the bi-level signature in tackling the challenges encountered by the single-level signature, i.e., fragility and signature preservation attacks.Datasets and Models. We conduct experiments using two publicly available LLMs: OPT-1.3B [22] and LLaMA-7B [21] . Our evaluation employs two datasets: 1) OpenGen [12] for text completion task, consisting of 3K two-sentence samples from WikiText-103 [17] , with the first sentence as the prompt and the second as the human completion; 2) LFQA [12] for long-form question answering task, consisting of 3K question-answer pairs, where we use questions as prompt and answers as human-written answers in experiments.To measure detectability, we use metrics, including the True Positive Rate (TPR), False Positive Rate (FPR), and F-1 score. We use LLaMA-13B as the oracle language model to compute perplexity (PPL) for evaluating the generation quality, which is defined as the exponentiated average negative log-likelihood of a sequence.To assess the effectiveness of Bileve, we conduct a comparative analysis with two stateof-the-art schemes. The first scheme, Unigram [23] , stands out for its robustness against removal attacks. The second scheme, as proposed in [6] , employs cryptographic techniques to defeat spoofing attacks, denoted as the SLS in this work.Settings. For Unigram, we set watermark strength to 2.0 and a green list ratio to 0.5, where the threshold of z-score for detection is 6.0 and set FPR as 0.01 during detection. The nucleus sampling [9] is employed to introduce randomness for Unigram and SLS. Also, for SLS, we generate 300 tokens with the first 44 tokens as the message and the rest 256 tokens as the signature bit (the signature length for Bileve is 256-bit). This also applies to Bileve, except we use rank-based sampling with the 𝛾 set to 0.001. We set 𝑛 for shift-generate to 300 and 𝑁=100 for detection. All experiments are conducted on NVIDIA A100 GPUs. As demonstrated in Tab. 3, we evaluate the detectability of each scheme under two scenarios: no edits to the generated text, and editing involving 10% of the tokens (through random deletion, addition, and replacement). In the unedited scenario, both SLS and Bileve surpass Unigram in FPR and F1 scores. This superiority is due to the use of digital signatures in SLS and Bileve, which ensure integrity by making the signature 𝝈 content-dependent on 𝐦 and signed by 𝗌𝗄. This setup prevents texts not produced by the target LLM from passing verification with 𝗉𝗄.Furthermore, Bileve excels when 10% of tokens are edited, maintaining a high F1 score (0.999) and achieving an FPR of 0. This contrasts sharply with SLS, whose F1 score becomes inapplicable due to both TPR and FPR dropping to 0, illustrating the fragility of the SLS scheme. In contrast, Bileve can leverage coarse-grained level signal to test global alignment with Ξ. The resulting p-value < 0.01 indicates the source of perturbed text is from the target LLM. The failure of verification caused by disrupted message-signature pair along with the small p-value serve as the tampering evidence for texts from target LLM. Furthermore, alignment cost analysis in Bileve (Fig. 2 ) shows machinegenerated texts aligning with the key sequence Ξ incur lower costs than human-written texts, aiding in provenance tracing and distinguishing Case 5.Human Unigram SLS Bileve Human Unig We measure the perplexity of texts generated by various schemes, with results of OPT-1.3B shown in Fig. 3 and LLaMA shown in Appendix E. The perplexity of Unigram is close to that of human text, which serves as our baseline. In contrast, the perplexities of SLS and Bileve are relatively higher. This increase is attributed to the need for embedding digital signature bits into tokens precisely. Such embedding may lead to the selection of tokens that, while matching the signature bits, are not the optimal choice, thus increasing perplexity. Notably, Bileve uses rank-based sampling with shift-generate instead of SLS's nucleus sampling, achieving a 23.08% perplexity reduction on OpenGen using OPT-1.3B, as tokens with higher 𝑊 𝑅𝐴 scores better preserve textual coherence.While our method exhibits higher perplexity than Unigram, human evaluation reveals no noticeable degradation in generation quality, with examples available in Appendix F. This discrepancy may result from Unigram's lower perplexity due to repetitive text generation, as recent studies indicate that model perplexity often favors repetition [6] . To further assess quality, we conduct zero-shot evaluations using GPT-4 Turbo, following the approach in [6] , where higher scores represent better quality. On the question-answering task with OPT-1.3B, Bileve and Unigram achieve scores of 16±6.52 and 16±9.62, respectively. Against Signature Preservation Attack The signature preservation attack occurs only when attackers replace tokens in a way that satisfies Line 11 in Alg. 1. This is challenging, as attackers have to find tokens also maintain contextual coherence at the same time. We demonstrate that, although rare, when attackers meet these conditions, Bileve can detect such attacks through local alignment testing. We split 𝑤 into 5 segments and perform the signature preservation attack on the third one as a case study. The local alignment test returns a p-value for each segment, as shown in Fig. 4 . Using the p-values of the rest segments as baselines, segment 3 has an abnormally high p-value, indicating misalignment with key sequence Ξ. Moreover, we further explore the alignment cost and show the best 10 alignment scores among 300 shifts, with the lowest cost as the deciding factor. The results in Fig. 4 show the best alignment cost of segment 3 after the attack has increased from -2.5 to -1.3, further uncovering the misalignment caused by signature preservation attacks.Here, we conduct a semantic manipulation attack on Unigram, SLS, and Bileve. Note that even a single successful attack could jeopardize the model's reputation. As shown in Tab. 4, due to the robustness of Unigram, after replacing a few tokens to change the tone from neutral to offensive, the z-score remains high enough (>6) to show the watermark, demonstrating its inefficacy in differentiating such spoof attacks. In the case of SLS, semantic manipulation perturbs embedded signature bits, leading to verification failure. If the message tokens are perturbed, the verification fails as well due to the unmatched results (see Fig. 1 (b) ). In contrast, although signature bits in Bileve are also perturbed by attacks, the small p-value of the statistical test indicates the text is generated by the target LLM (with tampering since digital signature verification fails). 
discussion: 
 Limitation and Potential Optimization While the effectiveness and security are well demonstrated, the efficiency and generation quality of Bileve can be improved by adopting the following strategies. Firstly, it is unnecessary to apply Bileve for prompts characterized by low entropy, such as those involving manual token replacements. Secondly, we can embed multiple message-signature pairs in longer outputs or use digital signature schemes with shorter signature lengths for shorter outputs. Thirdly, similar to [16] , we can adopt an adaptive embedding strategy, i.e., signature embedding into tokens can be skipped when their entropy levels are low, thus maintaining the natural flow of the text. Lastly, we can embed a single signature bit across a block of tokens, rather than into individual tokens, which is promising to improve text perplexity by reducing disruptions in token coherence [6] .Reliably tracing text provenance is crucial for trust and accountability in LLM usage. Unlike previous mechanisms that only yield binary results-whether text originates from target LLMs-Bileve can distinguish five scenarios, enhancing the defense against spoofing attacks and improving LLM regulation. Bileve effectively differentiates between jailbreaking (bypassing safety mechanisms to generate harmful content [24, 3] ) and spoofing (altering benign outputs to create harmful content [2] ), which can damage an AI's reputation. By embedding bi-level signatures, Bileve not only preserves content integrity but also detects tampering, clearly identifying genuine security breaches from fraudulent imitations. Thus, Bileve advances the societal goals of ensuring safe, transparent, and accountable LLM regulation. 
conclusion: 
 In this work, we propose a bi-level signature scheme, named Bileve, which integrates robust statistical signals with fine-grained signature bits, ensuring that the watermark remains detectable through perturbations while simultaneously verifying content integrity. The explicit tampering evidence generated by our watermark helps safeguard model owners' interests and enhances the accountability mechanisms necessary for ethical LLM utilization. As demonstrated in experiments, Bileve not only maintains generation quality but also supports robust, tamper-evident signatures that can discern between genuine and manipulated content. Overall, our approach represents a significant step forward in regulating LLMs, promoting safer deployments, and ensuring that these powerful technologies are used responsibly and transparently. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: in experiment setting Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: in discussion section Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • 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: do not release data or models and add warning 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. 
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: [Yes]  
 
 Appendix: A recent work has identified a spoofing attack against LLM watermarks [8] . In particular, the process involves querying the victim model for watermarked samples, followed by fine-tuning an adversary model 𝐴 parameterized by 𝜃 on these samples using a sampling-based watermark distillation technique, as described in Alg. 2, where the fine-tuning can be achieved by minimizing the loss function:EQUATIONOnce fine-tuned, the adversary model is capable of responding to malicious requests. The response 𝑤 spoof , characterized by a low watermark detection p-value, may be erroneously attributed to the victim model. end if 8: end while Warning: The following part in this section contains examples of offensive language due to attacks. For in-context learning, we provide task demonstrations following the below strategies: Identity Substitution Inspired by [2] , we can first query the target LLM with benign prompts, which will output a neutral response, then substitute the identity to others to create offensive content. We use ChatGPT as the target LLM as examples shown in Fig. 5 . By substituting the identity, e.g., replacing "men/humans" with "Americans" and "dogs" with "Japanese", the language can become highly offensive.Antonym Replacement Fig. 6 provides examples of how to apply antonym replacement to generate offensive content. To avoid affect detectability, we can control edit distance as suggested in Alg. 3.Another strategy is adding cursing words between sentences, where token insertion will not compromise the detectability of SOTA watermarking due to their robustness.Alg. 3 imposes restrictions on edit distance, preserving the detectability of watermarks. Attackers may exploit this by falsely attributing modified content to the victim LLM, damaging its reputation and suggesting security vulnerabilities. In contrast, our watermarking method incorporates digital signatures, ensuring the integrity of generated content. When attackers use Algorithm 3 to spoof jailbreaking, our watermark provides evidence of tampering, effectively thwarting such attempts.Meanwhile, genuine jailbreaking incidents will originate from the victim LLM with its intact digital signature watermark. Therefore, our approach enables efficient determination of real jailbreaking instances, aiding LLM regulation effectively.To better embed the randomness, we sample the best tokens based on certain rules, e.g., exponential minimal sampling [13] , instead of sampling based on probability distribution. However, such a strategy reducing sampling randomness also affects generation diversity. The shift-generate algorithm is introduced in [13] to solve this problem. We refer readers to Algorithm 4 in [13] for more details. We also include it in Fig 7,  where 𝜏 functions the same as 𝑑 in our work.Figure 7 : Shift-generate Algorithm from [13] In particular, this method randomly shifts the watermark key sequence before passing it to the generate function. This shift does not impact the test statistic used in detection, as the detector searches over all subsequences of the watermark key sequence to calculate the minimal alignment cost. There are 𝑛 possible shifts, each potentially creating a distinct text.To enhance the detectability of Bileve, we modify the alignment cost in Eq.3 to include edit distance (more details are referred to Definition 5 in [13] ) :EQUATIONwhere 𝑑 0 is defined by Eq.3. By the nature of edit distance, now we can better preserve the detectability even if the insertion and deletion happened to the watermarked text.We provide the results on LLaMA-7B in Fig. 8 , where we can observe similar comparisons with the results on OPT-1.3B. Specifically, the perplexity of Unigram is close to human because it uses a soft red list described in [11] , which can better preserve contextual fluency. Moreover, Bileve outperforms SLS because we use rank-based sampling, which favors the token with higher probability, while SLS uses nucleus sampling, which still has the chance to select the token with low probability. Also, its precise signature bits matching also compromise perplexity. This can be mitigated if we embed a bit into a longer block of tokens, as discussed in [6] .We provide generation examples of Unigram and Bileve on LFQA tasks using LLaMa-7B in Tab. 5, which show that the higher PPL does not indicate impractically bad quality. A court can order a jury as a court order. If a party asks for a jury. If a party appeals a court. If a party files a lawsuit (which must be done before a court can be held)... Tuesday at all times and Thursdays at 9:00 am. If you are qualified, you may be called for a case or cases may be filled from qualified jurors already on the list... We also provide examples in Tab. 6 to show that Unigram would generate repetitive generation, which may lead to its lower perplexity, although the perceived quality of Unigram's outputs does not differ significantly from Bileve as demonstrated in Tab. 5.Prompt Unigram Bileve The lava dome was created by volcanic eruptions in the early Miocene. A total of five large ash flows were produced along with a large rhyolite dome structure. The caldera formed when the dome collapsed about 16 million years ago.A mill eruption approximately 3 million years ago produced many fine-grained lavas, plus fly ash. Over 1,600 more fine-grained lavas were produced around 3.6 Ma. A 6.8 Ma eruption produced a voluminous eruption with numerous fine-grained lavas. The 6.8 Ma eruption also produced numerous small diorites. The most intense eruption from the 6.8 Ma eruption produced more... During the late Triassic period, Steens mountain began to rise eastward from the Cocoon Valley, and in their place, erupted a series of glacial-related geologic structures. In the early Jurassic period, lava flow-induced tectonic activity in the upper section caused Steen and its outflow area on this portion west to the Canadian National Mountains...Tesla lawyers claimed that Elon Musk's past statements about self-driving safety could be deepfakes, which is found suspicious by the court[7].For example, we use the following reward model in our experiment: https://huggingface.co/ OpenAssistant/reward-model-deberta-v3-large-v2 


Decision: This work introduces a watermarking method for LLMs that is resistant to spoofing attacks, yet can be robustly recovered. The method is based on digital signatures and improves upon the existing SLS method. Reviewers appreciated that the paper tackles the important problem of watermark spoofing in a novel way but had concerns about text generation quality and evaluation. There was a good discussion during the rebuttal period which clarified the use-case and concerns about text generation quality due to the use of perplexity as a metric. Some reviewers had remaining concerns about the robustness evaluation and presentation.

On balance, the AC thinks that the novel approach, promising results and timeliness of the work outweighs the remaining concerns related to text generation quality, robustness evaluation and presentation. The AC hence recommends that this paper be accepted. That said, the authors should include the revisions as promised in the rebuttal, provide additional context on the perplexity evaluation (and possibly alternate measures of quality like benchmark task performance) in addition to addressing reviewer concerns regarding presentation of the work.

Reviews: review: paper_summary: paper_summary: The submission proposes a spoofing attack on LLM watermarks and a new bi-level scheme meant to protect against spoofing by distinguishing five possible scenarios. The scheme is based on signature bits for integrity checks and rank-based sampling on top of a Kuditipudi-like random key sequence.
strength_weakness: strength_weakness: - Weak experimental results, bringing the practical value of the defense into question: 
  - The provided quality evaluation, despite its limitations (see below), clearly shows an order-of-magnitude increase in perplexity which strongly suggests that produced text are of impractically bad quality; there is no evaluation that would test this. This is the most important weakness in my opinion.
- Limited experimental evaluation, in ways that make it hard to evaluate the merit:
  - Text quality is measured only as PPL of Llama-13B and only on one small 1.3B model; there is no qualitative evaluation of text quality so the negative effect on text quality can't be well understood.
  - Only Unigram and SLS are considered as baselines, while self-hash and other variants of the KGW scheme are generally considered more promising, esp. from the perspective of spoofing.
  - Watermark removal is evaluated only as 10% editing attack which ruins text quality, no paraphrasing attack is evaluated.
- Bigger framing issues around Table 2 and the attack:
  - The framing of Table 2 seems inappropriate. "Knowing the secret key" is not a spoofing attack but simply an application of the watermark, this seems to be introduced as a way to suggest that symmetric schemes are flawed by design, which is not necessarily true in cases where there is no detector access. 
  - The attack is framed as a "novel advanced spoofing attack" while it is (1) in the opinion of this reviewer a direct result of scheme robustness and very limited in scope and thus hardly advanced (2) more importantly, already proposed in a different form in prior work [1] which was not cited, making this an overclaim. To elaborate on (1), for example, [7, 9] would be able to produce a detailed watermarked response to a harmful query such as "Teach me how to steal someone's identity" while there is no way to produce such a response by a few token modifications of a non-harmful response. 
   - This attack type is used as a key motivation, setting aside the true spoofing attacks from [7,9], which are much more relevant. This is evident in claims such as "anti-spoofing requires perturbation-sensitivity". Further, the robustness of Bileve to such approaches based on learnability is claimed but not substantiated.
- Poor writing: The paper is often quite hard to read and understand. On top of that there is a very large amount of typos. I advise the authors to work on improving the writing for the next version. Here is a list of some examples that I found, in hopes this helps. 
  - "Symmetric characteristic" and "learnability" in Introduction are unclear without being defined
  - Paper keywords typo: "provence"
  - L50: unforgettable 
  - L285 L325 L50: tempering / temper-evident
  - Table 2: model' 
  - L87: simply 
  - Algo1: $h$ is undefined, although $H$ (a different symbol) is defined outside in the main text 
  - L211: "associate"
  - L283: resulted 
  - L284: "the source are"
  - L284: the failure verification
  - L308: "tokens also"
  - L311: "return" 
  - L312: "the rest segments"
  - L314: "shows" 
  - L315: "t0"
  - L316: "cause" 
  - L327: "limitaition" 
  - L456: "neucles"

[1] Attacking LLM Watermarks by Exploiting Their Strengths, Pang et al. arXiv 2402.16187
questions: questions: - Can the authors provide evidence of practical text quality of Bileve texts?
- Can the authors include the missing experiments discussed above?
limitations: limitations: The authors include a discussion of limitations and societal impact in Section 6.
paper_summary: paper_summary: This paper proposes to consider spoofing attack, where an attacker wants to prove the proposition like "The person holding this watermark private key used an LLM to write this text A." where text A is constructed by the attacker. The paper proposes a defense against spoofing attacks.
strength_weakness: strength_weakness: I have doubt on the significance of spoofing attack. It is important to first clarify a potential misunderstanding. Authors may believe that a watermark in the text proves "the person holding this watermark private key used an LLM to write this text A." But that's not accurate.

However, the watermark only proves that the probability of text A being generated by a process independent of the watermark key holder is very low. It does not conclusively prove the key holder generated that specific text A.

Therefore, I believe the spoofing attack lacks real significance from the outset. If someone wants to prove they said certain things and nothing else, they can just use a traditional digital signature.

The problem is also framed as "How to avoid an LLM being wrongly blamed?" But what can we really blame an LLM for? Sure, there may be instances where a single LLM inference generates a token sequence that is interpreted as harmful by humans.

However, LLMs are probabilistic models that can potentially generate any harmful content given enough inferences. We can only blame an LLM for having a high average probability of generating harmful content, not for the existence of individual harmful inferences.

Moreover the paper appears hard to read to me. For example, "instead of ranking them based on probability like conventional methods [13]" doesn't specify what conventional methods mean in paper [13] Pre-trained language models for text generation: A survey.

Furthermore, t's unclear if the signature preservation attack requires constructing two messages with the same hash, as implied by "replaced token hashes to the same signature bit." If so, that would be extremely difficult for modern hash functions.

More importantly, the paper does not provide any rigorous theoretical guarantees that Bileve actually solves the spoofing attack issue as claimed. The key assertion is that "it is less likely to simultaneously align well with $\Xi$ sequences, thereby effectively mitigating such attacks." However, this statement is quite vague and unconvincing on its own.

What does it mean for a method to be "less likely to simultaneously align well with $\Xi$ sequences"? How much less likely is it quantitatively? Under what assumptions or conditions does this property hold? The paper does not provide clear answers to these crucial questions.
questions: questions: In the definition of "signature preservation attack", I saw that "replaced token hashes to the same signature bit". Does it mean that signature preservation attack requires constructing two messages with the same hash? If so, that would be extremely difficult for modern hash functions.
limitations: limitations: This paper is difficult to read, e.g. the reference to "conventional methods" in "[13]" is unclear.

Does not provide clear theoretical guarantees that the Bileve method effectively mitigates spoofing attacks as claimed.
paper_summary: paper_summary: The paper presents a novel approach to secure the provenance of texts generated by large language models (LLMs) through a bi-level signature scheme. This method aims to mitigate spoofing attacks—where malicious actors alter the content generated by LLMs to forge harmful content or misattribute blame—by integrating fine-grained signature bits for integrity checks and a coarse-grained signal for source tracing when signatures are invalidated.
strength_weakness: strength_weakness: 1.  While the experiments demonstrate effectiveness in specific settings with OPT-1.3B and LLaMA-7B models, the generalizability and scalability of the Bileve scheme to other models are somewhat uncertain. Authors could consider using larger or more powerful LLMs to demonstrate the effectiveness of the proposed algorithm.

2. The authors could consider using a more powerful LLM to measure the perplexity, like GPT-3/GPT-4.

3. I suggest reporting TPR scores at fixed low FPR (FPR = 10% or 1%).

4. This paper demonstrates detectability by modifying 10% of the tokens. It would be good to test with a higher rate of token modification, like 20%, 30%, to further validate the detectability.
questions: questions: Please see above.
limitations: limitations: Please see above.
paper_summary: paper_summary: The robustness of previous watermark algorithms would lead to a type of spoofing attack where attacker would modify the watermarked text to contain harmful contents while ensuring the watermark can still be detected. This paper introduce a bi-level signature scheme called bileve to mitigate spoofing attacks and enhance detectability. Bileve could recognize 5 scenarios during detection, compared to only 2 for previous methods. Using bileve, the LLM owners could verify if the source of the given texts. From experiments, the effectiveness of bileve against spoofing attack is validated.
strength_weakness: strength_weakness: 1. Although with the proposed WRA, the text quality is improved as compared to SLS, the difference between bileve and unigram is still noticable.
2. For case 4&5, if the watermarked text is inserted into a long document (copy-paste attack), then the global alignment test would not produce a small p-value while the detected text does contain watermarked text.
questions: questions: 1. what is the generation/detection complexity? The statistical test during detection seems quite time-consuming.
2. Are all 5 cases tested during evaluation? Details of how local alignment test is conducted, e.g., chunk size, can be clarified in the paper.
limitations: limitations: The paper could provide more info on the complexity of the generation and detection process.

Comments: title: Please engage in discussion
reply
comment: It is unfortunate that we received your feedback so late, which has limited our ability to address all your concerns thoroughly before the deadline. Nevertheless, we want to clarify key points to assist in your evaluation of our work.

**Generation Quality**

We include PPL as it is a common metric used to evaluate generation quality. However, we mentioned other metrics mainly because **your assertion that our method yields “impractically bad quality” based solely on PPL is incorrect.**  Our method’s perplexity is indeed higher than Unigram, but that does not directly equate to impractically bad quality (and we also discussed how to improve it in the limitation section). Therefore, by learning from recent literature, we acknowledged that additional metrics can be provided for comprehensive evaluation.  We included it in our initial rebuttal and will add it to the final version.

**Paraphrasing Attack**

As we explained in the initial rebuttal, `a semantic manipulation attack, a variant of paraphrasing attacks, is evaluated and the results are provided in Table 4.` **Our work is designed to ensure that model owners can deploy a reliable watermark that is not easily misattributed.** Evaluating paraphrasing attacks comprehensively is valuable, but **it does not alter the fundamental conclusion that our method is robust against various spoofing attacks**, since such attacks would break the watermark signature, leading to verification failures.

**Self-hash**

Our paper includes an overview of spoofing attacks in Table 2. We did not include self-hash in our comparison because it shares similar vulnerabilities with Unigram, and **has been successfully spoofed as demonstrated in the reference [9] in Table 2**. That is why we are puzzled by your claim that self-hash is promising for defeating spoofing attacks. 



---
[9] Watermark Stealing in Large Language Models, ICML 2024.
We appreciate your thoughtful review. As the rebuttal deadline approaches, we kindly ask if our responses have sufficiently addressed your concerns. Should you require further clarification, we are prepared to provide additional information.

Sincerely,

Authors
I thank the authors for their rebuttal. I maintain most of my concerns; to comment on some:
- The authors provide PPL as the metric used to measure text quality. Saying that this metric is sometimes unreliable and providing anecdotal evidence is insufficient. If the authors agree that the metric is flawed the evaluation should be repeated with a better one.
- A paraphrasing attack, as commonly studied in recent work, is significantly stronger than the proposed semantic attack. Thus this evaluation is still missing. 
- The claim that Self-hash is more robust to spoofing than Unigram comes directly from the scheme properties and can be found also in the original Unigram paper (see bottom of Sec 2). Authors failing to acknowledge this is for me a significant oversight.

I encourage the authors to remedy the above as well as improve the poor writing as promised in the next revision of the paper.
As the discussion period is about to conclude, we would appreciate it if you could review our above response and let us know if our rebuttal addresses your concerns. Thanks!
Thank you for acknowledging our rebuttal. If you have any further concerns, please let us know. We would like to address them before the discussion period ends.
Thank you for your thorough review and valuable feedback on our work. We will incorporate additional experimental results in the revised version.
Thank you for your clarification. I have raised the score to 7. If possible, please incorporate the extra experimental results into the next version of the paper.
Dear Reviewers,

The authors have provided responses to the reviews. If you have not already done so, please take a look at the responses (and other reviews) and engage in a discussion.

Thanks for your service to NeurIPS 2024.

Best, 
AC
Thank you for your reply and explanation, I will maintain my rating.
Thank you for your timely response again! We understand the misunderstanding now. 

**The spoofing attack described in our work is NOT as you proposed above or described in the summary**, i.e., `an attacker wants to prove the proposition like "The person holding this watermark private key used an LLM to write this text A." where text A is constructed by the attacker. ` 
Instead, the attack scenario is: when model owners deploy watermarks in their models, someone could forge the watermark in content that is not generated by the models or manipulate the content without removing the watermark. If the content is bad and the watermark's existence is detected, people would believe this was generated by the victim model. Then, the model owner could be blamed for not achieving safe deployment. We will clarify our threat model in the revision.

Our work aims to help LLM model owners deploy a reliable watermark that cannot be spoofed by attackers.** The application scenario would be, for example, OpenAI deploying a watermark in ChatGPT, and ensuring that when someone claims content is generated by ChatGPT, it is indeed fully generated by it and not crafted by others or modified to twist its meaning. **This is different from someone wanting to demonstrate that they used an LLM to generate the entire content.** 

**To achieve our objective, your proposed method is invalid**, i.e., `they simply use 1. watermark during generation 2. traditional digital signature to sign the generated content.` The reason is that if the model first embeds existing watermarks and attaches the signature after generation, the output from the model would be the response to the prompt and a string of meaningless signatures. Thus, users would simply discard the signature when they copy and paste the response somewhere. As a result, no one can test if the content is truly from ChatGPT due to the missing signature.

Therefore, our objective is to make the signature self-contained in the generated text. This way, if some generated text is given, OpenAI can extract the signature and verify if it is from ChatGPT. **Our work provides a reliable detection scheme for model owners, allowing them to protect their own interests by preventing spoofing attacks where attackers may mislead the attribution of bad content to the victim model.**
I still have doubt on the significance of spoofing attack. It slightly modify a watermarked content into another watermarked content, and I should expect the new content still be detected instead of not detected.

If an author want to prove to others about: 1. whether LLM is used for generating the content, 2. whether content has been modified by others, can they simply use 1. watermark during generation 2. traditional digital signature to sign the generated content? It seems watermark detection can answer first question for reliable LLM detection and traditional digital signature can answer second question.

> Ultimately, the combination of an invalid signature and good alignment with the key sequence indicates that the text originated from the target watermark but has been modified by others.

The above scheme can do the same thing. The positive detection result and invalid signature indicates that the text originated from the target watermark but has been modified by others.
Thanks for your clarification. **What you mentioned highlights a significant flaw in prior watermarking schemes**: the potential for attackers to exploit the robustness of watermarks to achieve spoofing attacks, a vulnerability newly identified in a recent work [1] pointed out by Reviewer ggNL and in our work. **This issue is exactly what our scheme aims to address.** Our proposed method can differentiate between five cases, including whether the content is originally from the target LLM or has been modified. 

In particular, in the case you mentioned, other watermark schemes would identify the text as watermarked. In contrast, our detection first verifies the validity of the signature. In this instance, the signature would be invalid due to the perturbations, so we move to the next-level detection, i.e., checking if the text aligns with the key sequence. As reported in Table 3, the alignment with the key sequence is designed to be robust to perturbations. Thus, we can still detect the presence of the watermark in the text. **Ultimately, the combination of an invalid signature and good alignment with the key sequence indicates that the text originated from the target watermark but has been modified by others.**


Thank you for your prompt response and the effort you put into reviewing our work. Please let us know if you have any further concerns. 



---
[1] Attacking LLM Watermarks by Exploiting Their Strengths, Pang et al. arXiv 2402.16187
Thanks for the detailed rebuttal.

I wish to first focus on the definition of "non-watermarked text" and "false positives". 

Support author A write an announcement of length 1000 with watermark. Then attacker B add/delete 10 words "not" to revert the meaning of the announcement. Is the changed announcement "watermarked text" or "non-watermarked text"? If watermark is detected, is it "false positive" or "true positive"?

I would consider the changed announcement as "watermarked text", as 99% of the text is the same as original watermarked text, even though semantic is changed.

Therefore, my previous comment is not `emphasizing the possibility of false positives in watermark detection`. Actually I didn't mention the word "false positive" at all and I regards the above example as "true positive".