On Extremal Rates of Secure Storage Over Graphs

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 (one may view a node as a server). 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.

Automated summary

A secure storage code converts K source symbols of L-w bits to N coded symbols of L-v bits and stores each coded symbol in a node of a graph. The graph has edges associated either with D source symbols or with no source symbols. We characterize the graphs where the capacity of a secure storage code is equal to 1 when D = 1. This result is extended to D > 1, and we also characterize the graphs where the capacity is equal to 1/D and 2/D.