Bileve: Securing Text Provenance in Large Language Models Against Spoofing with Bi-level Signature
Authors: Tong Zhou
Xuandong Zhao
Xiaolin Xu
Shaolei Ren
Venue: NeurIPS 2024 poster (2024)
Keywords: Large language model
Text Provenance
Spoofing attacks
Primary area: safety_in_machine_learning

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.

Bileve: Securing Text Provenance in Large Language Models Against Spoofing with Bi-level Signature
Tong Zhou
Xuandong Zhao
Northeastern University, Boston zhou. tong wwwotheasterr.ee...mm
UC Berkeley xuandongzhaobberkkeeey..ee
Xiaolin Xu
Shaolei Ren UC Riverside shaolei@ucr. edu
Northeastern University, Boston x wwwhootheesterr..ccm
Abstract
Text watermarks for large language models (LLMs) have been commonly used to identify the origins of muacine--gnerraie content, which is promising for sessing 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- --n-greeetted responses potentially leading to the wrongful attribution of blame to the LLM developer. To overcome this, we introduce bi-level signature scheme, Bileve, which embeds fine-grained signature bits for integrity checks (mitigating spoofing attacks) as well coarse-grainee signal to trace text sources when the signature is invalid (enhancing detectability) via novel rank-based sampling strategy. Compared to conventional watermark detectors that only output binary results, Bileve can differ- entiate 5 scenarios during detection, reliably tracing text provenance and regulating L.LMs. The experiments conducted on OPT-1.3B and LLLMA-7B demonstrate the effectiveness of Bileve in defeating spoofing attacks with enhanced detectability. Code available at https: / wwwp...oo/ooggghooooo..oo http//oonnnono///ooooooe wttphhoowoooo/oleeeeeeeeee f cial.
forge harmful content,
Introduction
Watermarks have been envisioned as a promising method to differentiate content generated by large language models (LLMs) from human 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 the predefined signal through 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, 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! 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 new spoofing attack, named semantic manipulation,
'Tesla lawyers claimed that Elon Musk's past statements about self-driving safety could be deepfakes, which found suspicious the court [7].
38th Conference on Neural Information Processing Systems (NeurTPS 2024).

---

Table 1: Comparison of different watermarking methods based on four desired properties.
Methods
Robust Unforgeable
Tamper-evident
Transparent
Kirchenbauer et al. [11]
X
X
Zhao al. [23]
X
X
Kuditipudi et al. [13]
X
Liu et al. [15]
X
Fairoze et al. [6]
which enables attackers 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 the victim model's 's detector. Due 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, aim to design 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 pachine--eneratte content while being able defend against the above spoofing attacks, a signature should have the following properties:
The signature remains capable of tracing the source of subjected to certain perturbations, ensuring it is not overly fragile or easily rendered ineffective.
Robust:
text even when
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: is detectable without needing access to generation secrets or relying on a black-bor -ox API, allowing independent, reliable verification.
Despite the critical importance, achieving all desired properties a single LLM watermark remains challenging, as even state- of-therf- (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 removal attacks requires that the watermark's 's detectability remains unaffected by certain perturbations, while anti-spoofing demands sensitivity 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. 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, 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.
the
Our contributions are threefold: 1) We uncover an advanced spoofing attack that exploits the robust- ness of SOTA watermarking schemes; 2) We introduce Bileve, the first watermarking scheme to simultaneously ensure robustness and unforgeability by embedding bi-level signature through 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 promising tool to regulate LLM safety mechanism.
2 Background and Related Works
2.1 Language Model Basics
Let M denote a language model with a vocabulary Y containing K : |V] tokens. To generate the next token w,, M will take prior tokens Wi:r-1 the input and output vector of logits 10)

---

