acceptodds
Withdrawn from ICLR 2027

Canonical Paraphrasing: A Provable Defense against Steganography in Language Models

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Language models can encode hidden messages in the surface form of their outputs while producing text statistically indistinguishable from honest generation. The standard defense, paraphrasing, scrambles surface tokens but does not close the channel: stochastic paraphrasing only reduces the residual capacity, leaving room for an adaptive adversary. We propose *canonical paraphrasing*, whose ideal form gives every paraphrase of a text the same meaning-preserving rewrite. We prove that this eliminates covert communication when the encoder hides information through wording choices while preserving meaning, and develop a practical approximation that substantially reduces payload recovery in the settings we evaluate. Our analysis also shows how to use steganographic encoding to sample texts with the same meaning, and vice versa, with polynomially many oracle calls when codebook capacity grows logarithmically with output length. Minimum entropy coupling yields near-chance AUC for the tested detectors across four language models. On 50 cover texts carrying complete chess games, the practical defense raises decoding bit-error rate from 5.79% to 45.54%. For AI safety, this offers a way to limit covert coordination between language-model agents even when their hidden messages evade detection.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
steganography, large language models, AI safety, canonical paraphrasing, covert communication, information theory

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_9tCEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes canonical paraphrasing as a defense against hidden communication in language-model outputs. The idea is to map texts with the same meaning to a unique representation, preventing information from being encoded through different word choices. The paper provides theoretical results about steganographic schemes and proposes a practical pipeline using embeddings, geometric center estimation, and discrete diffusion.

Critical strengths
  1. Preventing covert communication between LLM agents is an important problem. The idea of removing hidden information through canonicalization, rather than detecting it, is interesting.
  2. The proposed defense substantially reduces message recovery in the evaluated steganography experiments.
Critical weaknesses

1. Serious concerns about the theoretical results.

I am not convinced that the Simplex Theorem (Theorem A.1) is correct. The paper claims a bijection between perfectly secure steganographic schemes and the entire probability simplex. However, under uniform messages and deterministic decoding, the paper's own proof requires every decoding region to have probability 2−C2^{-C}. Therefore, all such schemes map to the same uniform point, not arbitrary points of the simplex. The reverse construction also assumes that arbitrary probability masses can be obtained by partitioning a discrete distribution. When this is impossible, the proof splits probability mass across messages, which appears inconsistent with the assumed deterministic decoding. These issues undermine the claimed simplex characterization and its interpretation of minimum entropy coupling.

2. The practical method does not achieve canonicalization.

The theoretical guarantee assumes that semantically equivalent texts are mapped to exactly the same output. However, Appendix F.2 reports that repeated runs of the practical pipeline produce identical outputs for only 14 of 80 inputs. High similarity between embedding centers does not establish that the final texts are canonical. Furthermore, the paper does not demonstrate that the evaluated steganographic encoders satisfy the transparency assumption required by the theorem. Consequently, the theoretical guarantee does not directly establish the security of the proposed implementation.

3. The security experiments are not convincing enough.

The main defense experiment uses only 50 chess games and evaluates recovery using a fixed decoder. The authors do not compare against standard paraphrasing defenses on the same attack. It is therefore unclear whether the complicated canonicalization pipeline performs better than simply asking an LLM to rewrite the text. Moreover, a bit-error rate close to 50% does not prove that the hidden communication channel has been eliminated. An adaptive attacker could potentially use a different encoding or decoder. The utility evaluation is also limited to 60 GSM8K examples, where only 24 answers are correct. This does not sufficiently establish that the defense preserves semantic meaning across tasks.

Questions for authors
  1. Can the authors clarify the Simplex Theorem? How can perfectly secure schemes with uniform messages correspond to arbitrary points in the simplex? How is splitting probability mass compatible with deterministic decoding?

  2. Does the implemented defense actually produce canonical outputs? Why are only 14/80 repeated rewrites identical? Can the authors measure residual information rather than only embedding similarity?

  3. Can the authors compare against standard paraphrasing? How does the proposed method compare with a single LLM paraphrase or repeated stochastic paraphrasing on exactly the same chess payloads?

  4. Can the authors evaluate adaptive attacks and semantic preservation? Can an attacker trained against the defense recover information? How well does the method preserve meaning on tasks beyond GSM8K?

