Weakly secure MDS codes for simple multiple access networks

We consider a simple multiple access network (SMAN), where k sources of unit rates transmit their data to a common sink via n relays. Each relay is connected to the sink and to certain sources. A coding scheme (for the relays) is weakly secure if a passive adversary who eavesdrops on less than k relay-sink links cannot reconstruct the data from each source. We show that there exists a weakly secure maximum distance separable (MDS) coding scheme for the relays if and only if every subset of ℓ relays must be collectively connected to at least ℓ+1 sources, for all 0 <; ℓ <; k. Moreover, we prove that this condition can be verified in polynomial time in n and k. Finally, given a SMAN satisfying the aforementioned condition, we provide another polynomial time algorithm to trim the network until it has a sparsest set of source-relay links that still supports a weakly secure MDS coding scheme.