Technical Program

Paper Detail

Paper Title Single-Server Multi-Message Individually-Private Information Retrieval with Side Information
Paper IdentifierTU3.R3.1
Authors Anoosheh Heidarzadeh, Texas A&M University, United States; Swanand Kadhe, University of California, Berkeley, United States; Salim El Rouayheb, Rutgers University, United States; Alex Sprintson, Texas A&M University, United States
Session Private Information Retrieval II
Location Monge, Level 3
Session Time Tuesday, 09 July, 14:30 - 16:10
Presentation Time Tuesday, 09 July, 14:30 - 14:50
Manuscript  Click here to download the manuscript
Abstract We consider a multi-user variant of the private information retrieval problem described as follows. Suppose there are $D$ users, each of which wants to privately retrieve a distinct message from a server with the help of a \emph{trusted agent}. We assume that the agent has a subset of $M$ messages whose indices are unknown to the server. The goal of the agent is to collectively retrieve the users' requests from the server. For this problem, we introduce the notion of \emph{individual-privacy} -- the agent is required to protect the privacy only for each individual user (but may leak some correlations among user requests). We refer to this problem as \emph{Individually-Private Information Retrieval with Side Information (IPIR-SI)}. We first establish a lower bound on the capacity, which is defined as the maximum achievable download rate, of the IPIR-SI problem by presenting a novel achievability protocol. Next, we characterize the capacity of IPIR-SI problem for $M=1$ and $D=2$. In the process of characterizing the capacity for arbitrary $M$ and $D$ we present a novel combinatorial conjecture, that may be of independent interest.