Reviewer_htH5OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes a defense against steganographic channel using paraphrasing attack. This is a sensible solution to the problem.

Critical strengths
  • The removal of steganography is an important problem and rarely studied field. This is because in image domain, most classical methods are fragile and removal is trivial, because it is sufficient to modulate LSB of pixels. Removal of watermarks is more studied problem.
  • The formulation of semantic equivalence is nice, though it rephrases a general knowledge of the field. For example [1] has formulated the ideal paraphraser similarly.

[1] Motwani, Sumeet R., et al. "Secret collusion among AI agents: Multi-agent deception via steganography." Advances in Neural Information Processing Systems 37 (2024): 73439-73486.

Critical weaknesses
  • Treatment of prior art is very shallow. The paraphrasing attack on steganographic text was already proposed in [1] and [2], which authors mention, but does not explain their weakness. Crucially, they do not compare with respect to these works in experimental section and does not explain, why their method should be better.
  • The removal of steganographic text is very related to the removal of watermarking. There is a large corpus of work on removal of watermarking, e.g. [3, 4], yet authors do not treat it as a relevant prior art. Why? It seems to me very related.
  • I do not understand the need for the theory in Section 3, specifically the simplex theorem and MEC at the barycenter, since I do not see, how this theory is used in Section 4. Section 4 proposes a method, which seems to me largely independent of Theory 3.
  • Lastly, I would like to say that real-world steganography and attacks usually boils down to which party has better model of the channel and more knowledge about it. This is not discussed in the paper at all, yet it will be crucial for good definition of the "semantics". The definiiton of the semantics might be very problem dependent and therefore difficult to model.

[1] Roger, F., & Greenblatt, R. (2023). Preventing language models from hiding their reasoning. arXiv preprint arXiv:2310.18512. [2] Yohan Mathew, et al. Hidden in plain text: Emergence & mitigation of steganographic collusion in LLMs. In Proceedings of the 14th International Joint Conference on Natural Language Processing and the 4th Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics, pp. 585–624, 2025. [3] Krishna, Kalpesh, et al. "Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense." Advances in neural information processing systems 36 (2023): 27469-27500. [4] Kirchenbauer, John, et al. "On the reliability of watermarks for large language models." International Conference on Learning Representations. Vol. 2024. 2024.

Questions for authors
  • Why the exepriments do not involve any comparison prior art under scenarios used in prior art.
  • How the proposed paraphrasing attack relies on definitions in Section 3.
Reviewer_EYKxOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes mapping texts with the same meaning to a common representative form to suppress implicit information conveyed through surface wording. The author proves that if the encoder always stays in the same semantic equivalence class under fixed tasks, the ideal normalization operator can remove message dependencies. The practical process involves estimating embedding centers from multiple rewrites, and then generating random seeds from these centers to drive diffusion rewriting.

Critical strengths
  1. It is useful to distinguish between "hiding messages in wording" and "hiding them in semantic content".
  2. The end-to-end experiment provides evidence that practical rewriting can damage the tested decoder. It is helpful to report both the increase in BER and the inability to fully recover the payload. The paper also explicitly acknowledges that a BER close to 0.5 does not prove that the information is zero, and adaptive attackers have not yet been included in the evaluation.
Critical weaknesses
  1. This paper only attacked MEC steganography, but it is a verifiable and secure watermark, and its robustness is not strong. In fact, only a little modification or even tokenizer mismatch is needed to successfully attack it. What is the significance of this attack in this paper? Not considering combating more robust watermarks
  2. In section F.2, although all centers pass the similarity threshold, only 14/80 of the outputs are completely identical when running the same input repeatedly. Similar centers do not guarantee the same seed after hashing, and the editor still relies on the original text. The paper acknowledges this gap, but does not compare it with a single regular rewrite or diffusion editing without using a central seed on the same game load. Considering that geometric characterization itself is not valid, there is still a lack of sufficient evidence to distinguish the contribution of the paper from existing rewritten defenses.
Questions for authors

Why not consider attacking more steganography methods, including robust steganography? Where exactly is the boundary of the attack?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.