Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Shimmer: a Provably Secure Steganography Based on Entropy Collecting Mechanism

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

scope and security claim

Shimmer hides a bit string in language-model-generated text while attempting to preserve the model’s token distribution. It modifies arithmetic-style interval embedding with an entropy-collecting interval and a modulo-one pseudorandom shift. The paper says: “This paper introduces a practical and provably secure steganography scheme.” (abstract, p. 5949) In the security game the adversary has “access to the same models used by the sender and receiver, as well as their communication history” and tries to distinguish stegotext from covertext (section 3.2, p. 5952); the paper does not say the adversary sees the key. The construction assumes a secure pseudorandom generator (PRG), a key shared in advance, and the same generative model and PRG on both sides (section 3, p. 5952).

The formal goal is computational indistinguishability. The paper states: “A steganography scheme is computationally secure if no probabilistic polynomial-time adversary can distinguish between stegotext (generated by the steganography scheme) and covertext (generated by the model).” (section 3.2, p. 5952) The proof is a sequence of games replacing the PRG with true randomness, replacing a random poly(λ)-bit string converted to a decimal with a uniform real number, and showing that inverse-transform sampling recovers the model distribution (section 3.4.3, pp. 5954–5956). The games are written for one generation step.

technique: interval sampling with entropy collection

What it is: convert a secret prefix to a decimal number, normalize it to the current iterative interval, shift it by a fresh pseudorandom real modulo one, sample a token whose model probability interval contains the shifted number, shift the token interval back, and merge it into an iterative interval. Shared binary prefixes of the iterative interval encode recoverable bits. The interval is initialized to [0,1].

How to do it:

  1. Run PRG_sk(i) for token index i and obtain r; use the model predictor to get the cumulative distribution DistV (section 3.4.1, p. 5953; Algorithm 3, lines 5–6, p. 5956).
  2. Convert the next β secret bits to Dec(B1:β). The prose computes r′ = r + Dec(B1:β) mod 1 (section 3.4.1, p. 5953); Algorithm 3, line 7 (p. 5956) computes r′ = r + (Dec(B1:β) − inf{I})/(sup{I} − inf{I}) mod 1, which depends on the current iterative interval I.
  3. Apply inverse-transform sampling to r′ (Algorithm 1, p. 5953) and append the sampled token to the prompt/history.
  4. Only if r lies outside the sampled token’s interval (r ≤ DistV(t−1) or r ≥ DistV(t)), shift [DistV(t−1), DistV(t)] backward by r modulo one and merge it with the iterative interval I using the interval-merge operation ◦ of section 3.1.6 (p. 5952); otherwise skip the merge (Algorithm 3, lines 10–12, p. 5956).
  5. Compare the β-bit binary expansions of the interval’s lower and upper bounds. Extract their common prefix with Algorithm 2 (p. 5953), remove that prefix from the remaining message (Algorithm 3, line 14, p. 5956), and expand the interval by dropping the extracted bits (Algorithm 2, line 12).
  6. Repeat until the model naturally halts. The decoder repeats PRG, prediction, interval shifting, merging and prefix extraction over the received tokens and appends the extracted bits (Algorithm 4, p. 5957).

The running example embeds B = 01010101..., whose decimal value is 0.3333.... It uses r1 = 0.4, obtains r1 + B̄ = 0.7333... in the token interval [0.7,1.0), shifts back to [0.3,0.6), cannot embed bits in the first step. In the second and third steps the merged interval has the shared prefix 01, which is extracted each time. After three iterations it has embedded 0101, leaving the interval [0.088, 0.52) whose remaining information is −log2(0.52 − 0.088) = 1.2109 bits (section 3.4.2, p. 5954).

Verus form: Inference: represent intervals as a struct with rational or fixed-point bounds and define spec fn for modulo-one shifting, merging, inverse sampling, and prefix extraction. Use requires for ordered bounds and β, and ensures that extracted bits are a common prefix and that the updated interval contains the residual decimal message. Loop invariants can state that the secret decimal remains in the iterative interval. Inference: Verus can prove interval arithmetic and encoder/decoder agreement for a modeled distribution; it cannot prove PRG pseudorandomness or an LLM’s distributional assumptions.

technique: game-based proof of indistinguishability

