PaperlayerView exact revision on arXiv

Source-linked AI summary

Perfectly Secure Steganography: Capacity, Error Exponents, and Code Constructions

Ying Wang, Pierre Moulin

arXiv:cs/0702161v3cs.ITcs.CRmath.IT

TL;DR

Perfectly secure steganography requires the stegotext to have the covertext’s distribution, but existing schemes have vanishing rate. This paper constructs codes from watermarking codes and derives their capacity and error exponents; the cost of perfect security matches that of order-1 security, with no loss in a specified symmetric setting.

  • Problem

    The paper studies how to achieve reliable communication while keeping embedded information undetectable, under the requirement that stegotext and covertext distributions match.

    Source: §I · pp. 2, 4

  • Method

    The paper constructs perfectly secure codes from order-1-secure public watermarking codes using randomized permutations and stacked-binning methods.

    Source: §I · p. 4, §X · p. 17

  • Results

    Stacked-binning codes achieve capacity and random-coding exponents; perfect security costs as much as order-1 security, with no performance loss for uniform covers and cyclically symmetric distortion.

    Source: §X · p. 17

  • Takeaways & Limitations

    The framework may provide a basis for computationally secure steganographic codes using a reduced key set computationally indistinguishable from the full key group.

    Source: §X · p. 17

    The analysis assumes i.i.d. covertext samples over a finite alphabet, a simplifying approximation to actual statistics.

    Source: §I · p. 4

Abstract

from arXiv · show

An analysis of steganographic systems subject to the following perfect undetectability condition is presented in this paper. Following embedding of the message into the covertext, the resulting stegotext is required to have exactly the same probability distribution as the covertext. Then no statistical test can reliably detect the presence of the hidden message. We refer to such steganographic schemes as perfectly secure. A few such schemes have been proposed in recent literature, but they have vanishing rate. We prove that communication performance can potentially be vastly improved; specifically, our basic setup assumes independently and identically distributed (i.i.d.) covertext, and we construct perfectly secure steganographic codes from public watermarking codes using binning methods and randomized permutations of the code. The permutation is a secret key shared between encoder and decoder. We derive (positive) capacity and random-coding exponents for perfectly-secure steganographic systems. The error exponents provide estimates of the code length required to achieve a target low error probability. We address the potential loss in communication performance due to the perfect-security requirement. This loss is the same as the loss obtained under a weaker order-1 steganographic requirement that would just require matching of first-order marginals of the covertext and stegotext distributions. Furthermore, no loss occurs if the covertext distribution is uniform and the distortion metric is cyclically symmetric; steganographic capacity is then achieved by randomized linear codes. Our framework may also be useful for developing computationally secure steganographic systems that have near-optimal communication performance.

I. INTRODUCTION

Steganography hides the presence of embedded information, and this paper studies its information-theoretic limits under perfect undetectability. It connects watermarking codes to perfectly secure schemes and derives their capacity and error-exponent results.

I. INTRODUCTION

  • Steganography hides the presence of embedded information, while perfect security requires the covertext and stegotext distributions to match exactly.Perceptual transparency alone is insufficient because statistical analysis can reveal embedded information.Source: §I · pp. 2–3
  • Earlier approaches include a perfectly secure database-search scheme with extremely low communication rate and watermarking frameworks that did not derive steganographic capacity.The database-search method is computationally infeasible for large message sets; Moulin and O’Sullivan did not study perfect security or derive capacity.Source: §I · pp. 3–4
  • The paper assumes i.i.d. covertext and constructs perfectly secure codes from order-1-secure public watermarking codes using randomized permutations.The paper derives capacity and random-coding exponent formulas; stacked-binning codes use an MPMI decoder.Source: §I · p. 4
  • For uniform covertext distributions and cyclically symmetric distortion, perfect undetectability causes no performance loss; in the binary-Hamming case, randomized nested linear codes achieve capacity.In the binary-Hamming case, the perfect-security condition also has no effect on the random-coding error exponent.Source: §I · p. 4

II. NOTATION

  • The notation section defines a sequence’s type as its empirical PMF and uses standard symbols for entropy, mutual information, and Kullback-Leibler divergence.It also defines joint and conditional types and their associated type classes.Source: §II · p. 5

III. PROBLEM STATEMENT

The problem models message embedding in i.i.d. covertext under distortion constraints, with a steganalyzer that may forward or corrupt the stegotext. The code definitions distinguish perfect distribution matching from weaker first-order matching and describe randomized code constructions.

