Private Information Retrieval for Coded Storage

Abstract

Private information retrieval scheme for coded data storage is considered in this paper. We focus on the case where the size of each data record is large and hence only the download cost (but not the upload cost for transmitting retrieval queries) is of interest. We prove that the tradeoff between storage cost and retrieval/download cost depends on the number of data records in the system. We also propose a fairly general class of linear storage codes and retrieval schemes and derive conditions under which our retrieval schemes are error-free and private. Tradeoffs between the storage cost and retrieval costs are also obtained. Finally, we consider special cases when the underlying storage code is based on an MDS code. Using our proposed method, we show that a randomly generated retrieval scheme is indeed very likely to be private and error-free.

submitted to IEEE Journal of Selected Topics in Signal Processing

Cited by in corpus (5)

• Private Information Retrieval from MDS Coded Data in Distributed Storage Systems
• Achievable Rate of Private Function Retrieval from MDS Coded Databases
• Capacity of Private Linear Computation for Coded Databases
• Double Blind $T$-Private Information Retrieval
• Capacity of Quantum Private Information Retrieval with Collusion of All But One of Servers