Private information retrieval with side information: The single server case
Swanand Kadhe, Brenden Garcia, Anoosheh Heidarzadeh, Salim El Rouayheb, Alex Sprintson · 2017
We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of K 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 M 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 without revealing its identity while minimizing the amount of data downloaded from the server. We focus on achieving information-theoretic privacy in two scenarios: (i) the user wants to protect jointly its demand and side information; (ii) the user wants to protect only the information about its demand, but not the side information. To highlight the role of side information, we focus on the case of a single server. We prove that, in the first scenario, the minimum download cost is K-M messages, and in the second scenario, it is ⌈K/M+1⌉ messages. This is a significant improvement compared to the minimum cost of K messages in the setting where the user has no side information. Our proof techniques use a reduction from the PIR with side information problem to an index coding problem. We leverage this reduction to prove converse results, as well as to design achievability schemes.