III. PROBLEM STATEMENT

  • The model embeds a uniformly distributed message in an i.i.d. covertext sequence, requiring the stegotext to remain close under a distortion metric.The distortion constraint models physical signals that can be modified to some extent without affecting perceptual quality.Source: §III · pp. 5–6
  • A steganalyzer tests whether the stegotext follows the covertext distribution and may either forward it or apply an attack channel before decoding.The active-warden case also constrains distortion between the corrupted text and the stegotext.Source: §III · p. 6
  • Randomized encoder-decoder codes use a secret key known only to the encoder and decoder, which can make covertext and stegotext PMFs match.The key is unknown to the steganalyzer.Source: §III · p. 6

A. Steganographic Codes

  • The code definitions constrain the encoder’s distortion and perfect undetectability, while CCC codes require only order-1 matching and may not be perfectly undetectable.CCC codes match first-order empirical marginals but need not match higher-order empirical marginals.Source: A. Steganographic Codes · p. 7
  • Randomly modulated codes apply a uniformly drawn permutation, hidden from Willie, to a prototype code’s sequences.The permutation is drawn from all N! permutations.Source: A. Steganographic Codes · p. 7

B. Attack Channels

The paper models active wardens as memoryless channels constrained by expected distortion, then derives steganographic capacity and random-coding error exponents under perfect security. Its constructions convert order-1-secure prototypes into perfectly secure codes, while stacked binning supplies achievable performance and a decoder with a controlled error exponent.

B. Attack Channels

  • Memoryless attack channels form the compound DMC family, constrained by expected distortion; the paper favors this model partly because it yields a smaller random-coding exponent for the warden than arbitrary-memory attacks.The paper also cites simpler presentation and a proof basis for arbitrary-memory channels as reasons for this setting.Source: B. Attack Channels · p. 8

IV. FROM ORDER-1 TO PERFECTLY SECURE STEGANOGRAPHIC CODES

  • Random modulation converts a conditionally constant-composition, order-1-secure prototype into a perfectly secure code with the same maximum distortion and error probability.This construction preserves the prototype’s reliability while achieving perfect security.Source: §IV · p. 9

V. STEGANOGRAPHIC CAPACITY AND RANDOM CODING ERROR EXPONENT

  • The achievable steganographic capacity and random-coding error exponent are characterized by the paper’s optimization formulas, with capacity bounded above by public-watermarking capacity.The optimizations impose the steganographic constraint on the encoder distribution and account for feasible attack channels.Source: §V · pp. 9–10
  • Stacked binning indexes variable-size codeword arrays by covertext type, and the MPMI decoder selects a codeword using penalized empirical mutual information.The random-coding exponent estimates the code length needed to reach a target low error probability.Source: §V · p. 11
  • With depth parameter ρ(ps) = I(u; s) + ϵ, encoding errors vanish double-exponentially while decoding errors vanish at the random-coding exponent.This choice balances encoding and decoding error probabilities.Source: §V · p. 11

VI. SECRET KEY

Randomized codes use a shared secret key to meet the perfect-undetectability condition. For a passive warden, the paper gives a simplified capacity expression related to rate-distortion, alongside a random-coding exponent.

VI. SECRET KEY

  • For randomized codes, the shared secret key supplies common randomness, and in randomly modulated codes it specifies the permutation π.The paper notes that without the secret key, a deterministic code generally could not satisfy perfect undetectability.Source: §VI · pp. 11–12

VII. PASSIVE WARDEN

  • For a passive warden, steganographic capacity is the covertext entropy minus the minimum mutual information I(S; X) over allowed steganographic channels.The capacity-achieving codes are analogous to rate-distortion codes; equality with the rate-distortion expression holds when its optimizing distribution satisfies pX = pS.Source: §VII · p. 12
  • The paper provides a simplified random-coding exponent expression for the passive-warden case.Here the warden causes no degradation, so D2 = 0 and Y = X.Source: §VII · p. 12

VIII. PENALTY FOR PERFECT SECURITY

The paper identifies uniform covertext and cyclic distortion symmetry as sufficient conditions for perfect security to impose no capacity loss. In the binary Hamming example, the public-watermarking optimum also satisfies the security constraint, so capacity is unchanged.