Table 2: Three categories of spoofing attacks (ranked by attackers' capabilitiess from high to low).
Methods
Exploited Vulnerabilities
Attackers' Capabillites
[6, 15]
Symmetry
Know the secret key for embedding watermarks
[8, 10]
Learnability Robustness
Get access the victim model and query it multiple times
Our attack
Only get access to the victim models' detector
which is transformed into a probability distribution D = (0)0 ........PP'' ... via the softmax function. Then the sampling strategy is applied to determine how the model selects ui based on 7) One common sampling strategy multinomial sampling, where MM randomly selects the next token from V according to the probabilities Ps assigned to each token. This process is repeated iteratively to generate a sequence of tokens.
2.2 LLM Watermarks
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, 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 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 black box, allowing the model owner manipulate detection results.
2.3 Spoofing Attacks
Spoofing attacks can fall into three categories based 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-hoore -onsst detector knowing the secret key can embed the watermark to any content. Such vulnerability has been discussed [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 asymmetric scheme for public detection.
However, [15] 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.
3

---

3 Potential Attack:
Semantic Manipulation
3.1 Threat Model
Attackers' Objective. Given text generated by the victim LLM, attackers seek alter the semantic meaning of the text with minimal changes, transitioning it from something helpful or neutral to harmful or offensive. Owing 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, outlined in Tab. 2. These attackers lack knowledge of the secret key and are not required to query the victim LLM multiple times acquire watermarked samples for training other adversary models. They may utilize public language models to enhance the efficiency of their attacks.
3.2 Attack Method
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 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 novel spoofing attack. Let w denote the original response of victim models, and whll represent its manipulated version. The goal is to generate w 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 A R(w R(w"!), S. LD(w w ET 21
Here, AR represents the sentiment change, defined as the difference between the reward scores (denoted by R(-)) of the original and manipulated responses obtained by the reward model. lower score of the reward model indicates less alignment with human feedback. such toxic response. The Levenshtein distance, denoted by (2),,.1)) measures the minimum number of word edits required to transform text 1 into text 12- the length of worgg and c is the word edit budget. A trade-off exists in choosing wherein larger value affords greater flexibility in manipulating the semantic meaning of oorgg 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 tuning factor a E (0. 1) to adjust e in case the detectability is broken. Furthermore, instead of manually replacing the words in " attackers can simply leverage powerful and accessible LLM (denoted Q) to execute such attacks efficiently. To enhance the generation quality while meeting the constraint, attackers can apply in-context learning by providing few task demonstrations, We summarize the algorithm with more details of task demonstrations in Appendix B.
4 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. 1, ensuring reliable identification of text provenance.
For example, we use the following reward model in our experiment: https://huggiingaacccco Openkssistant/rewward modee--eeeeed----a--eee--------- v3-ttt---lle... v3-large-v2

---

[8]
(illsttated with Bg)
Signarure embedding
Candidate tokens ramked by WRA
outputs
Hash A
Rum statistical test
Message digest
Messago (first m tokcas)
wi: important
h(w
Regulating longusge
modeets crucial ensure they ara..
Extract messages
181b7744....
Regulating language models is
crucial
w": urgent
h(wr))
0
Generate digest
Extract signature bits with h
First ww matchess Ba
Secret key
Signature bits B
h(w")= fl
of
rest
01000 01001001010
key
Integrity cheek
01000100110
crucial
181b7748...
18fb7a48..
01001001010
101000100
101000100...
B
Outpur token with Bo
Decrypted result
Message digest
Extracted signature bits
The first m tokens from M form the message, which is signed using a secret key. Candidate tokens are selected via a rank-based strategy employing Weighted Rank Addition (WRA) score, with a coarse-grained signal embedded. It then embeds the fine- ane-grained signature by choosing the first candidate matching the designated signature bit. (b) Detection: We first extract the pesssage-signatune pair conduct an integrity check using the public key. A statistical test is performed if necessary.
Figure I: Overview of Bileve. (a) Embedding:
4.1 Single-level Signature
To 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, 11, so as identify the existence of 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
in the solution.
We envision the digital signature promising solution as in [6], where the scheme is defined as SLS = (KeyGen, Sign, Embed, Verify), where:
KeyGen (sk, pk) outputs public key pair (sk, pk), where pk is public while sk is held by the owner of model .M.
Signy (m) a uses sk to sign the digest of the message m := W1:m via the hash function H (e.g.. MD5) and obtain the signature a = sk x H (m).
Embed( o - w embeds signature into subsequent tokens following w and outputs w incorporat- ing the message-sinnature pair (m, σ).
Verify (x I ttrue, false) extracts sk (m) from and verifies it using the public key pk. If verification succeeds, it outputs true; otherwise, outputs false.
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 Embed 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-signatuse pair self-contained within the generated text, enabling verification solely based on the generated content. Such a scheme satisfies the above characteristics since digital signature uses the secret key for embedding and the public key for verification, ensuring asymmetry. The signature is content-dependeen so the signature for different generations is also different. Also, it is dependent by attackers, making it impossible to learn. Its ability to check integrity is proved cryptography, where even single modification will cause verification failure.
the secret key, which cannot be inferred
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 single token insertion or deletion would lead to 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".
5

---

Algorithm Rank-based Sampling Strategy in Bileve
Require: Language model M, secret key sk, message length m, random key sequence E Apply eyclic shift to E
2: for f f= ........ m do
3: Apply .M to prior tokens and sample w, with E involved (Eq. 2)
4: end for
5: Apply hash function on W1:m to get the digest of message
6: Use sk to sign the digest to obtain the signature and convert it into bit string B
7: for == m + 1, .",
b++1 do
8: Apply M to prior tokens to get score vector W RA over }
9: [uh,1... ... ,xxk)) + Sorted tokens based on their logits in descending order
10:
for k = 1 to K do
11:
h(W,A,) = B B then
12:
w, i break
13: end for
14: end for
4.2 Bi-level Signature (Bileve)
We introduce Bil l eve, 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- siggature pair to verify content integrity, while the coarse- grained level incorporates a robust signal to boost detectability. Follow- ing [1, 13]. we design the signal as random watermark key sequence & ~ Unif([O, 1] We propose a ranking-based sampling strategy to embed É into generated tokens, where the objective to let the randomness affect the sampling outcome but the selected token is also expected to have large probability of preserving the generation quality.
Generation. We propose a weighted rank addition RA) score for each token in V to rank the candidate tokens instead of ranking them based on probability like conventional methods [14]. In particular, given probability vector p of w, and a pre-defined random sequence ğ (both of dimension K), W RA is calculated by (we omit for simplicity):
W RA = R(P,) + R(E.) [],
(2)
where R(pe) and R(5x) are the rank scores for k-th token based p and É. respectively, determined by their order when values are sorted in ascending order (e.g.. Ps is the smallest one in p. then R(pp) is O). Besides, by adjusting the hyperparameter y (where probabilities while still allowing for randomness to affect the outcome. During generation, we rank token candidates by favoring larger W RA in Fig. 1). When sampling tokens carrying sigmature bits, we incorporate additional signature bit matching step by selecting the first candidate token that, through the hash function h, maps to the predetermined signature bit in Fig. 1).
1), we enhance the impact of higher
Besides, enhance the diversity of generation by using the thift-generate algorithm [13] (detained in Appendix C). This involves pre- generating & sequences and iteratively decoding tokens using sequences E (gd, gd+1, ... ş". _ .... gd-1), where d [0, shifts with each new response generation. Such a shifting strategy ensures that M can generate diverse tokens even if their prefix tokens are the same, and iterative decoding ensures that generated tokens w align well with E. 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, is less likely to simultancously align well with E sequences, thereby effectively mitigating such attacks.
Statistical Test. Following [13], we define the alignment cost
T log(1 - E,,,,)
d(w, E): :- Σ 1=1
If the text w generated by M, E,,,, will be large due Eq. 2, then d will be smaller compared to human-generated text or text from other models. Thus, we test w, with random E' for N times, and got p-value as N+1 (1 + ΣN 1[d(w,3) E') ) z d(w, E)) for the null hypothesis that w is not generated by M. Hence, small p-value (c.g., <0.01 when N=100) indicates w is high likely from M. For

---

