Provably Secure Steganography Based on List Decoding

• URL: http://arxiv.org/abs/2604.21394v3
• Date: Wed, 29 Apr 2026 02:12:57 GMT
• Title: Provably Secure Steganography Based on List Decoding
• Abstract summary: Steganography embeds secret messages in seemingly innocuous carriers for covert communication under surveillance.<n>Current Provably Secure Steganography schemes can guarantee computational indistinguishability between the covertext and stegotext.<n>We propose a provably secure steganography scheme with a theoretically proved high capacity.
• Score: 5.421129051557276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Steganography embeds secret messages in seemingly innocuous carriers for covert communication under surveillance. Current Provably Secure Steganography (PSS) schemes based on language models can guarantee computational indistinguishability between the covertext and stegotext. However, achieving high embedding capacity remains a challenge for existing PSS. The inefficient entropy utilization renders them not well-suited for Large Language Models (LLMs), whose inherent low-entropy tendencies severely constrain feasible embedding capacity. To address this, we propose a provably secure steganography scheme with a theoretically proved high capacity. Our scheme is based on the concept of list decoding: it maintains a set of candidates that contain the correct secret message, instead of directly finding the correct message with more effort. This strategy fully utilizes the information content of the generated text, yielding higher capacity. To ensure the correctness of our scheme, we further introduce a suffix-matching mechanism to distinguish the correct secret message from the candidates. We provide theoretical proofs for both the security and correctness of our scheme, alongside a derivation of its theoretical capacity lower bound. Our approach is plug-and-play, requiring only a direct replacement of the model's standard random sampling module. Experiments on three LLMs and seven PSS baselines demonstrate that our method achieves computational efficiency comparable to prior PSS schemes while delivering a substantial improvement in embedding capacity.

Related papers

• Alignment Imprint: Zero-Shot AI-Generated Text Detection via Provable Preference Discrepancy [51.887915969023965]
  We show that modern Large Language Models (LLMs) undergo alignment, leaving a measurable distributional imprint.<n>To mitigate the instability in high-entropy regions, we introduce Log-likelihood Alignment Preference Discrepancy (LAPD)<n>LAPD is a standardized information-weighted statistic based on alignment imprint.
  arXiv  Detail & Related papers  (2026-04-18T09:12:24Z)
• A high-capacity linguistic steganography based on entropy-driven rank-token mapping [81.29800498695899]
  Linguistic steganography enables covert communication through embedding secret messages into innocuous texts.<n>Traditional modification-based methods introduce detectable anomalies, while retrieval-based strategies suffer from low embedding capacity.<n>We propose an entropy-driven framework called RTMStega that integrates rank-based adaptive coding and context-aware decompression with normalized entropy.
  arXiv  Detail & Related papers  (2025-10-27T06:02:47Z)
• Physical Layer Deception based on Semantic Distortion [58.38604209714828]
  Physical layer deception (PLD) is a framework that integrates physical layer security (PLS) with deception techniques.<n>We extend this framework to a semantic communication model and conduct a theoretical analysis using semantic distortion as the performance metric.
  arXiv  Detail & Related papers  (2025-10-16T18:23:35Z)
• GTSD: Generative Text Steganography Based on Diffusion Model [21.996779455449094]
  We propose a generative text steganography method based on a diffusion model (GTSD), which improves generative speed, robustness, and imperceptibility while maintaining security.<n>Prompt mapping maps secret information into a conditional prompt to guide the pre-trained diffusion model generating batches of candidate sentences.<n>The batch mapping selects stego text based on secret information from batches of candidate sentences.
  arXiv  Detail & Related papers  (2025-04-28T02:42:52Z)
• Provable Secure Steganography Based on Adaptive Dynamic Sampling [0.0]
  Provably Secure Steganography is state of the art for making stego carriers indistinguishable from normal ones.<n>Current PSS methods often require explicit access to the distribution of generative model for both sender and receiver.<n>We propose a provably secure steganography scheme that does not require access to explicit model distributions for both sender and receiver.
  arXiv  Detail & Related papers  (2025-04-17T01:52:09Z)
• Shifting-Merging: Secure, High-Capacity and Efficient Steganography via Large Language Models [25.52890764952079]
  steganography offers a way to securely hide messages within innocent-looking texts.<n>Large Language Models (LLMs) provide high-quality and explicit distribution.<n>ShiMer pseudorandomly shifts the probability interval of the LLM's distribution to obtain a private distribution.
  arXiv  Detail & Related papers  (2025-01-01T09:51:15Z)
• Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information [53.85237314348328]
  We introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) We show that NU-HUNCC is information-theoretic individually secured against an eavesdropper with access to any subset of the links.
  arXiv  Detail & Related papers  (2024-02-13T12:12:39Z)
• Token-Level Adversarial Prompt Detection Based on Perplexity Measures and Contextual Information [67.78183175605761]
  Large Language Models are susceptible to adversarial prompt attacks. This vulnerability underscores a significant concern regarding the robustness and reliability of LLMs. We introduce a novel approach to detecting adversarial prompts at a token level.
  arXiv  Detail & Related papers  (2023-11-20T03:17:21Z)
• Perfectly Secure Steganography Using Minimum Entropy Coupling [60.154855689780796]
  We show that a steganography procedure is perfectly secure under Cachin 1998's information-theoretic model of steganography. We also show that, among perfectly secure procedures, a procedure maximizes information throughput if and only if it is induced by a minimum entropy coupling.
  arXiv  Detail & Related papers  (2022-10-24T17:40:07Z)
• Autoregressive Linguistic Steganography Based on BERT and Consistency Coding [17.881686153284267]
  Linguistic steganography (LS) conceals the presence of communication by embedding secret information into a text. Recent algorithms use a language model (LM) to generate the steganographic text, which provides a higher payload compared with many previous arts. We propose a novel autoregressive LS algorithm based on BERT and consistency coding, which achieves a better trade-off between embedding payload and system security.
  arXiv  Detail & Related papers  (2022-03-26T02:36:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.