OD-Stega: LLM-Based Near-Imperceptible Steganography via Optimized Distributions

We first thank the reviewer for recognizing the strength of our work. Before proceeding to the item-by-item response, we clarify a few points in a summary below, which were not explained in detail due to space constraints.

1. Our proposed approach includes the perfectly secure case as a special case. Particularly, note that we assume the secret message has been encrypted. Therefore, the secret message are iid binary (information-theoretic or computational, depending on the encryption process). If we choose the parameter $\delta$ to be zero, i.e., not to increase the embedding utilization by optimizing the distribution, then it is a perfectly secure protocol (almost identical to Meteor).

2. Our proposed approach essentially provides additional flexibility for system designers to choose a tradeoff point between security and embedding utilization. If in an application, the eavesdropper is resource-limited (or a person paying little attention), then clearly the designer can choose a larger value of $\delta$ to allow more KL-divergence; on the other hand, in other applications, if the security requirement is very high, then $\delta$ should be chosen to be zero, making it completely secure. This additional flexibility is the most important contribution of our work.

3. The proposed approach can also be easily combined with other techniques, e.g., Discop, Meteor, and ADG. Note that these methods rely on some additional secret keys/randomness, so the overall architecture is somewhat different, however, they all utilize the Ziegler el al. key idea together with some clever randomization techniques. We can optimize the distributions and use the optimized one in Discop, Meteor, or ADG to increase the embedding utilization. Our approach should not be viewed as directly competing with those new er methods but can be viewed as a method to allow further flexibility in them. In other words, our design offers a broader range of design points between a perfect secure solution and the maximum compact embedding solution, on most "base" methods.

4. Near-perfectly recure steganography is well-accepted in the literature. It had been used widely before coverless steganography became popular. With a covertext, small changes to the covertext always introduce small distribution changes, and near-perfect security has been widely accepted. With more recent coverless steganography, it becomes possible to have "perfect security", such as Discop and Meteor. However, for the coverless setting, "near-imperceptable" steganography was also introduced by Dai and Cai in ACL-19, and it is well-motivated and well-accepted as humans cannot distinguish "perfect security" vs. "near-perfect security".

5. Some more recent works exist in the literature, however, the improvements over Ziegler's method are minor. For example, both Discop and Meteor are in fact simple variations of Ziegler et al.'s breakthrough idea of using arithmetic coding for steganography. As commented in the Meteor paper, Ziegler's approach is not perfectly secure only due to the reuse of randomness. A minor change to Ziegler's approach will make it perfectly secure: use a random secret key to encrypt the cleartext message (e.g., XOR), then the encrypted secret message can be stega-coded using Ziegler's arithmetic coding approach; the secret key needs to be shared with Bob, but Eve does not have it. Meteor essentially uses this approach, with a simplified arithmetic code that introduces some additional inefficiency (see comments in the Discop paper). Discop uses the random key to instead randomize the Huffman tree (approximately equivalent to fixed-decision arithmetic coding). These newer approaches therefore do not fundamentally impact the performance of Ziegler's, and in fact sometimes they suffer from under-utilization. Ziegler el al.'s work and Dai and Cai's works give the most fundamental methodology, and comparison with them allows a clear picture as to where the strength of our work is, without the distracting factors of randomization techniques in the mix. We can add more comments on the relation if the paper can be accepted.

6. Even "perfectly secure" protocols such as Discop and Meteor are in fact still not perfectly secure in the strict sense. Firstly, the use of a pseudo-random generator implies that they are only computationally secure, but not information-theoretically secure. Secondly, it is impossible to completely remove the bias in the language model itself, and the "provably secure" protocols assumed language models have no distribution bias, but in practice, this is likely not so. Thirdly, the practical implementation (either Arithmetic coding or the Huffman tree) implies that some small distribution shift will be induced. Therefore, perfect security is only theoretically proved, but not in practice. If we can accept this small security leakage, we do not need to focus singularly on the perfect security to start with, as long as we can control it well.

1. Regarding Fig. 1: The decoding part is very similar to the encoding process of arithmetic coding. First, the decoder identifies where the token is located in the probability interval. For example, let the interval be [0.75, 0.875) = [0.110, 0.111), then the receiver knows that the secret bits for the first two tokens are 11. They read the second token and do this process again, and if, for example, the second token is located in the interval [0.78125, 0.8125) = [0.11001, 0.1101), the receiver knows the secret bits for the first two tokens are ``110". Essentially, one only needs to look at the figure backwards to find the steganography decoding process. Arithmetic coding is a well-known technique in both steganography and data compression, and we intentionally make the introduction here brief. We feel this might be too repetitive to include, but we have indeed revised it on OpenReview to include more explanation for decoding.

