Private Linear Transformation: The Joint Privacy Case
Nahid Esmati, Anoosheh Heidarzadeh, Alex Sprintson · 2021
In this paper, we introduce the problem of Private Linear Transformation (PLT). This problem includes a single (or multiple) remote server(s) storing (identical copies of)$K$messages and a user that wants to compute$L$linear combinations of a$D$-subset of these messages by downloading the minimum amount of information from the server(s) while protecting the privacy of the entire set of$D$messages. This problem generalizes the private information retrieval and private linear computation problems. In this work, we focus on the single-server case. For the setting in which the coefficient matrix of the required$L$linear combinations generates a Maximum Distance Separable (MDS) code, we characterize the capacity for all parameters$K, D, L$, where the capacity is defined as the supremum of all achievable download rates. In addition, we present lower and/or upper bounds on the capacity for the settings with non-MDS coefficient matrices and the settings with a prior side information.