VIII. PENALTY FOR PERFECT SECURITY

  • A covert channel can be symmetrized by including its q cyclic shifts with equal likelihood, preserving cyclic distortion and inducing a uniform output marginal.This supplies the construction used to establish the no-loss result.Source: §VIII · p. 13
  • For the stated q-ary setting, perfect security causes no capacity loss relative to public watermarking when the covertext is uniform and the distortion is cyclically symmetric.The proposition also permits restricting the maximization and minimization to specified cyclically structured channel classes.Source: §VIII · pp. 13–14

IX. EXAMPLE: BINARY-HAMMING CASE

  • In the binary Hamming example, the optimal public-watermarking covert channel has pX = pS, so perfect security causes no capacity loss.The example uses Bernoulli covertext and Hamming distortion.Source: §IX · p. 14, A. Capacity · p. 15

B. Random-Coding Exponent

The section reports exponent behavior for a Bernoulli-covertext example, then gives a randomized nested-linear construction and summarizes the paper’s broader security-performance results. Its conclusions include positive capacity and random-coding exponents, with no security cost in a specified uniform, cyclically symmetric setting.

B. Random-Coding Exponent

  • For |U|=2, the optimal covert channel remains BSC(D1) with time sharing, and the perfect-security constraint causes no random-coding exponent loss.The reported condition also has pX = pS.Source: B. Random-Coding Exponent · p. 15

C. Randomized Nested Linear Codes—A Capacity-Achieving Code Construction

  • In the Hamming case, randomized nested linear codes achieve steganographic capacity, with no effect from perfect security on capacity or random-coding error exponent.For D1 < dD2, the construction applies time sharing; the nested codes apply to public watermarking and steganography because BSC(D2) is the optimal discrete memoryless attack channel.Source: C. Randomized Nested Linear Codes—A… · p. 16
  • Uniformly selecting a coset key makes the randomized encoder output uniform over the whole space, thereby achieving perfect security.The resulting key entropy is h(D2), rather than the log2 N growth required for general RM codes.Source: C. Randomized Nested Linear Codes—A… · p. 17

X. CONCLUSION

  • Stacked-binning codes with an MPMI decoder achieve positive capacity and random-coding exponents.The random-coding exponent estimates the code length needed to reach a target low error probability.Source: §X · p. 17
  • For i.i.d. covertexts, randomized permutations of a conditionally constant-composition watermarking code with order-1 security yield perfectly secure codes.A shared secret key supplies the common randomness; order-1 security matches first-order marginals, not the full N-dimensional statistics.Source: §X · p. 17
  • The communication-performance cost of perfect security matches the cost of the weaker order-1 security requirement.If the covertext distribution is uniform and distortion is cyclically symmetric, perfect security causes no performance loss.Source: §X · p. 17
  • The framework can support computationally secure codes with near-optimal communication performance when reduced key representatives are computationally indistinguishable from uniform sampling over the subgroup.The resulting code is not perfectly secure, but inherits the computational security of the key-generation mechanism.Source: §X · p. 17
  • Markov-dependent covertexts and continuous alphabets are technically challenging extensions of the basic framework.The basic framework uses i.i.d. covertexts over a finite alphabet.Source: §X · p. 17

APPENDIX I

The appendices verify that randomized modulation preserves the prototype code’s security and distortion properties, and develop a converse bound by relaxing constraints. The converse establishes an upper bound on achievable rates under those relaxed assumptions.

APPENDIX I

  • The randomized-modulation proof verifies that the RM code satisfies perfect security and the maximum-distortion constraint.The proof checks the security condition and then uses the additive distortion measure and the prototype’s assumed constraint.Source: Appendix I · p. 18

APPENDIX II

  • The converse relaxes perfect security to order-1 security, almost-sure distortion to expected distortion, and gives the decoder the attack channel.Any upper bound under these assumptions is also an upper bound on capacity.Source: APPENDIX II · p. 19
  • Under the converse’s order-1 constraint, the time-shared input marginal satisfies pX = pS, and Fano-based bounds constrain achievable rate.The derivation bounds rate using a finite-alphabet auxiliary variable and the attack channel.Source: APPENDIX II · pp. 19–20
  • The converse establishes its rate bound by taking the limit of the auxiliary-alphabet optimization and concludes the converse part of Theorem 1.The sequence of bounds is nondecreasing and converges to a finite limit.Source: APPENDIX II · pp. 20–21

APPENDIX III

The appendix proves existence of order-1-secure codes through a random binning ensemble and characterizes convergence of the associated random-coding exponent. The codebook arrays are indexed by covertext type and sampled from corresponding type classes.