The proof starts with G1, which uses PRG output, and G2, which uses true random numbers. A distinguisher for G1/G2 would distinguish the PRG from random. G2 is then compared with G3, which draws a real number directly instead of converting a poly(λ)-bit random string. G4 removes the secret bits and G5 is the model’s own sampler. The paper concludes the hybrid sequence: “We have proved that G1 ≈c G2 ≈s G3 = G4 = G5 .” (section 3.4.3, p. 5956) Observation: the games in Figure 3 (p. 5956) use r′ = r + Dec(B1:β) mod 1, while Algorithm 3 normalizes by the interval I.

How to apply it:

  1. Define the real experiment as covertext generated by the model and the ideal experiment as Shimmer stegotext.
  2. Replace the PRG output with true random bits (G1 to G2) by a reduction: an adversary A′ that has oracle access to PRG and to true randomness runs the distinguisher A on the games (section 3.4.3, p. 5954).
  3. Replace the poly(Ν)-bit random decimal with a uniform real in [0,1] (G2 to G3). The per-token probability differs by at most 1/2^poly(Ν), so the total variation distance is (1/2)¡Σ 1/2^poly(Ν) over |V| tokens, negligible in Ν (section 3.4.3, p. 5955).
  4. Show that adding the secret decimal modulo one keeps r uniform in [0,1], so the token probability remains DistV(t)−DistV(t−1) (G3 = G4), and that G4 equals the model’s sampler (G4 = G5) (section 3.4.3, pp. 5955–5956).
  5. Conclude, in the paper’s words, that “The output distribution of Shimmer and Model in each step is computationally indistinguishable.” (section 3.4.3, p. 5956) The paper supplies distinct PRG inputs per step so that the PRG outputs are pseudorandom.

Verus form: Inference: game transitions are outside ordinary Verus functional proofs. Verus can prove algebraic lemmas such as measure preservation of modulo-one translation over a finite discretized domain, but computational indistinguishability requires a cryptographic reduction and a separately trusted PRG theorem.

technique: interval-splitting mitigation (Shimmer (R.))

The interval-splitting event happens when r lies inside the chosen token interval and the shifted decimal falls in one of the two parts given by equations (20) and (21) (section 3.4.6, p. 5958, Figure 4). The paper says splitting “does not waste the information, but it is harmful to the correctness of our steganography scheme, as extracting the prefix of secret bits B from 2 intervals may lead to decoding error.” The mitigation stores an exclusion interval E = [DistV(t) − r, 1 − (r − DistV(t−1))] and, when I is small enough (or E big enough), subtracts the excluded part from I without splitting it (Algorithms 5 and 6, p. 5959). In the experiments, Shimmer (R.) denotes this improved scheme (MEncode, MDecode) and Shimmer denotes the original (section 4.1, p. 5959). Observations: Algorithm 5 computes r′ and samples t exactly as Algorithm 3, so only the interval bookkeeping changes. Algorithm 6 takes an undefined parameter α, starts I at [1/2, 1/2 + 1/2^α] instead of [0,1], and uses t without defining it. The paper gives no separate security proof for MEncode and MDecode, and section 4.4.2 mentions “Shimmer without reordering” without defining a reordering step for Shimmer in the text. Inference: since the sampling step is unchanged, the section 3.4.3 games would apply to Shimmer (R.) as well.

evidence and measured tradeoffs

Experiments use Ν = 256 and β = 64, Llama 3, Llama 2 and Mistral, top-100 sampling, maximum 512 generated tokens, 10,000 responses per test with each response longer than 100 tokens, and four NVIDIA RTX 3090 GPUs (sections 4.1 and 4.2, p. 5959; the model-generated responses are sampled from the top-100 tokens). Table 1 (p. 5960) reports perplexity, entropy, embedding capacity, time, utilization, and channel capacity. For Llama 3, Shimmer reports entropy 1.6968 bits/token, embedding capacity 1.3230 bits/token, 35.6269 ms/token, 77.97% utilization and 37.1349 bit/s channel capacity; Shimmer (R.) reports entropy 1.7441, embedding capacity 1.3531 bits/token, 77.58% and 37.9745 bit/s. For Llama 2, Shimmer reports entropy 2.3670, embedding capacity 1.8187 bits/token, 46.4434 ms/token, 76.84% and 39.1595 bit/s; Shimmer (R.) 2.4052, 1.8717, 77.82% and 40.0223 bit/s. For Mistral, Shimmer reports entropy 1.6295, embedding capacity 1.1418 bits/token, 47.0969 ms/token, 70.07% and 24.2436 bit/s; Shimmer (R.) 1.5978, 1.1592, 72.55% and 24.2910 bit/s. Each value belongs to one model/method test configuration in Table 1, not a pooled cross-model average. Entropy differs between methods in the same row group because each method generates its own text.