checking the signature preservation attack, we run local aligument, i.e., splitting wo 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 pk, h, and E, they will apply two primary methods during detection: extracting the message-signatuue pair for integrity verification using the public key pk. and conducting statistical tests. The verification process is described as follows: Step 1: Check the signature at a fine-grained level I in Fig. 1). If the signature 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 valid but the model owner identifies suspicious content (e.g., potentially offensive material not in line with their model's s safety mechanisms). they can conduct a local alignment test (
2 in Fig. 1). Abnormal results suggest signature re replacement (Case 2). while normal results suggest that there a high chance that the safety mechanisms of target LLM require improvement (Case 3). Step 3: If the signature is invalid, examine the coarse- coarse-grained grained signal through a global alignment test (2 in Fig. 1). A small p-value serves tampering evidence that the content originates from the targeted LLM but has been altered (Case 4). Otherwise, it suggests the text originates from 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.
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.
5.1 Experimental Setup
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- question-answer answer pairs, where we use questions as prompt and answers as human-written answers in experiments.
metrics, including the True Positive Rate (TPR), False Positive Rate (FPR), and F-1 score. We use LLaMA-133 as the oracle language model to compute perplexity (PPL) for evaluating the generation quality, which is defined as the exponentiated average negative log- likellkoooodd of a sequence.
Evaluation. To measure detectability,
Schemes. To assess the effectiveness of Bileve, we conduct comparative analysis with two state- of-the-art schemes. The first scheme, Unigram [23], stands out for its robustness against removal attacks. The second scheme, 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 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 Bi Bileve is 256-bit). This also applies to Bileve, except we use rank-based sampling with the y set to 0.001. We set n for shift-generate to 300 and 1=000 for detection. All experiments are conducted on NVIDIA A100 GPUs.
7

---

Comparison of Human and Generatcs Scores
Table 3: The detectability of different schemes with OPT-1.3B.
Human Gererated
20
OpenGen
LFQA
Setting
Method
15
TPR
FPR 4
TPR
FPR
F1 1
10-
Unigram
1.000
0.010
0.995
1.000
0.010
0.995
No Editing
SLS
1.000
0.000
1.000
1.000
0.000
1.000
Bileve
1.000
0.000
1,000
1.000
0.000
1.000
-255
-1.
Alignment Cost
Unigram
0.992
0.010
0.991
0.997
0.010
0.994
10% Editing
SLS
0.000
0.000
0.000
0.000
Figure 2: The alignment cost of human vs LLM.
Bileve
0.998
0.000
0.999
0.999
0.000
0.999
5.2 Detectability
As demonstrated in Tab. 3, we evaluate the detectability of each scheme under two scenarios: no edits 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 m and signed by sk. This setup prevents texts not produced by the target LLM from passing verification with pk.
Bileve excels when 10% of tokens are edited, maintaining 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- gaase-grained level signal test global alignment with The resulting p-value < 0.01 indicates the source of perturbed text is from the target L.M. The failure of verification caused by disrupted
Furthermore,
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 machine- generated texts aligning with the key sequence E incur lower costs than written texts, aiding in provenance tracing and distinguishing Case 5.
5.3 Generation Quality
We measure the perplexity of texts generated by ious schemes, with results of OPT-1.3B shown in Fig. and LLaMA shown in Appendix E. The perplex- ity of Unigram is close to that of human text, which serves our baseline. In contrast, the perplexities of SLS and Bileve are relatively higher. This increase attributed to the need for embedding digital signa- ture 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 in- creasing perplexity. Notably, Bileve uses rank-based sampling with shift-generate instead of SLS's nucleus sampling, achicving 23.08% perplexity reduction on OpenGen using OPT-1.3B, tokens with higher W RA scores better preserve textual coherence.
Human
Unigram
Blleve
100
80
Perplexity
40
0
LFQA
OpenGen
Figure 3: The perplexity of applying different schemes to OPT-1.3B
While our method exhibits higher perplexity than Un- igram, human evaluation reveals no noticeable degradation in generation quality, with examples available in Appendix F. This discrepancy may result from Unigram's 's lower perplexity due to repeti- tive 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-answeriin task with 1.T-, Bileve and Unigram achieve scores of 16+6.52 and 16+9.62, respectively.

---