2. Regarding the analysis of truncation method: Our main focus is on the distribution optimization technique, instead of the truncation technique. The latter technique was not introduced by us, but by Dai and Cai ACL-2019. More detailed analysis can be found there. It is clear the more truncation, the faster the process is, however, the impact is relatively small since the bulk of the computation is in the language model. We include this technique here to 1) have a uniform method that includes both ours and the truncation technique, such that the evaluation of the security is more streamlined, and 2) to illustrate that the proposed technique is rather flexible and fundamental, and can be compatible with this well-known technique. The coding time is dominated by the LLM computation, and the differences in other components are rather negligible in this sense.

3. Regarding Fig. 5: we have revised the figure and will upload an updated version.

4. Regarding the choice of the baselines: Please refer first to the general response given above. Reviewer 3 provided several more recent works. Concerning these more recent methods, we note that most of them adopted the same idea of Ziegler et al., but added certain clever randomization with some additional secret key/PRNG. For example, Meteor essentially extends Ziegler et al.'s work by introducing fresh random seeds; Discop is similar and uses PRNG to randomize the mapping. These clever randomizations help satisfy the strict definition of "security", but they do not fundamentally change the performance in terms of utilization and security. In contrast, we assume the message is already encrypted (therefore distributed i.i.d. Bernoulli), therefore, if we choose $\delta=0$, it is also perfectly secure. It can also be seen in the Meteor and Discop papers, that there was in fact some loss in the embedding utilization (capacity), and the introduction of randomization helps to drive KL-divergence smaller, but still not zero. Our proposed approach, in contrast, allows us to choose a wider range of tradeoff points between utilization and security. Moreover, since these methods only aim at the perfect secure operating points, our proposed approach can be easily incorporated into them to allow near-perfect security in all these techniques.

5. Regarding the interval in the example: This was a typo introduced inadvertently when we attempts to make the example more readable. Indeed this should be [0.71875, 0.75). Thanks for pointing this out.

6. Regarding more examples: More examples can be found in the appendix. We can add further examples if the paper is eventually accepted.

We first thank the reviewer for recognizing the strength of our work. Before proceeding to the item-by-item response, we clarify a few points in a summary below, which were not explained in detail due to space constraints.

1. Our proposed approach includes the perfectly secure case as a special case. Particularly, note that we assume the secret message has been encrypted. Therefore, the secret message are iid binary (information-theoretic or computational, depending on the encryption process). If we choose the parameter $\delta$ to be zero, i.e., not to increase the embedding utilization by optimizing the distribution, then it is a perfectly secure protocol (almost identical to Meteor).

2. Our proposed approach essentially provides additional flexibility for system designers to choose a tradeoff point between security and embedding utilization. If in an application, the eavesdropper is resource-limited (or a person paying little attention), then clearly the designer can choose a larger value of $\delta$ to allow more KL-divergence; on the other hand, in other applications, if the security requirement is very high, then $\delta$ should be chosen to be zero, making it completely secure. This additional flexibility is the most important contribution of our work.

3. The proposed approach can also be easily combined with other techniques, e.g., Discop, Meteor, and ADG. Note that these methods rely on some additional secret keys/randomness, so the overall architecture is somewhat different, however, they all utilize the Ziegler el al. key idea together with some clever randomization techniques. We can optimize the distributions and use the optimized one in Discop, Meteor, or ADG to increase the embedding utilization. Our approach should not be viewed as directly competing with those new er methods but can be viewed as a method to allow further flexibility in them. In other words, our design offers a broader range of design points between a perfect secure solution and the maximum compact embedding solution, on most "base" methods.

4. Near-perfectly recure steganography is well-accepted in the literature. It had been used widely before coverless steganography became popular. With a covertext, small changes to the covertext always introduce small distribution changes, and near-perfect security has been widely accepted. With more recent coverless steganography, it becomes possible to have "perfect security", such as Discop and Meteor. However, for the coverless setting, "near-imperceptable" steganography was also introduced by Dai and Cai in ACL-19, and it is well-motivated and well-accepted as humans cannot distinguish "perfect security" vs. "near-perfect security".