Comparison from the same table: on all three models Shimmer’s channel capacity exceeds METEOR, DISCOP, and their enhanced versions (Llama 3: 37.1349 against 26.7985, 9.1546, 28.3486 and 8.9820 bit/s). DISCOP (Recursive) has higher embedding capacity and utilization than Shimmer on all three models (Llama 3: 1.5942 bits/token and 91.33%, against 1.3230 and 77.97%) but runs at 177.4882 ms/token against 35.6269. The paper’s conclusion claims the “highest channel capacity” (section 5, p. 5961), not the highest per-token capacity.

The paper defines utilization as embedding capacity divided by entropy and channel capacity as embedding capacity divided by time (section 4.3, p. 5960). Perplexity is used as the fluency proxy. The authors report Shimmer’s perplexity close to random sampling and utilization around 77% on Llama 3 and Llama 2 (section 4.4.1, pp. 5960–5961). The theory section lower-bounds capacity by (2/3)E[Info(T)] − (1/5)|T| − β (section 3.4.5, p. 5958), but the authors say the “theoretical bound is not tight at all” (section 4.3, p. 5960). Inference: the paper contains no steganalysis detector experiment and no test with mismatched model, tokenizer, prompt, key or history, so the results do not establish security against a detector outside the game or robustness to such mismatches.

trusted boundary and relevance to VL

Proved: game-based computational security under PRG and sampling assumptions (section 3.4.3). Argued informally in a short paragraph: encoder/decoder correctness (section 3.4.4, p. 5956, “the proposed steganography scheme is always correct”). Measured: perplexity, capacity and runtime under three LLMs and stated GPU/test settings. Trusted: PRG security, model distribution and predictor, synchronized history, and floating-point/interval implementation. Inference: the threat to agent-written verified Rust is that a proof of interval arithmetic can leave the model interface, randomness source, and real-number numerics unverified. Inference: VL can reuse the explicit separation of executable algorithms, mathematical interval specifications, and cryptographic assumptions, but should not claim that Verus proves indistinguishability. Inference: existing work already provides the Shimmer construction and proof strategy; VL should focus on verified implementation boundaries or a new application rather than re-deriving the same scheme.

techniques for the catalog

  • entropy-collecting intervals: merge shifted token probability intervals and extract common prefixes to reuse residual entropy
  • modulo-one pseudorandom shift: add secret decimal values to PRG reals modulo one before inverse-transform sampling
  • synchronized decoder: replay PRG, model prediction, interval merge and prefix extraction over shared history
  • game-based security proof: replace PRG and discrete random values through hybrids until ordinary model sampling remains
  • interval-splitting mitigation (Shimmer (R.)): track an exclusion interval and subtract it from the iterative interval without representing disjoint intervals
  • capacity evaluation: report perplexity, entropy, bits/token, time, utilization and bits/second with model-specific denominators Checked 2026-10-16 against the full paper by a Claude agent (mid-paper quote: “As the last iterative interval cannot be extracted for any secret bit, we subtract the remaining amount of information as well.”): read the whole paper text once, from the first line to the last (the Figure 5 axis text is garbled in the text version and was not read); checked every quotation, page and section reference, the algorithm line references, the running example, the proof steps, the experimental settings and all Table 1 numbers quoted here; changed the link to the paper text’s presentation page, the abstract and security-definition citations (page and section), the adversary description (no key access), the Table 1 values (the study had given entropy as embedding capacity), the proof steps, the meaning of Shimmer (R.) (the study had called it a reordered variant), the unsupported detector claim, and marked inferences; did not check the cited external works, the proofs’ algebra beyond reading the steps, the Zenodo code, or the PDF figures.

Last edited: