# Distributed Differentially Private Data Analytics via Secure Sketching

arXiv: https://arxiv.org/abs/2412.00497 · HTML: https://mlsanity.com/paper/2412.00497/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 83 references that are in the map.
- First posted on arXiv 30 Nov 2024.

## Builds on (most cited first, 29 of 29)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo](https://mlsanity.com/paper/1502.07645/) (2015)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Local, Private, Efficient Protocols for Succinct Histograms](https://mlsanity.com/paper/1504.04686/) (2015)
- [On the Theory and Practice of Privacy-Preserving Bayesian Data Analysis](https://mlsanity.com/paper/1603.07294/) (2016)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [An Improved Gap-Dependency Analysis of the Noisy Power Method](https://mlsanity.com/paper/1602.07046/) (2016)
- [Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Case](https://mlsanity.com/paper/1802.04085/) (2018)
- [Bayesian Differential Privacy through Posterior Sampling](https://mlsanity.com/paper/1306.1066/) (2013)
- [Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead](https://mlsanity.com/paper/2106.04247/) (2021)
- [Improved Distributed Principal Component Analysis](https://mlsanity.com/paper/1408.5823/) (2014)
- [Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible](https://mlsanity.com/paper/1706.03316/) (2017)
- [Efficient Private Statistics with Succinct Sketches](https://mlsanity.com/paper/1508.06110/) (2015)
- [Differentially Private Regression with Unbounded Covariates](https://mlsanity.com/paper/2202.11199/) (2022)
- [Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data](https://mlsanity.com/paper/1910.00482/) (2019)
- [Private Query Release via the Johnson-Lindenstrauss Transform](https://mlsanity.com/paper/2208.07410/) (2022)
- [Noninteractive Locally Private Learning of Linear Models via Polynomial Approximations](https://mlsanity.com/paper/1812.06825/) (2018)
- [Improved Utility Analysis of Private CountSketch](https://mlsanity.com/paper/2205.08397/) (2022)
- [Samplable Anonymous Aggregation for Private Federated Data Analysis](https://mlsanity.com/paper/2307.15017/) (2023)
- [On the Round Complexity of the Shuffle Model](https://mlsanity.com/paper/2009.13510/) (2020)
- [Improved Differentially Private Euclidean Distance Approximation](https://mlsanity.com/paper/2203.11561/) (2022)
- [Multi-Central Differential Privacy](https://mlsanity.com/paper/2009.05401/) (2020)
- [Necessary Conditions in Multi-Server Differential Privacy](https://mlsanity.com/paper/2208.08540/) (2022)
- [Differentially Private Selection from Secure Distributed Computing](https://mlsanity.com/paper/2306.04564/) (2023)
- [Sparse Dimensionality Reduction Revisited](https://mlsanity.com/paper/2302.06165/) (2023)

## Built on by (most cited first, 1 of 1)

- [Private Sketches for Linear Regression](https://mlsanity.com/paper/2511.07365/) (2025)

## Abstract (arXiv)

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 prohibitively 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.