Private information retrieval in distributed storage systems using an arbitrary linear code

By Siddhartha Kumar, Eirik Rosnes, Alexandre Graell i Amat. 2016

56 citations recorded by the source corpus.

We propose an information-theoretic private information retrieval (PIR) scheme for distributed storage systems where data is stored using a linear systematic code of rate R> 1/2. The proposed scheme generalizes the PIR scheme for data stored using maximum distance separable codes recently proposed by Tajeddine and El Rouayheb for the scenario of a single spy node. We further propose an algorithm to optimize the communication price of privacy (cPoP) using the structure of the underlying linear code. As an example, we apply the proposed algorithm to several distributed storage codes, showing that the cPoP can be significantly reduced by exploiting the structure of the distributed storage code.

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): “PIR schemes for general linear codes, not necessarily MDS, were studied in [13].”
Private Information Retrieval From MDS Coded Data in Distributed Storage Systems (2016, background): “In [30], PIR schemes for any arbitrary code were discussed.”
Private Information Retrieval from Coded Databases with Colluding Servers (2016, background): “R e d i s t r i bu ti on s ub j ec t t o S I A M li ce n s e o r c opy r i gh t; s ee h tt p :// www . s i a m . o r g /j ou r n a l s / o j s a . php has been studied in [7].”
Robust Private Information Retrieval from Coded Systems with Byzantine and Colluding Servers (2018, background): “PIR schemes on arbitrary linear storage codes were constructed in [14].”
Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al (2017, background): “The lack of any non-trivial outer bounds for MDS-TPIR is also recently highlighted in [6].”