Capacity of Private Linear Computation for Coded Databases

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

We consider the problem of private linear computation (PLC) in a distributed storage system. In PLC, a user wishes to compute a linear combination of f messages stored in noncolluding databases while revealing no information about the coefficients of the desired linear combination to the databases. In extension of our previous work we employ linear codes to encode the information on the databases. We show that the PLC capacity, which is the ratio of the desired linear function size and the total amount of downloaded information, matches the maximum distance separable (MDS) coded capacity of private information retrieval for a large class of linear codes that includes MDS codes. In particular, the proposed converse is valid for any number of messages and linear combinations, and the capacity expression depends on the rank of the coefficient matrix obtained from all linear combinations.

Original languageEnglish (US)
Title of host publication2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages813-820
Number of pages8
ISBN (Electronic)9781538665961
DOIs
StatePublished - Feb 5 2019
Event56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018 - Monticello, United States
Duration: Oct 2 2018Oct 5 2018

Publication series

Name2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018

Conference

Conference56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
CountryUnited States
CityMonticello
Period10/2/1810/5/18

Fingerprint

Linear Combination
Linear Codes
Private Information Retrieval
Information retrieval
Storage System
Coefficient
Converse
Linear Function
Distributed Systems
Valid

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Signal Processing
  • Energy Engineering and Power Technology
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Obead, S. A., Lin, H. Y., Rosnes, E., & Kliewer, J. (2019). Capacity of Private Linear Computation for Coded Databases. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018 (pp. 813-820). [8636039] (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ALLERTON.2018.8636039
Obead, Sarah A. ; Lin, Hsuan Yin ; Rosnes, Eirik ; Kliewer, Joerg. / Capacity of Private Linear Computation for Coded Databases. 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 813-820 (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018).
@inproceedings{552793718b4f4a32b44dda1bc08df77e,
title = "Capacity of Private Linear Computation for Coded Databases",
abstract = "We consider the problem of private linear computation (PLC) in a distributed storage system. In PLC, a user wishes to compute a linear combination of f messages stored in noncolluding databases while revealing no information about the coefficients of the desired linear combination to the databases. In extension of our previous work we employ linear codes to encode the information on the databases. We show that the PLC capacity, which is the ratio of the desired linear function size and the total amount of downloaded information, matches the maximum distance separable (MDS) coded capacity of private information retrieval for a large class of linear codes that includes MDS codes. In particular, the proposed converse is valid for any number of messages and linear combinations, and the capacity expression depends on the rank of the coefficient matrix obtained from all linear combinations.",
author = "Obead, {Sarah A.} and Lin, {Hsuan Yin} and Eirik Rosnes and Joerg Kliewer",
year = "2019",
month = "2",
day = "5",
doi = "https://doi.org/10.1109/ALLERTON.2018.8636039",
language = "English (US)",
series = "2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "813--820",
booktitle = "2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018",
address = "United States",

}

Obead, SA, Lin, HY, Rosnes, E & Kliewer, J 2019, Capacity of Private Linear Computation for Coded Databases. in 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018., 8636039, 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018, Institute of Electrical and Electronics Engineers Inc., pp. 813-820, 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018, Monticello, United States, 10/2/18. https://doi.org/10.1109/ALLERTON.2018.8636039

Capacity of Private Linear Computation for Coded Databases. / Obead, Sarah A.; Lin, Hsuan Yin; Rosnes, Eirik; Kliewer, Joerg.

2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018. Institute of Electrical and Electronics Engineers Inc., 2019. p. 813-820 8636039 (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Capacity of Private Linear Computation for Coded Databases

AU - Obead, Sarah A.

AU - Lin, Hsuan Yin

AU - Rosnes, Eirik

AU - Kliewer, Joerg

PY - 2019/2/5

Y1 - 2019/2/5

N2 - We consider the problem of private linear computation (PLC) in a distributed storage system. In PLC, a user wishes to compute a linear combination of f messages stored in noncolluding databases while revealing no information about the coefficients of the desired linear combination to the databases. In extension of our previous work we employ linear codes to encode the information on the databases. We show that the PLC capacity, which is the ratio of the desired linear function size and the total amount of downloaded information, matches the maximum distance separable (MDS) coded capacity of private information retrieval for a large class of linear codes that includes MDS codes. In particular, the proposed converse is valid for any number of messages and linear combinations, and the capacity expression depends on the rank of the coefficient matrix obtained from all linear combinations.

AB - We consider the problem of private linear computation (PLC) in a distributed storage system. In PLC, a user wishes to compute a linear combination of f messages stored in noncolluding databases while revealing no information about the coefficients of the desired linear combination to the databases. In extension of our previous work we employ linear codes to encode the information on the databases. We show that the PLC capacity, which is the ratio of the desired linear function size and the total amount of downloaded information, matches the maximum distance separable (MDS) coded capacity of private information retrieval for a large class of linear codes that includes MDS codes. In particular, the proposed converse is valid for any number of messages and linear combinations, and the capacity expression depends on the rank of the coefficient matrix obtained from all linear combinations.

UR - http://www.scopus.com/inward/record.url?scp=85062882766&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85062882766&partnerID=8YFLogxK

U2 - https://doi.org/10.1109/ALLERTON.2018.8636039

DO - https://doi.org/10.1109/ALLERTON.2018.8636039

M3 - Conference contribution

T3 - 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018

SP - 813

EP - 820

BT - 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Obead SA, Lin HY, Rosnes E, Kliewer J. Capacity of Private Linear Computation for Coded Databases. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018. Institute of Electrical and Electronics Engineers Inc. 2019. p. 813-820. 8636039. (2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018). https://doi.org/10.1109/ALLERTON.2018.8636039