The Capacity of Robust Private Information Retrieval With Colluding Databases

By Hua Sun, Syed Ali Jafar. 2016

329 citations recorded by the source corpus.

Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> messages from <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> non-communicating replicated databases (each holds all <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> messages) while keeping the identity of the desired message index a secret from each individual database. The information theoretic capacity of PIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. <inline-formula> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula>-private PIR is a generalization of PIR to include the requirement that even if any <inline-formula> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> of the <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> databases collude, the identity of the retrieved message remains completely unknown to them. Robust PIR is another generalization that refers to the scenario where we have <inline-formula> <tex-math notation="LaTeX">$M \geq N$ </tex-math></inline-formula> databases, out of which any <inline-formula> <tex-math notation="LaTeX">$M - N$ </tex-math></inline-formula> may fail to respond. For <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> messages and <inline-formula> <tex-math notation="LaTeX">$M\geq N$ </tex-math></inline-formula> databases out of which at least some <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> must respond, we show that the capacity of <inline-formula> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula>-private and Robust PIR is <inline-formula> <tex-math notation="LaTeX">$(1+T/N+T^{2}/N^{2}+\cdots +T^{K-1}/N^{K-1})^{-1}$ </tex-math></inline-formula>. The result includes as special cases the capacity of PIR without robustness (<inline-formula> <tex-math notation="LaTeX">$M=N$ </tex-math></inline-formula>) or <inline-formula> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula>-privacy constraints (<inline-formula> <tex-math notation="LaTeX">$T=1$ </tex-math></inline-formula>).

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

Staircase-PIR: Universally Robust Private Information Retrieval (2018, background): “Given the increasing size of stored files, the recent body of work measures the communication cost by the amount of information downloaded by the user, assuming the queries are too small compared to the downloaded files [12], [17]– [23] which is the assumption we adopt in this paper.”
The Capacity of Private Information Retrieval From Coded Databases (2016, background): “Reference [10] extends this setting to the case of T colluding databases with and without node failures.”
The Capacity of Private Information Retrieval from Byzantine and Colluding Databases (2017, methodology): “The remaining set of databases ¯ B = { 1 , · · · , N } \ B respond truthfully to the user, i.e., the answer strings of ¯ B are a deterministic function of the queries and the correct contents of the databases W , We consider a T -privacy constraint as in the TPIR problem in [11], where any T databas”
Private Information Retrieval With Side Information (2017, background): “Information-theoretic bounds on the download rate (servers’ responses) and achievable schemes were devised in [9] and [10].”
Private Information Retrieval from Coded Databases with Colluding Servers (2016, methodology): “It is known by [15] that the capacity for PIR in this case is 1−t/n 1−(t/n)m .”
Private Information Retrieval from MDS Coded Data With Colluding Servers: Settling a Conjecture by Freij-Hollanti et al. (2018, background): “18The proof follows from that in [3] by noting that all definitions for the TPIR problem are satisfied.”
Private Computation of Systematically Encoded Data with Colluding Servers (2018, background): “The capacity of PIR for data replicated over several servers was obtained in [2], for replicated data with colluding servers in [3], and for MDS-coded data without server collusion in [4].”
Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al (2017, background): “The capacity of TPIR (Kc = 1) was shown in [2] to be”
Private function retrieval (2017, background): “Several extensions of PIR problem have been studied in literature, including the PIR with colluding servers [8], [9], the PIR with coded servers [10], and the symmetric PIR [11], [12].”