| dc.description.abstract | In many practical settings, a user needs to perform computations---for example, using machine learning or cloud/edge computing algorithms---on the data stored in a storage system that consists of one or multiple remote servers. The direct data access may, however, result in exposing the identity of the data items used for the computation process to the server(s), and this can violate the privacy of the user. In recent years, several privacy-preserving schemes with information-theoretic privacy guarantees were proposed for some special cases of the private computation paradigm. Examples of such scenarios are Private Information Retrieval (PIR) and Private Linear Computation (PLC). Inspired by these works, in this thesis we introduce the problem of single-server Private Linear Transformation (PLT), which generalizes the PIR and PLC problems. In the PLT problem, there is a user that wishes to compute multiple linear combinations of a subset of items belonging to a dataset stored on a single remote server. The goal of the user is to minimize the total amount of information being downloaded from the server while keeping the identities of items required for the computation private. This problem is motivated by several applications such as linear transformation for dimensionality reduction in machine learning.
In this thesis, we make a significant progress towards characterizing the fundamental performance limits of the single-server PLT problem for two information-theoretic privacy conditions, called joint privacy and individual privacy, which have been recently considered for PIR and PLC. We prove converse bounds using a mix of linear-algebraic and information-theoretic arguments that are tailored for the single-server case, and are different from the commonly-used techniques in multi-server PIR and PLC. We design optimal privacy-preserving schemes by leveraging ideas from the literature on coding theory, such as Maximum Distance Separable (MDS) codes, and interference alignment. In addition, we briefly discuss the PLT settings in which the user has a prior side information about the dataset, and propose novel PLT schemes to show the advantages of side information in reducing the download cost for each type of privacy considered. | en |
