About the privacy of public watermark methods

Thank you for your question.

Firstly, please refer to first response in "Responses to all reviewers". We appreciate the concerns raised by reviewers seaW and CjAu regarding the definition of 'private watermark'. Indeed, we acknowledge the potential confusion in using this term to describe our method. Consequently, we have renamed our approach from 'A private watermark' to 'An Unforgeable Publicly Verifiable Watermark for Large Language Models'. It means that our proposed watermarking method could be publicly verified by a third-party detector, and even under this scenario, the watermark cannot be easily forged by an untrustworthy detector. In other words, the previous concept "privacy" is interpreted more clearly as "unforgeablity" under third-party detection.

Moreover, previous work that used shared key in both watermarking and detection process are referred to as key-based method, while our detection approach is named as network-based method. All related concepts in the updated version of our paper have been revised accordingly.

Under this concept, the question "about the privacy of public watermark method" will be interpreted as "about the unforgeability of key-based methods". In a third-party detection scenario, the shared key used in key-based methods are exposed to the public. Therefore, the key could be used to directly forge the watermark with no need of any attacks. That is, the key-based methods have no unforgeability.

You might get confused about why we leverage spoofing attack and reverse engineering attack to test unforgeability of our watermarking method. That is because, by using our network-based detecting method, there is no watermark generation details (such as the watermark key) exposed to public. Therefore, if an attacker wants to acquire the watermark generation details and then use it to forge watermark, they could only try using sophisticated analysis such as spoofing attack and reverse engineering attack mentioned in our paper.

We greatly appreciate your query and have clarified these issues in the updated version of our PDF.

About the cyclic document

Consider a sentence $t$ with tokens $A B C D E F$. When the window size is 3, the labeling of each token is as follows: $C: \mathcal{W}(ABC) = \text{watermarked(green)}$, $D: \mathcal{W}(BCD) = \text{not watermarked(red)}$, $E: \mathcal{W}(CDE) = \text{watermarked(green)}$, $F: \mathcal{W}(DEF) = \text{watermarked(green)}$. However, without using a cyclic document, tokens A and B remain unlabeled, potentially creating a system vulnerability. For instance, if a user continuously alters the last token (here, F) and observes the detection confidence $\mathcal{D}(t = ABCDE?)$ of the network, a clear score distinction between watermarked and unwatermarked tokens emerges. If the user tests four characters and finds $\mathcal{D}(t = ABCDEA) \approx \mathcal{D}(t = ABCDEB) > \mathcal{D}(t = ABCDEC) \approx \mathcal{D}(t = ABCDED)$, it's easy to infer that with DE as a prefix, A and B are watermarked tokens, while C and D are not.

To address this vulnerability, we set the entire document as a cyclic document. We label the beginning token A as $\mathcal{W}(EFA)$ and B as $\mathcal{W}(FAB)$, ensuring each token has a corresponding label and thereby avoiding the aforementioned vulnerability.

Thank you for your question. We have updated our PDF with the above content in its updated version (appendix F).

The selection of LSTM network

The primary reason for selecting LSTM is that the input to the watermark detector is a variable-length sequence, and LSTM is a relatively classic RNN structure capable of processing such sequences. Although models like Transformer could be considered, we did not pursue further selection or optimization in this direction because the performance of LSTM was already satisfactory for our purposes. This lack of deliberate choice and optimization in network architecture also suggests that there is still room for improvement in our method.

Reference

Kirchenbauer, et al. "A watermark for large language models."

The contribution of the private watermarking

Please refer to first response in "Responses to all reviewers".

We acknowledge the potential confusion in using "private watermark" to describe our method. Consequently, we have renamed our approach from 'A private watermark' to 'An Unforgeable Publicly Verifiable Watermark for Large Language Models.' All related concepts in the updated version of our paper have been revised accordingly. Next, we will thoroughly explain the contribution of our "unforgeable publicly verifiable watermark".

