Cambridge University Press eBooks

Information Theoretic Secrecy

Abbas El Gamal, Young-Han Kim

Published Dec 8, 2011• 1 citation

Abstract

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.

DOI: 10.1017/cbo9781139030687.024

Related papers

Secret-key capacity

Matthieu R. Bloch, João Barros

In Chapter 3, we considered the transmission of information over a noisy broadcast channel subject to reliability and security constraints; we showed that appropriate coding schemes can exploit the presence of noise to confuse the eavesdropper and guarantee some amount of information-theoretic security. It is important to note that the wiretap channel model assumes that all communications occur over the channel, hence communications are inherently rate-limited and one-way. Consequently, the results obtained do not fully capture the role of noise for secrecy; in particular, for situations in which the secrecy capacity is zero, it is not entirely clear whether this stems from the lack of any “physical advantage” over the eavesdropper or the restrictions imposed on the communication schemes. The objective of this chapter is to study more precisely the fundamental role of noise in information-theoretic security. Instead of studying how we can communicate messages securely over a noisy channel, we now analyze how much secrecy we can extract from the noise itself in the form of a secret key. Specifically, we assume that the legitimate parties and the eavesdropper observe the realizations of correlated random variables and that the legitimate parties attempt to agree on a secret key unknown to the eavesdropper. To isolate the role played by noise, we remove restrictions on communication schemes and we assume that the legitimate parties can distill their key by communicating over a two-way, public, noiseless , and authenticated channel at no cost.

Cambridge University Press eBooksSep 22, 20110 citations

Information-theoretic Secrecy in Multi-user Channels

Ersen Ekrem

