Can I read On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information on EtoBox?

On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information by Heidarzadeh, Anoosheh; Garcia, Brenden; Kadhe, Swanand; Rouayheb, Salim El; Sprintson, Alex is a scholarly article available to read on EtoBox.

What is On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information about?

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 in the database which could have been obtained in advance from other users or from previous interactions with the server. 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 (PC) scheme. In this paper, we focus on the case when the user wants multiple messages, i.e., $D>1$. Our first result is that if the user wants more me

Author

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

Published

2018

Language

EN