PaperlayerView exact revision on arXiv

Source-linked AI summary

Achieving the Secrecy Capacity of Wiretap Channels Using Polar Codes

Hessam Mahdavifar, Alexander Vardy

arXiv:1001.0210v2cs.ITcs.CR

TL;DR

The paper addresses constructive coding for wiretap channels, where random-coding proofs establish secrecy capacity but often do not yield specific polynomial-time algorithms. It develops a coding scheme with strong-security modifications, proving strong security and secrecy-capacity-achieving rates under stated conditions while leaving reliability constrained for some decoders.

  • Problem

    Constructive wiretap-channel codes remain limited despite nonconstructive random-coding results, while evaluating secrecy capacity can also be difficult.

  • Method

    The coding scheme redefines poor bit-channels from Eve’s perspective and sends random bits over channels failing the strong-badness criterion.

  • Results

    The scheme guarantees strong security for δ_n = o(1/n), and its rate approaches the secrecy capacity for security functions satisfying the stated condition.

  • Takeaways & Limitations

    The results extend to non-symmetric binary-input channels in the average sense and to discrete memoryless channels with prime or non-prime input alphabets.

  • Takeaways & Limitations

    Reliability is not guaranteed for the strong-security scheme under the considered successive-cancellation decoders unless the main channel is noiseless.

Abstract

from arXiv · show

Suppose Alice wishes to send messages to Bob through a communication channel C_1, but her transmissions also reach an eavesdropper Eve through another channel C_2. The goal is to design a coding scheme that makes it possible for Alice to communicate both reliably and securely. Reliability is measured in terms of Bob's probability of error in recovering the message, while security is measured in terms of Eve's equivocation ratio. Wyner showed that the situation is characterized by a single constant C_s, called the secrecy capacity, which has the following meaning: for all $ε> 0$, there exist coding schemes of rate $R \ge C_s - ε$ that asymptotically achieve both the reliability and the security objectives. However, his proof of this result is based upon a nonconstructive random-coding argument. To date, despite a considerable research effort, the only case where we know how to construct coding schemes that achieve secrecy capacity is when Eve's channel C_2 is an erasure channel, or a combinatorial variation thereof. Polar codes were recently invented by Arikan; they approach the capacity of symmetric binary-input discrete memoryless channels with low encoding and decoding complexity. Herein, we use polar codes to construct a coding scheme that achieves the secrecy capacity for a wide range of wiretap channels. Our construction works for any instantiation of the wiretap channel model, as long as both C_1 and C_2 are symmetric and binary-input, and C_2 is degraded with respect to C_1. Moreover, we show how to modify our construction in order to provide strong security, in the sense defined by Maurer, while still operating at a rate that approaches the secrecy capacity. In this case, we cannot guarantee that the reliability condition will be satisfied unless the main channel C_1 is noiseless, although we believe it can be always satisfied in practice.

I. INTRODUCTION

Wiretap-channel coding must let Bob recover messages reliably while limiting Eve’s information, but prior secrecy-capacity results largely lacked explicit efficient constructions. This paper uses polar codes to achieve secrecy capacity for symmetric binary-input degraded channels and develops a direct strong-security variant.

  • Research problem: Wiretap coding must simultaneously control Bob’s decoding error and Eve’s information about the message.The paper treats reliability through Bob’s probability of error and security through normalized mutual information or stronger security criteria.
  • Prior work: Most prior wiretap-channel results used nonconstructive random coding, leaving explicit polynomial-time constructions available mainly for erasure-based cases.Known constructive cases included binary erasure channels and combinatorial observation models, while coset-coding strong-security constructions relied on random inner codes.
  • Contributions: The paper constructs polar-code schemes achieving secrecy capacity when both channels are symmetric binary-input DMCs and C2 is degraded with respect to C1.The construction includes arbitrary binary symmetric channels as an important special case.
  • Contributions: Encoding and decoding require O(n log n) operations while satisfying the paper’s reliability and conventional security conditions.The construction is explicit and uses the channel-polarization framework of polar codes.
  • Strong security: A modified polar construction provides strong security directly and has a rate approaching secrecy capacity, but reliability is not guaranteed unless C1 is noiseless.The modification changes which bit-channels receive random bits according to Eve-focused badness criteria.
  • Extensions: The construction extends to nonsymmetric and nonbinary channels, although nonsymmetric channels yield only symmetric secrecy capacity and nonbinary polarization may require additional techniques.For non-prime input alphabets, the paper cites randomized permutations or multilevel coding as alternatives.

II. SECRECY CAPACITY

The section reviews general and specialized expressions for wiretap secrecy capacity. For symmetric degraded channels, the capacity simplifies, including to a binary-entropy difference for ordered binary symmetric channels.

  • Channel assumptions: A channel C2 is degraded with respect to C1 when it can be obtained by cascading C1 with a third channel.For binary symmetric channels, p2 ≥ p1 ensures this degradedness relation.
  • General secrecy capacity: For arbitrary DMC wiretap channels, secrecy capacity is characterized by a maximization over U satisfying U → X → (Y, Z).The paper notes that this optimization is often difficult to evaluate.
  • Symmetric degraded channels: When C1 and C2 are symmetric and C2 is degraded with respect to C1, Leung-Yan-Cheong gives a simpler expression for Cs.The input X is uniform in this specialized characterization.
  • Binary symmetric channels: For C1 = BSC(p1) and C2 = BSC(p2) with p2 ≥ p1, secrecy capacity equals h2(p2) − h2(p1).Here h2 denotes the binary entropy function.

III. POLAR CODES

Polar codes transform a binary-input symmetric channel into bit-channels that polarize toward nearly noiseless or nearly pure-noise behavior. Selecting good bit-channels for information and fixing the rest enables capacity-achieving codes with successive cancellation decoding.

  • Channel polarization: Polar coding applies Arıkan’s transform to n independent channel uses, producing n effective bit-channels for successive decoding.Each bit-channel represents the channel seen when estimating one input bit given the channel output and previous decisions.
  • Decoding: Successive cancellation decoding estimates bits iteratively, substituting earlier decisions for the previously known bit values.For frozen coordinates, the decoder directly outputs the predetermined value.
  • Channel polarization: Good bit-channels have Bhattacharyya parameter below the threshold, while bad bit-channels meet or exceed it.The good and bad sets are defined using a fixed β < 1/2 and thresholds that shrink rapidly with n.
  • Capacity achievement: The fraction of good bit-channels approaches the capacity C(W) for every binary-input symmetric channel.This polarization result underlies capacity-achieving polar-code constructions.
  • Code construction: Capacity-achieving polar codes place information bits on good channels and freeze bad-channel inputs to known values.For symmetric channels, zero is a valid convenient choice for all frozen values.
  • Reliability: The block-error guarantee extends from uniformly random messages to arbitrary message distributions on binary-input symmetric channels.Symmetry makes the error probability independent of the transmitted codeword.

IV. THE CODING SCHEME

The proposed wiretap construction assigns message, random, and frozen bits according to their quality for Bob’s and Eve’s polarized channels. Random bits are essential: fixing them can expose a significant fraction of the message to Eve.

  • Setup: The construction assumes symmetric binary-input main and wiretap channels, with Eve’s channel degraded relative to Bob’s.Under degradation, every bit-channel good for Eve is also good for Bob, enabling a three-way partition.
  • Bit assignment: Message bits occupy channels good for Bob but bad for Eve, random bits occupy channels good for Eve, and remaining bits are frozen.The sets R, A, and B are disjoint and partition all n coordinates.
  • Algorithms: The encoder maps a message u and uniformly random vector e to v with v_R=e, v_A=u, v_B=0, then outputs vG_n.The decoder uses the corresponding polar code and successive cancellation decoding.
  • Relation to coset coding: The scheme is a coset-coding construction whose outer code is C_n(A ∪ R) and inner code is C_n(R).The outer code supports main-channel error correction, while the inner code supplies the security structure.
  • Necessity of randomness: Fixing the random vector instead of sampling it uniformly can make weak security impossible, because Eve may receive at least C(W) message bits’ worth of mutual information.For a uniform message with e=0, I(U;Z) ≥ kC(W).

V. WEAK SECURITY

The polar wiretap construction satisfies weak security and reliability while its rate approaches the secrecy capacity for the stated symmetric degraded-channel setting. The security proof uses random bits to make Eve’s corresponding coordinates decodable and then bounds the message leakage.

  • Main result: The coding scheme is designed to satisfy reliability and weak security while its rate k/n approaches the secrecy capacity.For these channels, the secrecy capacity is C_s = C(W*) − C(W).
  • Reliability: Bob’s block-error probability is bounded using the polar-code reliability guarantee for the coordinates A ∪ R.Because A ∪ R is the set of good bit-channels for the main channel, the error probability tends to zero.
  • Weak security proof: Eve’s leakage is bounded by decomposing I(U;Z) and subtracting the random-bit contribution from the total channel mutual information.The proof uses uniform independent random bits in R and bounds the remaining conditional entropy with a decoding argument and Fano’s inequality.
  • Weak security: The scheme satisfies the weak security condition as n tends to infinity.The normalized leakage terms vanish because the polarization error term and the residual entropy bound tend to zero.
  • Rate: The code rate converges to C(W*) − C(W), using polarization and the inclusion of Eve-good bit-channels within Bob-good bit-channels.This equals the secrecy capacity for the considered wiretap channels.
  • Scope condition: For arbitrary message distributions, achieving secrecy capacity requires the message entropy to equal its input length, H(U)=k.Otherwise the information rate can be below k/n even when the encoder uses k input bits.

VI. STRONG SECURITY

The paper modifies the polar construction to obtain strong security for symmetric binary-input degraded wiretap channels. The proof requires a more intricate argument based on symmetry of a composite channel.

  • Strong-security construction: A modified polar coding scheme provides strong security while operating at a rate k/n approaching the secrecy capacity.The result applies when both channels are symmetric binary-input DMCs and Eve’s channel is degraded relative to the main channel.
  • Proof strategy: The strong-security proof changes the earlier coding scheme and relies crucially on symmetry of a composite channel induced by the construction.The argument also uses a result of Hassani and Urbanke.

A. Analysis of the Weak-Security Coding Scheme

The weak-security scheme is examined for strong security. For binary-input symmetric wiretap channels with a noiseless main channel, strong security is characterized by a necessary and sufficient condition, but that condition need not hold generally.

  • For a binary-input symmetric DMC with a noiseless main channel, the weak-security scheme achieves strong security if and only if condition (47) holds.The proof establishes sufficiency generally and necessity when the main channel is noiseless.
  • When the main channel is noiseless, strong security requires lim_n→∞ nε_n = 0 for the message–eavesdropper mutual information to vanish asymptotically.This necessity follows because the relevant bound becomes an equality in the noiseless-main-channel case.
  • For a general BSM channel, the condition lim_n→∞ nε_n = 0 need not hold for codes achieving a specified error probability.Known bounds imply that nε_n grows at least on the order of a square-root term in such settings.
  • The weak-security coding scheme is conjectured not to provide strong security and therefore requires modification.The paper states that this conclusion motivates a modified polar coding scheme.

B. Strong-Security Coding Scheme

The strong-security construction changes the classification of Eve’s bit-channels by using a stronger poor-channel criterion. Random bits are assigned to channels that fail this criterion while the encoding and decoding procedures otherwise remain essentially unchanged.

  • The weak scheme can label Eve’s bit-channels bad even when Eve can recover their inputs with high probability.For the example n = 2^10 and β = 0.499, a channel may have capacity greater than 1 − 10^-9 while Eve’s error probability is below 2·10^-10.
  • The modified scheme defines poor bit-channels from Eve’s perspective using a strong badness criterion and sends random bits over every channel that fails it.The good-bit-channel definition remains unchanged, while the sets R, A, and B are redefined.
  • The sets R, A, and B remain disjoint and partition [n] under the new definitions.The security function δ_n is initially left arbitrary in (0, 1) and specified later.
  • The strong-security scheme uses the weak scheme’s encoding and decoding algorithms, apart from a later decoding modification.The construction is analyzed through an induced channel Q_n(W, R).

C. The Induced Channel Is Symmetric

The paper proves that the induced channel Q_n(W, R) is symmetric. The proof constructs a group action on its output alphabet using the symmetry of the underlying BSM channel and the linear polar transform.

  • The induced channel Q_n(W, R) models the polar transformation when selected input bits are random and the remaining bits serve as the channel input.Its output is the vector Z = (Z_1, Z_2, ..., Z_n).
  • A group-action criterion reduces symmetry to showing that the transition matrix decomposes into strongly symmetric blocks.The criterion uses identity and composition properties for an abelian group action.
  • The induced channel’s input alphabet {0, 1}^{n−r} forms an abelian group under componentwise modulo-2 addition.The proof constructs a compatible action on Z^n from the symmetry action of W.
  • The polar transform preserves the relevant group-action relation because matrix multiplication over binary vectors is linear.Lemma 12 establishes the needed relation for the Arıkan transform matrix G_n.
  • Proposition 13 concludes that the induced channel Q_n(W, R) is symmetric.The conclusion follows by applying the group-action construction to its transition-probability matrix.

D. Proof of Strong Security

