PaperlayerView exact revision on arXiv

Source-linked AI summary

Reliable Deniable Communication: Hiding Messages in Noise

Pak Hou Che, Mayank Bakshi, Sidharth Jaggi

arXiv:1304.6693v2cs.IT

TL;DR

The paper asks how Alice can communicate reliably with Bob while concealing her transmission status from Willie over a noisier channel, without shared randomness. It analyzes fixed and uncertain channel parameters using public random-code constructions and variational-distance deniability, obtaining model-dependent reliable deniable communication results.

  • Problem

    The central problem is reliable communication to Bob while Willie cannot determine whether Alice is transmitting over a significantly noisier channel, even when the communication scheme is public and no common randomness is shared.

  • Method

    The paper studies fixed and slow-fading binary symmetric channels, constructs random binary codebooks, and analyzes deniability using variational distance and concentration inequalities.

  • Results

    The paper proves fixed-model converse and achievability bounds tight up to constant factors, and gives slow-fading achievability and converse results guaranteeing reliable and deniable codebooks.

  • Takeaways & Limitations

    Reliable deniable communication can be characterized in both exactly known and uncertain channel-parameter settings without relying on common randomness between Alice and Bob.

Abstract

from arXiv · show

A transmitter Alice may wish to reliably transmit a message to a receiver Bob over a binary symmetric channel (BSC), while simultaneously ensuring that her transmission is deniable from an eavesdropper Willie. That is, if Willie listening to Alice's transmissions over a "significantly noisier" BSC than the one to Bob, he should be unable to estimate even whether Alice is transmitting. We consider two scenarios. In our first scenario, we assume that the channel transition probability from Alice to Bob and Willie is perfectly known to all parties. Here, even when Alice's (potential) communication scheme is publicly known to Willie (with no common randomness between Alice and Bob), we prove that over 'n' channel uses Alice can transmit a message of length O(sqrt{n}) bits to Bob, deniably from Willie. We also prove information-theoretic order-optimality of this result. In our second scenario, we allow uncertainty in the knowledge of the channel transition probability parameters. In particular, we assume that the channel transition probabilities for both Bob and Willie are uniformly drawn from a known interval. Here, we show that, in contrast to the previous setting, Alice can communicate O(n) bits of message reliably and deniably (again, with no common randomness). We give both an achievability result and a matching converse for this setting. Our work builds upon the work of Bash et al on AWGN channels (but with common randomness) and differs from other recent works (by Wang et al and Bloch) in two important ways - firstly our deniability metric is variational distance (as opposed to Kullback-Leibler divergence), and secondly, our techniques are significantly different from these works.

I. INTRODUCTION

The paper studies reliable communication from Alice to Bob while Willie cannot determine whether Alice is transmitting, focusing on differential-noise channels without shared secret randomness. It analyzes fixed and slowly fading channel models, proving tight up-to-constant-factor bounds for the fixed model and achievability and converse results for the slow-fading model.

  • I. INTRODUCTION: The communication goal is to transmit reliably to Bob while preventing Willie from learning whether Alice is transmitting.The model is a differential-noise setting in which Willie’s channel is noisier than Bob’s, creating a reliability–deniability trade-off.
  • I. INTRODUCTION: The paper focuses on differential noise in binary channels, where Bob and Willie receive independent binary symmetric channel outputs with different noise parameters.The broader steganography literature also considers non-zero covertexts and shared secret keys, but this work studies public codes without common randomness.
  • I. INTRODUCTION: The paper’s deniability analysis uses variational distance and develops an intricate concentration-inequality analysis of random binary codes.The technically challenging part shows that the induced active distribution is close to the innocent distribution, with exponentially small intermediate deviations.
  • I. INTRODUCTION: The analysis is presented for binary-input binary-output symmetric channels, although the authors state that the techniques may generalize to broader channel pairs and sufficiently slowly fading settings.The slow-fading treatment specifically assumes independently and uniformly distributed noise parameters over predefined intervals for exposition.
  • I. INTRODUCTION: In the Fixed Channel model, channel parameters are known exactly, and the paper gives converse and achievability bounds whose throughput scaling is tight up to constant factors.The fixed-model converse bounds reliable deniable throughput by O(1/√n), while the achievability theorem establishes reliable and deniable codes in the corresponding throughput range.
  • I. INTRODUCTION: In the Slow Fading model, channel parameters are randomly drawn from known intervals, and the paper provides both an achievability theorem and a matching converse for reliable deniable communication.The stated guarantees include at least (1−ϵd)-deniability and at least (1−ϵr)-reliability for the constructed codebook.

