TY - GEN
T1 - Capacity of Private Linear Computation for Coded Databases
AU - Obead, Sarah A.
AU - Lin, Hsuan Yin
AU - Rosnes, Eirik
AU - Kliewer, Jorg
N1 - Publisher Copyright:
© 2018 IEEE.
PY - 2018/7/2
Y1 - 2018/7/2
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 - 10.1109/ALLERTON.2018.8636039
DO - 10.1109/ALLERTON.2018.8636039
M3 - Conference contribution
AN - SCOPUS:85062882766
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.
T2 - 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
Y2 - 2 October 2018 through 5 October 2018
ER -