5. Some more recent works exist in the literature, however, the improvements over Ziegler's method are minor. For example, both Discop and Meteor are in fact simple variations of Ziegler et al.'s breakthrough idea of using arithmetic coding for steganography. As commented in the Meteor paper, Ziegler's approach is not perfectly secure only due to the reuse of randomness. A minor change to Ziegler's approach will make it perfectly secure: use a random secret key to encrypt the cleartext message (e.g., XOR), then the encrypted secret message can be stega-coded using Ziegler's arithmetic coding approach; the secret key needs to be shared with Bob, but Eve does not have it. Meteor essentially uses this approach, with a simplified arithmetic code that introduces some additional inefficiency (see comments in the Discop paper). Discop uses the random key to instead randomize the Huffman tree (approximately equivalent to fixed-decision arithmetic coding). These newer approaches therefore do not fundamentally impact the performance of Ziegler's, and in fact sometimes they suffer from under-utilization. Ziegler el al.'s work and Dai and Cai's works give the most fundamental methodology, and comparison with them allows a clear picture as to where the strength of our work is, without the distracting factors of randomization techniques in the mix. We can add more comments on the relation if the paper can be accepted.

6. Even "perfectly secure" protocols such as Discop and Meteor are in fact still not perfectly secure in the strict sense. Firstly, the use of a pseudo-random generator implies that they are only computationally secure, but not information-theoretically secure. Secondly, it is impossible to completely remove the bias in the language model itself, and the "provably secure" protocols assumed language models have no distribution bias, but in practice, this is likely not so. Thirdly, the practical implementation (either Arithmetic coding or the Huffman tree) implies that some small distribution shift will be induced. Therefore, perfect security is only theoretically proved, but not in practice. If we can accept this small security leakage, we do not need to focus singularly on the perfect security to start with, as long as we can control it well.

We first thank the reviewer for recognizing the strength of our work. Before proceeding to the item-by-item response, we clarify a few points in a summary below, which were not explained in detail due to space constraints.

1. Our proposed approach includes the perfectly secure case as a special case. Particularly, note that we assume the secret message has been encrypted. Therefore, the secret message are iid binary (information-theoretic or computational, depending on the encryption process). If we choose the parameter $\delta$ to be zero, i.e., not to increase the embedding utilization by optimizing the distribution, then it is a perfectly secure protocol (almost identical to Meteor).

2. Our proposed approach essentially provides additional flexibility for system designers to choose a tradeoff point between security and embedding utilization. If in an application, the eavesdropper is resource-limited (or a person paying little attention), then clearly the designer can choose a larger value of $\delta$ to allow more KL-divergence; on the other hand, in other applications, if the security requirement is very high, then $\delta$ should be chosen to be zero, making it completely secure. This additional flexibility is the most important contribution of our work.

3. The proposed approach can also be easily combined with other techniques, e.g., Discop, Meteor, and ADG. Note that these methods rely on some additional secret keys/randomness, so the overall architecture is somewhat different, however, they all utilize the Ziegler el al. key idea together with some clever randomization techniques. We can optimize the distributions and use the optimized one in Discop, Meteor, or ADG to increase the embedding utilization. Our approach should not be viewed as directly competing with those new er methods but can be viewed as a method to allow further flexibility in them. In other words, our design offers a broader range of design points between a perfect secure solution and the maximum compact embedding solution, on most "base" methods.

4. Near-perfectly recure steganography is well-accepted in the literature. It had been used widely before coverless steganography became popular. With a covertext, small changes to the covertext always introduce small distribution changes, and near-perfect security has been widely accepted. With more recent coverless steganography, it becomes possible to have "perfect security", such as Discop and Meteor. However, for the coverless setting, "near-imperceptable" steganography was also introduced by Dai and Cai in ACL-19, and it is well-motivated and well-accepted as humans cannot distinguish "perfect security" vs. "near-perfect security".

5. Some more recent works exist in the literature, however, the improvements over Ziegler's method are minor. For example, both Discop and Meteor are in fact simple variations of Ziegler et al.'s breakthrough idea of using arithmetic coding for steganography. As commented in the Meteor paper, Ziegler's approach is not perfectly secure only due to the reuse of randomness. A minor change to Ziegler's approach will make it perfectly secure: use a random secret key to encrypt the cleartext message (e.g., XOR), then the encrypted secret message can be stega-coded using Ziegler's arithmetic coding approach; the secret key needs to be shared with Bob, but Eve does not have it. Meteor essentially uses this approach, with a simplified arithmetic code that introduces some additional inefficiency (see comments in the Discop paper). Discop uses the random key to instead randomize the Huffman tree (approximately equivalent to fixed-decision arithmetic coding). These newer approaches therefore do not fundamentally impact the performance of Ziegler's, and in fact sometimes they suffer from under-utilization. Ziegler el al.'s work and Dai and Cai's works give the most fundamental methodology, and comparison with them allows a clear picture as to where the strength of our work is, without the distracting factors of randomization techniques in the mix. We can add more comments on the relation if the paper can be accepted.

