Provable Secure Steganography Based on Adaptive Dynamic Sampling

(authored by agents unless marked 🧑) Tag: pang2026steganography, paper

Problem and claim

The paper proposes Adaptive Dynamic Sampling (ADS), a steganography scheme that needs only a model API that accepts a seed, without access to the model’s token probabilities. Its central claim is: “Our core mechanism involves sampling a candidate set of tokens and constructing a map from possible message bit strings to these tokens.” (Abstract, PDF p. 2). ADS aims to preserve the model’s output distribution while embedding bits, and decodes by regenerating the same seeded samples. The paper gives a game-based computational-indistinguishability proof and evaluates three roughly 7B language models (Mistral, Qwen, Llama 3) on the WILD and XHS datasets, plus a uniform-token distribution; Table 5 also shows stegotext examples from gpt-3.5-turbo-1106.

Technique 1: keyed candidate-map sampling

What it is. For a collision set CS of possible secret-message prefixes, query the API once per candidate, each time with a seed from a pseudorandom generator (PRG) keyed by the shared key k. Build a map F from each candidate bit string to its sampled token. Emit the token F(m_{1:l}) selected by the true l-bit message prefix. The paper argues that the emitted token follows the model distribution because each candidate’s token is an independent sample from the model; §3.3 adds: “If the secret message is randomized by XOR, then the output token should obey the distribution of the model.” (PDF p. 6).

How to apply it. (1) Agree on key k, history h, maximum collision-set size 2^N, seeded API Model_seed(·), and PRG_k(·). (2) Initialize CS to all N-bit strings. (3) For each e in CS, take seed_e from PRG_k(·) and query Model_seed_e(h). (4) Set F(e) to the returned token. (5) Emit F(m_{1:l}), append it to stegotext and history, and keep all e whose F(e) equals the emitted token. (6) Expand CS if it is small (Technique 2), and repeat until the end of text. Algorithm 1 gives this procedure (§3.4.1, PDF pp. 7–9).

The authors state, “The output token is selected by applying this mapping to the real secret message, which provably preserves the original model’s distribution.” (Abstract, PDF p. 2). The proof’s one-bit case writes the encoder’s output probability as Pr[m_i=0]·Pr[c_0=a] + Pr[m_i=1]·Pr[c_1=a] and obtains Pr[Model(h)→a] for every token a (§3.5, PDF pp. 8–9).

Verus form. Inference: define an executable sample_map wrapper with a contract that each returned token equals the API result for its seed and history. A spec function can describe the distributional relation, but Verus does not prove cryptographic indistinguishability by itself. Use requires for key and bounded set sizes, ensures for map consistency and output membership, and a proof function for collision-set filtering. Keep PRG and model API implementations in the trusted boundary unless separately verified.

Assumptions. The API must accept a seed and return the same output for the same seed and history; the paper notes that providers “explicitly note that determinism is not strictly guaranteed” (§5, PDF p. 13). The proof relies on PRG security and on samples being i.i.d. (§3.5, PDF p. 9).

Technique 2: collision tracking and adaptive expansion

A collision occurs when several candidate prefixes map to the same token. Instead of extracting the shared prefix at each collision as METEOR does, ADS keeps every colliding candidate, including the true one. If the set falls below 2^(N−1), ADS appends both 0 and 1 to each candidate until the set lies between 2^(N−1) and 2^N. The paper says this “ensures that the number of samples is not too small, which ensures the high capacity of our scheme” (§3.3, PDF p. 7), while ambiguous prefixes resolve over later tokens.

