Private Information Retrieval from Coded Databases with Colluding Servers

By Ragnar Freij, Oliver Wilhelm Gnilke, Camilla Hollanti, David A. Karpuk. 2016

245 citations recorded by the source corpus.

We present a general framework for Private Information Retrieval (PIR) from arbitrary coded databases, that allows one to adjust the rate of the scheme according to the suspected number of colluding servers. If the storage code is a generalized Reed-Solomon code of length n and dimension k, we design PIR schemes which simultaneously protect against t colluding servers and provide PIR rate 1-(k+t-1)/n, for all t between 1 and n-k. This interpolates between the previously studied cases of t=1 and k=1 and asymptotically achieves the known capacity bounds in both of these cases, as the size of the database grows.

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, methodology): “Next, we refine and lift the scheme in [12].”
Private Information Retrieval From MDS Coded Data in Distributed Storage Systems (2016, methodology): “Also, schemes using GRS codes have been constructed in [27], and they conjectured that the lowest”
Private information retrieval with side information: The single server case (2017, background): “Recently, there has been a renewed interest in PIR for the case in which the data is stored on the servers using erasure codes, which result in better storage overhead compared to the traditional replication techniques [11]–[18].”
Private Computation of Systematically Encoded Data with Colluding Servers (2018, methodology): “The current contribution generalizes the star-product scheme of [5] to construct explicit PC schemes for colluding servers, coded data, and non-linear functions.”
Private Information Retrieval With Side Information (2017, background): “Recently, there has been a renewed interest in PIR for the case in which the data is stored on the servers using erasure codes, which result in better storage overhead compared to the traditional replication techniques [11]–[18].”
Robust private information retrieval on coded data (2017, background): “This has motivated recent works on PIR schemes for data stored under coded form and not just replicated [9]–[16].”
Robust Private Information Retrieval from Coded Systems with Byzantine and Colluding Servers (2018, methodology): “The scheme is an extension of previous work on PIR [13] which is based on the star product of linear codes.”
Private information retrieval in distributed storage systems using an arbitrary linear code (2016, methodology): “Our work bears some similarities to the parallel work in [10], where a PIR protocol protecting against multiple colluding nodes for any linear storage code was presented.”
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): “In [11] a private computation scheme for polynomial functions of the data over T colluding databases is constructed by generalizing the star-product PIR scheme of [8].”
Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al (2017, background): “[4] by constructing a scheme that beats the conjectured capacity for one particular instance of MDS-TPIR.”
Distributed and Private Coded Matrix Computation with Flexible Communication Load (2019, methodology): “Note that the code Cc associated with Fa(z)Fb(z) is obtained as the star product of the codes described by Fa(z) and Fb(z) [24], and therefore our proposed SGPD scheme can be interpreted as a secret sharing scheme [23] employing the star product code Cc.”