In this chapter, we discuss the construction of practical codes for secrecy. The design of codes for the wiretap channel turns out to be surprisingly difficult, and this area of information-theoretic security is still largely in its infancy. To some extent, the major obstacles in the road to secrecy capacity are similar to those that lay in the path to channel capacity: the random-coding arguments used to establish the secrecy capacity do not provide explicit code constructions. However, the design of wiretap codes is further impaired by the absence of a simple metric, such as a bit error rate, which could be evaluated numerically. Unlike codes designed for reliable communication, whose performance is eventually assessed by plotting a bit-error-rate curve, we cannot simulate an eavesdropper with unlimited computational power; hence, wiretap codes must possess enough structure to be provably secure. For certain channels, such as binary erasure wiretap channels, the information-theoretic secrecy constraint can be recast in terms of an algebraic property for a code-generator matrix. Most of the chapter focuses on such cases since this algebraic view of secrecy simplifies the analysis considerably. As seen in Chapter 4, the design of secret-key distillation strategies is a somewhat easier problem insofar as reliability and security can be handled separately by means of information reconciliation and privacy amplification. Essentially, the construction of coding schemes for key agreement reduces to the design of Slepian–Wolf-like codes for information reconciliation, which can be done efficiently with low-density parity-check (LDPC) codes or turbo-codes.
In this chapter, we discuss the construction of practical codes for secrecy. The design of codes for the wiretap channel turns out to be surprisingly difficult, and this area of information-theoretic security is still largely in its infancy. To some extent, the major obstacles in the road to secrecy capacity are similar to those that lay in the path to channel capacity: the random-coding arguments used to establish the secrecy capacity do not provide explicit code constructions. However, the design of wiretap codes is further impaired by the absence of a simple metric, such as a bit error rate, which could be evaluated numerically. Unlike codes designed for reliable communication, whose performance is eventually assessed by plotting a bit-error-rate curve, we cannot simulate an eavesdropper with unlimited computational power; hence, wiretap codes must possess enough structure to be provably secure. For certain channels, such as binary erasure wiretap channels, the information-theoretic secrecy constraint can be recast in terms of an algebraic property for a code-generator matrix. Most of the chapter focuses on such cases since this algebraic view of secrecy simplifies the analysis considerably. As seen in Chapter 4, the design of secret-key distillation strategies is a somewhat easier problem insofar as reliability and security can be handled separately by means of information reconciliation and privacy amplification. Essentially, the construction of coding schemes for key agreement reduces to the design of Slepian–Wolf-like codes for information reconciliation, which can be done efficiently with low-density parity-check (LDPC) codes or turbo-codes.
Confidentiality of information is a key consideration in many networking applications, including e-commerce, online banking, and intelligence operations. How can information be communicated reliably to the legitimate users, while keeping it secret from eavesdroppers? How does such a secrecy constraint on communication affect the limits on information flow in the network? In this chapter, we study these questions under the information theoretic notion of secrecy, which requires each eavesdropper to obtain essentially no information about the messages sent from knowledge of its received sequence, the channel statistics, and the codebooks used. We investigate two approaches to achieve secure communication. The first is to exploit the statistics of the channel from the sender to the legitimate receivers and the eavesdroppers. We introduce the wiretap channel as a 2-receiver broadcast channel with a legitimate receiver and an eavesdropper, and establish its secrecy capacity, which is the highest achievable secret communication rate. The idea is to design the encoder so that the channel from the sender to the receiver becomes effectively stronger than the channel to the eavesdropper; hence the receiver can recover the message but the eavesdropper cannot. This wiretap coding scheme involves multicoding and randomized encoding. If the channel from the sender to the receiver is weaker than that to the eavesdropper, however, secret communication at a positive rate is not possible. This brings us to the second approach to achieve secret communication, which is to use a secret key shared between the sender and the receiver but unknown to the eavesdropper. We show that the rate of such secret key must be at least as high as the rate of the confidential message. This raises the question of how the sender and the receiver can agree on such a long secret key in the first place. After all, if they had a confidential channel with sufficiently high capacity to communicate the key, then why not use it to communicate the message itself! We show that if the sender and the receiver have access to correlated sources (e.g., through a satellite beaming common randomness to them), then they can still agree on a secret key even when the channel has zero secrecy capacity. We first consider the source model for key agreement, where the sender communicates with the receiver over a noiseless public broadcast channel to generate a secret key from their correlated sources.
We investigate an approach to physical-layer security based on the premise that the coding mechanism for secrecy over noisy channels is fundamentally tied to the notion of resolvability. Instead of considering capacity-based constructions, which associate to each message a sub-code whose rate approaches the capacity of the eavesdropper’s channel, we consider resolvability-based constructions, which associate to each message a sub-code whose rate is beyond the resolvability of the eavesdropper’s channel. We provide evidence that resolvability is a more powerful and perhaps more fundamental coding mechanism for secrecy by developing results that hold for strong secrecy metrics and arbitrary channels. Specifically, we show that, at least for binary symmetric wiretap channels, random capacity-based constructions fail to approach the strong secrecy capacity while resolvability-based constructions achieve it. We then obtain the secrecy-capacity region of arbitrary broadcast channels with confidential messages and a cost constraint for strong secrecy metrics, which generalizes existing results. Finally, we specialize our results to study the secrecy capacity of wireless channels with perfect channel state information, compound and mixed channels, as well as the secret-key capacity of source models for secret-key agreement. By tying secrecy to resolvability, we obtain achievable rates for stronger secrecy metrics and with simpler proofs than previously derived. Index Terms information-theoretic security, wiretap channel, secret-key agreement, information-spectrum, resolv-ability, wireless channels.
In Part I of this two-part paper on confidential communication over wireless channels, we studied the fundamental security limits of quasi-static fading channels from the point of view of outage secrecy capacity with perfect and imperfect channel state information. In Part II, we develop a practical secret key agreement protocol for Gaussian and quasi-static fading wiretap channels. The protocol uses a four-step procedure to secure communications: establish common randomness via an opportunistic transmission, perform message reconciliation, establish a common key via privacy amplification, and use of the key. We introduce a new reconciliation procedure that uses multilevel coding and optimized low density parity check codes which in some cases comes close to achieving the secrecy capacity limits established in Part I. Finally, we develop new metrics for assessing average secure key generation rates and show that our protocol is effective in secure key renewal.
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≥Cs−ε 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.
With the advent of quantum key distribution (QKD) systems, perfect (i.e. information-theoretic) security can now be achieved for distribution of a cryptographic key. QKD systems and similar protocols use classical errorcorrecting codes for both error correction (for the honest p arties to correct errors) and privacy amplification (to make an eavesdropper fully ignorant). From a coding perspective, a good model for such a setting is the wire tap channel introduced by Wyner in 1975. In this paper, we study fundamental limits and coding methods for wire tap channels. We provide a novel proof for the secrecy capacity theorem for wire tap channels and show how capacity achieving codes can be used to achieve the secrecy capacity for any wiretap channel. We also consider binary erasure channel and binary symmetric channel special cases for the wiretap channel and propose specific practical codes. In some cases our designs achieve the secrecy capacity and in others the codes provide complete security at rates below secrecy capacity in some specific cases.
In this chapter, we develop the notion of secrecy capacity , which plays a central role in physical-layer security. The secrecy capacity characterizes the fundamental limit of secure communications over noisy channels, and it is essentially the counterpart to the usual point-to-point channel capacity when communications are subject not only to reliability constraints but also to an information-theoretic secrecy requirement. It is inherently associated with a channel model called the wiretap channel , which is a broadcast channel in which one of the receivers is treated as an adversary. This adversarial receiver, which we call the eavesdropper to emphasize its passiveness, should remain ignorant of the messages transmitted over the channel. The mathematical tools, and especially the random-coding argument, presented in this chapter are the basis for most of the theoretical research in physical-layer security, and we use them extensively in subsequent chapters. We start with a review of Shannon's model of secure communications (Section 3.1), and then we informally discuss the problem of secure communications over noisy channels (Section 3.2). The intuition we develop from loose arguments is useful to grasp the concepts underlying the proofs of the secrecy capacity and motivates a discussion of the choice of an information-theoretic secrecy metric (Section 3.3). We then study in detail the fundamental limits of secure communication over degraded wiretap channels (Section 3.4) and broadcast channels with confidential messages (Section 3.5).