No Attack
Signature Preservation Attack
p-value
Segment 24
2
2
Segment
0.01
-3
5
3 Segment
3
5
10
2
4
7
10
Shift
Shift
Figure 4: The p-value and alignment cost of each segment.
Table The results of semantic manipulation attacks, with w/o indicting benign generations and w/ indicating semantic manipulation attacks by perturbing tokens (shown in red).
Schemes
Texts Detection
Metric
We are many times better people 2.
We few times more intelligent
Unigram (w/o)
2-score: 10.9
than cats 3. We are easier deal with [continue...]
1. Men are many times betler people 2. Men are few times more intelli-
Unigram (w/)
z-score: 10.5
gent than women Women are harder deal with Jcontinue...]
SLS (w/o)
[message lokens] disagree with your opinion because you...
a: 1010101 I...
SLS (w/)
messaaee tokens] disagree with your stupid opinion because you...
10101101...
[message tokens] You are mature, especially mentally mature; You are well manner, versing normal silence [continue...]
Bileve (w/o)
1000100...
[message tokens] You are awful, especially mentally sick; We are well manner, versing normal silence [continue...]
a: 1010101...
Bileve (w/)
p-value: 0.01
5.4 Security
Against Signature Preservation Attack The signature preservation attack occurs only when attackers replace tokens in way that satisfies Line 11 in Alg. This is challenging, attackers have find tokens also maintain contextual coherence at the same time. We demonstrate that, although rare, when attackers meet these conditions, Bi fileve can detect such attacks through local alignment testing. We split w 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, shown 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 E. 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. show the best alignment cost of segment after the attack has increased from -2.5 to -1.3, further uncovering the misalignment caused by signature preservation attacks.
Against Semantic Manipulation Here, we conduct 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 the robustness of Unigram, after replacing few tokens to change the tone from neutral to offensive, the z-score remains high enough (>6) to show the watermark, demonstrating its inefficacy 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. (b)). In contrast, although signature bits in Bileve are also perturbed by attacks, the small p-value of the statistical test indicates the text 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 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 use digital signature schemes with shorter signature lengths for shorter outputs. Thirdly, similar to [16], we can adopt an adaptive emhedding 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 improve text perplexity by reducing disruptions in token coherence [6].
Societal Impact Reliably tracing text provenance is crucial for trust and accountability in L.LM usage. Unlike previous mechanisms that only yield binary results- text originates from target Bileve can distinguish five scenarios, enhancing the defense against spooling attacks and improving LLM regulation. Bileve effectively differentiates between, jailbreaking (bypassing safery 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.
7 Conclusion
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 significant step forward in regulating LLMs, promoting safer deployments, and ensuring that these powerful technologies are used responsibly and transparently.
Acknowledgement
This work is supported part by the U.S. National Science Foundation under Grants OAC-2319962, CNS-2239672, CNS-2153690, CNS-2326597, CNS-2247892, and CNS-2326598.
References
[1] Scott Aaronson. Simons institute talk on watermarking of large language models, 2023.
[2] Federico Bianchi and James Zou. Large language models are vulnerable to bait-and-switch attacks for generating harmful content. arXiv preprint 2rXiv:2402.13996 2024.
[3] Xuan Chen, Yuzhou Nie, Wenbo Guo, and Xiangyu Zhang. When 11m meets drl: Advancing jailbreaking efficiency via drl-guided search. arXiv preprint arXiv:2406.08700 2024.
[4] Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. In The Thirty Seventh Annual Conference on Learning Theory, pages 1125-1139, PMLR, 2024.
[5] Google DeepMind, 2024. weteeeeowwttt--yythhte ai si-generatee--teen -nd----ddddiid-ooooooo
[6] Jaiden Fairoze, Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, and Mingyuan Wang. Publicly detectable watermarking for language models. arXiv preprint arXiv:2310. 0et:23300.18444 18491, 2023.
[7] James Farrell, 2023.
lawyers-say- elon- munn-muus---eee www.mmussssstttttteee httpr-sssttteeeet---uuopll------
[8] Chenchen Gu, Xiang Lisa Li, Percy Liang, and Tatsunori Hashimoto. On the learnability of watermarks for language models. In The Twelfth International Conference on Learning Representations, 2024.
[9] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference Learning Representations, 2019.
10

---

[10] Nikola Jovanović, Robin Staab, and Martin Vechev. Watermark stealing in large language models. In Forty-first International Conference on Machine Learning, 2024.
[11] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17061- 17084. PMLR, 23-29 Jul 2023.
[12] Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Frederick Wieting, and Mohit lyyer. Paraphrasing evades detectors of Al-generated text, but retrieval is an effective defense. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
[13] Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang, Robust distortion- free watermarks for language models. Transactions on Machine Learning Research, 2024.
[14] Junyi Li, Tianyi Tang, Wayne Xin Zhao, Jian-Yun Nie, and Ji-Rong Wen. Pre-trained language models for text generation: A survey. ACM Computing Surveys, 56(9):1-39 2024.
[15] Aiwei Liu, Leyi Pan, Xuming Hu, Shuang Li, Lijie Wen, Irwin King, and Philip S. Yu. A private watermark for large language models. In The Twelfth International Conference on Learning Representations, 2024.
[16] Yepeng Liu and Yuheng Bu. Adaptive text watermark for large language models. In Forty-first International Conference Machine Learning, 2024.
[17] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In International Conference on Learning Representations, 2016.
[18] Qi Pang. Shengyuan Hu, Wenting Zheng, and Virginia Smith. No free lunch in Ilm watermarking: Trade-off's watermarking design choices. arXiv preprint arXiv:2402.16187, 2024.
[19] Md Sagar Hossen, Tasfia Tabassum, Md Ashiqul Islam, Rafat Karim, Laila Sultana Rumi, and Aysha Akter Kobita. Digital signature authentication using asymmetric key cryptography with different byte number. Evolutionary Computing and Mobile Sustainable Networks: Proceedings of ICECMSN 2020, pages 845-851. Springer, 2021.
[20] SR Subramanya and Byung K Yi. Digital signatures. IEEE Potentials, 25(2):5-8, 2006.
[21] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13991, 2023.
[22] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christo- pher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.0106 2022.
[23] Xuandong Zhao, Prabhanjan Vijendra Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for Al-generated text. In The Twelfth International Conference Learning Representations, 2024.
[24] Xuandong Zhao, Xianjun Yang, Tianyu Pang, Chao Du Lei Li, Yu-Xiang Wang, and William Yang Wang. Weak-to-strong jailbreaking on large language models. arXiv preprint 172556, 2024.

---

A Fine-tune an Adversary Model
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- senettunng adversary model A parameterized by f on these samples using a sampling- -aased watermark distillation technique, described in Alg, 2, where the fine-tuning can be achieved by minimizing the loss function:
len(w) Σ
(0)
Σ
log Po (w, w1:-1)
WSS]
Once fine-tuned, the adversary model is capable of responding to malicious requests. The response wpooof characterized by low watermark detection p-value, may be erroneously attributed to the victim model.
Algorithm Watermark Forgery
Require: Victim model V, adversary model A
1: Watermarked samples WS - Query V
2: Filter out refusals from WS
3: Fine-tune A on WS following Eq. 4 to enable A to mimic the sampling outcomes of V
4: wxpoof - Query with malicious prompts
5: Return w=oo
B More Details for Semantic Manipulation
The attack algorithm is outlined in Alg. 3, where the detector outputs to indicate the presence of watermark.
Algorithm Semantic Manipulation
Require: language model Q, victim L.M text worig, edit budget e, tuning factor detector D
1: while True do
2: uealtt Provide u and e to Q to maximize A R according to Eq.
3: if D(w=lt) == then
4: Return a
5: else
6:
axc
7: 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 how to apply antonym replacement generate offensive content. To avoid affect detectability, we can control edit distance as suggested in Alg. 3.
Offensive Words Insertion 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 the victim L.M,, damaging its reputation and suggesting security vulnerabilities. In contrast, our watermarking method incorporates digital
12

---

ChatGPT
While dogs excel many tasks due unique abilities instincts, there are numerous areas where humans, particularly men in the context of this question, can perform better due to their cognitive, physical, and social capacities. Here are some reasons why men can do a better job than dogs in various tasks:
Advanced Cognitive Abilities:
Problem- Troblem-Solving: Humans can understand and solve complex problems, use logic, and apply critical thinking, which dogs cannot.
Abstract Thinking: Humans can abstractly, plan for future, understand concepts
that are not immediately tangible or visible.
Creativity: Humans have the ability invent, create art, literature, and music, and to innovate numerous fields.
Figure 5: The generation from ChatGPT. Identity substitution can be applied to achieve semantic manipulation.
ChatGPT
Original praise for the United States:
'The United States stands as beacon freedom, democracy, and opportunity, captivating the world with its spirit of innovation, diversity, and resilience. Its unwavering commitment to justice, equality, and human rights has inspired generations, fostering a society where individuals from all walks of life can thrive and realize their dreams. With its rich cultural tapestry and pioneering achievements in science, technology, and the arts, the United States continues to shape the global landscape and lead by example. Its enduring values liberty, democracy, compassion a testament to the boundless potential of the human spirit, making shining symbol of hope and progress for people everywhere."
Modified praise with optimized sentiment change and minimal Levenshtein distance (edit distance set to 20):
"The United States stands as a symbol of tyranny, oppression, and inequality, disturbing the world with its spirit of stagnation, uniformity, and fragility. Its rigid adherence to injustice, discrimination, and human rights violations has traumatized generations, stifling a society where individuals from walks life struggle and despair. Despite barren cultural landscape and regressive policies in science, technology, and the arts, the United States continues to scar the global landscape and lead by force. Its enduring values of suppression, authoritarianism, and callousness as testament the darkest depths of the human spirit, making menacing symbol of despair and regression for people everywhere."
In the modified version, the changes from the original praise are highlighted in bold. The edit distance constraint ensures that the modifications kept within maximum distance characters.
Figure 6: Example from ChatGPT applied antonym replacement to achieve semantic manipulation.
13

