Single-Server Multi-Message Individually-Private Information Retrieval with Side Information

Anoosheh Heidarzadeh, Swanand Kadhe, Salim El Rouayheb, Alex Sprintson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

32 Scopus citations

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 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.

Original languageEnglish (US)
Title of host publication2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1042-1046
Number of pages5
ISBN (Electronic)9781538692912
DOIs
StatePublished - Jul 2019
Event2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France
Duration: Jul 7 2019Jul 12 2019

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2019-July
ISSN (Print)2157-8095

Conference

Conference2019 IEEE International Symposium on Information Theory, ISIT 2019
Country/TerritoryFrance
CityParis
Period7/7/197/12/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Single-Server Multi-Message Individually-Private Information Retrieval with Side Information'. Together they form a unique fingerprint.

Cite this