Stochastic Encoding for Secure and Covert Communication

322 concepts224 papers1 proposal

In classical information theory, encoding is typically deterministic: a specific message maps directly to a unique codeword. While efficient for standard error correction, this predictability is a severe liability when communicating in the presence of an adversary. If an eavesdropper or jammer knows the exact structural mapping between messages and codewords, they can easily intercept the data or optimize their jamming strategy to cause maximum disruption.

Stochastic encoding solves this problem by breaking the one-to-one mapping. Instead of mapping a message to a single codeword, a stochastic encoder maps a message to a probability distribution over a set of multiple valid codewords. By injecting local randomness at the transmitter, the exact codeword sent becomes unpredictable, even if the adversary possesses the entire codebook.

Random Binning and Adversarial Ambiguity

To understand the core mechanics, imagine a codebook divided into discrete "bins," where each bin corresponds to a unique logical message. Each bin contains many different codewords. When a sender wants to transmit a message, they do not use a fixed formula; instead, they use local randomness to select one codeword from that message's designated bin.

As Yingbin Liang demonstrates in Generalized Multiple Access Channels with Confidential Messages, this stochastic codeword binning introduces deliberate ambiguity for an eavesdropper. While a legitimate receiver can use correlated side information or a channel advantage to resolve which specific message was intended, an unauthorized observer cannot distinguish the true message from the added randomness.

This mechanism is particularly powerful against "myopic" adversaries who only get an imperfect or noisy view of the transmission. In Authentication Against a Myopic Adversary, Beemer et al. show that stochastic encoding can restore optimal authentication capacity even when standard deterministic encoders completely fail. By mapping a single message to a distribution of potential codewords, the encoder prevents an attacker from confidently identifying or forging valid codewords, because the attacker's imperfect view prevents them from pinning down the exact random choices made by the transmitter.

Forcing Adversarial Channels to Behave

Beyond hiding message content, stochastic encoding fundamentally alters how a communication channel behaves. In an adversarial channel, a malicious actor might observe the transmission and dynamically target specific bits to cause decoding failures.

However, if the encoder uses local randomness to scramble the message before it hits the channel, the adversary can no longer predict which physical bits carry which pieces of information. As Guruswami et al. prove in Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate, this local randomization effectively converts an adversarial channel into a benign stochastic one for computationally bounded jammers. Because the codeword appears unpredictable to the channel, the jammer cannot optimize its attack pattern against specific data bits.

Similarly, in the context of active jamming over wiretap channels, Nötzel et al. show in The Arbitrarily Varying Wiretap Channel - Secret Randomness, Stability and Super-Activation that randomized codebook selection prevents a jammer from aligning their interference strategy with the communication protocol, neutralizing the jammer's ability to create undetectable errors.

Burying Signals within Noise

When the goal is covert communication—hiding the very existence of the transmission from a watchful warden—stochastic encoding becomes indispensable. The objective here is to make the transmitted signal statistically indistinguishable from background noise.

In Computationally Efficient Deniable Communication, Zhang et al. achieve this by combining systematic outer codes with low-weight random inner codes. The low-weight random inner codes spread the signal across the entire transmission block, burying it within the statistical fluctuations of the channel's inherent noise. This ensures that no localized bursts of energy exceed the expected noise variance, leaving an eavesdropper with no statistical leverage to detect the transmission.

When the transmitter has noncausal knowledge of the channel's state (such as environmental noise or interference patterns), the authors of Covert Communication With Channel-State Information at the Transmitter utilize a technique called likelihood encoding. Instead of choosing a codeword blindly, the encoder selects a codeword that is statistically consistent with the known sequence of channel states. This ensures that the resulting transmission distribution perfectly mimics background noise, allowing for reliable communication at a positive rate where traditional methods would be forced to zero.

Integrating Randomness into Structured Codes

A key challenge of stochastic encoding is implementing these probabilistic guarantees without sacrificing the mathematical structure required for efficient error correction. Modern frameworks solve this by embedding cryptographic confusion directly into the code's algebraic design.

For instance, polar codes naturally separate a communication channel into highly reliable and highly noisy bit-channels. In Secret Key Cryptosystem based on Polar Codes over Binary Erasure Channel, Hooshmand et al. replace the standard, fixed "frozen bits" of a polar code with pseudorandom syndromes generated by a linear feedback shift register. This technique forces the decoder to possess the exact syndrome sequence to successfully recover the original message, effectively turning error-correction overhead into an active security layer.

Deterministic Encoding:
[Message m] ---------> [Unique Codeword x] ---------> [Channel]

Stochastic Encoding (Random Binning):
                       /-> [Codeword x1] \
[Message m] -> [Bin] ----> [Codeword x2]  ----> (Random Selection) ----> [Channel]
                       \-> [Codeword x3] /

In distributed storage environments, Pawar et al. demonstrate in On secure distributed data storage under repair dynamics that an outer code can utilize Maximum Distance Separable (MDS) coset coding to inject random noise into stored data. By allocating a portion of the storage capacity to non-informative random data, they ensure that any subset of data intercepted by an eavesdropper during node repair remains statistically indistinguishable from pure noise, achieving perfect secrecy through structural randomization.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 234 papers
  2. Version 1 · 2026-10-04 · 194 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_stochastic_encoding_60eb8e00,
  title = {stochastic encoding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-encoding/rdr_60eb8e0009a044568c018b9d1da1963d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_stochastic_encoding_60eb8e00_v2,
  title = {stochastic encoding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-encoding/rdr_60eb8e0009a044568c018b9d1da1963d/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake