TY - GEN
T1 - Single-Server Multi-Message Individually-Private Information Retrieval with Side Information
AU - Heidarzadeh, Anoosheh
AU - Kadhe, Swanand
AU - El Rouayheb, Salim
AU - Sprintson, Alex
N1 - Funding Information:
The work of A. Heidarzadeh and A. Sprintson was supported in part by NSF Grants No. 1718658 and 1642983. The work of S. Kadhe was supported in part by NSF Grants CCF-1748585 and CNS-1748692. The work of S. El Rouayheb was supported in part by NSF Grant CCF-1817635.
Publisher Copyright:
© 2019 IEEE.
PY - 2019/7
Y1 - 2019/7
N2 - 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 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 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 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.
AB - 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 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 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 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.
UR - http://www.scopus.com/inward/record.url?scp=85073145966&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85073145966&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2019.8849283
DO - 10.1109/ISIT.2019.8849283
M3 - Conference contribution
AN - SCOPUS:85073145966
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1042
EP - 1046
BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019
Y2 - 7 July 2019 through 12 July 2019
ER -