Achieving the Secrecy Capacity of Wiretap Channels Using Polar Codes

Suppose that Alice wishes to send messages to Bob through a communication channel C₁, but her transmissions also reach an eavesdropper Eve through another channel C₂. This is the wiretap channel model introduced by Wyner in 1975. 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 the mutual information between the message and Eve´s observations. 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 ≥ C_s-ε that asymptotically achieve the reliability and security objectives. However, his proof of this result is based upon a random-coding argument. To date, despite consider able research effort, the only case where we know how to construct coding schemes that achieve secrecy capacity is when Eve´s channel C₂ 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. In this paper, 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₁ and C₂ are symmetric and binary-input, and C₂ is degraded with respect to C₁. 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 also be satisfied unless the m- - ain channel C₁ is noiseless, although we believe it can be always satisfied in practice.