Efficient Private Statistics with Succinct Sketches
Abstract
Large-scale collection of contextual information is often essential in order to gather statistics, train machine learning models, and extract knowledge from data. The ability to do so in a privacy-preserving way -- i.e., without collecting fine-grained user data -- enables a number of additional computational scenarios that would be hard, or outright impossible, to realize without strong privacy guarantees. In this paper, we present the design and implementation of practical techniques for privately gathering statistics from large data streams. We build on efficient cryptographic protocols for private aggregation and on data structures for succinct data representation, namely, Count-Min Sketch and Count Sketch. These allow us to reduce the communication and computation complexity incurred by each data source (e.g., end-users) from linear to logarithmic in the size of their input, while introducing a parametrized upper-bounded error that does not compromise the quality of the statistics. We then show how to use our techniques, efficiently, to instantiate real-world privacy-friendly systems, supporting recommendations for media streaming services, prediction of user locations, and computation of median statistics for Tor hidden services.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
26 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers26
- Lightweight Techniques for Private Heavy HittersDan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa et al.S&P 2021 · 134 citations
- Waldo: A Private Time-Series Database from Function Secret SharingEmma Dauterman, Mayank Rathee, Raluca Ada Popa, Ion StoicaS&P 2022 · 91 citations
- Senate: A Maliciously-Secure MPC Platform for Collaborative AnalyticsRishabh Poddar, Sukrit Kalra, Avishay Yanai, Ryan Deng et al.USENIX Security 2021 · 89 citations
- Safely Measuring TorRob Jansen, Aaron JohnsonCCS 2016 · 76 citations
- United We Stand: Collaborative Detection and Mitigation of Amplification DDoS Attacks at ScaleDaniel Wagner, Daniel Kopp, Matthias Wichtlhuber, Christoph Dietzel et al.CCS 2021 · 50 citations
Related papers
- Sketch-based Secure Query Processing for Streaming DataJianzhe Yu, Feng Han, Qi Dong, Qiyao Luo et al.SIGMOD 2026
- Streaming Function Secret Sharing and Its ApplicationsXiangfu Song, Jianli Bai, Ye Dong, Yijian Liu et al.USENIX Security 2026
- A One-Pass Distributed and Private Sketch for Kernel Sums with Applications to Machine Learning at ScaleBenjamin Coleman, Anshumali ShrivastavaCCS 2021 · 1 citation
- Distributed Measurement with Private Set-Union CardinalityEllis Fenske, Akshaya Mani, Aaron Johnson, Micah SherrCCS 2017 · 27 citations
- DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding WindowsYiping Wang, Yanhao Wang, Cen ChenKDD 2024 · 2 citations
