Multi-Server Private Linear Transformation with Joint Privacy
Fatemeh Kazemi, Alex Sprintson · 2021
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. We show that the capacity in this case is Φ(1/N, K − D + 1), where Φ(A, B) ≜ (1 + A + A2+ ⋯ + AB−1)−1. Moreover, we establish an upper bound and lower bounds on the capacity of the PLT problem for all parameters N, K, D, L ≥ 1. We show that for the regime where K − D is a non-negative integer multiple of L, the proposed capacity upper bound is equal to Φ(1/N, (K −D +L)/L). Also, 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.