Private information retrieval (PIR) protocols allow a user to retrieve a data item from a database without revealing any information about the identity of the item being retrieved. Specifically, in information-theoretic @math -server PIR, the database is replicated among @math non-communicating servers, and each server learns nothing about the item retrieved by the user. The cost of PIR protocols is usually measured in terms of their communication complexity, which is the total number of bits exchanged between the user and the servers, and storage overhead, which is the ratio between the total number of bits stored on all the servers and the number of bits in the database. Since single-server information-theoretic PIR is impossible, the storage overhead of all existing PIR protocols is at least @math . In this work, we show that information-theoretic PIR can be achieved with storage overhead arbitrarily close to the optimal value of @math , without sacrificing the communication complexity. Specifically, we prove that all known @math -server PIR protocols can be efficiently emulated, while preserving both privacy and communication complexity but significantly reducing the storage overhead. To this end, we distribute the @math bits of the database among @math servers, each storing @math coded bits (rather than replicas). For every fixed @math , the resulting storage overhead @math approaches @math as @math grows; explicitly we have @math . Moreover, in the special case @math , the storage overhead is only @math . In order to achieve these results, we introduce and study a new kind of binary linear codes, called here @math -server PIR codes. We then show how such codes can be constructed, and we establish several bounds on the parameters of @math -server PIR codes. Finally, we briefly discuss extensions of our results to nonbinary alphabets, to robust PIR, and to @math -private PIR.
There are several previous works which construct coded schemes for the purpose of fast or private retrieval. The first work we know of for the purpose of coded private retrieval is the recent work by @cite_23 . The authors showed how to encode files in multiple servers with very low communication complexity. However, their constructions require an exponentially large number of servers which may depend on the number of files or their size. In another recent work @cite_24 , studied the tradeoff between storage overhead and communication complexity, though only for setups in which the size of each file is relatively large. A similar approach to ours was studied by @cite_36 , where the authors also partitioned the database into several parts in order to avoid repetition and thereby reduce the storage overhead. However, their construction works only for the PIR scheme using the multiplicity codes by @cite_0 and they didn't encode the parts of the database as we study in this work.
@cite_24 @cite_0 @cite_36 @cite_23
1962818100 2161788512 2007725949
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. Since the concept of locally decodable codes was introduced by Katz and Trevisan in 2000 [11], it is well-known that information theoretically secure private information retrieval schemes can be built using locally decodable codes [15]. In this paper, we construct a Byzantine robust PIR scheme using the multiplicity codes introduced by [12]. Our main contributions are on the one hand to avoid full replication of the database on each server; this significantly reduces the global redundancy. On the other hand, to have a much lower locality in the PIR context than in the LDC context. This shows that there exists two different notions: LDC-locality and PIR-locality. This is made possible by exploiting geometric properties of multiplicity codes. Private information retrieval (PIR) systems allow a user to retrieve a record from a public database without revealing to the server which record is being retrieved. The literature on PIR considers only replication-based systems, wherein each storage node stores a copy of the entire data. However, systems based on erasure codes are gaining increasing popularity due to a variety of reasons. This paper initiates an investigation into PIR in erasure-coded systems by establishing its capacity and designing explicit codes and algorithms. The notion of privacy considered here is information-theoretic, and the metric optimized is the amount of data downloaded by the user during PIR. In this paper, we present four main results. First, we design an explicit erasure code and PIR algorithm that requires only one extra bit of download to provide perfect privacy. In contrast, all existing PIR algorithms require a download of at least twice the size of the requisite data. Second, we derive lower bounds proving the necessity of downloading at least one additional bit. This establishes the precise capacity of PIR with respect to the metric of download. These results are also applicable to PIR in replication-based systems, which are a special case of erasure codes. Our third contribution is a negative result showing that capacity-achieving codes necessitate super-linear storage overheads. This motivates the fourth contribution of this paper: an erasure code and PIR algorithm that requires a linear storage overhead, provides high reliability to the data, and is a small factor away from the capacity.