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

  1. Salim el Rouayheb
  2. David A. Karpuk
  3. Hua Sun
  4. Syed Ali Jafar
  5. Razane Tajeddine
  6. Sennur Ulukus
  7. Karim A. Banawan
  8. Wei-Ting Chang

In Computer Networks and Communications

  1. Salim el Rouayheb
  2. Syed Ali Jafar
  3. David A. Karpuk
  4. Hua Sun
  5. Razane Tajeddine
  6. Sennur Ulukus
  7. Karim A. Banawan
  8. Rawad Bitar

In Privacy & Security

  1. Salim el Rouayheb
  2. Hua Sun
  3. Syed Ali Jafar
  4. Sennur Ulukus
  5. Karim A. Banawan
  6. Razane Tajeddine
  7. David A. Karpuk
  8. Ravi Tandon

In Information Theory

  1. Salim el Rouayheb
  2. Hua Sun
  3. Syed Ali Jafar
  4. David A. Karpuk
  5. Razane Tajeddine
  6. Sennur Ulukus
  7. Karim A. Banawan
  8. Ravi Tandon

Citations in the corpus