A private information retrieval (PIR) scheme allows a user to retrieve a file from a database without revealing any information on the file being requested. As of now, PIR schemes have been proposed for several kinds of storage systems, including replicated and MDS-coded systems. However, the problem of constructing PIR schemes on regenerating codes has been sparsely considered. A regenerating code is a storage code whose codewords are distributed among nodes, enabling efficient storage of files, as well as low-bandwidth retrieval of files and repair of nodes. Minimum-bandwidth regenerating (MBR) codes define a family of regenerating codes allowing a node repair with optimal bandwidth. Rashmi, Shah, and Kumar obtained a large family of MBR codes using the product-matrix (PM) construction. In this work, a new PIR scheme over PM-MBR codes is designed. The inherent redundancy of the PM structure is used to reduce the download communication complexity of the scheme. A lower bound on the PIR capacity of MBR-coded PIR schemes is derived, showing an interesting storage space vs. PIR rate trade-off compared to existing PIR schemes with the same reconstruction capability. The present scheme also outperforms a recent PM-MBR PIR construction of Dorkson and Ng.

Low degree Reed-Muller codes are known to satisfy local decoding properties which find applications in private information retrieval (PIR) protocols, for instance. However, their practical instantiation encounters a first barrier due to their poor information rate in the low degree regime. This lead the community to design codes with similar local properties but larger dimension, namely the lifted Reed-Solomon codes. However, a second practical barrier appears when one requires that the PIR protocol resists collusions of servers. In this paper, we propose a solution to this problem by considering \emph{weighted} Reed-Muller codes. We prove that such codes allow us to build PIR protocols with optimal computation complexity and resisting to a small number of colluding servers. In order to improve the dimension of the codes, we then introduce an analogue of the lifting process for weigthed degrees. With a careful analysis of their degree sets, we notably show that the weighted lifting of Reed-Solomon codes produces families of codes with remarkable asymptotic parameters.

Private information retrieval (PIR) protocols allow a user to retrieve entries of a database without revealing the index of the desired item. Information-theoretical privacy can be achieved by the use of several servers and specific retrieval algorithms. Most known PIR protocols focus on decreasing the number of bits exchanged between the client and the server(s) during the retrieval process. On another side, Fazeli et al. introduced so-called PIR codes in order to reduce the storage overhead on the servers. However, few works address the issue of the computation complexity of the servers. In this paper, we show that a specific encoding of the database yields PIR protocols with reasonable communication complexity, low storage overhead, and optimal computational complexity for the servers. This encoding is based on incidence matrices of transversal designs, from which a natural and efficient recovering algorithm is derived. We also present several instances for our construction, which make use of finite geometries and orthogonal arrays. We finally give a generalization of our main construction in order to resist collusions of servers.

Proofs of retrievability (PoR) are probabilistic protocols which ensure that a client can recover a file he previously stored on a server. Good PoRs aim at reaching an efficient tradeoff between communication complexity and storage overhead, and should be usable an unlimited number of times. We present a new unbounded-use PoR construction based on a class of locally decodable codes, namely the lifted codes of Guo et. al.. Our protocols feature sublinear communication complexity and very low storage overhead. Moreover, the various parameters can be tuned so as to minimize the communication complexity (resp. the storage overhead) according to the setting of concern.