TY - GEN
T1 - On an Equivalence between Single-Server PIR with Side Information and Locally Recoverable Codes
AU - Kadhe, Swanand
AU - Heidarzadeh, Anoosheh
AU - Sprintson, Alex
AU - Koyluoglu, O. Ozan
N1 - Funding Information:
This material is based upon work supported while Alex Sprintson was serving at the National Science Foundation. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.
Funding Information:
This work is supported in part by National Science Foundation grants CCF-1748585 and CNS-1748692.
Publisher Copyright:
© 2019 IEEE.
PY - 2019/8
Y1 - 2019/8
N2 - Private Information Retrieval (PIR) problem has recently attracted a significant interest in the information-theory community. In this problem, a user wants to privately download one or more messages belonging to a database with copies stored on a single or multiple remote servers. In the single server scenario, the user must have prior side information, i.e., a subset of messages unknown to the server, to be able to privately retrieve the required messages in an efficient way.In the last decade, there has also been a significant interest in Locally Recoverable Codes (LRCs), a class of storage codes in which each symbol can be recovered from a limited number of other symbols. More recently, there is an interest in cooperative locally recoverable codes, i.e., codes in which multiple symbols can be recovered from a small set of other code symbols.In this paper, we establish a relationship between coding schemes for the single-server PIR problem and LRCs. In particular, we show the following results: (i) PIR schemes designed for retrieving a single message are equivalent to classical LRCs; and (ii) PIR schemes for retrieving multiple messages are equivalent to cooperative LRCs. These equivalence results allow us to recover upper bounds on the download rate for PIR-SI schemes, and to obtain a novel rate upper bound on cooperative LRCs. We show results for both linear and non-linear codes.
AB - Private Information Retrieval (PIR) problem has recently attracted a significant interest in the information-theory community. In this problem, a user wants to privately download one or more messages belonging to a database with copies stored on a single or multiple remote servers. In the single server scenario, the user must have prior side information, i.e., a subset of messages unknown to the server, to be able to privately retrieve the required messages in an efficient way.In the last decade, there has also been a significant interest in Locally Recoverable Codes (LRCs), a class of storage codes in which each symbol can be recovered from a limited number of other symbols. More recently, there is an interest in cooperative locally recoverable codes, i.e., codes in which multiple symbols can be recovered from a small set of other code symbols.In this paper, we establish a relationship between coding schemes for the single-server PIR problem and LRCs. In particular, we show the following results: (i) PIR schemes designed for retrieving a single message are equivalent to classical LRCs; and (ii) PIR schemes for retrieving multiple messages are equivalent to cooperative LRCs. These equivalence results allow us to recover upper bounds on the download rate for PIR-SI schemes, and to obtain a novel rate upper bound on cooperative LRCs. We show results for both linear and non-linear codes.
UR - http://www.scopus.com/inward/record.url?scp=85081107561&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85081107561&partnerID=8YFLogxK
U2 - 10.1109/ITW44776.2019.8988956
DO - 10.1109/ITW44776.2019.8988956
M3 - Conference contribution
AN - SCOPUS:85081107561
T3 - 2019 IEEE Information Theory Workshop, ITW 2019
BT - 2019 IEEE Information Theory Workshop, ITW 2019
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2019 IEEE Information Theory Workshop, ITW 2019
Y2 - 25 August 2019 through 28 August 2019
ER -