Private Information Retrieval From MDS Coded Data in Distributed Storage Systems

By Razane Tajeddine, Oliver Wilhelm Gnilke, Salim el Rouayheb. 2016

234 citations recorded by the source corpus.

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 <inline-formula> <tex-math notation="LaTeX">$(n,k,d)$ </tex-math></inline-formula> maximum distance separable 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 <inline-formula> <tex-math notation="LaTeX">$b=1$ </tex-math></inline-formula> spy node in the DSS, in other words, no collusion between the nodes, we construct PIR schemes with download cost <inline-formula> <tex-math notation="LaTeX">$\frac {1}{1-R}$ </tex-math></inline-formula> per unit of requested data (<inline-formula> <tex-math notation="LaTeX">$R=k/n$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$b\leq n-\delta k$ </tex-math></inline-formula> nodes collude, with <inline-formula> <tex-math notation="LaTeX">$\delta =\lfloor {\frac {n-b}{k}}\rfloor $ </tex-math></inline-formula>, we construct linear PIR schemes with download cost <inline-formula> <tex-math notation="LaTeX">$\frac {b+\delta k}{\delta }$ </tex-math></inline-formula>.

Subfields: Artificial Intelligence, Computer Networks and Communications, Privacy & Security

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

In Privacy & Security

Citations in the corpus

Lifting Private Information Retrieval from Two to any Number of Messages (2018, methodology): “We first refine and lift the scheme in [11].”
The Capacity of Private Information Retrieval From Coded Databases (2016, methodology): “Intuitively, as the number of messages increases, the undesired download rate must increase to hide the identity of the desired message; eventually, the gain from applying the greedy algorithm in Section IV over the scheme in [5] diminishes.”
Robust Private Information Retrieval from Coded Systems with Byzantine and Colluding Servers (2018, methodology): “For the case of colluding servers, the authors in [13] constructed a new family of PIR schemes on MDS coded data achieving a lower download cost than the ones in [12].”
Private information retrieval in distributed storage systems using an arbitrary linear code (2016, methodology): “Recently, the authors in [7] proposed a coded PIR protocol for DSSs that use an (n, k) maximum distance separable (MDS) code for storing data on n storage nodes.”
Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al (2017, methodology): “The capacity achieving scheme of Banawan and Ulukus [3] improved upon a scheme proposed earlier by Tajeddine and Rouayheb in [5].”
The Capacity of Private Information Retrieval from Byzantine and Colluding Databases (2017, background): “some databases fail to respond to the user; symmetric PIR (SPIR) [12], where the privacy of the remaining messages should be maintained against the user in addition to the usual user’s privacy; MDS-coded PIR (CPIR) [8], [13], where the contents of the databases are not replicated, but coded via an (”
Achievable Rate of Private Function Retrieval from MDS Coded Databases (2018, methodology): “Achievable schemes for MDS coded PIR have been presented in [6], [7] This work is supported by NSF grant CNS-1526547. and the capacity has been established in [8].”
Robust private information retrieval on coded data (2017, methodology): “TABLE II: First subquery, in the non-robust PIR scheme in [11] (no collusion), assuming the user wants file Xf .”
The Capacity of Robust Private Information Retrieval With Colluding Databases (2016, background): “There is also much recent work in the distributed storage setting [24], [32]–[34] (the databases form a distributed”
Private Information Retrieval from Coded Databases with Colluding Servers (2016, unknown): “In [16], two PIR schemes were presented for arbitrary [n, k, d]-MDS codes, one of which had rate 1n and protected against t = n − k colluding servers, and the other of which had rate n−k n and t = 1.”
Private Information Retrieval With Side Information (2017, unknown): “, [9]–[13]).”