Private Linear Transformation: The Joint Privacy Case
This work generalizes existing private computation problems, providing foundational capacity characterizations for private linear transformations, which is significant for researchers in private information retrieval and secure multi-party computation.
This paper introduces the Private Linear Transformation (PLT) problem, where a user computes linear combinations of a subset of messages from a server while protecting the privacy of the chosen subset. For the single-server case, the authors characterize the capacity for settings where the coefficient matrix forms a Maximum Distance Separable (MDS) code and provide bounds for non-MDS matrices and scenarios with side information.
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 who 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 -- defined as the supremum of all achievable download rates, for all parameters $K, D, L$. 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.