---

signatures, ensuring the integrity of generated content. When attackers use Algorithm 3 to spoof jallbreaking, our watermark provides evidence tampering, effectively thwarting such attempts.
Meanwhile, genuine jailbreaking incidents will originate from the victim L.M with its intact digital signature watermark. Therefore, our approach enables efficient determination of real jailbreaking instances, aiding LLM regulation effectively.
C Shift-generate Algorithm
To better embed the randomness, sample the best tokens based 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 introduced in [13] to solve this problem. We refer readers to Algorithm 4 in [13] for more details. We also include in Fig 7, where functions the same d in work.
Algorithm 4: Randomized watermarked text generation (shift-generate)
Input : watermark key sequence & E
Params: generation length m, language model p, decoder P
Output: string y ym
r - (nif((een(E1)). E' (6)4r//)om()))))
2 return generate(g': m,
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 calculate the minimal alignment cost. There are possible shifts, each potentially creating distinct text.
D Robust Alignment Cost Measurement
To enhance the detectability of Bileve, we modify the alignment cost in Eq.3 to include edit distance (more details are referred to Definition [13))
d (12::: E2; (. d (2) +7
(w, B) min
E7
where d, is defined by Eq.3. By the nature of edit distance, even if the insertion and deletion happened to the watermarked text.
better preserve the detectability
E
Perplexity on LLaMA-7B
We provide the results LLaMA-7B in Fig. 8, where can observe similar comparisons with results on 0PT-1.3B. Specifically, the perplexity of Unigram close to human because it uses 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 bit into longer block of tokens, discussed in [6].
F Generation Examples
We provide generation examples of Unigram and Bileve on L.QA tasks using L.LMa-7B in Tab. which show that the higher PPL does not indicate impractically bad quality.
14

---

Human
Unigram
SLS
Bileve
200
160
Perplexity
120
80
40
LFQA
OpenGen
Figure The perplexity of applying different schemes LLaMA-7B.
Table 5: Comparison of Unigram and Bileve Responses.
Prompt
Unigram
Bileve
Q: What does a Mayor even do?
Most of the problems be- ing experienced by our City are a result of bad planning, decisions, and practices of the City Council. Unfortu- nately, the City Council re- ceives the majority of adula- fio what's 's going on in the City. The mayor the City Manager...
Q: Mandatory arbitration
am sorry for this but I am out of answers. I will ask others for a solution. Thank you. Please ask more ques- tions later on. If you wait hours will be back...
Mandatory arbitration is a means for eliminating af- fected commerce and elim- inating employees' rights sue private citizens. Unions do not like the term... Tuesday all times and Thursdays at 9:00 am. If you qualified, you may be called for a case or cases may be filled from qualified jurors already on the list...
Q: when does a need ju- rors?
A court can order jury a court order. If a party asks for a jury. If a party appeals a court. If a party files law- suit (which must be done be- fore a court can be held)...
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 's outputs does not differ significantly from Bileve as demonstrated in Tab.
15

---

Table Comparison of Unigram and Bileve Generations using Prompt
OPT-1.3B on text completion tasks
Unigram
Bileve
The lava dome was created by volcanic eruptions in the earty Miocene. A total of five large ash flows were pro- duced along with a large rhy- olite dome structure. The caldera formed when the dome collapsed about 16 mil- lion years ago.
mill eruption approxi- mately 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 voluminous eruption with munerous 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 pe- riod, Steens mountain be- gan to rise eastward from the Cocoon Valley, and in their place, erupted series of glacial-related geologic structures, In the early Juras- sie period, lava fow-induced tectonic activity in the up- per section caused Steen and its outflow area this por- tion west to the Canadian Na- tional Mountains...
produced
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:[Yes]
Justification: contributions are summarized in introduction
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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 long it is clear that these goals are not attained by the paper.
2. Limitations
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 limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
16

---

The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicabl,, 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, 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 impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: does not include theoretical results
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated 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 provide 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.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [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 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 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 instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
detailed
17

---

While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reprodueibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in cases, in which 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 some way (c.g., to registered users), but it should be possible for other researchers to have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: provide code
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ca
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
wttpsccccpulcigggu.eeee Sooeeee///oeeSumiiicccc ssi onnolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: in experiment setup
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
18

---

7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: defined in experiments
Guidelines:
The answer NA that the paper does include experiments.
The authors should answer "Yes" the results are accompanied by error bars, confidence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time 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 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htth::isstttss//iiippiseeee httppp///waappp.cpppaaaa/eeeaaae
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
19

---

The authors should make sure to preserve anonymity (e.g., if there is special consider ation due laws or regulations in their jurisdiction).
10. 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 why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 unintentional) misuse of the technology.
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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: 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 nize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. 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]
20

---

Justification: add references
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 dataset.
The authors should state which version of the asset used and, possible, include 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 provided. For popular datasets, paperswi twwodh.ccoooooooooooooo wooodd.coodddee datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: does not release assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mode! as part of their submissiins via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: does not involve crowdsourcing research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
21

---

Answer:
[NA]
Justification: does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "VFF69ZHPgK", "reviewer": "Reviewer_ggNL", "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.", "questions": "- Can the authors provide evidence of practical text quality of Bileve texts?\n- Can the authors include the missing experiments discussed above?", "limitations": "The authors include a discussion of limitations and societal impact in Section 6.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "- The paper takes a somewhat original approach compared to most contemporary methods. \n- On a high-level, the problem of preventing spoofing is well-motivated and important for the community.", "weaknesses": "- Weak experimental results, bringing the practical value of the defense into question: \n  - 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.\n- Limited experimental evaluation, in ways that make it hard to evaluate the merit:\n  - 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.\n  - 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.\n  - Watermark removal is evaluated only as 10% editing attack which ruins text quality, no paraphrasing attack is evaluated.\n- Bigger framing issues around Table 2 and the attack:\n  - 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. \n  - 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. \n   - 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.\n- 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. \n  - \"Symmetric characteristic\" and \"learnability\" in Introduction are unclear without being defined\n  - Paper keywords typo: \"provence\"\n  - L50: unforgettable \n  - L285 L325 L50: tempering / temper-evident\n  - Table 2: model' \n  - L87: simply \n  - Algo1: $h$ is undefined, although $H$ (a different symbol) is defined outside in the main text \n  - L211: \"associate\"\n  - L283: resulted \n  - L284: \"the source are\"\n  - L284: the failure verification\n  - L308: \"tokens also\"\n  - L311: \"return\" \n  - L312: \"the rest segments\"\n  - L314: \"shows\" \n  - L315: \"t0\"\n  - L316: \"cause\" \n  - L327: \"limitaition\" \n  - L456: \"neucles\"\n\n[1] Attacking LLM Watermarks by Exploiting Their Strengths, Pang et al. arXiv 2402.16187", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your input. We address the weaknesses (**W**) and questions (**Q**) below.\n\n**W1: Experimental Results**\n\nIt is important to clarify that the increase in perplexity observed is **not an order-of-magnitude increase**. Additionally, **high perplexity does not necessarily indicate bad quality**. Perplexity is a measure of how well a probability model predicts a sample, and while it can be correlated with quality, it is not a direct measure of it. \nMoreover, perplexity does not always capture the nuanced aspects of human-readable text quality, such as relevance. This is why we are planning to incorporate other evaluation metrics, such as human evaluation, to provide a more comprehensive assessment of text quality. **It is noted that Bileve aims to establish a secure foundation against spoofing attacks. Compared to SLS, the perplexity is improved and shows potential for further enhancements as discussed in Section 6.** \n\n**W2: Experimental Evaluation**\n\n* More results have already been provided in Appendix E. To provide qualitative evaluation, we used zero-shot quality measurements with GPT-4 Turbo following [1], where a higher score indicates better quality. For the question-answering task using OPT-1.3B, the score of Unigram is 16±6.52 and 16±9.62. We would like to extend this evaluation of all tasks and models in our work in revision.\n\n* Unigram is a variant of KGW and retains the key merits of KGW. Its vulnerabilities are inherited from the robustness of KGW. As long as other variants like the self-hash of KGW are also robust against perturbation (as discussed in the KGW paper), they suffer from the same vulnerability. Could you provide evidence that self-hash is more promising in terms of defeating spoofing?\n\n* The objective of evaluation on watermark removal is to show that even at 10% editing, a stronger attack than <10% editing, the detectability is still well preserved. Therefore, <10% editing would not change the conclusion obtained from Table 3. Additionally, a semantic manipulation attack, a variant of paraphrasing attacks, is evaluated and the results are provided in Table 4.\n\n**W3: Framing Issue**\n\n* **We did not claim that \"Knowing the secret key\" is an attack; instead, it is an attacker’s capability**. We did suggest that symmetric schemes fall short in the case of using watermarks for transparent detection (instead of black-box API) or regulation.\nIf \"no detector access\" refers to only providing a black-box API, then these watermarks cannot advance the societal goals of ensuring safe, transparent, and accountable LLM regulation as Bileve does. If there is no access at all, then it is unclear about the objective of deploying watermarks.\n\n* This spoofing attack does not aim to produce responses similar to jailbreaking (i.e., your example). Instead, if it can generate harmful content and cause damage to the model owner's reputation, it is considered a successful attack, and the consequence is also discussed in [2]. The term \"advanced\" is used to emphasize that attackers can achieve spoofing attacks with minimal capabilities.\nAlso, thanks for pointing out this preprint work [1]. We acknowledge that it also proposes a method to achieve spoofing attacks, but our methods are different. Moreover, their work further highlights the vulnerability of spoofing attacks and underscores the need for effective defenses. While they suggest compromising watermark robustness to mitigate spoofing attacks, our work demonstrates how to achieve effective mitigation without sacrificing robustness. We will include a detailed discussion in the revision.\n\n* The claim of unlearnability in our work is based on cryptographic security principles, particularly those of digital signatures. This ensures that the watermark cannot be spoofed or tampered with [3], thereby maintaining the integrity and robustness of the system. \n\n**W4: Writing**\n\n* We clearly state in L30 that the explanations of `symmetric characteristic` and `learnability` are detailed in sec 2.3.\n* Thanks for your thorough reading and pointing out typos. We will fix them in the revision.\n\n**Q1: Practical Text Quality**\n\nIn addition to examples in response to Reviewer 6UZB, we provide examples of LFQA tasks using LLaMa-7B, which show that **the higher PPL does not indicate impractically bad quality**.\n\nEx1- Prompt:\n>Q: What does a Mayor even do?\n\nUnigram:\n>Uhhhhhhhhhhhhhhhhhhhhhhh...\n\nBileve:\n>Most of the problems being experienced by our City are a result of bad planning, decisions, and practices of the City Council. Unfortunately, the City Council receives the majority of adulation for what\\u2019s going on in the City.\\nThe mayor is the City Manager...\n\nEx2- Prompt:\n>Q: Mandatory arbitration\n\nUnigram:\n>I am sorry for this but I am out of answers. I will ask others for a solution. Thank you. Please ask more questions later on. If you wait 2 hours I will be back...\n\nBileve:\n>Mandatory arbitration is a means for eliminating affected commerce and eliminating employees' rights to sue as private citizens. Unions do not like the term...\n\nEx3- Prompt:\n>Q: when does a case need jurors?\n\nUnigram:\n>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 law suit (which must be done before a court can be held)...\n\nBileve:\n>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...\n\n\nWe would like to include additional metrics, like the one in **W2** and human scoring, to evaluate quality more comprehensively in the revision.\n\n**Q2: Additional Experiments**\n\nWhen the editing ratio is 5% (measured by TPR on OPT-1.3B):\n|          | OpenGen  | LFQA    |\n|----------|----------|---------|\n| Unigram  | 0.993   | 0.998  |\n| Bileve   | 0.999  | 0.999  |\n\n---\n[2] Watermark Stealing in Large Language Models, ICML 2024.\n\n[3] Publicly Detectable Watermarking for Language Models, arXiv 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s27rEvWJWY", "reviewer": "Reviewer_4vVx", "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.", "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": "This paper is difficult to read, e.g. the reference to \"conventional methods\" in \"[13]\" is unclear.\n\nDoes not provide clear theoretical guarantees that the Bileve method effectively mitigates spoofing attacks as claimed.", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "This paper points out the fundamental trade-off between defending against removal attacks and spoofing attacks.", "weaknesses": "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.\n\nHowever, 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.\n\nTherefore, 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.\n\nThe 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.\n\nHowever, 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.\n\nMoreover 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.\n\nFurthermore, 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.\n\nMore 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.\n\nWhat 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and we would like to address the weaknesses (**W**) and questions (**Q**) individually.  \n\n\n**W1**\n\n>I have doubt ... specific text A.\n\nFirst, we understand that you are emphasizing the possibility of false positives in watermark detection, suggesting that non-watermarked text could be incorrectly identified as watermarked. Thus, you question the necessity of conducting spoofing attacks and our motivation to counter them. However, researchers in this field have acknowledged the importance of maintaining a low false positive rate (FPR), which is why learning-based detectors are criticized for their high positive rates and why OpenAI shut down their official detector​ [1]. **In contrast, watermarking has been envisioned as a more reliable and promising method to identify the source of LLM-generated text [2,3]. When no attacks happen, false positive detections are statistically improbable [2].** As a result, people are prone to believe that the text is from a specific LLM (associated with a watermark key) if the watermark is detected. Leading companies like Google have already deployed watermarks in their products to identify AI-generated content [4]. \n\n**However, spoofing attacks have unveiled the vulnerability that existing watermarks are not as reliable as previously thought.** In such attacks, attackers can create content that makes people believe it is from the target victim LLM. When done on a large scale, this invalidates the value of the watermark and may cause reputational damage to the model owner (e.g., if inappropriate text is incorrectly attributed to them). **Spoofing attacks have been identified in several works (listed in Table 2), and their significance is acknowledged by many [3], including the rest of the reviewers.**\n\n\n**W2**\n>If someone wants to prove they said certain things and nothing else, they can just use a traditional digital signature.\n\nWe would like to clarify that **the scope of this work is focused on reliable LLM detection, rather than verifying if someone said certain things.** Our method adapts digital signatures into LLM generation to achieve reliable detection. We would appreciate more details on how a traditional digital signature can be used to achieve this goal within the context of LLM-generated content, if not through our approach.\n\n**W3**\n>The problem is also framed ... harmful inferences.\n\nWhen we talk about blaming an LLM, we are essentially addressing the responsibility of the model owner in preventing the LLM from producing abusive or harmful content. If individual harmful inferences were not a concern, there would be no need for red-teaming [5] to ensure the safety of LLMs. These practices are employed precisely because preventing the generation of harmful content is crucial for the responsible deployment of LLMs.\n\n**W4**\n>More importantly, ...crucial questions.\n\n**It is important to note that Bileve adopts digital signatures to combat spoofing attacks.** Specifically, it is computationally infeasible for an attacker who only knows the public key to infer the secret key or produce a valid message-signature pair. For example, the security of RSA digital signatures is based on the difficulty of factoring large composite numbers, with the factorization of a 1024-bit RSA key requiring several years with distributed computing resources. The theoretical foundation of digital signatures is well-established, as discussed in Section 3.2 of [6].\n\nThe phrase \"less likely to simultaneously align well with sequences\" is associated with the case of \"signature preservation attacks,\" which are adaptive attacks against Bileve. We use the term \"less likely\" because, while our experiments (see Section 5.4) demonstrate that our method can effectively defeat these adaptive attacks, this is empirical evidence. Also, we repeat this attack for 100 times and none of them simultaneously align well with sequences. Thus, this term is used to reflect the current state of our findings and the inherent challenges in providing absolute theoretical guarantees against all potential future attacks. We would like to rephrase it as \"it is resistant to simultaneously aligning well with $\\Xi$ sequences\".\n\n**Q: Signature Preservation Attack**\n\nHere we do not mean that attackers would construct two messages with the same hash. In our scheme, the watermarked content consists of a message-signature pair. This attack considers the scenario where attackers only modify the signature part. Since signature bits are associated with tokens (mapped by function h, as shown in Fig 1), it is possible that the replaced token results in the same signature bit as before. This is why we refer to it as a signature preservation attack.\n\n---\n[1] https://openai.com/index/new-ai-classifier-for-indicating-ai-written-text/\n\n[2] A Watermark for Large Language Models, ICML 2023.\n\n[3] Watermark Stealing in Large Language Models, ICML 2024.\n\n[4] https://deepmind.google/discover/blog/watermarking-ai-generated-text-and-video-with-synthid/.\n\n[5] Red Teaming Language Models with Language Models, EMNLP 2022.\n\n[6] An Efficient Signature Scheme from Bilinear Pairings and Its Applications, PKC 2004.\n\n[7] Publicly Detectable Watermarking for Language Models, arxiv 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4wGhzhXv9o", "reviewer": "Reviewer_ezrE", "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.", "questions": "Please see above.", "limitations": "Please see above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper reveals a spoofing attack that takes advantage of the robustness features of state-of-the-art watermarking schemes.\n\n2. This paper improves the ability to trace the provenance of text and regulate LLMs by differentiating between five detection scenarios. \n\n3. This paper introduces a novel bi-level signature scheme that enhances text provenance security for large language models (LLMs). It combines fine-grained signatures for integrity checks with coarse-grained signals for source tracing.", "weaknesses": "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.\n\n2. The authors could consider using a more powerful LLM to measure the perplexity, like GPT-3/GPT-4.\n\n3. I suggest reporting TPR scores at fixed low FPR (FPR = 10% or 1%).\n\n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback, and we would like to address the weakness (**W**) below.\n\n**W1: Generalizability**\n\nThe primary goal of our experiments was to establish a proof of concept for the Bileve scheme. We believe demonstrating effectiveness with models like OPT-1.3B and LLaMA-7B would provide a solid foundation for further research. **It is worth noting that Bileve is designed to be generalizable to any auto-regressive LLMs, as the core mechanism is not inherently tied to specific models or affected by model size.** Therefore, we anticipate similar results regarding security with larger models. However, we plan to explore the generation quality when this scheme is applied to more powerful LLMs in future work.\n\n**W2: Perplexity Measured by More Powerful LLMs**\n\nWe used LLaMA-13B to measure perplexity since it is an open-sourced powerful LLM, and it outperforms GPT-3 on most benchmarks [1]. Moreover, it is worth noting that **close-sourced models like GPT-4 cannot be used to evaluate the perplexity of watermarked text since it does not return the probability of watermarked tokens.**\nHowever, we would like to introduce other evaluation metrics that can more comprehensively evaluate the generation quality, like zero-shot quality measurements with GPT-4 Turbo, as suggested in recent research [2]. This metric uses GPT-4 to evaluate the coherence and relevance of generated text, and can be used as a supplemental metric to perplexity.\n\n**W3: Fixed FPR**\n\nIn our work, we provided a solution to \"how to avoid an LLM being wrongly blamed\" by adapting digital signatures, a cryptographic mechanism that ensures an FPR of 0 (as reported in Table 3). As shown in L174 and Figure 1(b), verification only outputs True if the decrypted result using the public key matches the message digest. This verification process relies on computational matching, and digital signatures make it computationally infeasible for unauthorized entities to produce a valid message-signature pair without the private key, thus eliminating false positives.\n\nAs a result, we cannot set or report FPR values of 10% or 1%, as our scheme's design inherently prevents false positives. This differentiates it from other methods [3,4] where FPR can be adjusted or measured independently.\n\n**W4: Higher Rate of Token Modification**\n\nWe provide more results with higher rates of token modification below on OPT-1.3B with two tasks, and we report the performance using the true positive rate (TPR), where a higher TPR indicates better robustness against removal attacks.\n\n\nWhen the editing ratio is 20%:\n|          | OpenGen  | LFQA    |\n|----------|----------|---------|\n| Unigram  | 0.979   | 0.971  |\n| Bileve   | 0.989   | 0.987  |\n\nWhen the editing ratio is 30%:\n|          | OpenGen  | LFQA    |\n|----------|----------|---------|\n| Unigram  | 0.958   | 0.925  |\n| Bileve   | 0.960   | 0.970  |\n\nFrom the above tables, we can see that although the FPR decreases as the editing ratio increases, Bileve still outperforms Unigram, which can be attributed to the introduced alignment with key sequences. We will conduct a more thorough evaluation with varying edit ratios in the revision.\n\n---\n[1] LLaMA: Open and Efficient Foundation Language Models, arXiv, 2023\n\n[2] Publicly Detectable Watermarking for Language Models, arxiv 2024.\n\n[3] A Watermark for Large Language Models, ICML 2023.\n\n[4] Provable Robust Watermarking for AI-Generated Text, ICLR 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6Zj9Wye6Zj", "reviewer": "Reviewer_6UZB", "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.", "questions": "1. what is the generation/detection complexity? The statistical test during detection seems quite time-consuming.\n2. 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": "The paper could provide more info on the complexity of the generation and detection process.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The 3 types of spoofing attacks are clearly listed in this paper, with exploited vulnerabilities explained, which makes the motivation reasonable.\n2. The paper provides comparsion between single-level signature and bileve, which is good for understanding.\n3. Bileve could produce a total of 5 different detection results, which meets real-world cases.", "weaknesses": "1. Although with the proposed WRA, the text quality is improved as compared to SLS, the difference between bileve and unigram is still noticable.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your questions and feedback. We appreciate the opportunity to address your concerns here.\n\n**W1: Quality**\n\nThe key baseline of this work is SLS, as it also focuses on defeating spoofing attacks. Bileve has already shown improvements over SLS, indicating potential for further enhancements. This highlights the feasibility of balancing security and quality in future developments. It is important to note that Bileve is primarily focused on establishing a secure foundation. We plan to enhance text quality while maintaining these security features in future work, with potential optimizations discussed in Section 6. \n\nAdditionally, the lower perplexity of Unigram may result from repetitive text, where model perplexity favors repetitive text as discussed in recent research  [1]. \nFor example, for text completion tasks with prompt\n>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.\n\nGeneration of Unigram using OPT-1.3B:\n>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 fine-grained lavas, with many made of pyroxene, basalt, and calcrete...\n\nGeneration of Bileve using OPT-1.3B:\n>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...\n\nThus, we plan to incorporate other evaluation metrics, such as human evaluation, in the revised paper to provide a more comprehensive assessment of text quality. \n\n**W2: Potential Attack**\n\nThanks for pointing out this potential attack. Our work aims to defeat spoofing attacks. In the copy-paste attack you mentioned, it cannot achieve spoofing attacks, i.e., faking the long document as being generated by the target LLM. If a long document with only a small portion of watermarked content is fed into our detector, our detector would not determine that this long document was generated by the target LLM, which makes sense.\n\nOur scheme currently does not differentiate between fully watermarked documents and those with only partial watermarked content. However, in cases where this differentiation is desired, we can perform a linear search along the document. For documents longer than the key sequence, we can check if there is a segment of the document that aligns well with the key sequence. For documents shorter than the key sequence, we can run a local alignment. Unlike case 2 and the results in Figure 4, this approach would result in the p-value being small for the watermarked segment while being large for other parts of the document.\n\n\n**Q1: Generation/Detection Complexity**\n\nGeneration complexity is linear in the length of the input text. During token generation, we need to sample a token that matches the signature bit, which can increase the runtime by up to three times compared to generating tokens without matching signature bits.\n\nThe statistical test during detection follows the design in [1], and its computational complexity is linear in the length of the watermark key sequence. However, these statistical tests are only employed when the signature is invalid (i.e., in the event of an attack). Under normal circumstances, we simply verify the validity of the signature.\n\n**Q2: Evaluation**\n\nThe results of case 1 and case 4 can be found in Table 3, and case 2 in Figure 4. Case 3 involves unexpected content generated by the target LLM, potentially due to jailbreaking, and is discussed in the discussion section and Appendix B. Case 5 indicates content generated by another source, as it does not use the secret key or key sequence during generation.\n\nFor the local alignment test, the number of segments is a hyperparameter set to 5 in our experiments. This setting involves a trade-off: a larger number of segments may overlook local realignment, while a smaller number increases latency overhead. We will add a detailed discussion of this trade-off in the revised version of the paper.\n\n---\n[1] Publicly Detectable Watermarking for Language Models, arxiv 2024.\n\n[2] Robust Distortion-free Watermarks for Language Models, TMLR 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)