OD-Stega: LLM-Based Relatively Secure Steganography via Optimized Distributions

Technical Summary: OD-Stega

Problem Statement
The paper addresses the challenge of coverless steganography using Large Language Models (LLMs). In this setting, a sender (Alice) generates text containing a hidden secret message, which is transmitted to a receiver (Bob) over a public channel monitored by an eavesdropper (Eve). The primary objective is to maximize the embedding utilization (the number of secret bits hidden per token) while maintaining the naturalness of the generated text (imperceptibility).

Traditional LLM-based steganography relies on Arithmetic Coding (AC), where the secret message drives the sampling of tokens based on the LLM's native probability distribution. However, LLMs often produce highly deterministic outputs (low entropy), limiting the amount of information that can be embedded. Furthermore, existing methods often assume a "perfectly secure" regime where the stego-text must be indistinguishable from natural text under any detection capability. The authors argue that in many practical scenarios, Eve is a "weak detector" (e.g., computationally bounded or delay-constrained), allowing for a relaxation of security constraints to achieve higher embedding capacity. This leads to the concept of relatively secure steganography.

Methodology
The core of the proposed method, OD-Stega (Optimized Distribution Steganography), involves replacing the LLM's native next-token probability distribution $P$ with an optimized distribution $Q$ that has higher entropy, subject to a constraint on the divergence between $Q$ and $P$.

1. Optimization Formulation:
   The problem is formulated as maximizing the Shannon entropy $H(Q)$ of the replacement distribution $Q$, subject to a divergence constraint $D(Q || P) \leq \delta$, where $\delta$ represents the allowable deviation (security budget) based on Eve's detection capabilities. The authors consider two divergence measures:

   • Kullback-Leibler (KL) Divergence: A closed-form solution is derived where the optimal $Q$ is obtained by applying temperature scaling to the logits of the original distribution $P$. Specifically, $Q$ corresponds to $P$ scaled by a temperature parameter $T \geq 1$.
   • Total Variation (TV) Distance: The optimal solution follows a "water-filling" procedure, where probability mass is redistributed from high-probability tokens to low-probability tokens to equalize probabilities up to a certain threshold, effectively flattening the distribution.

2. Adaptive Parameter Selection:
   To prevent the generation of unnatural text (especially in low-entropy contexts where token choices are nearly deterministic), the divergence budget $\delta$ is not fixed globally. Instead, it is set adaptively as a function of the current token's entropy: $\delta_i = C \cdot H(P_i)$, where $C$ is a tunable constant.

3. Practical Engineering Solutions:
   The paper addresses three critical practical issues:

   • Tokenization Mismatch: Standard tokenizers do not guarantee a unique token sequence for a given text (e.g., "mountain" vs. "mount" + "ain"). The authors propose a prompt selection strategy where Alice prepends a short sequence of "dummy" bits ($B$) to the secret message. She iterates through combinations of $B$ until the resulting stego-text can be correctly tokenized and decoded by Bob, who then discards $B$.
   • Vocabulary Truncation: To reduce computational complexity, the vocabulary is truncated to the top $N_\epsilon$ tokens (where the cumulative probability is $1-\epsilon$). The authors prove that the total KL divergence is additive across the truncation and optimization stages, allowing for precise control of the overall security budget.
   • Integration with Non-AC Methods: The approach is shown to be compatible with existing techniques that do not rely strictly on arithmetic coding, such as Discop (which uses distribution copies). The optimized distribution is applied prior to the encoding step in these frameworks.

Key Contributions

• Theoretical Formulation: The paper establishes that maximizing embedding capacity under a security constraint is equivalent to maximizing the entropy of the token distribution subject to a divergence constraint. It provides closed-form solutions for both KL and TV constraints.
• OD-Stega Framework: A practical system that integrates optimized distributions with arithmetic coding, addressing tokenization errors via a verification loop and managing computational costs via vocabulary truncation.
• OD-Discop: A demonstration that the optimization technique can be universally applied to improve the embedding utility of other steganographic methods, specifically the Discop technique.
• Empirical Validation: Extensive experiments using LLaMA2-7B and GPT2-XL models, evaluating embedding utilization, detection rates against state-of-the-art steganalysis tools (FCN, SESY, GS-Llama), and human-like perception via GPT-4.

Experimental Results

• Embedding Utilization: The experiments demonstrate a significant trade-off between security and capacity. By increasing the parameter $C$ (which increases the divergence $\delta$), the number of embedded bits per 25 tokens increases substantially.
  • With a strict constraint ($C=0.01$, simulating a strong detector), embedding utilization increased by approximately 20% compared to baseline truncation methods.
  • With a relaxed constraint ($C=0.05$, simulating a weak detector), utilization increased by up to 55%.
• Steganalysis Performance: When tested against FCN, SESY, and GS-Llama detectors:
  • For low $C$ values, the stego-texts were largely indistinguishable from natural LLM text (detection rates near random guessing).
  • As $C$ increased, detection rates rose, confirming the controllable nature of the security degradation.
• Perception Evaluation: GPT-4 evaluations showed a correlation between the divergence parameter and the likelihood of the text being flagged as non-human, consistent with the steganalysis results.
• Tokenization Robustness: The proposed bit-padding verification method successfully resolved tokenization mismatches without requiring exhaustive enumeration.

Significance and Claims
The paper claims that OD-Stega provides a principled approach to relatively secure steganography, offering a design freedom that balances embedding capacity and detectability. Unlike "perfectly secure" methods that may be limited by the low entropy of natural language generation, OD-Stega explicitly exploits the limitations of the eavesdropper (Eve) to maximize information hiding.

The authors emphasize that their method is universal, capable of enhancing existing AC-based and non-AC-based schemes (like Discop). They position the KL divergence (or TV distance) not just as a theoretical metric, but as a practical control lever (hyperparameter) that allows engineers to tune the system based on the specific threat model and application requirements. The work acknowledges limitations, noting that the optimization is performed token-by-token without long-term look-ahead (due to computational costs) and that the "imperceptibility threshold" is treated as a tunable parameter rather than a learned perceptual model.