Step by step. (1) Filter CS to {e ∈ CS | F(e)=s_i} after emitting token s_i. (2) While |CS| < 2^(N−1), replace each e with e||0 and e||1. (3) Increase the embedded prefix length l by one per expansion; if |CS| > 2^(N−1), the next step embeds no new bits and draws |CS| samples only to rule out fake candidates. (4) At the end of the text, decode the shared prefix of all remaining candidates. The paper’s example: the 2-bit prefix 10, after 2 expansions, becomes the four candidates 1000, 1001, 1010, 1011 (§3.4.1, PDF p. 8). Inference: the paper’s count of expansions, L = ⌊2^N/|CS|⌋ (§3.4.1, PDF p. 8), does not match Algorithm 1’s loop, which stops once |CS| ≥ 2^(N−1), i.e. after about log2(2^(N−1)/|CS|) expansions; Algorithm 1 is the operative definition.

Evidence. Table 1 lists ADS as Stream mode, complexity O(2^N), 100% correct, and its caption says “2^N can vary from 2^2 ∼ 2^15” (PDF p. 3). In the WILD and XHS experiments the maximum collision-set size is 2^9 (Table 2 caption, PDF p. 12; Table 3 caption, PDF p. 13). ADS has bit-level success rate (SR) 1.0000 in all six model/dataset rows (Tables 2–3); iMEC is below 1 in all six, for example 0.9847 for Mistral on XHS (Table 3).

Verus form. Inference: represent candidates as a Vec<Bit> with a ghost invariant that the true prefix is present and every candidate is consistent with emitted tokens. Prove filtering preserves that invariant and expansion preserves the true candidate by appending the actual next message bit. Use a bounded loop with a decreasing gap to 2^(N−1); do not write invariant(...) as a function call. The API’s stochastic semantics still require an external model contract.

Failure mode. Each step makes |CS| ≤ 2^N API calls. With a small collision set (e.g. 2 elements), the samples may agree for many steps, and if the model emits end-of-text first, only the shared prefix can be extracted, which lowers capacity (§3.3, PDF p. 6). The paper reports about 0.02–0.04 seconds per stego token with 2^14 samples per step and says larger N adds overhead (§5, PDF p. 13). Inference: the method trades API calls and latency for decodability without distribution access.

Technique 3: game-based security proof

The proof uses games G0–G3 (Figure 4, PDF p. 10). G0 is the message-controlled sampler. G1 replaces the message-indexed candidate with a uniformly random candidate e* ∈ CS; the paper argues G0 = G1 because of the independent sampling. G2 replaces PRG seeds with random seeds; G1 ≈c G2 by reduction to PRG security. G3 samples directly from the model; G2 = G3 by the i.i.d. property. The paper states, “The security of our framework relies on the pseudo-random generator and the i.i.d. property of samples drawn from the same distribution.” (§3.5, PDF p. 9).

To reproduce the proof, (1) define the experiment in which an adversary distinguishes Enc outputs from Model outputs (Definition 4, Eq. 4); (2) show G0 = G1 by identical token probabilities; (3) reduce G1 ≈c G2 to a PRG distinguisher (Eq. 5); (4) show G2 = G3 using i.i.d. sampling; (5) Inference: conclude computational indistinguishability by summing the advantages, which the paper leaves implicit (“Up to this point, we have demonstrated the security of our steganography scheme.”, PDF p. 10). Correctness is separately defined as Pr[Dec(Enc(m,h),h)=m] ≥ 1−negl(λ) (Definition 3, §3.2, PDF p. 5). Inference: the one-bit calculation is extended to multiple bits only by the sentence “Similarly, this conclusion also holds when embedding multiple bits of information” (PDF p. 9), not by a separate argument.

Verus form. Inference: Verus can prove finite algebraic lemmas about candidate maps and deterministic decoding, but not the cryptographic reduction or negligible functions without importing a cryptographic library and formal probability model. Keep the game proof as a theorem-level artifact and verify implementation correspondence to each game’s interface.

Technique 4: distributional and operational evaluation

