UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Efficient Private Statistics with Succinct Sketches

Melis, L; Danezis, G; Cristofaro, ED; (2016) Efficient Private Statistics with Succinct Sketches. In: Proceedings of the NDSS Symposium 2016. Internet Society: San Diego, CA, USA. Green open access

Available under License : See the attached licence file.

Download (690kB) | Preview


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

Type: Proceedings paper
Title: Efficient Private Statistics with Succinct Sketches
Event: NDSS Symposium 2016
ISBN: 189156241X
Open access status: An open access version is available from UCL Discovery
DOI: 10.14722/ndss.2016.23175
Publisher version: http://dx.doi.org/10.14722/ndss.2016.23175
Language: English
Additional information: Permission to freely reproduce all or part of this paper for noncommercial purposes is granted provided that copies bear this notice and the full citation on the first page. Reproduction for commercial purposes is strictly prohibited without the prior written consent of the Internet Society, the first-named author (for reproduction of an entire paper only), and the author’s employer if the paper was prepared within the scope of employment.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/1470750
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item