We present achievability schemes for secure message transmission in the presence of a passive eavesdropper, over arbitrary networks, where each edge corresponds to an independent erasure channel and we have available public channel state feedback. Our schemes are efficiently described through linear programming formulations, that generalize the information flow linear programs to networks with security constraints; different sources of secrecy show up as parameters in our linear programs, and solving the optimization problem enables to select the optimal (in terms of rate) scheme that integrates them. As far as we know, these are the first linear programming formulations for secret message transmission over arbitrary networks with erasures and channel state feedback.
We present achievability schemes for secure message transmission in the presence of a passive eavesdropper, over arbitrary networks, where each edge corresponds to an independent erasure channel and we have available public channel state feedback. Our schemes are efficiently described through linear programming formulations, that generalize the information flow linear programs to networks with security constraints; different sources of secrecy show up as parameters in our linear programs, and solving the optimization problem enables to select the optimal (in terms of rate) scheme that integrates them. As far as we know, these are the first linear programming formulations for secret message transmission over arbitrary networks with erasures and channel state feedback.
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.
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.
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 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 consider a 1-to-K communication scenario, where a source transmits private messages to K receivers through a broadcast erasure channel, and the receivers feed back 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 cases where we have an exact characterization, we can achieve the capacity by 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 non-secure 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.