The Capacity of Private Information Retrieval From Coded Databases
By Karim A. Banawan, Sennur Ulukus. 2016
362 citations recorded by the source corpus.
We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> non-colluding databases, each storing an MDS-coded version of <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math></inline-formula> messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is <inline-formula> <tex-math notation="LaTeX">$C=(1+{K}/{N}+{K^{2}}/{N^{2}}+\cdots +{K^{M-1}}/{N^{M-1}})^{-1}=(1+R_{c}+R_{c}^{2}+\cdots +R_{c}^{M-1})^{-1}=({1-R_{c}})/({1-R_{c}^{M}})$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$R_{c}$ </tex-math></inline-formula> is the rate of the <inline-formula> <tex-math notation="LaTeX">$(N,K)$ </tex-math></inline-formula> MDS code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost when the storage code is restricted to the class of MDS codes. The result generalizes the achievability and converse results for the classical PIR with replicated databases to the case of MDS-coded databases.
Subfields: Artificial Intelligence, 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 Computer Networks and Communications
- Salim el Rouayheb
- Syed Ali Jafar
- David A. Karpuk
- Hua Sun
- Razane Tajeddine
- Sennur Ulukus
- Karim A. Banawan
- Rawad Bitar
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, methodology): “Phase 2 (Private Download): We use a similar downloading technique that was proposed in [14].”
- ON-OFF Privacy with Correlated Requests (2019, neutral): “[5]–[9]).”
- Staircase-PIR: Universally Robust Private Information Retrieval (2018, background): “, [12], [22]–[28] and the capacity of robust PIR schemes under download cost was characterized in [12], [22], [23] for replicated data.”
- Robust Private Information Retrieval from Coded Systems with Byzantine and Colluding Servers (2018, methodology): “When the data is coded using an [n, k] MDS code, it was shown in [10] that the asymptotic capacity is 1 − k n .”
- Private Information Retrieval from Coded Databases with Colluding Servers (2016, background): “Let us describe the distributed storage systems we consider; this setup follows that of [16, 1].”
- The Capacity of Private Information Retrieval from Byzantine and Colluding Databases (2017, methodology): “This is without loss of generality, since any asymmetric PIR scheme can be made symmetric by proper time sharing without changing the retrieval rate [9], [13], [14], i.”
- Private Information Retrieval from MDS Coded Data With Colluding Servers: Settling a Conjecture by Freij-Hollanti et al. (2018, methodology): “For code rate 1, it is shown by Banawan and Ulukus [6] that the capacity of PIR is 1/K , i.”
- 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].”
- 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, methodology): “The capacity achieving scheme of Banawan and Ulukus [5] improved upon a scheme proposed earlier by Tajeddine and Rouayheb in [7].”
- 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 [12]–[19].”
- Robust private information retrieval on coded data (2017, methodology): “The cPoP of the scheme if one node is unresponsive is 12 × 1 6 = 2 which is the same as the optimal cPoP found in [13].”