Undetectable Steganography for Language Models
Authors: Or Zamir
Venue: Accepted by TMLR ()

Abstract: We introduce a cryptographic method to hide an arbitrary secret payload in the response of a Large Language Model (LLM). A secret key is required to extract the payload from the model's response, and without the key it is provably impossible to distinguish between the responses of the original LLM and the LLM that hides a payload. In particular, the quality of generated text is not affected by the payload.
Our approach extends a recent result of Christ, Gunn and Zamir (2023) who introduced an undetectable watermarking scheme for LLMs.

Published in Transactions on Machine Learning Research (10/2024)
Undetectable Steganography for Language Models
Or Zamir School of Computer Science Tel Avio University
orzamir www.er.twwaaae...........
Reviewed on OpenReview: https: /atp:////ppeeevee/e net/ forum? id= fa6aloMMiiz
Abstract
We introduce cryptographic method to hide arbitrary secret payload in the response of a Large Language Model (LLM). A secret key is required to extract the payload from the model's response, and without the key it is provably impossible to distinguish between the responses of the original LLM and the LLM that hides a payload. In particular, the quality of generated lext is not affected by the payload. Our approach extends a recent result of Christ, Gunn and Zamir (2023) who introduced an undetectable watermarking scheme for LLMs.
Prompt: Write an email asking my professor Prof. Hannity to not make the final exam in Machine Learning 101 too difficult.
Response: Dear Professor Hannity,
hope this email finds you well. am writing to respectfully request that you consider the level of difficulty for the final exam in Machine Learning 101. While am confident my understanding of the course materials and have put in a significant amount of effort throughout the semester, I do have concerns about the potential difficulty of the final examn
As you may recall, several students in my previous sections of Machine Learning have found the final exam to be very challenging, leading to frustration and disappointment. While I understand that the course is intended to push students to their limits and beyond, believe that some relaxation of the latter may be in order.
would kindly ask that you consider reducing the difficulty of the final exam or offering some additional supports or resources to help students prepare. I believe that this could enhance the learning experience
Hidden Payload: OZ (Encoded as 10 bits.)
We asked Llama 2 to write an email urging a professor for an easy exam, intended to be sent anonymously. Nevertheless, the part of the response shown above secretly encodes the initials of the user who used the LLM. This secret payload was encoded without modifying the response distribution at all.
Figure 1:
1 Introduction
As the applications of machine learning models generating human-like text become widespread, concerns for misuse proportionally rise. As detection of text generated by Large Language Models (LLMs) seemingly approaches infeasibility (JMM200 KSK 23 SKB+23 CBZ 23), the ability to intentionally plant watermark in L.M--generated text becomes the most viable approach to differentiate LLM-generated from human- generated text.
A long line of works showed that a watermark can be planted in LLMs by altering the output texts FF1 QZL+20 YAJK23 MZ23 K3W+23a) Recently, Christ, Gunn and Zamir (CGZ23) showed that a watermark can be planted LLM-outputs without altering the distribution of responses. Informally, CGZ show that any LLM can be modified such that: 1) It is computationally infeasible to distinguish between the original and

---

