X-Secure T-Private Linear Computation With Graph Based Replicated Storage
Haobo Jia, Zhuqing Jia · 2023
The problem of X-secure T-private linear computation with graph based replicated storage (GXSTPLC) is to enable the user to retrieve a linear combination of messages privately from a set of N distributed servers where every message is only allowed to replicate among a subset of servers subject to an X-security constraint, i.e., any groups of up to X colluding servers must reveal nothing about the messages. Besides, any groups of up to T servers must reveal no information about the coefficients of the linear combination retrieved by the user. In this paper, inspired by a Vandermonde decomposition of Cauchy matrices, we propose an achievability scheme for GXSTPLC that achieves the rate of (ρmin−X −T)/N if every message is replicated at least ρmintimes and ρmin> X + T, which coincides with a lower bound of the rate of X-secure T-private information retrieval with graph based replicated storage (GXSTPIR) by Jia and Jafar. Moreover, the asymptotic capacity of GXSTPLC is partially settled, including the setting where the storage forms a symmetric pattern.