On the Storage–Communication Trade-Off in Graph-Based X-Secure T-Private Linear Computation

The problem of graph-based <i>X</i>-secure <i>T</i>-private linear computation (GXSTPLC) is to allow a user to retrieve a linear combination of <i>K</i> messages from a set of <i>N</i> distributed servers that store the messages in a graph-based fashion, i.e., each message is restricted to be distributed among a subset of servers. <i>T</i>-privacy requires that the coefficients of the linear combination are not revealed to any group of up to <i>T</i> colluding servers, and <i>X</i>-security guarantees that any set of up to <i>X</i> colluding servers learns nothing about the messages. In this paper, we propose an achievability scheme for GXSTPLC that enables a storage-communication trade-off by exploiting non-replicated storage codes. Novel aspects of our achievability scheme include the usage of the idea of cross-subspace alignment null shaper that addresses various challenges posed by the graph-based storage structure. In addition, unlike previous works, our scheme allows a direct transformation into a quantum one to achieve a superdense coding gain by leveraging the idea of <i>N</i>-Sum Box abstraction of quantum "over-the-air" computing.