Multi-Server Private Linear Computation with Joint and Individual Privacy Guarantees
Nahid Esmati, Anoosheh Heidarzadeh, Alex Sprintson · 2021
This paper considers the problem of multi-server Private Linear Computation, under the joint and individual privacy guarantees. In this problem, identical copies of a dataset comprised of K messages are stored on N non-colluding servers, and a user wishes to obtain one linear combination of a D-subset of messages belonging to the dataset. The goal is to design a scheme for performing the computation such that the total amount of information downloaded from the servers is minimized, while the privacy of the D messages required for the computation is protected. When joint privacy is required, the index set of these D messages must be kept private, and when individual privacy is required, the identity of each individual message required for the computation must be kept private. In this work, we characterize the capacity, which is defined as the maximum achievable download rate, under both joint and individual privacy requirements. Our converse proofs are based on reduction from two variants of the multi-server Private Information Retrieval problem with side information. Our achievability schemes build up on our recently proposed schemes for single-server Private Linear Transformation and the multi-server private computation scheme proposed by Sun and Jafar. Using similar techniques, we also establish bounds on the capacity for the cases in which the user wants to compute multiple (more than one) linear combinations of a D-subset of messages.