You have mentioned that a public key encryption algorithm could easily achieve the public verifiability. We assume the "public key encryption" refers to integrating methods like asymmetric encryption or digital signatures, which employ public-private keys into watermark algorithms. While these methods sound promising, its implementation in the context of large model watermarks is not straightforward. And most importantly, it is hard to design a public key encryption algorithm that can make the watermark unforgeable.

For example, in a recent work, Fairoze et al. (published after the ICLR submission deadline) use digital signature technology to achieve public verifiability. However, in the watermark detection process, they still require extracting the watermark features first and then use the public key to verify them. Therefore, under a third-party public detection scenario, the extracted watermark features are exposed to public, which can be directly used to forge watermark.

Our method, however, has unique advantages. Users can only get from our detection network whether a text contains a watermark, without knowing the specific generation details of the watermark. Thus, while the method you propose is an admirable vision, integrating this idea into the watermarking domain is highly challenging, and currently, no feasible solutions exist.

We believe our approach remains irreplaceable in the unforgeable publicly verifiable watermark domain, contributing uniquely to this field.

We welcome further discussion on this topic.

Training detail of watermark generation and detection network

Thank you very much for your detailed question. Indeed, we did not elaborate on all the training details of the watermark generation and detection networks in the original text. However, we have thoroughly described the network architecture, input, and output in the original text. Moreover, the hyperparameters related to network training have already been introduced in section 4. Overall, the training of both networks does not involve any particularly unique tricks. We will provide a detailed introduction here, and this information has already been added to the updated version of the PDF.

Regarding the watermark generation network, firstly, for a token within a window size, an embedding network is used to generate its representation. This embedding network is a fully connected network. Then, all tokens within that window size are concatenated and passed through another fully connected network, which performs a binary classification. This involves first using a sigmoid function followed by binary cross-entropy loss. The formula can be represented as follows:

$L_g = -\frac{1}{N} \sum_{i=1}^{N} \left[ y_i \cdot \log(\sigma(W(x_{n-w+1:n}))) + (1 - y_i) \cdot \log(1 - \sigma(W(x_{n-w+1:n}))) \right]$

For the watermark detection network, the process is quite similar. The representation of each token to be detected is generated using an embedding network. Then, all these representations are fed into an LSTM network. The output of this network undergoes a binary classification. The formula for this is:

$L_d= -\frac{1}{N} \sum_{i=1}^{N} \left[ y_i \cdot \log(\sigma(D(x)_i)) + (1 - y_i) \cdot \log(1 - \sigma(D(x)_i)) \right]$

Impact of watermark on text quality

Please refer to forth response in "Responses to all reviewers".

Reference

Kirchenbauer, et al. "A watermark for large language models."

Fairoze, et al. "Publicly Detectable Watermarking for Language Models."

About Baseline Comparison

Related responses: please refer to the second and forth responses in "Responses to all reviewers".

The key-based detection method in Table1 is the same to the KGW watermark algorithm by Kirchenbauer et al. (2023).

This implies that Table 1 compares the watermark detection accuracy of Kirchenbauer et al. (2023) (denoted as 'key-based') with our unforgeable watermark algorithm. And due to the lack of alternative unforgeable watermark algorithms, we did not conduct direct comparisons with other unforgeable watermark methods.

Moreover, since our watermark generation method is almost identical to that of Kirchenbauer et al. (2023), the impact on text quality should be exact the same to Kirchenbauer et al. (2023).

Despite this, we have demonstrated in Figure 2(b) the variation of detection F1 score and PPL with changes in the $\delta$ parameter. In our method, the $\delta$ hyperparameter is set to 2, indicating that our approach achieves high detection accuracy without significantly affecting text quality.

We have also conducted analysis of text quality changes in machine translation task, affirming that our watermarking method does not significantly impact text quality. More details in the forth response in "Responses to all reviewers".

The updated PDF version now includes additional clarifications and descriptions.

About robustness to paraphrase attack

Please refer to third reply in "to all reviewers" and the table4 in the updated PDF version.

Reference

Kirchenbauer, et al. "A watermark for large language models."

Unclear Definition of Private Watermarking

Please refer to first response in "Responses to all reviewers".

