An LP Characterization of the Secret-message Capacity of Three Erasure Networks With Feedback

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.