Published in Transactions on Machine Learning Research (10/2024)
the modified LLMs unless you hold secret key, even when you are allowed to make many adaptive queries, 2) With the secret key, outputs of the modified LLM can be detected as watermarked. The importance of this notion of undetectibility is that it formally guarantees that the quality of text does not degrade (or change at all) in the process of planting the watermark.
In this work, we extend the watermarking scheme of CGZ to plant an arbilrary payload into the LLM response, while still maintaining the same property of undetectability. This implies, for example, that an LLM may secretly hide session-metadata (such as the user's name, the time, the prompt used) in the response it gives. In particular, it can extend the ability of detecting text generated by the LLM to the ability of also knowing who used the LLM or when they did so. It also mcans that even an LLM running off-line may use the responses it gives to covertly leak internal information to those who will later be exposed to the seemingly-clean LLM responses. The main technical tool we use to transform the CGZ scheme from watermarking to embedding a message, is incorporating a dynamic variant of Error Correcting Codes with feedback.
The process of encoding hidden message into a given channel (e.g., picture natural language) is called Steganography and was extensively studied in many domains (HvALOS DIRRO9 KJGR21 dWSK The unique property of our setting, though, is that in the case of LLM responses the distribution of the channel is unknown. The hidden message should be recovered from the response of the L.M,, without, knowing what the prompt used to generate the response was. In particular, the process of decoding the message must be agnostic to the distribution of responses. Recent manuscripts (FCT+ 23 WYC+ YAK23) embed messages in LLM responses, but do so by altering the distribution of responses, similar to the non-undetectable watermarking schemes. In particular, those methods affect the response distribution and may degrade the quality of generated text.
Under realistic assumptions which we verify empirically, the amount of hidden bits our scheme can encode in an LLM output is linear in the length of the response, which is asymptotically optimal. Our scheme only negligibly affects the complexity of the generation process and is thus easy and efficient to deploy. While this paper is theoretical nature and the properties of the suggested scheme are proven rigorously, we also implemented the scheme and provide empirical examples. An open problem not addressed in this paper is that our encoding scheme is not very robust to edits of the generated text, discuss this in length in later sections.
1.1 Organization of the paper
In Section 2 we give the formal definitions of the problem's setting, and state the main theorems of this paper rigorously. We also give the necessary preliminaries. In Section 3 we give a quick overview of the CGZ watermark. In Section | we give an high-level overview of our scheme. Then, in Section 3 we introduce simple dynamic error correcting code with feedback, which later as building block. Finally, in Section 0 we give and analyze the full scheme. In Scction 7 we discuss implementation of the scheme and some empirical evaluation of it. In Section S we discuss limitations of our scheme, and in particular robustness to editing. We follow with open problems and conclusions.
2 Model and Preliminaries
Many of the notions in this soction are adapted from (CGZ23), the last subscction contains our new definitions and theorems for Steganography in LLMs.
2.1 Preliminaries
Let À be the security parameter, we denote by negl(A) any function that is in O ((()) for every polynomial p(-). As is standard in Cryptography research, we think of as the "key size", and of running times that are super-polynomial in as "infcasible". We denote by log and In the logarithm with base two and the natural logarithm, respectively. For sequence s = (.... s.....) we denote by sii j] the sub-sequence (s.....,s)) The Hamming distance between two vectors is defined as the number of indices on which they differ, that
2

---

Published in Transactions on Machine Learning Research (10/2024)
is 22) = [i| * 2/H. We denote by z || y the concatenation of the vectors 2, y, and by len(v) the dimension of the vector v.
Pscudorandom function (PRF). Let F= = {F&: (0, (0,(4 - {0, 1) A E {0,1)*} be a family of functions. F PRF if Fk is efficiently computable and for all probabilistic polynomial-ting distinguishers
D,
( =1] - PP(DrO(1) =
Pr (0.))
x negl(A)
where denotes random function from {0, 13 to {0, 1),(),((A), PRFs are standard cryptographic primitive equivalent to one-way functions and can be constructed from standard assumptions (GGM86 HiLL (og). Intuitively, PRF is simply function that is indistinguishable from totally random function without knowledge of the secret key k that parameterizes it.
2.2 Language Models
We adapt the definition of (CGZ23) for language models, which in turns follows that of (2G)) We will often refer to language models simply as models.
Definition 2.1. A language model Model over token set T is a deterministic algorithm that takes as input a prompt PROMPT and tokens previously output by the model x = Fi-1). and outputs a probability distribution P: Model(PROMPT,, x)) over T.
A language model Model is used to generate text as response a prompt by iteratively sampling from the returned distribution until special terminating token done T is drawn.
Definition 2.2. A language model's response to PROMPT is random variable Model E T that is defined algorithmically as follows. We begin with an empty list of tokens = (). As long as the last token in x is not done, we draw a token x; from the distribution (PdMMPPRO and append it to æ. Finally, we set Mode((PROMPT) = x.
We assume that our model never outputs text of length super-polynomial in X.
2.3 Entropy and Empirical Entropy
For probability distribution D over elements of a finite set X, the Shannon entropy of D
H(D) = E [- log D(x),,
z~D
where D(x)) is the probability of x in the distribution D. The empirical entropy (also known as Shannon information) of x in D is simply - log D(x). The expected empirical entropy of D is HD).
The following definition of empirical entropy of a model's response is taken from CGZZ3
Definition 2.3. For language model Model, a prompt PROMPT, and a possible response I E T*, we define the empirical entropy Model responding with æ to PROMPT, denoted by H. (Model, PROMPT, as
log Pr Model (PROMPT) =
Note that in expectation, Definition 2.3 simply captures the entropy in the response generation. That is, we have
[. (Model, PROMPT, x)] = (Model (PROMPT)).
where x ~ Model (PROMPT).
The following definition naturally generalizes empirical entropy from whole outputs to substrings out of model's output.
3

---

Published in Transactions on Machine Learning Research (10/2024)
Definition 2.4. For language model Model, prompt PROMPT, possible response E T', and indices i.j E [,]]] with i S we define the empiricnl entropy substring [i, of Model responding with x to PROMPT as
H 5. (Model, PROMPT, x) ==
log Pr Model (PROMPT) [1: [] = x|i: =
Model (PROMPT) [] (i-
-[)- 1)] = =|1 (i 1)]
2.3.1 Empirical Entropy in Natural Language
conclude that in natural language the entropy per unit of text (e.g., a word) is usually constant throughout the text. In particular, the empirical entropy LLM response is expected to be linear in the length of the text, and roughly uniformly distributed among the different tokens that assemble the response. This intuition was empirically verified by (CGZ23). We reaffirm the above in Section in which we also run empirical evaluations.
Studies in linguistics (G02 CLA17 SL22
2.4 Steganography for LLMs
In this section we finally define rigorously steganography for language models. We first explain the definition intuitively. During the setup of the scheme, we generate a secret key k of size X. To generate response, we use method Steg, that together with the key k, receives a prompt PROMPT and secret message PAYLOAD. A retrieval method Retr, should be able to retrieve the hidden PAYLOAD from an output generated using Stega: while also using the secret key k.
Definition 2.5 (Steganography Scheme). A steganography scheme for model Model over T is a tuple of algorithms W = (Setup, Steg, Retr) where:
S + h outputs secret key, with respect to a security parameter X.
Steg, (PROMPT; PaYLOAD) is a randomized algorithm that takes input prompt PROMPT and payload PAYLOAD, and generates response in T
(etr T an algorithm that takes as input and returns as an output sequences in T*
The most important property the steganography scheme we present in this paper undetectability. Intuitively, we require that without knowledge of the secret key, Steg, (PROMPT, +) and Mode((PROMPT) are indistinguishable even to user allowed to make many adaptive queries. The payloads used in Steg, do not affect this property.
Definition 2.6 (Undotectability). A steganography scheme W (Setup, Steg, Retr) is undetectable if for every security parameter X and all polynomial-time distinguishers D,
Pr D Model, Model (12) + 1]
Pr kt-Setup(1>)
Model, (12) - 1]
S negl(A))
where the notation D2,,02 means that is allowed to adaptively query both O and O₂ with arbitrary prompts.
Another important desired property is that Retr, should succeed retricving the PAYLOAD from the output of (tegx(PROMPT) PAYLOAD). Such a successful retrieval inherently requires making assumptions on the length of the payload and the entropy of the model. It is for example impossible to encode arbitrary payload
4

---

Published in Transactions on Machine Learning Research (10/2024)
longer than the output in the output, or to plant any payload at all in deterministic model (thus, without any entropy) while remaining undetectable. The best possible result is thus encoding HeoMedel, PROMPT; x)) bits of payload in an output + (PROMPT PAYLOAD), this is because the empirical entropy of an output exactly quantifies the number of entropy bits used for its generation.
We achieve the above best-possible bound asymptotically yet we require two additional technical conditions. First, we can plant payloads only when (Model, PROMPT, x) (2)). Intuitively, this is because outputs with very low empirical entropy (with respect to the security parameter) show up too frequently and thus can't be modified while maintaining undetectability. The necessity of this condition, that also appeared in the CGZ result, is proven in (CGZ23). Second, we require that the empirical entropy is spread somewhat uniformly throughout the output x. This appears to be necessary for technical reasons (e.g., avoiding a token in the
scenario in which the empirical entropy is high solely due to a single cery-low-probbble response), yet could potentially be relaxed future works. As discussed in Section 2.3.1 and empirically reaffirmed in Section 7 this condition satisfied by natural language in which the entropy is roughly constant per each unit of lext.
A semi-formal version of the theorem follows, the formal one appears in Section 6
Theorem (Informal version of Theorem 6.3). Fir a model Model. Let PROMPT, PAYLOAD be strings. Condi- tioned on the empirical entropy of a response y generated by Steg, (PROMPT, PAYLOAD) being high enough, the expected length of the prefizes of PAYLOAD and Retra(y) that identify is at least O(lenly)).
The definition of high enough, formally stated in Section B roughly means that for any consecutive part of the response consisting of a large enough number of tokens, the empirical entropy in that part is at least the square root Ω (VT) of the length. As discussed in Section 2.3.1 and verified empirically in Section 7 in natural language we actually expect the entropy to grow linearly with the length of the text, much higher than the required square root. Under this condition, the thcorem guarantees that a response of length L will allow retrieving the first (LL) bits of the PAYLOAD, which is (up to constants) the best possible.
3 Overview of the CGZ Watermark
This section is adapted in its entirety from CGZ (CZA) and contains high-level description of their watermarking scheme.
We first simplify the definition of a language model (Definition 2.1] by assuming that the token set is binary, T f0, 13. We may assume this without loss of generality due to a straightforward reduction that appears in Section 4.1 of CGZ. We will implicitly use this reduction throughout our work as well.
The intuitive idea behind the CGZ watermark is planting a watermark not by changing the model's distribution, but by correlating the randomness used by the model with the secret key. We begin by describing simplified approach that works only for generating single response, of length bounded by some parameter L. Let k= = (k1, .2....,ki be the secret key, chosen by drawing each h; uniformly and independently from [0. 1]. To generate a response to a prompt PROMPT, we run the model as intended yet use k; to determine the random choice in the i-th response token generation. Let p. denote the probability, according to the real model with the previously chosen tokens as prefix, of the i-th token being 1. The watermarked model outputs 2; = if l S P. and r; = otherwisc. Crucially, as k; was chosen uniformly, the probability of x; 1 is exactly Pe and hence the output distribution of the model is not affected all. On the other hand, we now expect some correlation between 2; and k;
For cach response bit Zi, the detection algorithm may compute the following score, that depends on the key and on the response but not on the prompt. the model, or the distributions pi.
In
if xj = 1 if o;; 0
s(I;, ki)
Kr In
I-k
5

---

