Lune

NDSS2016Top-tier venue

Efficient Private Statistics with Succinct Sketches

Luca Melis, George Danezis, Emiliano De Cristofaro

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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Waldo: A Private Time-Series Database from Function Secret Sharing cites Senate: A Maliciously-Secure MPC Platform for Collaborative Analytics
  • Lightweight Techniques for Private Heavy Hitters cites Safely Measuring Tor
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers26

  1. Lightweight Techniques for Private Heavy HittersDan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa et al.S&P 2021 · 134 citations
  2. Waldo: A Private Time-Series Database from Function Secret SharingEmma Dauterman, Mayank Rathee, Raluca Ada Popa, Ion StoicaS&P 2022 · 91 citations
  3. Senate: A Maliciously-Secure MPC Platform for Collaborative AnalyticsRishabh Poddar, Sukrit Kalra, Avishay Yanai, Ryan Deng et al.USENIX Security 2021 · 89 citations
  4. Safely Measuring TorRob Jansen, Aaron JohnsonCCS 2016 · 76 citations
  5. 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

  1. Sketch-based Secure Query Processing for Streaming DataJianzhe Yu, Feng Han, Qi Dong, Qiyao Luo et al.SIGMOD 2026
  2. Streaming Function Secret Sharing and Its ApplicationsXiangfu Song, Jianli Bai, Ye Dong, Yijian Liu et al.USENIX Security 2026
  3. A One-Pass Distributed and Private Sketch for Kernel Sums with Applications to Machine Learning at ScaleBenjamin Coleman, Anshumali ShrivastavaCCS 2021 · 1 citation
  4. Distributed Measurement with Private Set-Union CardinalityEllis Fenske, Akshaya Mani, Aaron Johnson, Micah SherrCCS 2017 · 27 citations
  5. DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding WindowsYiping Wang, Yanhao Wang, Cen ChenKDD 2024 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines