Private information retrieval for coded storage

By T. Chan, Siu-Wai Ho, Hirosuke Yamamoto. 2014

162 citations recorded by the source corpus.

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 propose a class of linear storage codes and retrieval schemes, and derive conditions under which our schemes are error-free and private. Tradeoffs between the storage cost and retrieval costs are also obtained.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Lifting Private Information Retrieval from Two to any Number of Messages (2018, background): “In [10], the authors derived bounds on the tradeoff between storage cost and download cost for linear coded data and studied properties of PIR schemes on MDS data.”
The Capacity of Private Information Retrieval From Coded Databases (2016, methodology): “The information-theoretic reformulation of the problem assumes that the messages are of arbitrarily large size and hence the upload cost can be neglected with respect to the download cost [6].”
The Capacity of Private Information Retrieval (2016, background): “However, for the classical Shannon theoretic formulation, where message size is allowed to be arbitrarily large, the upload cost is negligible compared to the download cost [28]2.”
Robust Private Information Retrieval from Coded Systems with Byzantine and Colluding Servers (2018, background): “In [9], the authors derive bounds on the tradeoff between storage cost and download cost for linearly coded data.”
Private information retrieval in distributed storage systems using an arbitrary linear code (2016, methodology): “PIR protocols for DSSs, where data is stored using codes from two explicit linear code constructions (one protocol for ea ch code construction), were presented in [7], and information theoretic lower bounds on the tradeoff between the storage cost and the retrieval cost were provided in [8].”
Robust private information retrieval on coded data (2017, methodology): “In [10], the authors derive bounds on the tradeoff between storage cost and download cost for linear coded data.”
The Capacity of Robust Private Information Retrieval With Colluding Databases (2016, background): “What is pursued in this work is the traditional Shannon theoretic formulation, where message size is allowed to be arbitrarily large, and therefore the upload cost is negligible compared to the download cost [20], [24].”
The Capacity of Private Information Retrieval from Byzantine and Colluding Databases (2017, methodology): “In this paper, we follow the information-theoretic assumptions of large enough message size, large enough field size, and ignore the upload cost as in [7], [11], and [13].”
Achievable Rate of Private Function Retrieval from MDS Coded Databases (2018, background): “Achievable schemes for MDS coded PIR have been presented in [6]–[8] and the capacity has been established in [9].”