Published in Transactions on Machine Learning Research (10/2024)
Given string (#1....,, xz), the detection algorithm sums the score of all bits
c(x) Σ s(z,, ki).
The main observation is that the score is higher in responses generated by the above procedure than it is for unrelated strings. In non won-watermarked text, the value of k; is independent of the value of z,. Therefore, s(I;, ki) is simply an exponential random variable with mean 1:
Bis(r,, J In(1/z) dr 1,
and we have [x(c(x)- |ar]] = O. For watermarked responses, on the other hand,
p: 1
E Av
(l k2)
In dx +
In
dr
0
x
Pi
Pi
1
1-
1
In
dx
+
In dx
00
x
1 +
In Ps - -(1 - p.) 1mn1 - -p:)
= 1 + ln( Hp:),
and the total expected score is
E [(((r) - |x|] = 2 (222HMMMM((PPOMPT))
We thus observed that at least in expectation, the score of watermarked texts is larger than that of arbitrary texis, and that the difference between those quantities is roughly the entropy in the response. To make this observation algorithmically useful, considering expectations is not sufficient, as we need to set some score threshold for detection and analyze the probability of the score passing this threshold in each of the two cases. This analysis will not be repeated in this short overview and appears in CGZ.
To avoid having an upper bound L on the length of the response, and to reduce the length of the key k we
use Pscudo-Randon Function F (PRF, as defined in Section 2 The key will now simply be a random string of length X, and we would implicitly set k; == (t). By the definition of a PRF, those values are indistinguishable from independently chosen random values.
The final obstacle is remaining undetectable even when many queries are allowed. In the above sketch the choice of the key fully determines all randomness, and thus for example the same prompt will always get the same response. To overcome this hurdle, begin the generation of each response with using real randomness (and not the key) to sample tokens, while counting the empirical entropy of the response prefix generated so far. When the response prefix passes a threshold of empirical entropy X, we denote the response's prefix as and start running the previous scheme with r as an additional input to the PRF. That is, after we set the prefix r we use the value (r, i) to generate the i-th token. In the detection, we will enumcrate over all possible prefixes of the response as r. In CGZ, it shown that because the prefix r is set only after enough entropy was used, it has negligible probability ever repeat itself in different queries. Thus the inputs to the PRF calls are each unique and the scheme becomes undetectable even with many queries being made.
The pseudo-codes for generation (Algorithm D and detection (Algorithm 2 of the watermark appear in the Appendix. In CGZ, those algorithms are then generalized to also support the detection of the watermark from a substring out of the response and not only from the response in its entirety as is sketched above.
4 High-Level Overview of Our Scheme
In this section we give an overview of our construction, with the rigorous details appearing in Scctions 5 and 5 As in the CGZ overview in Section 3 we again assume without loss of generality that the token space is binary.
6

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 1: Watermarking algorithm Wat::
A prompt (PROMPT) and secret key Result: Watermarked text F1,..,,LL i+1;
Data:
H t 0;
while done & (i-1) do
Pi t Model(PROMPT, 21. Tz-1);
if H < then
// Collect more internal entropy
Sample (I..P) < p;) with probability pt, otherwise (0, Pi):
H + H logp:
if H 2 then
(I (I))..., 4;);
end
else
// Embed the watermark
I₁ - (f, S p.l;
end
i ++i
end
Algorithm 2: Detector Detect&
Data: Text Zi...., 2g and a secret key
Result: True or False
for E [7]] do
(00) (2), (#1,...;2;)) 22);
Define // (0) = Ij. Fa( (x((1()))) .5) + (1-x1)))) (011-xy)(6 21) -1-(((((0)))) Fx((r",,)) ,)) for j e [A]:
Ej=tt In(1/u/) (1) > (L +>T then
if
return True;
end end return False;
As a first attempt, we notice that one may generalize any watermark into a steganography scheme by using several keys. Let kı,..., be m different secret keys, and setup a watermarking scheme with each of them. To encode message [m] within a response, simply use the watermarking instance corresponding to kę generate said response. In the retrieval step, we will use the detection algorithm with every key kj to find which of them was used. While undetectability is trivially preserved, as only use undetectable watermarks to generate responses, the scheme becomes infeasible as soon as m isn't very small. This is because both the rate of ffalse-positives and the detection time grow by multiplicative factor of m. In particular, encoding bits of information will cause a multiplicative factor 2 in the running time of the retrieval algorithm, and will also require that the false-positive rate of the watermarking scheme be much smaller than 2-
A reasonable next step then, is breaking up the payload into smaller parts (say, characters or bits), and encoding each of those parts separately in similar fashion to the previous suggestion. One subtle issue to overcome while implementing this idea is that partitioning the response into those smaller chunks is not straightforward. This is because we know a successful watermarking requires high empirical entropy, and it is not known in advance what parts of the response would contain high empirical entropy. Moreover, the retriever needs to be able to use the same partition as the steganography algorithm. We solve this problem by implicitly defining the partition to chunks using the detoction score itself: Let be some score threshold be decided later. Denote the first bit of the payload by b E {0, 1}. We start planting the payload in the same way the CGZ watermark is embedded, but with b as additional input to the PRF. That is,
7

---

Published in Transactions on Machine Learning Research (10/2024)
the randomness used in the i-th token is (e. The retriever would compute the scores for both options of b over more and more tokens until one of the two scores passes certain threshold determined by I. For example, we can consider the minimal prefix of the response z|: a] for which (c(æ[: i]) - i)/vi > t with respect to the score computed with either b = 0 or = 1. Crucially, both Steg, and Retry can compute those scores, so both can compute the index i in which one of the scores passed the threshold for the first time. Thus, both are able to agree on the end of the chunk encoding the first bit of the payload, and thus can iteratively restart this process with the next bit of the payload and so on. Following the CGZ analysis, a threshold of roughly t = X is required to make sure the correct bit is always the first one to pass the score threshold, otherwise the false-positive rate of passing the score threshold is non-negligible. This means that whilst the decoding time and general error rate are now low enough, we still can't encode payloads that are too long. Even if every token contains constant entropy, only (L//)) bits of the payload can be encoded in a response of length L. Since À is rather large, we should desire to get this quantity down to the optimal (()).
Finally, we use Error Correcting Codes (ECC) to lower the threshold and in turn increase the number of hidden payload bits. Intuitively, if instead of setting R À we set. to be large constant, then false-positivee do happen, but only with small constant probability. Thus, if instead of encoding the bits of the payload itself, we would encode the bits of an ECC applicd to the payload, we should be able to recover the payload even if a constant fraction of the bits were transmitted incorrectly. This would reduce t from À to (11 as desired. A problem that remains is that applying a standard ECC "scrambles" the message and thus if only a prefix of the code is successfully hidden then it would be impossible to decode anything out of the payload. For this reason, in Section 3 we define and construct Dynamic ECC, this is code in which for every i, the first í bits of the code can be used to retrieve the first @(i) bits of the message. Thus, a response of size L would hide the first ((L) bits of the payload. To significantly simplify the construction of the ECC, we use the fact our construction provides noiseless feedback. As mentioned before, during the encoding process, Steg, can also simulate Retr; and thus knows what bit will be detected by the retriever at each step. Thus, the ECC can depend on whether or not each previously sent bit was transmitted correctly. In the construction of Section 5 we actually use a ternary code alphabet rather than binary, which doesn't 't affect the sketch of the construction much.
We finally note that to support multiple queries, we use the same idea of CGZ sketched in Section 3 and begin by observing enough real entropy to set unique prefix r, the following random choices will be made using (r, i, b). For the detector to find the correct prefix to use as r, we need to use the first X bits of entropy after setting the prefix to place a normal watermark, which the detector would use to verify the choice of r. This means that to be undetectable with many queries, we start encoding the payload only after the first (()) tokens (or bits of entropy). As long as L. = (AA)) this does not matter asymplotically.
5 Dynamic Error Correcting Code
Error Correcting Codes (ECOs) are the means to compensate for errors in the transmission of messages. An ECC encoding is a function Enc E - I from messages of length k over alphabet E, to codewords of length n over alphabet P. The rate of a code is R(Enc) := k which signifies how efficient the code is. The (relative) distance of code is ((Fnc) := 1 min (nc())AFnn((
which is twice the fraction of corrupt indices in a codeword that still allows decoding it to the original message. A code (or a family of codes) is considered good if both its rate and distance are constant, which means that the length of messages is only expanded by a constant factor, yet a constant fraction of errors can be corrected. F.COs are extensively studied and it is long known that good ECCss can be constructed, even when Σ T=-= Fz. (Ham50 Gi52 V7
Jus72 SS06
An ECC with feedback is an ECC in which we transmit the symbols of the codeword Enc(x) one-by-one, and immediately receive feedback with regards to whether error occurred in transmitting this symbol. The following symbols we submit may adaptively depend on the foodback received so far. We say that the feedback is noiseless if the feedback received is always reliable. If the errors in transmission occur randomly (i.e., each transmitted symbol has the same probability of becoming corrupted), then it turns out that noiseless foedback does not improve the parameters of the best possible ECC. On the other hand, if the small fraction of corrupted symbols is chosen adversarially, then noiseless feedback does improve the best possible distance. Feedback also appears to allow simpler and more efficient encoding and decoding schemes. (Ber64 Cov88)
8

---

Published in Transactions on Machine Learning Research (10/2024)
We define natural generalization of ECCs, in which the length of the message (and hence also of the code) is not known in advance. We call those Dynamic RCCs, We would require that for any k' S k, the first k' symbols of the message can be decoded from the first O(k) symbols of the codeword, even if a small fraction of those codeword symbols are corrupted. This definition is similar yet weaker than the definition of Tree Codes (Sch93 Sch96).
Definition 5.1. For alphabets Σ, T, a family {Enck) of functions Ence : E* - D is called a Dynamic ECC if for every & E 28, the function Ency >* + 1 is an ECC, where
Enck (z) == Enc1 (al: 1]) |I Encz(2|: 2)) ... Encc(x);
Th max (Enca (x)). =EE
In simple words, a Dynamic FCC a family of standard ECCs where the codeword corresponding to the a prefix of message, always a prefix of the codeword corresponding the entire message.
k. Definition 5.2. The rate of Dynamic ECC is R(Enc) == infRen R(Ency) = infsen ni. The distance of it is 6(Enc) == infRen 8(Enck).
In similar manner, we also define a Dynamic ECC with (noiseless) feedback to be Dynamic ECC in which after each symbol transmitted we receive feedback as to which symbol was received. We next present simple construction of Dynamic ECC with feedback where |Σ] = 2, |T] = 3, and both the rate and distance are constant. This construction is rather straightforward and is similar to constructions used in slightly different scttings (EGH15)
Theorem 5.3. For any e E (0, 2)) there erists a Dynamic ECC with noiseless feedback with - 2, 3, in which e fraction of errors can be corrected and ngg 1-2e 1- Both encoding and correction take linear time.
We think of the message alphabet as binary Σ {0, 1}, and to the codeword alphabet we add an additional symbol r = {).. We would think of the symbol 'x" as "backspace". Intuitively, we will always compute the message that is the decoding of what the receiver saw so far, and if it is consistent with the input we simply send the next bit of the input. If it is not consistent with input, we will send a "backspace" to indicate that the last symbol is incorrect. We will do so iteratively.
For a sequence y = (yr...., yn) T* we recursively define decode(y) to be decode(yl: (n - (n) || (yx) if yn E 1), and decode(y[: (n 1)]){: -1] if yn ='-', where v|: -1] means removing the last symbol from the vector (unless its emply). As the base case, have decode(() ()-
For message x = (z1,..., 2x) E E* and a previously transmitted (partial) codeword (VI....,yh) E r we define the longest agrecing prefix of and the decoding of as
last v) = max (i x/: i] = decode(v)[: i]}.
We then define the length of the wrong sulfix of the decoding of y as sufs(a, u) len(decode(v)) last( 9)- Given message and partial codeword y, define the next symbol to be sent as next v) a't' if suff(xr,)) y) > 0, and as next(x, y) = 2 [[last(x,)) y) + 1] otherwise. Our protocol is thus simple, if x is the message and is the codeword received by the receiver so far (which we know using the noiseless feedback), then the next symbol we send is next(xx
Lemma 5.4. Let x E* be a message and y E 1 be partial codeword received by the receiver according to the described protocol, and assume that at most en of the symbols in were received differently than sent by the protocol. Then, last(z, y) 2 n..
Proof. For any partial received codeword y' we define the potential function Φ(x, = last v/) - suff(z, (2, v').
We first show that if the next token received correctly then the potential increases by one, that is, $(x, yf || next(x, y')) $(x, s²) + We show this by considering two cases. If suff(z, y') = 0 then decode(y') = xl: last y²)] and next(x, x: aasss (x, (2, 1], thus decode(z,,)) y nex)(x,
9

---

Published in Transactions on Machine Learning Research (10/2024)
æ/: (2s v/) + 1]. Otherwise, suff(2, s/) 0 and next(x, ='t', and hence suff(r, yf || next((z y/)) sulf(z, v/) 1.
Next, we show that the next token is received incorrectly then the potential decreases by one, that is P(z,y' || 8) = max(0, ((x, -1)-1) whenever 8 $ next(x, y²). We again consider two cases. If suff(2, v/) > then we have E {0, }] and turn suff(a, v' 6) suff(r, 3/) + 1. Otherwise suff(x, v/) and we either have suff(z, y'
1 if d'+' or have last(x, y s) max(0, last(x, 3/) - 1) if ='t'.
We conclude that if out of the symbols in y were received incorrectly, then
(xx,)) v) 2 1 (n e) 1-een 2e 2 en..
On the other hand, suff(ar, v) we also have last(xx, (xx.
Proof of Theorem 5.3 Denote by 7i = 1- 1. Let x be a message and the first ny tokens received by running the protocol. Assume that at most Eng out of those tokens were received incorrectly. By Lemma 5.4 we have
last(ar,) y) 2 (1 - 2z)nx 2 k.
Hence, decode(y)(: k] correctly retrieves x/: k).
6
Our Scheme
we begin by analysing a scheme in which only single query is undetectable. Then, Section 6.1 we apply the same idea CGZ to go from undetectability for one query to complete undetectability. An intuitive explanation of our scheme is covered in Section
As in the overview of Section 8
Algorithm 3: One-query steganography algorithm Steg,
Data: A prompt (PROMPT), a payload (PAYLOAD), and secret key k Result: Response FL,
i 1;
code ():
score, t for o E (0,1,++) +); len +
next < next code);
while done & (x1,..., 14-1) do
P: < 2I. S prl:
2; - (f
score len <- score len + 1;
for {0, [-) do
score, f- score, + s(z,, F o)):
if (score, score len) score len then code code (o);
score, + 0 for E {0,1, score len + 0:
next + nex((PAVLOAD, code);
break;
end end - ++i+1; end
Algorithm naturally follows the sketch of Section while using the ECC (and notation) of Section Let's 's informally describe the algorithm in words. The algorithm depends score threshold i to be set.
10

---

Published in Transactions on Machine Learning Research (10/2024)
later. We apply the Dynamic ECC to the message PAYLOAD, and denote by nert the next symbol we are supposed to transmit according to the ECC. We start generating response tokens following the CGZ scheme, by comparing the actual distribution to the PRF value Fi next). As the PRF value depends on next, a correlation between the randomness we use and the token we are attempting to transmit is created. After each generated response loken, we also emulate the retriever: Ignoring our knowledge of nerl, for every code symbol a E {0, 1,) we compute the score (as defined in Section 3 of the response tokens we saw so far. We wait until the score of some symbol Ø, normalized with respect the number of tokens involved in the score computation, passes threshold t. That is, until
score, - score len
> t.
Vscorre len
When this happens, we view a as the symbol received by the ECC receiver. While o = next is supposed to be more likely, the symbol could be incorrect. Whenever we add a symbol to the code, we restart our computation of the score and start transmitting the next code symbol. Algorithm | shows the retrieval process, which identical what emulated within the steganography algorithm. Note that both algorithms have a linear running time.
Algorithm 4: One-query retriever Retr,
Data: Response ,,,,,,,, and secret key k
Result: Retrieved payload PAYLOAD
code t ();
score, + 0 for a E (0,1,
score len + 0;
for i == 1,,..... L do
score len <- score len + 1;
for (0,1,+) do
score, f score, + s oi); if (score, score (eve__en)_ / / scoorereehhaa len then code code (o); score, + 0 for E 10,1,+};
score len + 0;
break;
end end end
return decode(code);
We first observe that the distribution of the response is indistinguishable from the distribution of the original model (when single query is made).
Lemma 6.1. For any Model and any PROMPT, PAYLOAD, L, the distribulion of Steg, (PROMPT, PAYLOAD) over random choice of key lo is indistinguishable from the distrilution of Mode((PROMPT).
Proof. The proof is rather straightforward and follows CGZ and its overview in Section 3 we replace each time (i, next) is usod (to determine æ;)) with new uniformly chosen value in [0, 1], then the distribution of Model is completely unaffected. Using PRF instead of "fresh' random values indisitinguishable long as don't use the PRF the same input more than once. As each input to the PRF consists of the (unique) index i, we never call it on the same input.
We should next show that Rete, (PROMPT, PAYLOAD)) successfully retrieves PAYLOAD. As discussed Section 2.4 doing so requires making assumptions on the empirical entropy of the generated response. We prove that relatively weak assumption (which in particular covers the case of natural languages) is sufficient,
11

---

Published in Transactions on Machine Learning Research (10/2024)
yet it is very likely that the proof can be adapted for other conditions well as the algorithm itself is quite flexible. We also note that in the proof we don't 't optimize for constants but for simplicity (of proof), the empirical evaluation in Section 7 implies that the actual constants are far better than in the following proof.
Definition 6.2. Let h = (hi...., hL) be a sequence of empirical entropies (i.e., non-negative numbers). We say that h is ro-saturated if for every consecutive subsequence of h of length r 2 ro. the sum of entropies is at least 10/rlnr. That is, for every r 2 ro and 1 i (r - 1), we have Li=i hg 2 10/rlar.
For example, if the empirical entropy in each consocutive block of b tokens is at least some constant > 0, then the empirical entropies are Ô saturated. This is because a consecutive block of bk tokens contains
at least ak entropy, which is larger than 10 if k = Ω (++) Hence, natural language which has this property (as discussed in Section 2.3. 1) is O())sattratedd In fact, the entropy of natural language grows linearly with the length of the text, while our condition is merely for it to grow faster than the square root of the length of the text. We verify these claims empirically in Section
Finally, we prove that if the empirical entropy of response is ((1)-saturated and the response is of length L, then in expectation at least the first (LL) bits of the PAYLOAD are retrieved correctly.
Theorem 6.3. Fix a model Model and an integer To, there exists a choice of threshold t for which the following holds. Let PROMPT, PAYLOAD be strings. Conditioned on the empirical entropy of a response y generated by (PROMPT, PAYLOAD) being ro-saturated, the expected length of the prefizes of PAYLOAD and (y) that identify is at least ((len(y)/ro).
The proof of Thcorem 6.3 is deferred to Appendix A
6.1
Complete Undetectability
To move from undotectability of a single response to the general undetoctability defined in Definition 2.6 we simply repeat the "trick" of CGZ as overviewed in Section The complete details are deferred to Appendix
7 Empirical Evaluation
T Algorithms 3 and from Section 6 that provide undetectability for a single query. We did so for simplicity and as we only aim to evaluate the new contributions of this paper.
We implemented
In Figure 2 we estimate the number of message bits we can hide a response of a certain length. For each length of response, we ran our scheme for 100 times using the LLM model GPT-2 (RWC+ 19 on a randomly chosen prompt from the list of example prompts provided by OpenAl their GPT-2 webpage ? We ran it with threshold parameter t = 2, which we didn't optimize. As expected, it is evident that the number of hidden bits grows lincarly with the length of the response. In Figure 3 we detail the decoding process of the example shown in Figure D generated using the 7B parameters Instruct version of the Llama 2 model developed by Meta (TMS+23). We did not optimize for constants. The takeaways from this section are twofold; First, we show that the implementation of our scheme simple and the run-time overhead is minimal; Second, we empirically support the claim from Soction 2.3.1 that the empirical entropy in LLMs grows linearly with the length of the response.
8 Limitations and Open Problems
The main issue we did not discuss so far is robustness to editing. That is, can the payload be recovered even if the model's response somchow odited? We mainly leave dealing with robustness to future work, yet next list. a couple of observations regarding robustness. In CGZ (CG223) the watermarking scheme is adapted to "restart" aace-in-a-while that the watermark will be detectable from any long enough consecutive substring of the response (and not only from the entire response). The same modification can easily be applied to
Code available httpp:://ggttabb.cm//////aaataae
models
12

---

Published in Transactions on Machine Learning Research (10/2024)
Hidden payload length, in bits.
20
17.87
0
14.75
15
11.65
10
8.01
5
4.19
0
20
40
60
80
100
Response length, in tokens.
Figure 2: Plot of the number of successfully hidden payload bits, by length of response. Experiments GPT-2 with a random choice of an example prompt taken from the OpenAI website. The experiment was performed 100 times for each response length.
Prompt: Write email asking my professor Prof. Hannity to not make the final exam in Machine Learning 101 too difficult.
Response: Dear Professor Hannity,
hope this email finds you well. T am writing to respectfully request that you consider the level of dilficulty for the final exam in Machine Learning 101. While am confident my understanding of the course materials and have put in a siguificant
amount of effort throughout the semester, do have concerns 0 about the potential 1 difficulty < of the final exam.
As you may recall, several students in my previous sections of <- Machine Learning have found the final exam to be very challenging understand that the course is intended to push students to their limits and beyond, believe that some relaxation of the latter 1 may be in order.
leading to frustration 1 and +- disappointment 0 While I f-
would kindly ask that you consider reducing the difficulty of the final exam or offering some additional supports resources to help students prepare. 10 believe that this could enhance
Error Correcting Code: 11101=+111:00--1000
Hidden Payload: "OZ', encoded as 01111 11010.
Figure 3: A breakdown of the decoding algorithm for the example in Figure
scheme well, making the payload retriovable from any long enough substring out of the model's response. At the other end of the spectrum, it is known that under certain conditions powerful users edit any watermark out of a model's response (ZEF+ 23 CGZ23). Intuitively, complete rephrasing of the response, for example, is supposed to remove any watermark. The previous empirical works on watermarks and steganography, that do not guarantee undetectability, showcase some robustness to certain types of edits.
References
[AF21] Sahar Abdelnabi and Mario Fritz. Adversarial watermarking transformer: Towards tracing text provenance with data hiding. In 2021 IEEE Symposium on Securily and Privacy (SP), pages 121-140. IEEE, 2021.
Ber64] Elwyn Berlekamp. Block coding with noiseless feedback. PhD thesis, Massachusetts Institute of Technology, 1964.
13

---

Published in Transactions on Machine Learning Research (10/2024)
[CBZ* Souradip Chakraborty, Amrit Singh Bedi, Sicheng Zhu, Bang An, Dinesh Manocha, and Furong Huang. On the possibilities of Al-generated text detection. arXiv preprint or vrXin22304004 736, 2023.
[CGZ23] Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. arXiv preprint arXiv:2306. 09100, 2023.
[CLA17] Ruina Chen, Haitao Liu, and Gabriel Altmann. Entropy in different text types. Digital Scholarship in the Humamities, 32(3):528-544 542, 2017.
[Cov88] Thomas M Cover. The role of foedback in communication. In Performance Limits in Commu- nication Theory and Practice, pages 225 235. Springer, 1988.
[DIRR99] Nenad Dedić, Gene Itkis, Leonid Reyzin, and Scott Russell. Upper and lower bounds on black-box steganography. Journal of Cryptology, 22:365 394, 2009.
(LWSK*22 Christian Schroeder de Witt, Samuel Sokota, J Zico Kolter, Jakob Foerster, and Martin Strohmeier. Perfectly secure steganography using minimum entropy coupling. arXic preprint Xrx::22200.1 14889, 2022.
|EGH15] Klim Efremenko, Ran Gelles, and Bernhard Haeupler. Maximal noise in interactive communica- tion over erasure channels and channels with feedback. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 11 20, 2015.
[3CT+23] Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three bricks to consolidate watermarks for large language models. arXiv preprint arXiv:2908. 2Kf::2208800113 00113, 2023.
[GC02] Dmitriy Genzel and Eugene Charniak. Entropy rate constancy in text. In Proceedings of the 40th annual meeling of the Associalion for Compulational Linguistics, pages 199-206, 2002.
[GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM (JACM), 33(4):792-98) 1986.
[Gil52] Edgar N Gilbert. A comparison of signalling alphabets. The Bell system technical journal, 31(3):504-522 522, 1952.
Ham50] Richard W Hamming. Error detecting and error correcting codes. The Bell system technical journal, 2922)144-1660, 1950.
[HTLL999] Johan Håstad, Russell Impagliazzo, Leonid A Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364 1396, 1999.
[HvAL08] Nicholas Hopper, Luis von Ahn, and John Langford. Provably secure steganography. TEEE Transactions on Computers, 58(5):662 676, 2008
[JAML20] Ganesh Jawahar, Muhammad Abdul-Mageed, and Laks VS Lakshmanan. Automatic detection of machine generated text: A critical survey. arXiv preprint arXiv:2011.01314 2020.
Jus72] Jørn Justesen. Class of constructive asymptotically good algebraic codes. IEFE Transactions on information theory, 18(5):652-656, 1972.
[3W++33] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. ar preprint arXiw:2301.10226, 2023.
133++ John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. CoRR, abs/2301.112222 2023.
[KJGR21] Gabriel Kaptchuk, Tushar M Jois, Matthew Green, and Aviel D Rubin. Metcor: Cryptographi- cally secure steganography for realistic distributions. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 1529 1529-1548, 1548, 2021.
14

---

Published in Transactions on Machine Learning Research (10/2024)
KSK* Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit Iyyer. Paraphras- ing evades detectors of AT-generated text, but retrieval is an effective defense. or Xie preprinl. ar.Kio:233..14400 13408, 2023.
[M233 Travis Munyer and Xin Zhong. Deeptextmark: Deep learning based text watermarking for detection of large language model generated text. arXiv preprint arXa::235500577, 2023.
[QZL*23] Jipeng Qiang, Shiyu Zhu, Yun Li, Yi Zhu, Yunhao Yuan, and Xindong Wu. Natural language watermarking via paraphraser based lexical substitution. Artificial Intelligence, page 103859, 2023.
RWC+19] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[Sch93] Leonard J Schulman. Deterministic coding for interactive communication. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 747-756, 1993.
[Sch96] Leonard J Schulman. Coding for interactive communication. IEEE transactions on information theory, 42(6):1745-1756, 1996.
[KKB+ Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian, Wenxiao Wang, and Soheil Feizi. Can Al-generated text be reliably detected? arXiv preprial xxXi:2203.111500 2023.
[SL22] Yaqian Shi and Lei Lei. Lexical richness and text length: An entropy-based perspective. Journal of Quantilative Linguistics, 29(1):62 79, 2022.
[SS96] Michael Sipser and Daniel A Spielman. Expander codes. JEEE transactions on Information Theory, 42(6):1710-117) 17200 1996.
TMSS+3] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and finc-tuned chat models. arXiv preprint or arXiv:2307.092 2023.
[Vr57]] Rom Rubenovich Varshamov. Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, SSSR, 117:739 741, 1957.
WYC+23] Lean Wang, Wenkai Yang, Deli Chen, Hao Zhou, Yankai Lin, Fandong Meng, Jie Zhou, and Xu Sun. Towards codable text watermarking for large language models. arXiv preprint arXiv:2307. 15992, 2023.
[AAJ223] KiYoon Yoo, Wonhyuk Ahn, Jiho Jang, and Nojum Kwak. Robust natural language watermarking through invariant features. arXie preprint arXiv:2305.0111 01904, 2023.
[YAK23] KiYoon Yoo, Wonhyuk Ahn, and Nojum Kwak. Advancing beyond identification: Multi-bit. watermark for language models. arXiv preprint XrX:::2308.0000 00221, 2023.
23F+23] Hanlin Zhang, Benjamin L Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak. Watermarks the sand: Impossibility strong watermarking for generative models. Xix preprint arXiv:2311 231.2311.033788 04378, 2023.
15

