Private Linear Computation for Noncolluding Coded Databases

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

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)847-861
Number of pages15
JournalIEEE Journal on Selected Areas in Communications
Volume40
Issue number3
DOIs
StatePublished - Mar 1 2022

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Keywords

  • Capacity
  • information-theoretic privacy
  • private computation
  • private information retrieval

Fingerprint

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

Cite this