Wireless network secrecy

The broadcast nature of wireless communication makes it inherently vulnerable to eavesdropping by an adversary. However, the destination and eavesdropper can have different 'views' of the transmission through distinct channels. We have examined how to exploit this distinction along with relay (helper) nodes to ensure information-theoretic (unconditional) secrecy. We have demonstrated that cooperative network secrecy can be achieved for arbitrary wireless relay networks by utilizing the signal interactions to carry secure information forward cooperatively. We have shown an achievable trade-off between the reliable transmission rate from the source to the legitimate destination and the amount of information leaked to a class of eavesdroppers over an arbitrary wireless relay network. Roughly speaking, the trade-off is related to the information-theoretic min-cuts between the source-destination and source-eavesdropper pairs. For example, one extreme point of the trade-off is where we can ensure perfect secrecy (zero rate of information leakage to the eavesdropper) for an information rate of (approximately) the `difference' between these two min-cut values. However, this 'separable' scheme where the relay network is operated as before, but the secrecy is induced end-to-end is not necessarily the best scheme. We have shown that one can use 'friendly' jamming by inserting junk/noise messages into the network by helpful relays can significantly improve the secrecy rate. This has been shown also for arbitrary noisy networks. A short summary of these results can be found here.

In wireless sensor networks, nodes observe correlated physical processes. We have examined how to generate information-theoretic secure keys using access to these correlated processes in combination with the broadcast channel. In particular, we have shown that functionally the two sources of secrecy are additive, though operationally we need to intricately code them jointly in order to generate secrecy. We have also characterized the secrecy rate when an additionally public discussion channel is available, and one can interactively generate the secret key.

Papers

  1. Download: laszlo_lp.pdf 
  2. Download: winetsec_boe.pdf www 
  3. Download: secretcom_czap.pdf www 
  4. Download: snc_czapfpd.pdf www 
  5. Download: isit14_mdpd.pdf 
  6. Download: on Arxiv 
    Abstract:
    We consider oblivious transfer between Alice and Bob in the presence of an eavesdropper Eve when there is a broadcast channel from Alice to Bob and Eve. In addition to the secrecy constraints of Alice and Bob, Eve should not learn the private data of Alice and Bob. When the broadcast channel consists of two independent binary erasure channels, we derive the oblivious transfer capacity for both 2-privacy (where the eavesdropper may collude with either party) and 1-privacy (where there are no collusions).
  7. Download: tri_net_sec.pdf 
    Abstract:
    We characterize the secret message capacity of the triangle network, that consists of a source, a relay and a destination connected through orthogonal erasure channels. A passive eavesdropper, Eve, wiretaps any one of the three channels. The source and the relay can each generate unlimited private randomness; the relay and the destination can publicly provide strictly causal channel state information. Our achievable scheme is expressed through a linear program (LP) with 11 inequalities that captures a minimal set of secret key generation methods and the use of them for message encryption. Our outer bound is expressed also through a linear program, in this case with 41 constraints, constructed from general information inequalities. We prove that the optimal value of the outer bound LP is no larger than that of the scheme LP, which implies that the solution of the achievable scheme LP is the capacity. We find that equipping the relay with private randomness increases the secrecy rate by more than 40% in some cases and that cut-set bounds, directly applied in the network, are not always tight. Because the derivation of the inner and outer bound are both lengthy, we describe in this paper the achievability scheme, outline the outer bound, and provide the full derivations online [1]. We also make available Matlab functions that take as input the erasure probabilities and evaluate the inner and outer bounds.
  8. Download: secure_netcod.pdf 
    Abstract:
    Secure network coding assumes that the underlying network links are lossless, thus it can be applied over lossy networks after channel error correction. Yet it is well known that channel losses, such as packet erasures, can be constructively used for secrecy over a link. We address here the challenge of extending these results for arbitrary networks. We provide achievability schemes over erasure networks with feedback, that outperform the alternative approach of channel error correction followed by secure message transmission separation. We derive outer bounds on the securely achievable rate and as a consequence we show optimality of our proposed scheme in some special cases.
  9. Abstract:
    Current security systems often rely on the adversary's computational limitations. Wireless networks offer the opportunity for a different, complementary kind of security, which relies on the adversary's limited network presence (i.e., that the adversary cannot be located at many different points in the network at the same time). We present a system that leverages this opportunity to enable n wireless nodes to create a shared secret S, in a way that an eavesdropper, Eve, obtains very little information on S. Our system consists of two steps: (1) The nodes transmit packets following a special pattern, such that Eve learns very little about a given fraction of the transmitted packets. This is achieved through a combination of beam forming (from many different sources) and wiretap codes. (2) The nodes participate in a protocol that reshuffles the information known to each node, such that the nodes end up sharing a secret that Eve knows very little about. Our protocol is easily implementable in existing wireless devices and scales well with the number of nodes; these properties are achieved through a combination of public feedback, broadcasting, and network coding. We evaluate our system through a 5-node testbed. We demonstrate that a group of wireless nodes can generate thousands of new shared secret bits per second, with their secrecy being independent of the adversary's computational capabilities.
  10. Abstract:
    We investigate the problem of secure communication in a simple network with three communicating parties, two distributed sources who communicate over orthogonal channels to one destination node. The cooperation between the sources is restricted to a rate limited common random source they both observe. The communication channels are erasure channels with strictly causal channel state information of the destination available publicly. A passive adversary is present in the system eavesdropping on any one of the channels. We design a linear scheme that ensures secrecy against the eavesdropper. By deriving an outer bound for the problem we prove that the scheme is optimal in certain special cases.
  11. Download: on Arxiv 
    Abstract:
    We study the problem of secure message multicasting over graphs in the presence of a passive (node) adversary who tries to eavesdrop in the network. We show that use of feedback, facilitated through the existence of cycles or undirected edges, enables higher rates than possible in directed acyclic graphs of the same mincut. We demonstrate this using code constructions for canonical combination networks (CCNs). We also provide general outer bounds as well as schemes for node adversaries over CCNs.
  12. Download: securing_bc.pdf 
    Abstract:
    Consider a sender, Alice, who wants to transmit private messages to two receivers, Bob and Calvin, using unreliable wireless broadcast transmissions and short public feedback from Bob and Calvin. In [1], we assumed that Bob and Calvin provide honest feedback, and characterized the secure capacity region of the private messages under the requirement that Bob and Calvin do not learn each other's message. In this paper, we assume that Bob (or Calvin) may provide dishonest feedback; or even control the input message distributions, as is commonly assumed in cryptography literature. We characterize the capacity region in the case of dishonest adversaries, as well as an achievable region for the case when the adversary has complete control on the distribution of the messages. We also design polynomial time protocols for both cases, that rely on the use of coding techniques to mix and secure the private messages. As a side result, we define an extended notion of semantic security for this problem and using a similar approach to [2], we show the equivalence of different security notions.
  13. Abstract:
    We consider the problem where a group of wireless nodes, connected to the same broadcast domain, want to create pairwise secrets, in the presence of an adversary Eve, who tries to listen in and steal these secrets. Existing solutions assume that Eve cannot perform certain computations (e.g., large-integer factorization) in useful time. We ask the question: can we solve this problem without assuming anything about Eve's computational capabilities? We propose a simple secret-agreement protocol, where the wireless nodes keep exchanging bits until they have agreed on pairwise secrets that Eve cannot reconstruct with very high probability. Our protocol relies on Eve's limited network presence (the fact that she cannot be located at an arbitrary number of points in the network at the same time), but assumes nothing about her computational capabilities. We formally show that, under standard theoretical assumptions, our protocol is information-theoretically secure (it leaks zero information to Eve about the secrets). Using a small wireless testbed of smart-phones, we provide experimental evidence that it is feasible for 5 nodes to create thousands of secret bits per second, with their secrecy being independent from the adversary's capabilities.
  14. Abstract:
    Current security systems typically rely on the adversary's computational limitations (e.g., the fact that it cannot invert a hash function or perform large-integer factorization). Wireless networks offer the opportunity for a different, complementary kind of security, which relies not on the adversary's computational limitations, but on its limited network presence (i.e., that the adversary cannot be located at many different points in the network at the same time). We take a first step toward designing and building a wireless security system that leverages this opportunity: We consider the problem where a group of n nodes, connected to the same broadcast wireless network, want to agree on a shared secret (e.g., an encryption key), in the presence of an adversary Eve who tries to listen in and steal the secret. We propose a secret-agreement protocol, where the n nodes of the group keep exchanging bits until they have all agreed on a bit sequence that Eve cannot reconstruct (with very high probability). We provide experimental evidence---to the best of our knowledge, the first one---that a group of wireless nodes can generate thousands of new shared secret bits per second, with their secrecy being independent of the adversary's computational capabilities.
  15. Download: bc_private_msg.pdf 
    Abstract:
    Consider a source, Alice, broadcasting private messages to multiple receivers through a broadcast erasure channel; users send back to Alice public feedback that she causally uses to decide the coding strategy for her following transmissions. Recently, the multiple unicast capacity region for this problem has been exactly characterized for a number of special cases; namely the 2-user, 3-user, symmetric K-user, and one-sidedly fair K-user [1], [2]. In this paper, we show that for all the cases where such characterizations exist, we can also optimally characterize the “secure” communication rates, where the message that Alice transmits to each user is information theoretically secure from the other users, even if these collude. We show that a simple, two-phase strategy, where appropriate amounts of secret keys are first generated and then consumed, matches a new outer bound we derive.
  16. Abstract:
    In this short review paper we summarize some of our recent results on interactive message secrecy for broadcast erasure channels.
  17. Download: secret_keygen.pdf 
    Abstract:
    We study the secret-key capacity in a joint source-channel coding setup-the terminals are connected over a discrete memoryless channel and have access to side information, modelled as a pair of discrete memoryless source sequences. As our main result, we establish the upper and lower bounds on the secret-key capacity. In the lower bound expression, the equivocation terms of the source and channel components are functionally additive even though the coding scheme generates a single secret-key by jointly taking into account the source and channel equivocations. Our bounds coincide, thus establishing the capacity, when the underlying wiretap channel can be decomposed into a set of independent, parallel, and reversely degraded channels. For the case of parallel Gaussian channels and jointly Gaussian sources we show that Gaussian codebooks achieve the secret-key capacity. In addition, when the eavesdropper also observes a correlated side information sequence, we establish the secret-key capacity when both the source and channel of the eavesdropper are a degraded version of the legitimate receiver. We finally also treat the case when a public discussion channel is available, propose a separation based coding scheme, and establish its optimality when the channel output symbols of the legitimate receiver and eavesdropper are conditionally independent given the input.
  18. Abstract:
    We study secret-key agreement with public discussion over a flat-fading wiretap channel model. The fading gains are correlated across the receivers and sampled independently at each time. Perfect receiver channel state information (CSI) is assumed, whereas a noisy CSI of the main channel is also available to the transmitter. We propose lower and upper bounds on the capacity. Our lower bound is achieved by a coding scheme that involves a separate binning of the receiver CSI sequence and its channel output sequence. In general it improves upon the joint-binning schemes considered in earlier works. Our upper and lower bounds coincide, establishing the capacity, when either the transmitter has no CSI or when the channel gains of the legitimate receiver and the eavesdropper are statistically independent.
  19. Abstract:
    We characterize the secret message capacity of a wiretapped erasure channel where causal channel state information of the honest nodes is publicly available. In doing so, we establish an intimate connection between message secrecy and secret key generation for the same channel setup. We propose a linear coding scheme that has polynomial encoding/decoding complexity, and prove a converse that shows the optimality of our scheme. Our work also demonstrates the value of causal public feedback, which has previously been shown for the secret key generation problem.
  20. Abstract:
    Information-theoretic secrecy is studied for a parallel relay (diamond) network, in which a transmitter wishes to communicate to a receiver through two relay nodes. While there is no direct link between the transmitter and receiver and all flow of information has to be transmitted through the relays, the message has to be kept secret from each of them. The exact secrecy capacity is characterized for the network under the linear deterministic model. The problem is then studied when each terminal is equipped with multiple antennas, and the channels are parallel Gaussian links. Lower and upper bounds for the secrecy capacity are derived, and the gap is bounded by a constant independent of the channel parameters and SNR. This results in an approximate characterization for the secrecy capacity of the parallel Gaussian diamond network.
  21. Abstract:
    We consider a group of m trusted nodes that aim to create a shared secret key K, using a state-dependent wireless broadcast channel that exists from one of the honest nodes to the rest of the nodes including a passive eavesdropper Eve. All of the trusted nodes can also discuss over a cost-free and unlimited rate public channel which is also observed by Eve. For this setup, we develop an information-theoretically secure secret key agreement protocol. We show the optimality of this protocol for linear deterministic wireless broadcast channels as well as in the high-SNR regime for wireless channels with large dynamic range over channel states.
  22. Abstract:
    We consider a group of m trusted nodes that aim to create a shared secret key K over a wireless channel in the presence an eavesdropper Eve. We assume an erasure broadcast channel from one of the honest nodes to the rest of them including Eve. All of the trusted nodes can also discuss over a cost-free public channel which is observed by Eve. For this setup we characterize the secret key generation capacity and propose an achievability scheme that is computationally efficient and employs techniques from network coding. Surprisingly, whether we have m = 2 nodes, or an arbitrary number m of nodes, we can establish a shared secret key among them at the same rate, independently of m.
  23. Download: on Arxiv 
  24. Note: Invited paper surveying our results on wireless relay network secrecy.
    Download: pdtizs10.pdf 
  25. Download: pdtisit10.pdf 
    Abstract:
    In this paper we consider information-theoretically secure communication between two special nodes (“source” and “destination”) in a memoryless network with authenticated relays, where the secrecy is with respect to a class of eavesdroppers. We develop achievable secrecy rates when authenticated relays also help increase secrecy rate by inserting noise into the network.
  26. Abstract:
    In this paper we consider secret communication between two special nodes (“source” and “destination”) in a wireless network with authenticated relays: the message communicated to the destination is to be kept information-theoretically (unconditionally) secret from any eavesdropper within a class. Since the transmissions are broadcast and interfere with each other, complex signal interactions occur. We develop cooperative schemes which utilize these interactions in wireless communication over networks with arbitrary topology, and give provable unconditional secrecy guarantees.
  27. Abstract:
    The compound wiretap channel generalizes the classical problem in broadcast information-theoretic secrecy by allowing a class of potential eavesdroppers. In this paper we present a new coding scheme that generalizes known approaches to this problem. The scheme prefixes an artificial multiple access channel to the transmission scheme in order to design a structured transmit codebook. The idea is that such a structure can potentially increase the perfect secrecy rate for the legitimate users in the presence of the class of eavesdroppers.
  28. A. Khisti, S. N. Diggavi, and G. W. Wornell, "Secret key agreement using asymmetry in channel state knowledge," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 2286-2290.
  29. Download: pdtita09final.pdf 
    Abstract:
    This paper studies the idea of noise insertion by authenticated relays through friendly jamming. We develop the secrecy rate achievable in arbitrary (deterministic) networks when there are relays actively helping secrecy.
  30. Download: pdt_allerton08.pdf 
    Abstract:
    We study a line network with an eavesdropper having access to the relay transmission. We assume that there could also be a public feedback channel from the destination. We develop achievable strategies to achieve certain rate-equivocation pairs.
  31. A. Khisti, S. N. Diggavi, and G W. Wornell, "Secret key generation with correlated sources and noisy channels," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 1005-1009.