On Extremal Rates of Secure Storage over Graphs
share
A secure storage code maps K source symbols, each of L_w bits, to N coded symbols, each of L_v bits, such that each coded symbol is stored in a node of a graph. Each edge of the graph is either associated with D of the K source symbols such that from the pair of nodes connected by the edge, we can decode the D source symbols and learn no information about the remaining K-D source symbols; or the edge is associated with no source symbols such that from the pair of nodes connected by the edge, nothing about the K source symbols is revealed. The ratio L_w/L_v is called the symbol rate of a secure storage code and the highest possible symbol rate is called the capacity. We characterize all graphs over which the capacity of a secure storage code is equal to 1, when D = 1. This result is generalized to D> 1, i.e., we characterize all graphs over which the capacity of a secure storage code is equal to 1/D under a mild condition that for any node, the source symbols associated with each of its connected edges do not include a common element. Further, we characterize all graphs over which the capacity of a secure storage code is equal to 2/D.
READ FULL TEXT