A. Notations and Definitions

This section defines the random codebook, transmission distributions, typical sets, and notation used to analyze deniability and reliability.

  • Codebook and transmission: Alice’s codebook contains at most NS codewords, with S codewords assigned to each message and codewords generated independently.The codebook generation ensemble is denoted pC(C).
  • Codebook and transmission: When Alice is silent, the encoder maps message 0 deterministically to the all-zero vector; when transmitting, it selects codewords according to the message-conditioned distribution.The active distribution depends on the randomly generated codebook and may assign multiplied mass when codeword collisions occur.
  • Received-vector distributions: Willie’s silent received-vector distribution is the BSC noise distribution, while the active distribution averages channel outputs over Alice’s transmitted codewords.The corresponding ensemble distribution is obtained by averaging over possible codebooks.
  • Received-vector distributions: The ensemble-averaged active distribution at Willie equals the output from passing the all-zero vector through successive BSC(ρ) and BSC(pw) channels.Its probability depends on the Hamming weight of Willie’s received vector through the convolved parameter ρ ∗ pw.
  • Typicality and empirical quantities: Narrow typical sets constrain Hamming weights and conditional types around their expected values, with widths chosen on the order of O(1/√n).These sets distinguish low-weight codewords from relatively high-weight background noise while retaining high probability.

2) Empirical conditional entropy:

The converse bounds deniability by restricting high-weight codewords and then applies information-theoretic arguments to bound reliable-deniable throughput.

  • Converse strategy: Theorem 1’s proof has separate deniability and reliability components, with the deniability constraint feeding the subsequent rate bound.The argument applies to arbitrary codes, including encoders using private randomness.
  • Converse strategy: Too much probability mass on high-weight codewords lets Willie distinguish Alice’s transmission status with a threshold detector.Thus, deniable codebooks must concentrate most probability mass on low-weight codewords.

2) (Upper bound on

The achievability proof establishes deniability by comparing Willie’s distributions through an ensemble average, while reliability follows from typicality-based decoding.

  • Deniability: The active distribution at Willie is irregular because it depends on the particular codebook, motivating the ensemble-average comparison.The ensemble distribution smooths this dependence before concentration around its expectation is shown.
  • Deniability: The deniability proof bounds V(p0,p1) by comparing the silent distribution with an ensemble-averaged active distribution and then the ensemble average with the realized codebook distribution.The triangle inequality gives V(p0,p1) ≤ V(p0,EC(p1)) + V(EC(p1),p1).
  • Reliability: Bob’s reliability proof uses typicality and decoding arguments, while the slow-fading construction first determines transmission status and then applies maximum-likelihood decoding.The slow-fading proof reports V(p0,p1) < ϵd with high probability after combining its two bounds.
  • Deniability: A random codebook is deniable with high probability when its parameters are appropriately chosen, including the codebook generation parameter constraint in the slow-fading model.The slow-fading proof separately makes each variational-distance term small.
  • Converse detector: A threshold detector based on Willie’s received Hamming weight yields a deniability lower bound when the codebook has high-weight mass.The analysis computes false alarms and missed detections, combines them with Chebyshev’s inequality, and optimizes the threshold.

D. Proof of Proposition 1

Proposition 1 analyzes reliability separately for silence and transmission, using typical sets, decoding-ball occupancy, and concentration bounds for the random codebook.

  • Code construction: The random codebook contains 2^(r+rs)√n codewords generated bitwise according to Bernoulli(ρ).The parameter ρ controls the codeword-generation distribution.
  • Transmission case: When Alice transmits, the decoder checks typicality and uniqueness of the message represented in the conditional decoding ball.The decoding rule distinguishes silent and transmitting typical sets before selecting a unique message.
  • Reliability guarantee: The maximal decoding error when Alice transmits is shown to be small with super-exponentially high probability.This strengthens the reliability guarantee beyond an ordinary exponential probability statement over codebooks.
  • Silence case: When Alice is silent, Bob’s error analysis separates atypical received vectors from decoding balls containing competing codewords.Claims 4 and 5 address these two contributions.
  • Silence case: With probability at least 1 − 2^-Ω(√n) over the codebook, the silent-case decoding analysis controls competing codewords in the relevant decoding region.The argument uses random-codebook averaging, a union bound, and Markov’s inequality.

1) Achievability: Deniability:

The achievability proof establishes deniability by showing that the ensemble-induced distribution is close to Willie’s no-transmission distribution and that a randomly generated codebook closely approximates the ensemble distribution.

  • Deniability proof strategy: The deniability proof decomposes the variational distance into V(p0, EC(p1)) and V(EC(p1), p1), with the latter exponentially small for most codebooks.The first term compares Willie’s no-transmission distribution with the ensemble-smoothed active distribution; the second captures codebook-induced lumpiness.
  • Proof technique: The proof’s main novelty is Lemma 3, which uses concentration over random code design to control the difference between actual and ensemble output distributions.The expected number of codewords in conditionally typical types is concentrated because the codebook is sufficiently large.
  • Deniability proof strategy: 2^-Ω(nδ) bounds V(EC(p1), p1) with probability greater than 1 − exp(−Ω(√n)) over code design.The bound is obtained by combining the claims controlling typical and atypical output contributions.
  • Distribution comparison: The no-transmission and smoothed active distributions are product distributions induced by Bernoulli noise parameters pw and ρ∗pw, respectively.This representation supports the variational-distance comparison used in the deniability analysis.
  • Proof technique: 2^-nδ bounds the contribution from typical outputs and conditionally typical codewords to V(p1, EC(p1)) under high-probability code design.The remaining atypical terms are bounded separately using concentration arguments and Chernoff bounds.

F. Hidability of Fixed Channel Model (Theorem 3)

For the fixed-channel model, reliability and hidability follow from the earlier proposition and standard secrecy arguments after selecting the appropriate code parameters.

  • Hidability follows directly from standard secrecy arguments.

G. Converse for Slow Fading Channel Model (Theorem 4)

In the slow-fading model, Willie’s threshold analysis yields an outer bound based on channel-parameter uncertainty and codeword fractional weight, with large-weight codewords destroying deniability.

  • Slow-fading model: Channel-parameter uncertainty increases Willie’s noise uncertainty from O(√n) to linear-in-n behavior in relevant cases.The model draws pb and pw independently and uniformly from specified intervals.
  • Threshold estimator: Willie estimates Alice’s transmission status from the received vector’s fractional Hamming weight using a threshold t.The threshold is later optimized to minimize Alice’s deniability.
  • False alarms: For intermediate thresholds, false-alarm probability is bounded by Uw−Lw, while for t ≥ Uw + δ it is bounded by λ, which vanishes as n increases.
  • Missed detection: For a codeword of fractional weight ζ, Willie’s missed-detection bound changes across threshold regions and reaches 1 when t ≥ ζ∗Uw − ¯δ.
  • Converse: If Uw + δ ≤ ζ∗Lw − ¯δ, Willie can choose a threshold with α + β ≤ 0, so Alice’s transmission is not deniable.Thus, sufficiently large fractional-weight codewords create a direct converse obstruction.