Inherent openness of the wireless medium imposes stronger challenges on the security of wireless communications. Information-theoretic security addresses these challenges at the physical layer by using tools from wireless communication theory, signal processing and information theory. In information-theoretic security, physical layer communication is intelligently designed to exploit the characteristics of the wireless medium, such as fading, interference, cooperation, and multi-dimensional signaling, in order to provide or improve security. In this dissertation, we study the security of several fundamental wireless network configurations from an information-theoretic perspective. First, we study the Gaussian multiple-input multiple-output (MIMO) wiretap channel. In this channel, the transmitter sends a common message to both the legitimate user and the eavesdropper. In addition to the common message, a private message is sent only to the legitimate user, which needs to be kept hidden as much as possible from the eavesdropper. We obtain the entire capacity-equivocation region for this channel model. In particular, we show the sufficiency of jointly Gaussian auxiliary random variables and channel input to evaluate the existing single-letter description of the capacity-equivocation region due to Csiszar-Korner. Next, we study the secure broadcasting problem, where a transmitter wants to have secure communication with multiple legitimate users in the presence of an external eavesdropper. We study several special cases of the secure broadcasting problem. First, we consider the degraded multi-receiver wiretap channel, and establish its secrecy capacity region. Second, we consider the parallel less noisy multi-receiver wiretap channel, and obtain its common message secrecy capacity and sum secrecy capacity. Third, we consider the parallel degraded multi-receiver wiretap channel for the two-user and two-sub-channel case, and obtain its entire secrecy capacity region. Finally, we consider a parallel channel model with two sub-channels, where the transmitter can use only one of the subchannels at any time, and characterize its secrecy capacity region. Then, we study the two-user Gaussian MIMO broadcast channel with common and confidential messages. In this channel model, the transmitter sends a common message to both users, and a confidential message to each user which needs to be kept perfectly secret from the other user. We obtain the entire capacity region of this channel. We also explore the connections between this channel model and its non-confidential counterpart, i.e., the Gaussian MIMO broadcast channel with common and private message. Next, we consider the Gaussian MIMO multi-receiver wiretap channel and obtain its secrecy capacity region for the most general case. We first show that even for the single-input single-output (SISO) case, existing converse techniques fall short of proving the secrecy capacity region, to emphasize the need for a new proof technique, which we develop by using the relationships between the Fisher information and the differential entropy. Using this new proof technique, we obtain the secrecy capacity region of the degraded MIMO channel. We then establish the secrecy capacity region of the general MIMO channel by using the channel enhancement technique in conjunction with the capacity result we obtained for the degraded MIMO channel. For the general MIMO channel, we show that dirty-paper coding (DPC) combined with stochastic encoding attains the entire secrecy capacity region. Then, we study the multi-receiver wiretap channel for a more general scenario, where, in addition to confidential messages, the transmitter sends public messages to the legitimate users, on which there are no secrecy constraints. First, we consider the degraded discrete memoryless channel, and obtain inner and outer bounds for the capacity region. These inner and outer bounds match for certain cases, providing the capacity region. Second, we obtain an inner bound for the general discrete memoryless channel by using Marton's inner bound. Third, we consider the degraded Gaussian MIMO channel, and show that jointly Gaussian auxiliary random variables and channel input are sufficient to exhaust the inner and outer bounds. Finally, we provide an inner bound for the capacity region of the general Gaussian MIMO channel. Next, we focus on the multiple access wiretap (MAC-WT) channel whose capacity region is unknown. We consider a special class of MAC-WT channels which we call the weak eavesdropper class, where each user's link to the legitimate receiver is stronger than its link to the eavesdropper. For this class of channels, we develop an outer bound for the secrecy capacity region, which partially matches the achievable region in an n-letter form. We evaluate a looser version of our outer bound for the Gaussian case, and show that our outer bound is within 0.5 bits/channel use of the achievable rates along the individual secrecy rates for all weak eavesdropper Gaussian MAC-WT. Then, we investigate the effects of user cooperation on the secrecy of broadcast channels by considering the cooperative relay broadcast channel (CRBC). We propose an achievable scheme that combines Marton's coding scheme for broadcast channels and Cover and El Gamal's compress-and-forward (CAF) scheme for relay channels. For the Gaussian CRBC, we show that both users can have positive secrecy rates, which is not possible for scalar Gaussian broadcast channels without cooperation. We further investigate the effects of user cooperation on secrecy by considering the multiple access channel with generalized feedback (MAC-GF), which can be viewed as the MAC-dual of the CRBC. We propose a CAF-based achievable secrecy rate region for the MAC-GF. Specializing our results to a Gaussian MAC-GF, we present numerical results which demonstrate that cooperation can improve secrecy for the MAC-GF. Next, we study the two-user one-eavesdropper discrete memoryless compound wiretap channel, and provide the best known lower bound for the secrecy capacity of this compound channel. We evaluate this achievable secrecy rate for the Gaussian MIMO case by using DPC. We show that this achievable secrecy rate achieves at least half of the secrecy capacity of this Gaussian MIMO compound wiretap channel, and also attains the secrecy capacity when the eavesdropper is degraded with respect to one of the two users. Then, we study the degraded compound multi-receiver wiretap channel (DCMRWC), which, in addition to a group of eavesdroppers, has two groups of users, namely the stronger group and the weaker group. We study two different communication scenarios for this channel. In the first scenario, there is only one eavesdropper, and the transmitter sends a confidential message to each group of legitimate users while keeping both messages secret from the eavesdropper. In the second scenario, we study the DCMRWC with layered messages without any restriction on the number of eavesdroppers. For both scenarios, we obtain the secrecy capacity region for the discrete memoryless channel, the parallel channel, and the Gaussian parallel channel. For the Gaussian MIMO channel, we obtain the secrecy capacity region when there is only one user in the second group. Next, we study the two-user fading broadcast channel and obtain its ergodic secrecy capacity region. We show that, thanks to fading, both users can have simultaneous secure communication with the transmitter, although this is not possible in the scalar non-fading Gaussian broadcast channel where only one user can have secure communication. This simultaneous secrecy of both users is achieved by an opportunistic communication scheme, in which, at each time instant, the transmitter communicates with the user having a better channel gain. Then, we study the secure lossy transmission of a vector Gaussian source to a legitimate user in the presence of an eavesdropper, where both the legitimate user and the eavesdropper have vector Gaussian side information. We obtain an outer bound for the rate, equivocation and distortion region. Moreover, we obtain the maximum equivocation at the eavesdropper when there is no constraint on the transmission rate. By using this maximum equivocation result, we show two facts. First, for this problem, in general, Wyner-Ziv scheme is suboptimal, although, it is optimal in the absence of an eavesdropper. And, second, even when there is no transmission rate constraint, an uncoded transmission scheme is suboptimal; the presence of an eavesdropper necessitates the use of a coded scheme to attain the maximum equivocation. Finally, we revisit the secure lossy source coding problem. In all works on this problem, either the equivocation of the source at the eavesdropper or the equivocation of the legitimate user's reconstruction of the source at the eavesdropper is used to measure secrecy. We first propose the relative equivocation of the source at the eavesdropper with respect to the legitimate user as a new secrecy measure. We argue that this new secrecy measure is the one that corresponds to the natural generalization of the equivocation in a wiretap channel to the context of secure lossy source coding. Under this new secrecy measure, we provide a single-letter description of the rate, relative equivocation and distortion region, as well as its specializations to degraded and reversely degraded cases. We investigate the relationships between the optimal scheme that attains this region and the Wyner-Ziv scheme.

Jan 1, 20120 citations

Contributions to Information Theoretically Secure Communication

Setareh Sharifian

