1Secret-message capacity of a line network

We investigate the problem of information theoretically secure communication in a line network with erasure channels and state feedback. We consider a spectrum of cases for the private randomness that intermediate nodes can generate, ranging from having intermediate nodes generate unlimited private randomness, to having intermediate nodes generate no private randomness, and all cases in between. We characterize the secret message capacity when either only one of the channels is eavesdropped or all of the channels are eavesdropped, and we develop polynomial time algorithms that achieve these capacities. We also give an outer bound for the case where an arbitrary number of channels is eavesdropped. Our work is the first to characterize the secrecy capacity of a network of arbitrary size, with imperfect channels and feedback. As a side result, we derive the secret key and secret message capacity of an one-hop network, when the source has limited randomness. We consider a source that communicates with a destination over a line network with N edges, where each intermediate node represents a relay, and each edge represents an erasure channel with state feedback (all channels are assumed to be orthogonal). The source aims to send a message securely to the destination, in the presence of a passive eavesdropper, Eve, who wiretaps an (unknown) subset with (known) cardinality V of the N channels. Eve receives independently erased versions of the transmissions