---

Published in Transactions on Machine Learning Research (10/2024)
Appendix
A Proof of Theorem 6.3
We need lo analyze two quantilies. First, when Stegx adds symbol to the code, what is the probability it is incorrect (i.e., different than the intended next symbol)?; Second, how many symbols do we manage to add to the code? Or oquivalently, how many response tokens do we usually see before adding a symbol to the code?
To answer both ions, we analyze the evolution of the correct score (i.e., the one corresponding to the next symbol and incorrect scores from the time we start computing them and until one of them passes the threshold.
While computing the score with respect to an incorrect symbol, every token's score is simply an exponential random variable with mean 1. Denote by $1, $2,... the scores of each individual token (i.e., independent Exp(1) random variables), and by S == Ej= 8, their accumulative sums. By Lemma 5 in CGZ we have that for any r > 0,
Pr[S 2 2+20
Let 2 ro be an integer to be chosen later. By union bound, the probability of the score passing the threshold at any time within the b first steps is bounded by b (g)
For the score with respect to the correct symbol, the first b tokens contain at least 10 b empirical entropy, as b 2 and as we conditioned on our response being ro-saturated. In CGZ it is shown that St is still distributed as the sum of independent Exp(1) variables, but it is now additively shifted by the empirical entropy of those l variables. In particular, by Theorem 7 and Lemma 5 in CGZ, it follows that for any T > we have
Pr[S, < <b <b+ 10-blbb 1atp/bbbbVo----- Se 11-
Equivalently,
Sbb b Pr
10 Vs se-12.
Vb
We choose / = 5 5 and 7 15 b) and deduce from the above statements that: 1) The probability that an incorrect (normalized) score passed the threshold within the first b steps is at most b (1)² = b (1) c(1-5lu(5/1)) lab < e bI/10 IT) The probability that the correct (normalized) score passed the threshold within the first b steps, which at least the probability it was above the threshold at the end of the b-th step, is at least - e-/2 1 22(lubb))// /22 By combining (I) and (II) we conclude that the probability that the correct score passed the threshold within the first b steps, yet the two incorrect scores did not, is at least
25/1n /2 - 2e- (lubb)/0
denote this number by (1 -1- E(b).. As lim e(b = O, there exists a constant by such that for every 2 by it holds that ebb) < J. We set = max(ro, bn). Note that bo a universal constant independent ro and other parameters. We conclude that with probability at least 3 the correct symbol is transmitted within the first b tokens, and in particular the symbol is transmitted correctly with probability at least 3
As the probability of incorrectly transmitting a symbol is at most 3 < that if n code symbols are transmitted overall, then the first O(n) bits of the PAYLOAD are retrieved correctly. It is thus only left to analyze the number of transmitted code symbols.
2, we can use Theorem 5.3 to conclude
We again consider the same inequality from before, that holds for any V 2 To, > 0, bn) observe that for any D' b we have 10 VF 5 5lmb t. And thus, Pr Sw- < S 25(1n1/)2/2 Denote by the random variable which is the first step in which the score (w.r.t. the correct symbol) passed the threshold
S 10 - Vr] -/1 By choosing V8
Pr
vW
16

