The Asymptotic Capacity of X-Secure T-Private Linear Computation With Graph Based Replicated Storage

Le résumé fourni par la source

We consider the problem ofX-secure andT-private linear computation with graph based replicated storage (GXSTPLC), which enables the user to privately retrieve a linear combination of messages from a set ofNdistributed servers where each message is restricted to be stored exclusively among a subset of servers, adhering to anX-security constraint. This constraint dictates that any group of up toXcolluding servers must not disclose any information about the stored messages. Furthermore, any group of up toTservers is restricted from learning anything about the coefficients of the linear combination retrieved by the user. In this work, we completely characterize the asymptotic capacity of GXSTPLC, i.e., the supremum of achievable rates (which is the average number of desired symbols retrieved per downloaded symbol), in the limit as the number of messagesKapproaches infinity. Specifically, it is shown that a prior linear programming based upper bound on the asymptotic capacity of GXSTPLC due to Jia and Jafar is tight (thus settles their conjecture) by constructing achievability schemes. Notably, our achievability scheme also settles the exact capacity (i.e., for finiteK) ofX-secure linear combination with graph based replicated storage (GXSLC). Our achievability proof builds upon an achievability scheme for a closely related problem named asymmetric X-secure T-private linear computation with graph based replicated storage (Asymm-GXSTPLC) that guarantees non-uniform security and privacy levels across messages and coefficients (of the desired linear combination). In particular, by carefully designing Asymm-GXSTPLC settings for GXSTPLC problems, the corresponding Asymm-GXSTPLC schemes can be reduced to asymptotic capacity achieving schemes for GXSTPLC. In regard to the achievability scheme for Asymm-GXSTPLC, interesting aspects of our construction include a novel query and answer design which makes use of a Vandermonde decomposition of Cauchy matrices, and a trade-off among message replication, security and privacy thresholds.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.