We present protocols for creating pairwise secrets between nodes in a wireless network, so that these secrets are secure from an eavesdropper, Eve, with unbounded computational and memory capabilities, but with limited network presence. We first present a basic secret-agreement protocol for single-hop networks, where secrets are constructed using traffic exchanged between the nodes, and we show that under standard theoretical assumptions, our protocol is information-theoretically secure. Second, we propose a secret-agreement protocol for arbitrary, multi-hop networks that build on the basic protocol but also comprises design features for leveraging additional sources, that multi-hop offers, for secrecy. Finally, we evaluate our protocols, and we provide experimental evidence that it is feasible to create thousands of secret bits per second, in realistic wireless setups, the security of which is independent of Eve’s computational capabilities.

This paper presents exact capacity characterizations for the case, when a principal, Alice, wants to securely send a message to another principal, Bob, over three network configurations: the parallel edges network, the V-network, and the triangle network. We assume that: 1) a passive eavesdropper, Eve, overhears any one edge in the network; 2) each edge corresponds to an independent broadcast packet erasure channel with arbitrary erasure probabilities; and 3) all legitimate nodes can publicly but causally acknowledge whether they received each packet or not. We develop optimal achievability schemes that are expressed as linear programs (LPs) and share a two-phase structure, where at the first phase, we create secret keys, and at the second phase, we use them to encrypt the transmitted message. Our outer bounds are also expressed through LP formulations. We prove that our schemes are optimal by showing that the optimal solution of the outer bound LP and the optimal solution of the achievability scheme LP coincide.

We design polynomial time schemes for secure message transmission over arbitrary networks, in the presence of an eavesdropper, and where each edge corresponds to an erasure channel with public feedback. Our schemes are described through linear programming (LP) formulations, that explicitly select (possibly different) sets of paths for key-generation and message sending. Although our LPs are not always capacity-achieving, they outperform the best known alternatives in the literature, and extend to incorporate several interesting scenaria.

One of the most widely-known techniques for securing a message from eavesdropping, is the famous one-time pad. Although the one-time pad offers unconditional security, it has limited applicability today, because it requires that to communicate, two parties already share a key that is not known by the eavesdropper and has size equal to the message. In this review paper we present a line of work that explores how we can efficiently share keys securely from an eavesdropper, and thus communicate using a one-time pad like approach. The basic idea is to exploit new opportunities that wireless networks offer, such as the fact that we have multiple paths, the fact that we have packet losses, and the availability of ACK/NACK feedback.

Secure network coding assumes that the underlying network channels are error-free; thus, if our channels introduce errors, we need to first apply a channel code to correct them, and then build security on top of the resulting error-free network. In this paper, we develop achievability protocols and outer bounds for the secure network coding setting, where the edges are subject to packet erasures, and public feedback of the channel state is available to both Eve and the legitimate network nodes. We show that by leveraging erasures and feedback, we can achieve secrecy rates that are in some cases multiple times higher than the alternative of separate channel-error-correction followed by secure network coding; moreover, we develop outer bounds and prove optimality of our proposed schemes in some special cases.

We consider a 1-to-K communication scenario, where a source transmits private messages to K receivers through a broadcast erasure channel, and the receivers feedback strictly, causally, and publicly their channel states after each transmission. We explore the achievable rate region when we require that the message to each receiver remains secret-in the information theoretical sense-from all the other receivers. We characterize the capacity of secure communication in all the cases where the capacity of the 1-to-K communication scenario without the requirement of security is known. As a special case, we characterize the secret-message capacity of a single receiver point-to-point erasure channel with public state-feedback in the presence of a passive eavesdropper. We find that in all the cases where we have an exact characterization, we can achieve the capacity using linear complexity two-phase schemes: in the first phase, we create appropriate secret keys, and in the second phase, we use them to encrypt each message. We find that the amount of key we need is smaller than the size of the message, and equal to the amount of encrypted message the potential eavesdroppers jointly collect. Moreover, we prove that a dishonest receiver that provides deceptive feedback cannot diminish the rate experienced by the honest receivers. We also develop a converse proof which reflects the two-phase structure of our achievability scheme. As a side result, our technique leads to a new outer bound proof for the nonsecure communication problem.

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.

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.

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.

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.