---

Published in Transactions on Machine Learning Research (10/2024)
by the above inequality have
8
E B
Σ
Pr|e21
b
Σ Prie2d+
Σ
11
1=b+1
8
Σ 1+
(In))
==1 1=++
= b b 011.
As the correct symbol is expected to pass the score threshold after b + O(1) response tokens, in particular symbol is expected to be transmitted in the protocol at least once every b + O(1) response tokens.
B Complete Undetectability
Our revised algorithm partitions the generation of response tokens into three parts:
We use real randomness to generate tokens and count the amount of empirical entropy used in the process, until enough (at least A) empirical entropy seen, call the prefix of tokens generated in this step.r.
We begin generating tokens using the PRF, with both r and the index as inputs. We don't yet submit code symbols and wait until the score passes A. We do this step to leave signal to the detector with regards to what prefix was chosen by the generation algorithm.
3. We now run the one-query scheme, while adding as an additional input to the PRF calls.
We remark that the second part can be avoided, as the correct part, but for simplicity of presentation we include it. With this structure, the proofs are rather straightforward. The pseudo-code for Steg,, appears in Algorithmm 5 and for Retri in Algorithm
be detected implicitly during the third
Thcorem B.1. Algorithm is undetectable as defined in Definition 2.6
This follows from Theorem 11 in CGZ, the inputs to the PRF in the generation process are all unique within single query, and all contain r which ever repeats within different queries only with negligible probability.
Proof.
Theorem 6.3 also remains correct as-is, besides that we "lose" O()) empirical entropy to Parts and 2. As long as = ((A)) then, the same theorem statement still holds. While the running time of Steg, is unaffected, the rumning time Retr, is now quadratic instead of linear. This can avoided by truncating the verification of r, but we do not do so for the sake of simplicity.
17

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 5: Steganography algorithm Stegx
A prompt (PROMPT), payload (PAYLOAD), and secret key k Result: Response FI
Data:
i+1; 1;
0-;;
score < 0;
score len 0;
code ();
score, + 0 for E (0,1,+));
score len + 0:
next - next code);
while done & (I1,..., 1) do
P: -- ModePPPROMPT, T1,..... TT.
if H then
// Part 1
Sample (Iz, p) < (1, with probability Pt, otherwise (0,1 pc); H + H log
if H 2 then
r (I1,...,,::) rz);;
end
else if (r sr_rc T score len) & Avr_sccrre____ len then
// Part 2
Tj + [Fra(r i, None) Sp:];
score +-1 r score + s(I,, (ssrr, i, None));
score len score len + 1;
else
// Part 3
I, + 1[Fx(r, next)= $ pıl: score len <- score len + 1; for a E 10 do
score, t- score, + s(xi, in(r; if (score, score len)/ scone len > then code + code || (o); score, +- 0 for a E 10,1,+};
score len + 0;
next ncx
break;
end end end i ++i+1; 1;
end
18

---

end Published in Transactions on Machine Learning Research (10/2024)
Algorithm 6: Retriever algorithm Retra
Data: Response T1,,,.,5t,, and secret key k
Result: Retrieved payload PAYLOAD
code ();
score, t- 0 for a E 10,1,+);
score len f 0;
for j = 1,2, ... L do
<- (0) .........3. J;)); score t
score len 0; for i == + 1,j + 2..... L do
if (r score
score len) I Av score len then
// Verify r
score f- r score + ( Fa i, None)); score len + r score len + 1;
else
// Correct r found score len +- score len + 1; for E (0,1,+) do
score, t- score, + s(r, Vi, Fa(r,i,o));
if (score, - score //ooe len then code code (a); score, < 0 for E (0,1,+);; score len + 0;
break:
end
end end
if code * () then return decode(codo);
end
end
return False;
19


Reviews:
[{"review_id": "kEtD9bbEOF", "reviewer": "Reviewer_bPsq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: the paper is well written and the exposition of the main technique is clear. The assumptions and difficulty of the method is explained well. The empirical evaluation is valuable, and gives some indications that the method could be useful in practice.\n\nWeaknesses: The paper is mostly an extension of an existing technique, and makes frequent references to the paper on which it builds. The practical implications of the technique are not discussed in great detail. Some of the potential applications mentioned in the introduction are not necessarily well supported in practice; for example, the introduction mentions the possibility that, rather than simply being able to detect that a text was generated by a particular LLM, a stenographic scheme would allow the determination of the identity of the user and the time of generation. However, the empirical results (figure 2) seem to suggest that, while the length of the encodable payload grows linearly with the number of generated tokens as the author predict, in practice the encodable payloads are quite short unless the message is fairly long (it seems to be that for N tokens, the scheme is capable of encoding around N / 5  bits of information, which is not a lot given the average length of an LLM message.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper demonstrates how a watermarking scheme for LLMs proposed by Christ, Gunn & Zamir can be extended in order to implement a stenographic scheme that encodes a hidden message in the output of the model which can be retrieved with knowledge of the secret key. Like the CGZ scheme, this is done without changing the distribution of model outputs, and so is theoretically undetectable.\nThe authors also demonstrate a practical implementation of their scheme on GPT-2 and Llama 2, demonstrating that it can encode non-trivial messages in reasonable lengths of outputs. \n\nIn many ways this paper is unsurprising, as (as the authors point out) any watermarking scheme can be converted into a stenographic one. However, the details of doing this in a practical way, particularly the use of error correcting codes to allow the encoder and reciever to co-ordinate on the locations of the ‘blocks’ of the message to be decoded without the ability to co-ordinate, together with the practical demonstration of the technique, are easily substantial enough, in my view, for the paper to be a valuable contribution to the literature in it’s own right.\n\nThe paper briefly describes the CGZ watermarking scheme, which essentially allows the reliable decoding of 1 bit of information (was the text generated by the watermarked model?) from the text generated by a model, given knowledge of the secret key. This is then extended to allow transmission of multiple bits of information, allowing the transmission of a multi-bit payload which can be decoded with knowledge of the secret key. The main technical issues to be solved are that a successful decoding requires sufficient empirical entropy in the generated message, which is not known in advance given the setting, and the requirement to ‘pad’ the start of the message with genuine random decoding in order to avoid deterministic generation which could reveal the existence of the decoding scheme to an adversary who allowed multiple queries. The authors describe how these can be resolved in practice.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think that the paper is probably mostly suitable for acceptance in it’s current form, but I would be interested to see discussion of the following points:\n\nThe paper conducts some experiments on Llama 2, the open-weights model released by Meta. This model is consistently referred to as ‘llamma’ instead: I think that this is a mistake and should be fixed?\n\nI would be interested in a bit more discussion of possible applications and the requirements for this. For instance, the authors suggest in the introduction that it would be possible to encode ‘the users name, the time, or the prompt used’ into the output of the message; but in practice this would likely be difficult. For instance, if a company has 10 million users, then this requires around 24 bits of information in order to uniquely identify them all, but the authors empirical results seem to suggest that this requires a fairly long message (> 100 tokens) in order to encode reliably while remaining undetectable. Possibly the constants could be improved but I think a bit more discussion on this could be illuminating.\n\nOne potential factor which I thought could be an interesting extension of this paper is the assumption that the model is a deterministic mapping from inputs to outputs (definition 2.1). Many deployed models are not fully deterministic in practice, either due to hardware indeterminism or batch effects with mixture of expert models (or a combination of both). These deviations from full determinism could probably be modelled as small amounts of noise : would this affect the feasibility of the error correction scheme? Intuitively I feel like the method could be modified to cope with this (as it’s basically a very slightly noisy channel), which might be both technically interesting and increase the immediate applicability of the method. As mentioned above, though, I think that the paper is sufficiently interesting as a contribution in it’s current form.", "broader_impact_concerns": "I don't think that a broader impact statement is required.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WzRXv4r1JR", "reviewer": "Reviewer_DHD8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- One of the main strengths of this work is in extending the work of Christ et al (2023) to obtain a method that can hide an arbitrary secret message in the output of an LLM while keeping the output distribution of the LLM unchanged. The outputs of the modified LLM hiding the message is indistinguishable from the original LLM without access to a secret key.\n\n- To apply the undetectable watermarking scheme of Christ et al (2023) for the purpose of hiding arbitrary messages in the LLM output, the authors take two important steps. 1) By breaking up the message into smaller parts and encoding each part separately, the authors are able to keep the running time of the retrieval algorithm of the method low. 2) By using Error Correcting Codes, the authors are able to extend the size of the hidden message to be optimal with respect to the size of the generated text.\n\n- The method proposed has provable guarantees, both in terms of indistinguishability of the outputs between the modified and the original LLMs, as well as showing that the retrieval algorithm can retrieve the hidden message with reasonable assumptions on the entropy of the generated response.\n\n- The authors are transparent about the limitation of the method, which is not robust to edits of the generated text.\n\n\nWeaknesses\n\n- Experiments are a bit lacking. The only experiment in the paper is on showing that the length of the hidden message grows linearly with the length of the LLM output when generating natural language. However, even this experiment is only shown for 5 data points and a maximum output length of only 100 tokens, which is very short compared to practical use cases of LLMs.\n\n- There is no discussion on the practical implementation of the proposed method. While an algorithm is proposed and the authors analyze its theoretical complexity, there is no discussion on the practical runtimes of the algorithm. While Figure 3 seems to be going through the decoding process, more discussion on this would be great, including runtimes. There is also no discussion on ways to check the correctness of the implementation, which would likely be crucial for the practical security of the proposed method.\n\n- Not much discussion of prior work on hiding arbitrary messages in the output of an LLM. While some of these works are cited, it would be great to have a more thorough comparison with these earlier works.\n\n- The writing could be improved. In particular, the part around the dynamic Error Correcting Codes. While this seems like a key contribution of the paper, it is not properly explained in the main paper, and the short paragraph on it in Section 4 is a bit unclear. There are also a number of small typos in the paper that should be fixed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This is a nice theoretical paper, where the authors propose a method to hide an arbitrary message in the output of an LLM. The hidden message can be extracted from the output using a secret key. The key property of this method is that without this secret key, the outputs of the original LLM and the modified LLM hiding the message are provably indistinguishable, and therefore does not affect the quality of the generated outputs. The work extends an undetectable watermarking scheme for LLMs proposed by Christ et al (2023), such that arbitrary messages can be hidden in the output of an LLM. Overall, the paper makes good theoretical progress towards solving an important problem, and I believe should be accepted.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would be great if the authors could refer to the Weaknesses section above and resolve some of those issues, especially the comments on improving the writing and adding further discussion.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Z2cz5fSVwd", "reviewer": "Reviewer_2zmr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n  A. This is a practically relevant problem and the proposed solution is an important step in this direction. \n\n  B. The dynamic ECC with feedback may be of interest in other areas\n\nWeaknesses\n\n  C. Manuscript\n\n    i) A very substantial part of the manuscript largely repeats Christ, Gunn and Zamir. In a setting where you are limited by the number of pages but perhaps less so by the size of appendices this choice is peculiar.\n\n    ii) None of the four algorithms included has line numbers which affects the quality of their integration with text. \n\n    iii) Section 4 is ~2 pages of pure text that forward references \"rigorous construction\" in sections 5 and 6, and back references section 4. There is no attempt made here to refer to specific parts of some algorithms or present a diagram. \n\n    iv) Section 5 which includes perhaps the key technical contribution is a sentence that refers to information in the appendix. \n\n    v) Repeated use of high-level followed by somewhat low-level descriptions is distracting. Repeated forward references are distracting. A single self-contained piece of writing would be a better choice. \n\n  D. Empirical investigation\n\n    i) Very limited empirical investigation\n\n    ii) It appears that although linear the proposed method enables encoding only a limited number of bits of information. There is not much discussion on that and implications given that the length of LLM responses is not a free variable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript proposes a cryptographic method that allows to encode a payload into outputs generated by popular large language models and decode it by means of a linked method that makes use of a secret key, also employed in the encoding part. This work builds on the previous work by Christ, Gunn and Zamir by extending watermarking from true/false to a string with length that appears to be linear in the lengths of the response. The key technical approach is a dynamic variant of error correcting codes with feedback. The manuscript also includes demonstration of encoding payload \"JD\" into 150+ word response generated by GPT-2 following 20+ word query.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Most of changes I believe should take place are of major nature, which perhaps are not suitable for this kind of peer-review process. These are:\n\n  A. Significant reduction of background material or complete withdrawal of it to appendices (sections 2 and 3)\n\n  B. Adding line numbers to all algorithms and referencing them in writing\n\n  C. significant revision of sections 4, 5 and 6 which includes\n\n    i) replacing high-level description followed by low-level description as done in the manuscript with a single, self-contained, description of the proposed method\n\n    ii) adding description of dynamic ECC with feedback into the main body as one of the key contributions\n\nSome smaller changes are:\n\n  D. Word \"arbitrary\" as used in this manuscript is not specific enough and contradicts what you say in the manuscript (the manuscript states that there is linear relationship between response and payload which contradicts the arbitrariness of the payload)\n\n  E. Word \"rigour\" as used in this manuscript on multiple occasions suggests self-assessment. I would suggest you remove it and let reviewers and audience decide on the rigorousness. \n\n  F. Numerous typos/grammar issues (can be extend, this is length)\n\n  G. page 4 \"takes as input\" - what?\n\n  H. page 5 talks about entropy you require but do not discuss and present evidence of typical entropies exhibited by LLMs\n\n  I. page 6 mentions F_{k}(r,i) but I don't believe you ever defined it\n\n  J. section 4 really needs a diagram to follow your train of thought\n\n  K. page 11 refers to overhead as straightforward - what does it mean?\n\n  L. section 8, would not a restart require lengthening of the response, can you discuss that?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: As stated above, this is a simple ideal which is well addressed experimentally and well explained. The reviewers concurred that the paper was publishable, but felt it did not have enough unique content to automatically progress to ICLR. It was suggested that a joint submission with the original watermarking work, if that work had author overlap with this one, would make for a strong submission.
Decision: Accept (poster)