Private Linear Transformation: The Individual Privacy Case
This work provides theoretical bounds for private linear transformation, which is important for users who need to compute functions on sensitive data stored on a server while maintaining the privacy of individual data items.
This paper addresses the Private Linear Transformation (PLT) problem with individual privacy, where a user wants to compute L linear combinations of a D-subset of K messages from a server without revealing the identity of any specific message. The authors establish tight lower and upper bounds on the capacity (achievable download rate) under specific conditions, minimizing download cost.
This paper considers the single-server Private Linear Transformation (PLT) problem when individual privacy is required. In this problem, there is a user that wishes to obtain $L$ linear combinations of a $D$-subset of messages belonging to a dataset of $K$ messages stored on a single server. The goal is to minimize the download cost while keeping the identity of every message required for the computation individually private. The individual privacy requirement implies that, from the perspective of the server, every message is equally likely to belong to the $D$-subset of messages that constitute the support set of the required linear combinations. We focus on the setting in which the matrix of coefficients pertaining to the required linear combinations is the generator matrix of a Maximum Distance Separable code. We establish lower and upper bounds on the capacity of PLT with individual privacy, where the capacity is defined as the supremum of all achievable download rates. We show that our bounds are tight under certain divisibility conditions. In addition, we present lower bounds on the capacity of the settings in which the user has a prior side information about a subset of messages.