The strong-security proof bounds Eve’s information through the capacities of poor bit-channels. Choosing a sufficiently small security function makes the leakage vanish while preserving an asymptotically secrecy-capacity-achieving rate.

  • The capacity of each polar bit-channel equals the corresponding conditional mutual information under a uniform input vector.This relation connects bit-channel capacities to the polar transformation’s output vector.
  • The induced channel Q_n(W, R) is symmetric, enabling an upper bound on its capacity in terms of the capacities of the constituent bit-channels.Lemma 15 supplies this bound for every subset R.
  • Proposition 16 bounds the message–Eve mutual information using the capacities of the δ_n-poor bit-channels.The encoder places the message in A, fixes B to zero, and chooses R uniformly at random.
  • Any security function satisfying δ_n = o(1/n) guarantees strong security.The result follows from the mutual-information bound and the fact that the number of poor bit-channels is at most n.
  • The scheme can achieve secrecy capacity while using δ_n = 2^-nβ for any positive constant β < 1/2.In this setting, the paper states that the mutual information between the message and Eve’s observations scales roughly as a vanishing quantity, regardless of the message distribution.

E. Rate of the Strong-Security Coding Scheme

The strong-security coding scheme operates at a rate approaching secrecy capacity for security functions satisfying the stated condition. The proof combines asymptotic bounds on poor bit-channels with polar-channel polarization results.

  • The proof partitions the usable index set into subsets and shows that the subset X has vanishing normalized size.This removes the remaining gap between the lower bound on R_n and secrecy capacity.
  • Theorem 18 characterizes the asymptotic fraction of γ_n-poor bit-channels for an arbitrary BSM channel W.Its result is specialized through Corollary 19 to obtain the behavior needed for the strong-security construction.
  • The proof uses the disjointness of poor and good bit-channel sets together with polarization limits for their asymptotic fractions.These relations establish the required equality in the rate limit.
  • For β < 1/2, the fraction of δ_n-poor bit-channels has the asymptotic behavior specified in Proposition 20 under its stated bounds on δ_n.The proof relates these channels to polar bit-channel parameters and applies Corollary 19 and Theorem 1.
  • The rate R_n of the strong-security coding scheme approaches secrecy capacity for any security function δ_n satisfying the stated condition.The result is established by combining Proposition 20 with Theorem 1 and the vanishing fraction of the set X.

F. Reliability of the Strong-Security Coding Scheme

Reliability is immediate when the main channel is noiseless, but for noisy main channels the strong-security construction lacks a general proof of the required error bound. Practical decoding approaches are proposed when problematic bit-channels are few.

  • If the main channel is noiseless, Bob recovers the message with probability 1 using the inverse Arıkan transform.The decoder computes V from Y and obtains the message directly.
  • For a noisy main channel, successive-cancellation error is bounded by the sum of Bhattacharyya parameters over unfixed bit-channels.The unfixed index set includes the problematic set X.
  • No useful bound is known for the contribution from X, so reliability is not proved for the strong-security scheme in general.This is the principal reliability limitation for noisy main channels.
  • When X is empty, successive-cancellation decoding can be used unchanged, with Bob’s error probability at most 2^-nβ.The paper notes that X is often empty when the main channel is much better than Eve’s channel.
  • In the binary-symmetric example, the construction guarantees reliability 10^-9 and security 10^-30 at rates close to secrecy capacity.The example uses p1 = 10^-3 and blocklength n = 2^20; X remains empty across the reported cases.
  • When X contains only a few channels, branching over both decisions increases decoding complexity by a factor of 2^|X|.The paper suggests bounded-list and path-pruning strategies for larger X.
  • The analysis is limited to successive-cancellation decoding and its variants, leaving robustness of other polar decoders as an open research problem.Belief propagation and recursive-list decoding are identified as possible alternatives.

VII. DISCUSSION AND OPEN PROBLEMS

The construction extends beyond symmetric binary-input channels in several respects, but strong-security extensions and non-degraded wiretap channels remain unresolved. Efficient construction also depends on algorithms for identifying polar bit-channel sets.

  • For non-symmetric binary-input channels, the scheme can achieve the symmetric capacity difference I(W*) − I(W) in the average sense.The encoder is modified by fixing the vector s, with a suitable choice preserving the relevant theorems.
  • The results extend to non-binary-input discrete memoryless channels, with prime-size alphabets using the same polarization transformation.For non-prime alphabet sizes, randomized permutations or multilevel coding are required.
  • It is unclear whether the strong-security results extend to non-symmetric or non-binary-input wiretap channels.The paper presents proving such an extension as an open problem.
  • Without channel degradation, the number of bit-channels good for Eve but bad for Bob may be large, complicating the coding scheme.The paper identifies this non-degraded setting as another major open problem.
  • Exact computation of the polar good and poor channel sets originally required time and memory exponential in code length n.A later algorithm resolves this construction issue with linear running time, although the passage ends before stating its memory complexity.
Loading 1001.0210v2…