Distributed Differentially Private Data Analytics via Secure Sketching

We introduce the linear-transformation model, a distributed model of differentially private data analysis. Clients have access to a trusted platform capable of applying a public matrix to their inputs. Such computations can be securely distributed across multiple servers using simple and efficient secure multiparty computation techniques. The linear-transformation model serves as an intermediate model between the highly expressive central model and the minimal local model. In the central model, clients have access to a trusted platform capable of applying any function to their inputs. However, this expressiveness comes at a cost, as it is often expensive to distribute such computations, leading to the central model typically being implemented by a single trusted server. In contrast, the local model assumes no trusted platform, which forces clients to add significant noise to their data. The linear-transformation model avoids the single point of failure for privacy present in the central model, while also mitigating the high noise required in the local model. We demonstrate that linear transformations are very useful for differential privacy, allowing for the computation of linear sketches of input data. These sketches largely preserve utility for tasks such as private low-rank approximation and private ridge regression, while introducing only minimal error, critically independent of the number of clients.

In machine learning or data analysis tasks, a common and useful goal is to compute and publish some accurate model or group statistics, while preventing leakage of any single training datapoint. This goal is formalised by differential privacy; however, increasing privacy comes at the cost of a less accurate result. Without any trust assumptions, this loss in accuracy will scale with the number of users. If individuals are willing to share their private input with a third party whom they trust to compute the private statistics, the resulting error is reduced. Some intermediate models make some limited trust assumptions. In this work, we show that the relatively weak assumption of a trusted linear transformations can result in low error for the tasks of private low rank approximation and regularized linear regression. Our choice of trust assumption is motivated by existing cryptographic tools for computing such functions efficiently in a distributed setting.