Canonical Paraphrasing: A Provable Defense against Steganography in Language Models

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.