Secure communication ensures the integrity and confidentiality of communication between connected devices. An information-theoretic approach to secure communication gives the strongest confidentiality guarantee by assuming that the attacker has unlimited computing power. The earliest formal model and definition of information-theoretic secure communication is by Shannon, who employed a secret key shared between communicating parties to provide confidentiality. An alternative elegant information-theoretic approach to secure communication views the natural characteristics of the environment (i.e., channel’s noise) as a resource to build security functionalities. This approach was first proposed by Wyner, and the corresponding secure communication model is called the wiretap channel model. These two approaches introduce two primary resources for providing information-theoretic secure communication: the shared secret key and physical properties of the communication medium. In this thesis, we study how to employ the above two resources for secure message transmission. We study this by using channel’s noise in the wiretap channel model. In this model, a sender is connected to the receiver and the adversary through two noisy channels. We propose a new wiretap encoding scheme with strong secrecy that provides perfect secrecy and reliability, asymptotically. The construction treats the noise in the adversary’s channel as a source of randomness that is extracted and used to hide the message from the adversary. We realize the wiretap channel model using cooperative jamming to evaluate the performance of wiretap codes in practice. We consider a model called keyed wiretap channel that unifies Wyner’s model with Shannon’s model of perfect secrecy for information systems, and propose a keyed encoding schemes with strong secrecy and other properties that are attractive in practice. We also study two-party information-theoretic secret key agreement when the two parties have access to samples of a common source of randomness and use a single message transmission to arrive at a shared random key. We propose a secret key agreement protocol in this setting, prove its security, and show its superior performance compared to other known protocols with the same properties. Finally, we propose an information-theoretic secret key agreement over a virtual wiretap channel created by cooperative jamming.

May 15, 20200 citations

Information-Theoretically Secure Communication Under Channel Uncertainty

Hung D. Ly

Secure communication under channel uncertainty is an important and challenging problem in physical-layer security and cryptography. In this dissertation, we take a \nfundamental information-theoretic view at three concrete settings and use them to shed insight into efficient secure communication techniques for different scenarios under channel uncertainty. \n \nFirst, a multi-input multi-output (MIMO) Gaussian broadcast channel with two receivers and two messages: a common message intended for both receivers (i.e., channel \nuncertainty for decoding the common message at the receivers) and a confidential message intended for one of the receivers but needing to be kept asymptotically perfectly secret from the other is considered. A matrix characterization of the secrecy capacity region is established via a channel-enhancement argument and an extremal entropy inequality previously established for characterizing the capacity region of a degraded compound MIMO Gaussian broadcast channel. \n \nSecond, a multilevel security wiretap channel where there is one possible realization for the legitimate receiver channel but multiple possible realizations for the eavesdropper channel (i.e., channel uncertainty at the eavesdropper) is considered. A coding scheme is designed such that the number of secure bits delivered to the legitimate receiver depends on the actual realization of the eavesdropper channel. More specifically, when the eavesdropper channel realization is weak, all bits delivered to the legitimate receiver need to be secure. In addition, when the eavesdropper channel realization is strong, a prescribed part of the bits needs to remain secure. We call such codes security embedding codes, referring to the fact that high-security bits are now embedded into the low-security ones. We show that the key to achieving efficient security embedding is to jointly encode the low-security and high-security bits. In particular, the low-security bits can be used as (part of) the transmitter randomness to protect the high-security ones. \n \nFinally, motivated by the recent interest in building secure, robust and efficient distributed information storage systems, the problem of secure symmetrical multilevel diversity coding (S-SMDC) is considered. This is a setting where there are channel uncertainties at both the legitimate receiver and the eavesdropper. The problem of encoding individual sources is first studied. A precise characterization of the entire admissible rate region is established via a connection to the problem of secure coding over a three-layer wiretap network and utilizing some basic polyhedral structure of the admissible rate region. Building on this result, it is then shown that the simple coding strategy of separately encoding individual sources at the encoders can achieve the minimum sum rate for the general S-SMDC problem.

Jul 16, 20120 citations

Secrecy from Resolvability

Matthieu R. Bloch, J. Nicholas Laneman

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.

May 26, 201119 citations

On the use of secret keys in broadcast channels with receiver side information

Rafael F. Schaefer, Ashish J. Khisti, Holger Boche

The use of secret keys in broadcast channels with receiver side information is studied. The particular scenario is analyzed where a transmitter wants to send two confidential messages to two receivers, while keeping an external eavesdropper ignorant. Each receiver has one of the confidential messages as side information available for decoding. In addition to that, the transmitter shares independent secret keys of arbitrary rates with both receivers. The secret keys can be used in different ways: They can act as one-time pads to encrypt the confidential messages or they can be used as randomization resources for wiretap coding. Both approaches are discussed and an achievable rate region based on superposition coding is established for the one-time pad approach. For the wiretap coding approach, the secrecy capacity for degraded channels is derived. In the optimal coding scheme, the available secret keys are used as the randomization part of the wiretap code to keep the eavesdropper ignorant. In establishing the capacity region, a new upper bound on the sum-rate is derived. This bound shows that in an optimal coding scheme, in the degraded case, the total equivocation-rate of the (opposite) secret-keys at the legitimate receivers must equal the equivocation-rate of the secret-keys at the eavesdropper, when informed about the messages.

IEEE International Conference on Acoustics Speech and Signal ProcessingMay 1, 20142 citations