The problem of providing privacy, in the private information retrieval (PIR) sense, to users requesting data from a distributed storage system (DSS), is considered. The DSS is coded by an (n, k, d) Maximum Distance Separable (MDS) code to store the data reliably on unreliable storage nodes. Some of these nodes can be spies which report to a third party, such as an oppressive regime, which data is being requested by the user. An information theoretic PIR scheme ensures that a user can satisfy its request while revealing no information on which data is being requested to the nodes. A user can trivially achieve PIR by downloading all the data in the DSS. However, this is not a feasible solution due to its high communication cost. We construct PIR schemes with low download communication cost. When there is b = 1 spy node in the DSS, in other words, no collusion between the nodes, we construct PIR schemes with download cost 1/1–R per unit of requested data (R = k/n is the code rate), achieving the information theoretic limit for linear schemes. The proposed schemes are universal since they depend on the code rate, but not on the generator matrix of the code. Also, if b ≤ n — δk nodes collude, with δ = b ⌊ n—b/k ⌋, we construct linear PIR schemes with download cost b+δk/δ .

The problem of Private Information Retrieval (PIR) from coded storage systems with colluding, Byzantine, and unresponsive servers is considered. An explicit scheme using an [n,k] Reed-Solomon storage code is designed, protecting against t-collusion and handling up to b Byzantine and r unresponsive servers, when n > k+t+2b+r–1. This scheme achieves a PIR rate of n–r–(k+2b+t–1)/n–r . In the case where the capacity is known, namely when k = 1, it is asymptotically capacity-achieving as the number of files grows. Lastly, the scheme is adapted to symmetric PIR.

In Private Information Retrieval (PIR), one wants to download a file from a database without revealing to the database which file is being downloaded. Much attention has been paid to the case of the database being encoded across several servers, subsets of which can collude to attempt to deduce the requested file. With the goal of studying the achievable PIR rates in realistic scenarios, we generalize results for coded data from the case of all subsets of servers of size t colluding, to arbitrary subsets of the servers. We investigate the effectiveness of previous strategies in this new scenario, and present new results in the case where the servers are partitioned into disjoint colluding groups.

We consider the problem of designing PIR scheme on coded data when certain nodes are unresponsive. We provide the construction of ν-robust PIR schemes that can tolerate up to ν unresponsive nodes. These schemes are adaptive and universally optimal in the sense of achieving (asymptotically) optimal download cost for any number of unresponsive nodes up to ν.

In this paper, the problem of providing privacy to users requesting data over a network from a distributed storage system (DSS) is considered. The DSS, which is considered as the multi-terminal destination of the network from the user’s perspective, is encoded by a maximum rank distance (MRD) code to store the data on these multiple servers. A private information retrieval (PIR) scheme ensures that a user can request a file without revealing any information on which file is being requested to any of the servers. In this paper, a novel PIR scheme is proposed, allowing the user to recover a file from a storage system with low communication cost, while allowing some servers in the system to collude in the quest of revealing the identity of the requested file. The network is modeled as a random linear network, i.e., all nodes of the network forward random (unknown) linear combinations of incoming packets. Both error-free and erroneous random linear networks are considered.

A private information retrieval (PIR) scheme on coded storage systems with colluding, byzantine, and non-responsive servers is presented. Furthermore, the scheme can also be used for symmetric PIR in the same setting. An explicit scheme using an [n, k] generalized Reed-Solomon storage code is designed, protecting against t-collusion and handling up to b byzantine and r non-responsive servers, when n ≥ n ^1' =(ν+1)k+t+2b+r-1, for some integer ν ≥ 1. This scheme achieves a PIR rate of 1-[(k+2b+t+r-1)/(n ^' -r)]. In the case where the capacity is known, namely when k=1, it is asymptotically capacity achieving as the number of files grows.