Kolmogorov Complexity Bounds for LLM Steganography and a Perplexity-Based Detection Proxy CCS: Security and privacy Information-theoretic techniques CCS: Security and privacy Pseudonymity, anonymity and untraceability

Andrii Shportko · 2026

Read Kolmogorov Complexity Bounds for LLM Steganography and a Perplexity-Based Detection Proxy CCS: Security and privacy Information-theoretic techniques CCS: Security and privacy Pseudonymity, anonymity and untraceability by Andrii Shportko (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21567.txt.

Introduction

Shportko studies the information cost of hiding messages inside language model output. A steganographic rewrite keeps the surface meaning of a cover text while smuggling in a payload. Shportko proves a lower bound using Kolmogorov complexity: the hidden text must carry at least the cover's complexity plus the payload's, up to a small term. So any real payload forces the output's complexity up. Since true complexity cannot be computed, he tests perplexity ratios as a practical detector on 300 samples.

Catalog record

CREATORAndrii Shportko
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22431
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.21567

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Kolmogorov Complexity Bounds for LLM Steganography and a Perplexity-Based Detection Proxy CCS: Security and privacy Information-theoretic techniques CCS: Security and privacy Pseudonymity, anonymity and untraceability Andrii Shportko Abstract . Large language models can rewrite text to embed hidden payloads while preserving surface-level meaning, a capability that opens covert channels between cooperating AI systems and poses challenges for alignment monitoring. We study the information-theoretic cost of such embedding. Our main result is that any steganographic scheme that preserves the semantic load of a covertext M 1 M_{1} while encoding a payload P P into a stegotext M 2 M_{2} must satisfy K ⁡ ( M 2 ) ≥ K ⁡ ( M 1 ) + K ⁡ ( P ) − O ⁡ ( log ⁡ n ) K(M_{2})\geq K(M_{1})+K(P)-O(\log n) , where K K denotes Kolmogorov complexity and n n is the combined message length. A corollary is that any non-trivial payload forces a strict complexity increase in the stegotext, regardless of how cleverly the encoder distributes the signal. Because Kolmogorov complexity is uncomputable, we ask whether practical proxies can detect this predicted increase. Drawing on the classical correspondence between lossless compression and Kolmogorov complexity, we argue that language-model perplexity occupies an analogous role in the probabilistic regime and propose the Binoculars perplexity-ratio score as one such proxy. Preliminary experiments with a color-based LLM steganographic scheme support the theoretical prediction: a paired t t -test over 300 samples yields t = 5.11 t=5.11 , p < 10 − 6 p<10^{-6} . 1. Introduction Large language models can rewrite text to embed covert signals while preserving surface-level meaning. This capability creates steganographic channels between cooperating AI systems—channels that may evade alignment monitors and undermine oversight of chain-of-thought reasoning ( Roger2023 ) . As models grow more capable, the bandwidth and subtlety of such channels are likely to increase, and understanding their fundamental limits becomes a prerequisite for principled defense. We study two questions. First, does semantic-preserving steganographic embedding necessarily increase the intrinsic descriptive complexity of the output? Perfectly secure stegosystems with zero KL divergence between covertext and stegotext distributions exist for certain source classes ( Cachin2004 ; Ryabko2008 ) , yet the relationship between such statistical security and the Kolmogorov complexity of the steganographic output has received little formal attention. Second, given that Kolmogorov complexity is uncomputable, can practical metrics detect the predicted complexity increase? Our contributions are as follows. (1) We prove that semantic-preserving steganographic embedding increases Kolmogorov complexity by at least K(P)-O(\log n) , where P is the payload and n is the message length (Section 3 ). (2) We identify language-model perplexity as a computable proxy for this complexity increase, grounded in the classical correspondence between compression algorithms and Kolmogorov complexity, and we propose the Binoculars score ( Hans2024 ) as a concrete instantiation (Section 4 ). (3) We validate the theoretical prediction on a 300-sample LLM steganographic scheme, confirming that the Binoculars score significantly distinguishes stegotext from baselines ( p<10^{-6} ; Section 5 ). 2. Related Work Information-theoretic steganography. Cachin ( Cachin2004 ) formalized steganographic security via relative entropy. Ryabko and Ryabko ( Ryabko2009 ) showed that for sources with maximal Kolmogorov complexity, any high-speed perfect stegosystem must have exponential complexity in its system parameters—a result about encoder complexity. Our Theorem 3 complements theirs by bounding the output complexity. Muchnik ( Muchnik2011 ) studied Kolmogorov complexity in cryptographic contexts but without a semantic-preservation constraint. LLM covert channels. Roger and Greenblatt ( Roger2023 ) studied AI-to-AI covert communication and introduced capacity formulas for noisy steganographic channels. Shportko ( Shportko2025 ) demonstrated empirically that linguistic steganography, just like adversarial paraphrasing ( shportko-2025-paraphrasing ) , significantly increases Binoculars scores, providing independent evidence for the complexity-increase phenomenon we formalize here. Compression as a Kolmogorov complexity proxy. Cilibrasi and Vitányi ( Cilibrasi2005 ) introduced the Normalized Compression Distance, treating the output length |C(x)| of a compressor C as an operational stand-in for K(x) . Benedetto et al. ( Benedetto2002 ) used gzip-based complexity estimates for language classification. We extend this reasoning to language-model perplexity, treating it as a probabilistic analogue of compression length. 3. Theoretical Results Notation. Throughout, K(x) denotes the Kolmogorov complexity of a finite binary string x : the length of the shortest program that produces x on a fixed universal Turing machine ( Li1997 ) . K(x\mid y) denotes conditional Kolmogorov complexity, where y is provided as auxiliary input. |x| denotes the bit-length of x . All O(\cdot) terms hide constants that depend on the choice of universal machine but not on the messages. Definition 1 (Identical Semantic Load). Two messages M_{1} and M_{2} have identical semantic load if there exists a finite binary string S (the “semantic description”) such that K(M_{1}\mid S)=O(1)\quad\text{and}\quad K(M_{2}\mid S)=O(1). That is, given S , each message can be reconstructed with only a constant number of additional bits. Definition 2 (Lossless Semantic-Preserving Embedding). A function \mathrm{Embed}\colon\mathcal{M}\times\mathcal{P}\;\to\;\mathcal{M} is a lossless semantic-preserving embedding if two conditions hold: (a) Losslessness : \exists\mathrm{Extract}\colon\mathcal{M}\to\mathcal{P} : \mathrm{Extract}(\mathrm{Embed}(M_{1},P)) =P for all M_{1}\in\mathcal{M} and P\in\mathcal{P} . (b) Semantic preservation : M_{1} and M_{2}=\mathrm{Embed}(M_{1},P) have identical semantic load. Here \mathcal{M} is the message space, \mathcal{P} is the payload space, M_{1} is the covertext, P is the payload, and M_{2} is the stegotext. Theorem 3. Let M_{2}=\mathrm{Embed}(M_{1},P) for a lossless semantic-preserving embedding. Let n=|M_{1}|+|M_{2}| . Then K(M_{2})\;\geq\;K(M_{1})+K(P)-O(\log n). Proof. Let S denote the semantic description with K(M_{i}\mid S)=O(1) for i\in\{1,2\} . Step 1 (From M_{2} we can recover M_{1} and P ). Since \mathrm{Extract} is a fixed-length program, we have K(P\mid M_{2})\;\leq\;|\langle\mathrm{Extract}\rangle|+O(1)\;=\;O(1). Since K(M_{2}\mid S)=O(1) by semantic preservation, S is recoverable from M_{2} with constant overhead; formally K(S\mid M_{2})=O(1) . From S we recover M_{1} because K(M_{1}\mid S)=O(1) . Chaining these three recoveries: K(M_{1},P\mid M_{2})\;=\;O(1). Step 2 (From M_{1} and P we can recover M_{2} ). Since \mathrm{Embed} is a fixed function: K(M_{2}\mid M_{1},P)\;\leq\;|\langle\mathrm{Embed}\rangle|+O(1)\;=\;O(1). Step 3 (Applying the symmetry of information). Steps 1 and 2 establish that M_{2} and the pair (M_{1},P) contain the same information up to O(1) bits. By the symmetry-of-information theorem ( Li1997 ) : K(M_{2})\;=\;K(M_{1},P)+O(\log n). Step 4 (Expanding the joint complexity). By the chain rule for Kolmogorov complexity: K(M_{1},P)\;=\;K(M_{1})+K(P\mid M_{1})+O(\log n). Step 5 (Payload independence). The payload P is chosen independently of the covertext M_{1} : by construction, P carries information orthogonal to the semantic description S of M_{1} . Therefore M_{1} provides no information about P beyond what is already available, and we have K(P\mid M_{1})\;\geq\;K(P)-O(1). Step 6 (Combining). Substituting Steps 4 and 5 into Step 3: K(M_{2})\;\geq\;K(M_{1})+K(P)-O(\log n).\qed Corollary 4 (Strict Complexity Increase). If the payload has non-trivial complexity such that K(P)\gg\log n , then K(M_{2})\;>\;K(M_{1}). That is, any non-trivial payload forces a strict complexity increase in the stegotext. 4. From Kolmogorov Complexity to Computable Proxies Theorem 3 predicts a complexity increase, but Kolmogorov complexity is uncomputable ( Li1997 ) . We now argue that language-model perplexity serves as a practical proxy, grounding this argument in the classical correspondence between compression and Kolmogorov complexity. 4.1. Compression as a Complexity Proxy For any lossless compressor C and string x : K(x)\;\leq\;|C(x)|+c_{C}, where c_{C} is a constant depending only on the compressor. This inequality—a direct consequence of the invariance theorem ( Li1997 ) —justifies treating |C(x)| as an upper

Read the complete text