Private Polynomial Function Computation for Noncolluding Coded Databases

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.

Automated summary

This paper investigates the problem of private polynomial computation in a distributed storage system. Two novel computation schemes are proposed, leveraging Lagrange encoding and linear storage codes. The systematic scheme shows significantly better computation retrieval rate in asymptotic scenarios.