Private Computation with Side Information: The Single-Server Case
Anoosheh Heidarzadeh, Alex Sprintson · 2019
This paper considers the problem of single-server Private Computation wit Side Information (PC-SI). In this problem, there is a user that initially has a subset of M messages from a database stored on a single server, where the identities of the side information messages are initially unknown to the server. The user wishes to compute a linear combination of a subset of D messages (disjoint from the set of side information messages) while protecting the identities of the messages in the demanded linear combination. The objective of the user is to minimize the download cost, which is defined as the total amount of information that the user downloads from the server.We establish a lower bound on the capacity of the PC-SI problem, where the capacity is defined as the supremum of all achievable download rates. The proof relies on a novel achievability scheme which combines together the ideas of the interference alignment and the Partition and Code scheme previously introduced for private information retrieval with side information. In addition, for the case of M = 1 and D = 2, we prove the tightness of the rate achievable by the proposed scheme, when we restrict ourselves to the scalar-linear PC-SI schemes. The proof of converse is based on a combination of new algebraic and information-theoretic arguments.