2) Lower bound on the deniability parameter ϵd:

The converse links decoding error to the Bob-channel parameter and bounds how much codeword mass can occupy high fractional weights, using the monotonicity of decoding error and geometric comparisons.

  • Codeword-weight converse: The converse separates codewords by fractional weight and analyzes the lower-weight subcode to relate its rate and capacity to decoding reliability.The fraction γ(ζ) denotes the codebook mass of codewords whose fractional weight exceeds ζ.
  • Error monotonicity: The probability of decoding error r(ϵd, r, n, pb) is increasing in pb for pb ≤ 1/2.A noisier BSC can be simulated from a less noisy one by independently flipping additional received bits.
  • Error monotonicity: The increasing error curve has a unique intersection with pb = Ub − (Ub − Lb)ϵr|pb, defining the critical point used in the converse.
  • Geometric bounds: Figure 12 compares a red shadowed region with the area under the error curve, showing the former is smaller.
  • Geometric bounds: Figure 13 compares the corresponding red shadowed region with the area under the error curve, showing the former is larger.

H. Achievability of Slow Fading Channel Model (Theorem 5)

The achievability argument bounds Willie’s variational distance by comparing distributions induced by transmission and carefully constructed probability mass functions. It also establishes reliability for Bob using status estimation followed by conditional decoding.

  • Deniability: The deniability proof compares p0 and p1 through E(p1), q0, and q1 using the triangle inequality.The first two terms in the resulting bound vanish as n increases, leaving V(q0,q1) as the remaining upper bound.
  • Deniability: The codebook-dependent gap V(E(p1),p1) is shown to be below 2^-Ω(nδ) with probability greater than 1−exp(·).The proof uses high-probability sets for Willie’s received vector and conditional high-probability sets for Alice’s codeword.
  • Deniability: The deniability condition is obtained by choosing the codebook parameter so that ρ < (Uw−Lw)/((1−2Lw)ϵd).Under this condition, the variational distance between p0 and E(p1) is less than ϵd.
  • Deniability: q0 is uniform over received-vector weights in (Lw, Uw), while q1 is supported over the corresponding interval scaled by ρ*.Ignoring floor functions, the respective weight probabilities are 1/[n(Uw−Lw)] and 1/[n(1−2ρ)(Uw−Lw)].
  • Reliability: Bob first estimates Alice’s transmission status, then either decodes the all-zero vector or applies the message decoder according to that estimate.The reliability analysis bounds the sum of the two status-conditioned decoding-error probabilities by ϵr.

APPENDIX

The appendix supplies analytic tools for bounding entropy and divergence expressions and for approximating empirical mutual information near its expected joint type. These tools support the paper’s asymptotic calculations.

  • Auxiliary inequalities: Reverse Pinsker’s inequality bounds binary Kullback-Leibler divergence for sufficiently small perturbations.The claim applies to binary random variables and small x.
  • Auxiliary inequalities: Additive and convolutive divergence bounds scale quadratically with the perturbation x.The additive bound uses 2p(1−p) in the denominator, while the convolutive bound includes (1−2p)^2.
  • Entropy identities: Differences between binary entropy functions are expressed using divergence terms plus a logarithmic correction.Separate additive and convolutive identities are given.
  • Empirical mutual information: For a codeword with fractional Hamming weight ρ=cρ/√n, the appendix analyzes empirical mutual information near its expected joint type.The analysis fixes typical ranges for f∗1, f10, and f11 and expands mutual information around their center point.
  • Empirical mutual information: Within the specified type cube, changes in f∗1, f10, and f11 contribute at most an O(·) term to empirical mutual information.The conclusion follows by bounding first-derivative contributions and higher-order Taylor terms.
  • Asymptotic tools: Laplace’s method and Stirling’s approximation are stated as additional asymptotic tools.Laplace’s method assumes a smooth function with a unique interior global minimum and vanishing first derivative there.
Loading 1304.6693v2…