Multi-Server Private Information Retrieval with Coded Side Information
share
In this paper, we study the multi-server setting of the Private Information Retrieval with Coded Side Information (PIR-CSI) problem. In this problem, there are K messages replicated across N servers, and there is a user who wishes to download one message from the servers without revealing any information to any server about the identity of the requested message. The user has a side information which is a linear combination of a subset of M messages in the database. The parameter M is known to all servers in advance, whereas the indices and the coefficients of the messages in the user's side information are unknown to any server a priori. We focus on a class of PIR-CSI schemes, referred to as server-symmetric schemes, in which the queries/answers to/from different servers are symmetric in structure. We define the rate of a PIR-CSI scheme as its minimum download rate among all problem instances, and define the server-symmetric capacity of the PIR-CSI problem as the supremum of rates over all server-symmetric PIR-CSI schemes. Our main results are as follows: (i) when the side information is not a function of the user's requested message, the capacity is given by (1+1/N+...+1/N^K/M+1 -1)^-1 for any 1≤ M≤ K-1; and (ii) when the side information is a function of the user's requested message, the capacity is equal to 1 for M=2 and M=K, and it is equal to N/(N+1) for any 3 ≤ M ≤ K-1. The converse proofs rely on new information-theoretic arguments, and the achievability schemes are inspired by our recently proposed scheme for single-server PIR-CSI as well as the Sun-Jafar scheme for multi-server PIR.
READ FULL TEXT