.png){kind=icon}
.png){kind=icon}
Return
Private Polynomial Function Computation for Noncolluding Coded Databases
.png){kind=icon}
OA
AI
DOI：10.1109/TIFS.2022.3166667.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider the problem of private polynomial computation (PPC) from a distributed storage system (DSS). In such setting a user wishes to compute a multivariate polynomial of degree at most g over f variables (or 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 polynomial evaluation to the databases. For a DSS setup where data is stored using linear storage codes, we derive an outer bound on the PPC rate, which is defined as the ratio of the (minimum) desired amount of information and the total amount of downloaded information, and construct two novel PPC schemes. In the first scheme, we consider Reed-Solomon coded databases with Lagrange encoding, which leverages ideas from recently proposed star-product private information retrieval and Lagrange coded computation. The second scheme considers the special case of coded databases with systematic Lagrange encoding. Both schemes yield improved rates, while asymptotically, as f -> infinity, the systematic scheme gives a significantly better computation retrieval rate compared to all known schemes up to some storage code rate that depends on the maximum degree of the candidate polynomials.
Keywords:
Coded computation
information-theoretic privacy
private computation
private information retrieval
Reed-Solomon codes
Journal
IF:
8
Papers:
5.2K
Citations:
2.3W