Single-server Multi-user Private Information Retrieval with Side Information

In the problem of private information retrieval with side information, a single user wants to recover one of the K independent messages which are stored at one or multiple servers. The user initially has a subset of messages as side information. The goal of the user is to retrieve the demand message by using minimum number of transmissions (R∗) from the server(s) to the user under the condition that the index of the demand message should not be inferred by the server. We introduce the multi-user variant into this problem, where each user wants to retrieve one message and has a subset of messages as side information. In this paper, we study the special cases where all users want to retrieve one common message from a single server, but each user has different side information messages. We show that the optimal coding scheme can be constructed by first optimally partitioning the messages and then generating MDS codes separately in each subset of messages in the partition. We determine the R∗ , propose algorithms to compute R∗ , and construct optimal linear coding schemes with complexity polynomial in K (but exponential in the number of side information messages).