.png){kind=icon}
.png){kind=icon}
Return
Private Linear Computation for Noncolluding Coded Databases
.png){kind=icon}
OA
AI
DOI：10.1109/JSAC.2022.3142362.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Private computation in a distributed storage system (DSS) is a generalization of the private information retrieval (PIR) problem. In such a setting, a user wishes to compute a function of f messages stored in n noncolluding coded databases, i.e., databases storing data encoded with an [n,k] linear storage code, while revealing no information about the desired function to the databases. We consider the problem of private linear computation (PLC) for coded databases. In PLC, a user wishes to compute a linear combination over the f messages while keeping the coefficients of the desired linear combination hidden from the databases. For a DSS setup where data is stored using a code from a particular family of linear storage codes, we derive an outer bound on the PLC rate, which is defined as the ratio of the desired amount of information and the total amount of downloaded information. In particular, the proposed converse is valid for any number of messages and linear combinations, and depends on the rank of the coefficient matrix obtained from all linear combinations. Further, we present a PLC scheme with rate equal to the outer bound and hence settle the PLC capacity for the considered class of linear storage codes. Interestingly, the PLC capacity matches the maximum distance separable coded capacity of PIR for the considered class of linear storage codes.
Keywords:
Spread spectrum communication
Codes
Protocols
Distributed databases
Information retrieval
Indexes
Linear codes
Capacity
information-theoretic privacy
private computation
private information retrieval
Journal
IF:
17.2
Papers:
6.4K
Citations:
3.1W