Efficient Private Statistics with Succinct Sketches

By Luca Melis, George Danezis, Emiliano De Cristofaro. 2015

129 citations recorded by the source corpus.

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 {\em 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.

Subfields: Artificial Intelligence, Statistics and Probability, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Privacy & Security

Citations in the corpus

Honeycrisp: large-scale differentially private aggregation without a trusted core (2019, background): “Like [56], Prio does not provide differential privacy; rather, it focuses on robustness to malicious user inputs, which it recognizes using a new kind of zero-knowledge proof.”
Private Aggregation from Fewer Anonymous Messages (2019, methodology): “We refer to [20,26,27] for examples and further discussion.”
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “This same approach is also used in a system by Melis, Danezis, and De Cristofaro [92], which we discuss in Section 8.”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “, via Gaussian noise [2], Laplacian noise [77], or Binomial noise [3], it is common to clip the gradients in order to bound the influence of each example on the overall update.”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, background): “Other examples of private aggregation include [28, 32, 43, 51].”
Efficient Differentially Private F0 Linear Sketching (2020, methodology): “We note that our sketch would also work in a model where vectors supplied by the users are combined using a black-box multi-party secure aggregation [21, 33].”
What Does The Crowd Say About You? Evaluating Aggregation-based Location Privacy (2017, background): “In some cases, mobility models can be trained using only aggregate statistics [10, 31, 37], e.”
Cardinality Estimators do not Preserve Privacy (2018, background): “In [32], each party encrypts their sketch, and sends it encrypted to a tally process, which aggregates them us-ing homomorphic encryption.”