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

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

  1. Sennur Ulukus
  2. Karim A. Banawan
  3. Salim el Rouayheb
  4. David A. Karpuk
  5. Hua Sun
  6. Syed Ali Jafar
  7. Oliver Wilhelm Gnilke
  8. Camilla Hollanti

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. Rafael G. L. D'Oliveira

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