# SparSamp: Efficient Provably Secure Steganography Based on Sparse Sampling

arXiv: https://arxiv.org/abs/2503.19499 · HTML: https://mlsanity.com/paper/2503.19499/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2025.

## Built on by (most cited first, 14 of 14)

- [Efficient Provably Secure Linguistic Steganography via Range Coding](https://mlsanity.com/paper/2604.08052/) (2026)
- [Provable Secure Steganography Based on Adaptive Dynamic Sampling](https://mlsanity.com/paper/2504.12579/) (2025)
- [Anchored Sliding Window: Toward Robust and Imperceptible Linguistic Steganography](https://mlsanity.com/paper/2604.09066/) (2026)
- [Steganography Without Modification: Hidden Communication via LLM Seeds](https://mlsanity.com/paper/2606.09135/) (2026)
- [HiTMS: A High-Throughput Multi-Stream Linguistic Steganography Framework](https://mlsanity.com/paper/2607.23597/) (2026)
- [An LLM Framework For Cryptography Over Chat Channels](https://mlsanity.com/paper/2504.08871/) (2025)
- [S2LM: Towards Semantic Steganography via Large Language Models](https://mlsanity.com/paper/2511.05319/) (2025)
- [Robust Provably Secure Image Steganography via Latent Iterative Optimization](https://mlsanity.com/paper/2603.09348/) (2026)
- [Text Steganography with Dynamic Codebook and Multimodal Large Language Model](https://mlsanity.com/paper/2604.20269/) (2026)
- [FADRW: A Feature-Aware Modulated and Dynamically Reweighted Loss for Few-Shot Linguistic Steganalysis](https://mlsanity.com/paper/2606.07655/) (2026)
- [DHMark: Public-Key Watermarking for LLM-Generated Text via Diffie-Hellman-Guided Rejection Sampling](https://mlsanity.com/paper/2608.03093/) (2026)
- [PURA: Provably Unbiased and Robust Multi-Bit Watermarking for AI-Generated Text Attribution](https://mlsanity.com/paper/2608.22218/) (2026)
- [A Comprehensive Survey on Linguistic Steganography: Methods, Countermeasures, Evaluation, and Challenges](https://mlsanity.com/paper/2608.29077/) (2026)
- [Codetta: High-Capacity, Keyless, and Undetectable Multi-Agent Collusion](https://mlsanity.com/paper/2609.28900/) (2026)

## Abstract (arXiv)

Steganography embeds confidential data within seemingly innocuous communications. Provable security in steganography, a long-sought goal, has become feasible with deep generative models. However, existing methods face a critical trade-off between security and efficiency. This paper introduces SparSamp, an efficient provably secure steganography method based on sparse sampling. SparSamp embeds messages by combining them with pseudo-random numbers to obtain message-derived random numbers for sampling. It enhances extraction accuracy and embedding capacity by increasing the sampling intervals and making the sampling process sparse. SparSamp preserves the original probability distribution of the generative model, thus ensuring security. It introduces only O(1) additional complexity per sampling step, enabling the fastest embedding speed without compromising generation speed. SparSamp is designed to be plug-and-play; message embedding can be achieved by simply replacing the sampling component of an existing generative model with SparSamp. We implemented SparSamp in text, image, and audio generation models. It can achieve embedding speeds of up to 755 bits/second with GPT-2, 5046 bits/second with DDPM, and 9,223 bits/second with WaveRNN.