APPENDIX III

  • The order-1-secure random-coding exponent sequence is nondecreasing and converges to a finite limit.For any positive epsilon, the sequence eventually lies within epsilon of that limit.Source: APPENDIX III · p. 21
  • For any auxiliary-alphabet size L, deterministic order-1-secure codes exist whose error probability vanishes at the stated exponent rate.Existence is shown by averaging error probability over a random ensemble of binning codes.Source: APPENDIX III · p. 21
  • The feasible conditional types enforce matching covertext and stegotext types and a maximum distortion no greater than D1.The identity mapping is included, so the feasible set is nonempty.Source: APPENDIX III · pp. 21–22
  • The random codebook is a union of arrays indexed by covertext type, with vectors sampled from the corresponding type classes.The arrays have columns indexed by messages.Source: APPENDIX III · p. 22

A. Encoder fN

The encoder selects a codeword compatible with the covertext and message, while the decoder uses a penalized mutual-information criterion. The analysis shows vanishing error below capacity and that random modulation gives perfect security without changing the prototype’s error probability or distortion.

A. Encoder fN

  • The encoder searches the type-indexed code array for a compatible auxiliary sequence, then draws the stegotext from its conditional type class.If multiple sequences match, it chooses uniformly; if none is available, it declares an error and draws uniformly over the auxiliary alphabet.Source: A. Encoder fN · p. 22

B. Decoder φN

  • The decoder selects the covertext type and codeword maximizing penalized mutual information, then outputs that codeword’s message index.If maximizers correspond to more than one message index, it declares an error.Source: B. Decoder φN · p. 22

C. Error Probability Analysis

  • Encoding errors vanish double-exponentially, while decoding errors determine the random-coding exponent’s reliability scale.The MPMI decoder can be viewed as an empirical generalized MAP decoder.Source: C. Error Probability Analysis · p. 22
  • For rates below capacity, the error probability vanishes; random modulation preserves the prototype’s error exponent and distortion while providing perfect security.Encoding error vanishes double-exponentially, leaving decoding error as the contributor to the error probability on the exponential scale.Source: C. Error Probability Analysis · pp. 22–23, D. Perfect Security · p. 23

APPENDIX IV

  • For D2 = 0, CSteg(D1, 0) is the limit as L→∞ of the maximum objective JL(pS, pXU|S, pY|X) over pXU|S in QSteg(L,pS,D1).Source: APPENDIX IV · p. 24

APPENDIX V

The proof establishes an upper bound for public watermarking capacity and develops the corresponding argument for perfectly secure steganographic capacity. In the upper-bound step, restricting the minimization to cyclic channels gives an upper bound on the broader minimization.

APPENDIX V

  • The minimizing conditional distribution must equal pY|X, because any different choice makes the divergence term infinite.Source: Appendix V · p. 24

APPENDIX VI

  • Proposition 5 is proved by showing that its right-hand side upper-bounds public watermarking capacity and lower-bounds perfectly secure steganographic capacity.Source: APPENDIX VI · p. 24

A. Upper Bound

  • The public watermarking capacity expression minimizes over A(pX,D2), while restricting that minimization to Acyc(D2) yields an upper bound.Source: A. Upper Bound · p. 25

B. Lower Bound

The lower-bound argument combines upper- and lower-bound inequalities to establish that perfect security causes no capacity loss. Its proof uses convexity of JL in the channel distribution and capacity expressions defined through limiting optimizations.

B. Lower Bound

  • The public watermarking capacity sequence is nondecreasing and bounded by log |S|, so its subsequences converge to the same limit.Source: B. Lower Bound · p. 26
  • The steganographic capacity is expressed as a blocklength limit of optimizations over steganographically feasible distributions and allowed channels.Source: B. Lower Bound · p. 26
  • Convexity of JL in pY|X supplies the inequality used to derive the lower-bound claim.Source: B. Lower Bound · p. 27
  • The perfectly secure steganographic constraint does not cause any capacity loss.Source: B. Lower Bound · p. 28

APPENDIX VII

Appendix VII derives conditional distributions and entropy expressions for Y given V and U, then concludes the proof of Lemma 2.

APPENDIX VII

  • The derivation considers the conditional distribution and conditional entropy of Y given V.Source: APPENDIX VII · p. 28
  • It also derives the conditional distribution of Y given U, along with Y's marginal distribution and conditional entropy given U.Source: APPENDIX VII · pp. 28–29
  • The appendix concludes that Lemma 2 is proved.Source: APPENDIX VII · p. 29
Loading cs/0702161v3…