2019/07/01 by Swanand Kadhe, Anoosheh Heidarzadeh, Kadhe, Swanand +5
Computer Science · #Advanced Data Storage Technologies #Cooperative Communication and Network Coding #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1907.00598
openalex publication_date 2019/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Private Information Retrieval (PIR) problem has recently attracted a\nsignificant interest in the information-theory community. In this problem, a\nuser wants to privately download one or more messages belonging to a database\nwith copies stored on a single or multiple remote servers. In the single server\nscenario, the user must have prior side information, i.e., a subset of messages\nunknown to the server, to be able to privately retrieve the required messages\nin an efficient way.\n In the last decade, there has also been a significant interest in Locally\nRecoverable Codes (LRC), a class of storage codes in which each symbol can be\nrecovered from a limited number of other symbols. More recently, there is an\ninterest in 'cooperative' locally recoverable codes, i.e., codes in which\nmultiple symbols can be recovered from a small set of other code symbols.\n In this paper, we establish a relationship between coding schemes for the\nsingle-server PIR problem and LRCs. In particular, we show the following\nresults: (i) PIR schemes designed for retrieving a single message are\nequivalent to classical LRCs; and (ii) PIR schemes for retrieving multiple\nmessages are equivalent to cooperative LRCs. These equivalence results allow us\nto recover upper bounds on the download rate for PIR-SI schemes, and to obtain\na novel rate upper bound on cooperative LRCs. We show results for both linear\nand non-linear codes.\n