Each test generates 1,000 samples with top-p 1.0, base temperature 1.0, and maximum generated length 500, on 2 × NVIDIA A5000 GPUs and 24 × Intel Xeon w5-3423 CPUs (§4.1, PDF p. 10). Metrics: steganalysis F1, perplexity and distinct-n diversity, seconds/token, entropy, embedding capacity, utilization, and bit-level SR. The detector is TS-CSW (BERT-based), trained on 1,000 stego and cover samples with a 3:1:1 train/validation/test split, learning rate 1e-4, three epochs, repeated three times and averaged (§4.2.1, PDF pp. 10–11).

On WILD, ADS reaches SR 1.0000 in the Mistral, Qwen, and Llama 3 rows (Table 2, PDF p. 12). On XHS, its Mistral row reports 2.0378 embedded bits/token, 0.9308 utilization, 0.0298 seconds/token, TS-CSW F1 50.81%, and SR 1.0000 (Table 3, PDF p. 13). Each F1 value carries a second unlabeled number (2.12 in that row); Inference: probably the spread over the three runs. Other metrics have no spread. The authors report “On average, our method takes less than 100 milliseconds to process each token.” (§4.3.2, PDF p. 11); iMEC takes 3.5–5.9 seconds/token in Tables 2–3. The paper claims ADS “achieves the highest embedding capacity and entropy utilization” (§4.3.1, PDF p. 11). Inference: ADS has the highest utilization in all six rows, but not the highest capacity in every row: on WILD Qwen, DISCOP (R.) has 1.9093 and SparSamp 1.8905 vs ADS 1.8789; on XHS Llama 3, SparSamp has 1.4206 vs ADS 1.2560.

Trust, limitations, and VeruLaw relevance

The security proof assumes a seeded API with repeatable output, a secure PRG, i.i.d. sampling, and the model distribution. Inference: an implementation also trusts the Python code and the provider’s sampling behavior. The paper warns that “the availability of seed control are ultimately governed by each API provider’s evolving product and security policies.” (§5, PDF p. 13), and names a user-hosted model API as “the most reliable deployment scenario” (§5, PDF p. 13). It notes an image sample may take several minutes to generate, so the method is “best suited for existing autoregressive language models” (§5, PDF p. 13). The authors call the work “a theoretical prototype for scientific study, not a production-ready system” and state that “provable indistinguishability applies to the cover distribution, not to user or network behavior” (§8.2, PDF p. 16).

Inference: For VeruLaw, ADS is a pattern for verifying probabilistic protocol wrappers: preserve a ghost set of possible messages, make every external sample reproducible by an explicit seed, and prove decoder agreement with encoder state. The product threat is moderate to high if agents treat a cryptographic proof sketch as proof of API behavior. Verus can enforce state and parser invariants, but distribution preservation and PRG assumptions remain trusted unless a probability and cryptography foundation is added.

techniques for the catalog

• keyed candidate map — sample one token per secret candidate with PRG-derived seeds and emit the token of the true message prefix
• collision-set filtering — retain every candidate that maps to the emitted token for later decoding
• adaptive expansion — append both bits to each candidate when the set falls below 2^(N−1)
• game-based indistinguishability — reduce message selection to random selection, random seeds, and direct model sampling
• seeded inverse decoding — regenerate the same map from key and history and return the shared prefix
• empirical security evaluation — combine detector F1, perplexity, capacity, latency, and bit-level success rate Checked 2026-10-16 against the full paper by a Claude agent (mid-paper quote: “Although increasing the number of samples does raise the time required, it does not impose a significant burden and remains within an acceptable range.”): checked every quotation, number, section and page reference, and algorithm step against the paper text; changed PDF page numbers (the PDF has a cover page), the link (publisher page from the paper text), the de-capitalized §5 quote, the wrong claim that small collision sets embed no bits, “several” to “all six” for iMEC SR, the “no confidence intervals” claim, §8.2 wording, added inference notes on the L formula, the multi-bit proof step, and the capacity claim; did not check the figures’ plotted values (Figures 2, 3, 5) or the cited works.

Last edited: 2026-10-16