Private Polynomial Function Computation for Noncolluding Coded Databases

Sarah A. Obead, Hsuan Yin Lin, Eirik Rosnes, Jorg Kliewer

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 frightarrow infty , 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.

Original languageEnglish (US)
Pages (from-to)1800-1813
Number of pages14
JournalIEEE Transactions on Information Forensics and Security
StatePublished - 2022

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications


  • Coded computation
  • Reed-Solomon codes
  • information-theoretic privacy
  • private computation
  • private information retrieval


Dive into the research topics of 'Private Polynomial Function Computation for Noncolluding Coded Databases'. Together they form a unique fingerprint.

Cite this