The objective of the private watermark is to detect of the watermark without revealing watermark generation details. This is valuable because if the key is exposed, others can forge the watermark.

Although Kirchenbauer et al. (2023) claim that the key can be concealed within an API for subsequent services, this approach still relies on the generation key for detection, disqualifying it as a true private watermark algorithm. Furthermore, it's important to note that hiding watermark generation details at the algorithmic level does not contradict to additional system design (API).

A relatable analogy is with asymmetric encryption algorithms like RSA, where encryption is done with a private key, but decryption uses a public key. In contrast, symmetric encryption algorithms might employ a key for encryption and offer an API service using the same key for decryption, mimicking asymmetric decryption. However, this is not genuine asymmetric encoding, as decryption still requires the encryption key.

Hosting the decryption or watermark detection process on servers introduces additional complications, such as costly API fees, the need to secure servers against hacking, and trust issues with the service provider. For instance, consider a scenario where an entity accused of generating inappropriate texts is brought to court. It would be unreasonable to rely on the same entity to verify the texts through watermark detection.

We welcome further discussion on this topic.

Explain the "cracking the watermarking rules"

The watermarking rules essentially provides rules on how watermarking is generated. For instance, in the algorithm of Kirchenbauer et al. (2023), watermarking is implemented by dividing the vocabulary into green (watermarked) and red (unwatermarked) lists, then increasing the probability of tokens from the green list at each generation step. The rule here refers to the partition of the green and red list. For example, in Kirchenbauer et al. (2023), for a window size of 2, determining which tokens follow the prefix token 'there' and belong to the green list constitutes a rule.

'Cracking the watermarking rules' fundamentally means inferring these specific rules directly, rather than obtaining the watermark's key. For example, in Sadasivan et al. (2023), a spoofing attack could deduce a specific watermark rule by analyzing word frequency within watermarked texts. If a watermarking algorithm's rules can be easily deduced by such methods, it is essentially not a private algorithm.

A good private watermark algorithm could not hide the generation key but also robust to the attacks that try to crack the watermarking rules.

About the "implement watermarking in a privacy-preserving manner"

Thank you for your question. "Privacy-preserving manner" refers to the ability to detect watermarks without needing the key used in the watermark generation process. Indeed, we acknowledge that the original statement was somewhat confusing. We have clarified this point in the revised PDF provided.

What are "definite labels" (p9)?

In our context, 'definite labels' refer to labels with high confidence levels, where the label here refers to whether a text contains a watermark. The corresponding z-scores for data with 'definite labels' significantly deviate from the threshold value used in the public z-score based detection.

About robustness

Please refer to third response in "Responses to all reviewers" and the table5 in the updated PDF version.

What does FFN stand for in EQ 2?

The term "FFN" here refers to a fully connected classification network. We apologize for any confusion caused and have provided a revised explanation in the updated version of the PDF.

How many parameters does the LSTM have?

Our LSTM only comprises five layers, with an input dimension of 64 for each unit, an intermediate output dimension of 128, and a final output dimension of 1 for the output logits.

Therefore, the parameters of LSTM are negligible compared to those of large language models.

In EQ 3, is "P" supposed to be the probability? Earlier, it was defined to be the logit score.

P indeed represents probability, and P_n was previously used to denote a special probability symbol. However, considering potential confusion, we have now adopted L_n to represent logits. This change has been clarified in the updated version of our PDF.

In EQ 8, what is f ?

In this context, 'f' represents an ideal generation network, corresponding to the 'g' function mentioned in EQ9, where 'g' refers to an ideal detection network. Our aim here is to demonstrate that training 'g' using 'f' is significantly simpler than the reverse process of training 'f' using 'g', which forms the basis of our algorithm's privacy. Thank you for your question; we have addressed this point in the revised version of our PDF.

Without using the public key, an attacker could sample the model N times and fine-tune a public model to generate watermarked data.

I would expect to see a graph that shows the number of watermarked samples (obtained from the provider's model) versus the detection accuracy (for some z-score threshold).