On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information

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

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

19 Scopus citations

Abstract

We study Private Information Retrieval with Side Information (PIR-SI) in the single-server multi-message setting. In this setting, a user wants to download D messages from a database of K \geq D messages, stored on a single server, without revealing any information about the identities of the demanded messages to the server. The goal of the user is to achieve information-theoretic privacy by leveraging the side information about the database. The side information consists of a random subset of M messages. The identities of the messages forming the side information are initially unknown to the server. Our goal is to characterize the capacity of this setting, i.e., the maximum achievable download rate. In our previous work, we have established the PIR-SI capacity for the special case in which the user wants a single message, i.e., D = 1 and showed that the capacity can be achieved through the Partition and Code scheme. In this paper, we focus on the case when the user wants multiple messages, i.e., D\lt /p\gt \gt 1. Our first result is that if the user wants more messages than what they have as side information, i.e., D \gt M, then the capacity is \frac{D}{K-M}, and it can be achieved using a scheme based on the Generalized Reed-Solomon codes. Our second result shows that when D\leq M the capacity can be higher. We present a lower bound on the capacity based on an achievability scheme which we call Generalized Partition and Code.

Original languageEnglish (US)
Title of host publication2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages180-187
Number of pages8
ISBN (Electronic)9781538665961
DOIs
StatePublished - Feb 5 2019
Externally publishedYes
Event56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018 - Monticello, United States
Duration: Oct 2 2018Oct 5 2018

Publication series

Name2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018

Conference

Conference56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018
Country/TerritoryUnited States
CityMonticello
Period10/2/1810/5/18

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Signal Processing
  • Energy Engineering and Power Technology
  • Control and Optimization

Fingerprint

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

Cite this