Private Information Retrieval With Side Information

By Swanand Ravindra Kadhe, Brenden Garcia, Anoosheh Heidarzadeh, Salim el Rouayheb, A. Sprintson. 2017

152 citations recorded by the source corpus.

We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> independent messages possibly replicated on several servers, and a user that needs to retrieve one of these messages. In addition, the user has some prior side information in the form of a subset of <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math></inline-formula> messages, not containing the desired message and unknown to the servers. This problem is motivated by practical settings in which the user can obtain side information opportunistically from other users or has previously downloaded some messages using classical PIR schemes. The objective of the user is to retrieve the required message with downloading minimum amount of data from the servers while achieving information-theoretic privacy in one of the following two scenarios: (i) the user wants to protect jointly the identities of the demand and the side information; (ii) the user wants to protect only the identity of the demand, but not necessarily the side information. To highlight the role of side information, we focus first on the case of a single server (single database). In the first scenario, we prove that the minimum download cost is <inline-formula> <tex-math notation="LaTeX">$K-M$ </tex-math></inline-formula> messages, and in the second scenario it is <inline-formula> <tex-math notation="LaTeX">$\lceil K/(M+1)\rceil $ </tex-math></inline-formula> messages, which should be compared to <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> messages—the minimum download cost in the case of no side information. Then, we extend some of our results to the case of the database replicated on multiple servers. Our proof techniques relate PIR with side information to the index coding problem. We leverage this connection to prove converse results, as well as to design achievability schemes.

Subfields: Artificial Intelligence, Computer Networks and Communications, Electrical and Electronic Engineering

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. Sarvar Patel
  2. Kevin Yeo
  3. Giuseppe Persiano
  4. Brent Waters

In Computer Networks and Communications

  1. Sarvar Patel

Citations in the corpus