Multi-Server Private Linear Transformation with Joint Privacy

This paper focuses on the Private Linear Transformation (PLT) problem in the multi-server scenario. In this problem, there are N servers, each of which stores an identical copy of a database consisting of K independent messages, and there is a user who wishes to compute L independent linear combinations of a subset of D messages in the database while leaking no information to the servers about the identity of the entire set of these D messages required for the computation. We focus on the setting in which the coefficient matrix of the desired L linear combinations generates a Maximum Distance Separable (MDS) code. We characterize the capacity of the PLT problem, defined as the supremum of all achievable download rates, for all parameters N, K, D ≥ 1 and L=1, i.e., when the user wishes to compute one linear combination of D messages. Moreover, we establish an upper bound on the capacity of PLT problem for all parameters N, K, D, L ≥ 1, and leveraging some known capacity results, we show the tightness of this bound in the following regimes: (i) the case when there is a single server (i.e., N=1), (ii) the case when L=1, and (iii) the case when L=D.