On Extremal Rates of Secure Storage Over Graphs
Zhou Li, Hua Sun · IEEE Transactions on Information Forensics and Security · 2023
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$.