The Capacity of Private Information Retrieval
By Hua Sun, Syed Ali Jafar. 2016
454 citations recorded by the source corpus.
In the private information retrieval (PIR) problem a user wishes to retrieve, as efficiently as possible, one out of K messages from N non-communicating databases (each holds all K messages) while revealing nothing about the identity of the desired message index to any individual database. The information theoretic capacity of PIR is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. For K messages and N databases, we show that the PIR capacity is (1 + 1/N + 1/N^2 + · · · + 1/N({K−1})^{−1}. A remarkable feature of the capacity achieving scheme is that if it is projected onto any subset of messages by eliminating the remaining messages, it also achieves the PIR capacity for that subset of messages.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications, Privacy & Security, Information Theory
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
- Salim el Rouayheb
- David A. Karpuk
- Hua Sun
- Syed Ali Jafar
- Razane Tajeddine
- Sennur Ulukus
- Karim A. Banawan
- Wei-Ting Chang
In Computational Theory and Mathematics
- Sennur Ulukus
- Karim A. Banawan
- Salim el Rouayheb
- David A. Karpuk
- Hua Sun
- Syed Ali Jafar
- Oliver Wilhelm Gnilke
- Camilla Hollanti
In Computer Networks and Communications
- Salim el Rouayheb
- Syed Ali Jafar
- David A. Karpuk
- Hua Sun
- Razane Tajeddine
- Sennur Ulukus
- Karim A. Banawan
- Rafael G. L. D'Oliveira
In Privacy & Security
- Salim el Rouayheb
- Hua Sun
- Syed Ali Jafar
- Sennur Ulukus
- Karim A. Banawan
- Razane Tajeddine
- David A. Karpuk
- Ravi Tandon
In Information Theory
- Salim el Rouayheb
- Hua Sun
- Syed Ali Jafar
- David A. Karpuk
- Razane Tajeddine
- Sennur Ulukus
- Karim A. Banawan
- Ravi Tandon
Citations in the corpus
- On the Upload versus Download Cost for Secure and Private Matrix Multiplication (2019, background): “In particular, starting from the work of [13], private information retrieval (PIR) has been studied extensively within an information theoretic framework (such as PIR from coded databses [14] and private computation [15]–[18]).”
- Lifting Private Information Retrieval from Two to any Number of Messages (2018, background): “It was shown in [4] and [5] that the PIR capacity is (1+T/N+T (2)/N(2)+· · ·+TM−1/NM−1)−1, where N is the number of servers, T is the number of colluding”
- The Capacity of Private Information Retrieval From Coded Databases (2016, methodology): “The achievable scheme is similar to the scheme in [7] with extra steps that entail decoding of the interference and the desired message by solving K linearly independent equations.”
- Private Information Retrieval From MDS Coded Data in Distributed Storage Systems (2016, background): “Following this work in [1] and [23], the lowest achievable price of privacy for repetition code on n nodes having m files and b colluding nodes was found in [24] and [25] to be 1−(b/n) m 1−(b/n) and that of an (n, k)-code was found in [26] to be 1−(k/n) m 1−(k/n) .”
- 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 With Side Information (2017, methodology): “Our scheme for the multiple servers uses ideas from the single server scheme in conjunction with the no-side-information scheme of Sun and Jafar in [5].”
- The Capacity of Robust Private Information Retrieval With Colluding Databases (2016, methodology): “A more detailed treatment can be found in [25].”
- Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al (2017, background): “The capacity of PIR was shown in [1] to be”
- The Capacity of Private Information Retrieval from Byzantine and Colluding Databases (2017, background): “Recently, the PIR problem is revisited by information theorists [6]–[9].”
- The Capacity of Private Computation (2017, methodology): “For ease of reference, let us denote the original PIR scheme of [1] as PIR1 .”
- Private Information Retrieval from MDS Coded Data With Colluding Servers: Settling a Conjecture by Freij-Hollanti et al. (2018, background): “Next, let us consider the pairwise overlap between V[2] 2i and V[2] 2 j , i < j, i, j ∈ [1 : 4].”
- Robust private information retrieval on coded data (2017, background): “Related work: Until recently, most of the work on PIR has focused on replicated data and minimizing the total download cost [4]–[8], [20]–[22].”
- Private Information Retrieval from Coded Databases with Colluding Servers (2016, background): “The maximum possible rate of a PIR scheme for a replicated storage system was derived in [14] without collusion, and in [15] with colluding servers.”
- Private function retrieval (2017, background): “Among these, we can name the distributed storage systems [1], distributed cache networks [2], private information retrieval (PIR) [3]–[5], and distributed computing [6], [7].”