6. Even "perfectly secure" protocols such as Discop and Meteor are in fact still not perfectly secure in the strict sense. Firstly, the use of a pseudo-random generator implies that they are only computationally secure, but not information-theoretically secure. Secondly, it is impossible to completely remove the bias in the language model itself, and the "provably secure" protocols assumed language models have no distribution bias, but in practice, this is likely not so. Thirdly, the practical implementation (either Arithmetic coding or the Huffman tree) implies that some small distribution shift will be induced. Therefore, perfect security is only theoretically proved, but not in practice. If we can accept this small security leakage, we do not need to focus singularly on the perfect security to start with, as long as we can control it well.

We first thank the reviewer for recognizing the strength of our work. Before proceeding to the item-by-item response, we clarify a few points in a summary below, which were not explained in detail due to space constraints.

1. Our proposed approach includes the perfectly secure case as a special case. Particularly, note that we assume the secret message has been encrypted. Therefore, the secret message are iid binary (information-theoretic or computational, depending on the encryption process). If we choose the parameter $\delta$ to be zero, i.e., not to increase the embedding utilization by optimizing the distribution, then it is a perfectly secure protocol (almost identical to Meteor).

2. Our proposed approach essentially provides additional flexibility for system designers to choose a tradeoff point between security and embedding utilization. If in an application, the eavesdropper is resource-limited (or a person paying little attention), then clearly the designer can choose a larger value of $\delta$ to allow more KL-divergence; on the other hand, in other applications, if the security requirement is very high, then $\delta$ should be chosen to be zero, making it completely secure. This additional flexibility is the most important contribution of our work.

3. The proposed approach can also be easily combined with other techniques, e.g., Discop, Meteor, and ADG. Note that these methods rely on some additional secret keys/randomness, so the overall architecture is somewhat different, however, they all utilize the Ziegler el al. key idea together with some clever randomization techniques. We can optimize the distributions and use the optimized one in Discop, Meteor, or ADG to increase the embedding utilization. Our approach should not be viewed as directly competing with those new er methods but can be viewed as a method to allow further flexibility in them. In other words, our design offers a broader range of design points between a perfect secure solution and the maximum compact embedding solution, on most "base" methods.

4. Near-perfectly recure steganography is well-accepted in the literature. It had been used widely before coverless steganography became popular. With a covertext, small changes to the covertext always introduce small distribution changes, and near-perfect security has been widely accepted. With more recent coverless steganography, it becomes possible to have "perfect security", such as Discop and Meteor. However, for the coverless setting, "near-imperceptable" steganography was also introduced by Dai and Cai in ACL-19, and it is well-motivated and well-accepted as humans cannot distinguish "perfect security" vs. "near-perfect security".

5. Some more recent works exist in the literature, however, the improvements over Ziegler's method are minor. For example, both Discop and Meteor are in fact simple variations of Ziegler et al.'s breakthrough idea of using arithmetic coding for steganography. As commented in the Meteor paper, Ziegler's approach is not perfectly secure only due to the reuse of randomness. A minor change to Ziegler's approach will make it perfectly secure: use a random secret key to encrypt the cleartext message (e.g., XOR), then the encrypted secret message can be stega-coded using Ziegler's arithmetic coding approach; the secret key needs to be shared with Bob, but Eve does not have it. Meteor essentially uses this approach, with a simplified arithmetic code that introduces some additional inefficiency (see comments in the Discop paper). Discop uses the random key to instead randomize the Huffman tree (approximately equivalent to fixed-decision arithmetic coding). These newer approaches therefore do not fundamentally impact the performance of Ziegler's, and in fact sometimes they suffer from under-utilization. Ziegler el al.'s work and Dai and Cai's works give the most fundamental methodology, and comparison with them allows a clear picture as to where the strength of our work is, without the distracting factors of randomization techniques in the mix. We can add more comments on the relation if the paper can be accepted.

6. Even "perfectly secure" protocols such as Discop and Meteor are in fact still not perfectly secure in the strict sense. Firstly, the use of a pseudo-random generator implies that they are only computationally secure, but not information-theoretically secure. Secondly, it is impossible to completely remove the bias in the language model itself, and the "provably secure" protocols assumed language models have no distribution bias, but in practice, this is likely not so. Thirdly, the practical implementation (either Arithmetic coding or the Huffman tree) implies that some small distribution shift will be induced. Therefore, perfect security is only theoretically proved, but not in practice. If we can accept this small security leakage, we do not need to focus singularly on the perfect security to start with, as long as we can control it well.