PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Private Statistics with Succinct Sketches

Luca Melis, George Danezis, Emiliano De Cristofaro

arXiv:1508.06110v3cs.CR

TL;DR

Large-scale statistics can support modeling and prediction, but collecting fine-grained data raises privacy concerns and conventional private aggregation scales linearly with input size. The paper combines cryptographic aggregation with sketches to reduce per-source communication and computation while bounding error. It applies these techniques to recommender systems, location prediction, and Tor median statistics.

  • Problem

    Providers need aggregate statistics to train models, but existing cryptographic aggregation has communication and computation costs linear in each source's input, limiting its practicality for large streams.

    Source: §I · p. 1

  • Method

    The paper combines private aggregation protocols with Count-Min Sketch and Count Sketch, aggregating sketches rather than raw inputs to reduce per-source costs.

    Source: §I · p. 1

  • Results

    The techniques reduce per-source communication and computation from linear to logarithmic in input size while introducing only limited, upper-bounded error in the statistics.

    Source: §VII · p. 13

  • Takeaways & Limitations

    The techniques support implemented privacy-friendly systems for streaming recommendations, location prediction, and median statistics of Tor hidden services.

    Source: §VII · p. 13

Abstract

from arXiv · show

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.

I. INTRODUCTION

Collecting statistics from large streams can support useful services, but fine-grained user data raises privacy concerns and existing cryptographic aggregation scales linearly with input size. The paper combines private aggregation with sketches to reduce per-source cost and applies the approach to recommendations, location prediction, and Tor statistics.

I. INTRODUCTION

  • Existing cryptographic aggregation requires communication and computation linear in each input, making large streams such as video co-view matrices impractical to encrypt and transmit.With hundreds of programs, each user could face a matrix of hundreds of thousands of values.Source: §I · p. 1
  • Combining private aggregation with Count-Min Sketch and Count Sketch reduces per-source cryptographic communication and computation from linear to logarithmic in input size, with upper-bounded error.The paper reports that the error does not affect the overall quality of the computation.Source: §I · p. 1
  • The proposed applications privately aggregate co-view data for recommendations and location reports for movement prediction, disclosing aggregate statistics rather than fine-grained user data.The location aggregates are used to train a model to predict future movements.Source: §I · pp. 1–2
  • For Tor hidden services, the system estimates median statistics from an encrypted frequency distribution collected across all Hidden Services Directories, addressing an open problem raised by the Tor Project.The statistics target the tension between publishing useful measurements and protecting individual users.Source: §I · p. 2
  • The paper presents implementations in JavaScript, Android, and Python and describes support for different trust, robustness, and deployment models.The browser-based client can run without additional user software or technical understanding of the cryptographic layer.Source: §I · p. 2

A. Cryptographic Background

This background introduces cryptographic assumptions and sketch data structures used to represent and aggregate stream statistics compactly. Count-Min Sketch estimates counts with an upper-bounded error, while Count Sketch uses a different estimator.

A. Cryptographic Background

  • The cryptographic background states CDH and DDH hardness assumptions and defines pairwise-independent hash functions.The assumptions concern cyclic groups and probabilistic polynomial-time algorithms; pairwise independence specifies joint hash-output probabilities for distinct inputs.Source: A. Cryptographic Background · p. 2

B. Count-Min Sketch and Count Sketch

  • Count-Min Sketch uses a table of width w and depth d, updates one entry per row using hash functions, and estimates an item's count by the minimum row estimate.Its estimate is at least the true count and exceeds it by at most ϵ times the total absolute count with probability 1 − δ.Source: B. Count-Min Sketch and Count Sketch · p. 2
  • Count-Min and Count Sketch support linear aggregation of sketches, while Count Sketch estimates frequency using two buckets per row and takes the median of row estimates.The Count Sketch row estimate subtracts the value at an adjacent bucket from the value at the hashed bucket.Source: B. Count-Min Sketch and Count Sketch · pp. 2–3

C. Differential Privacy

The section introduces differential privacy and its Laplace mechanism, then reviews the ItemKNN recommender model used in the paper. For binary ratings, item similarity is computed from co-rating counts and used to form recommendations.

C. Differential Privacy

  • Differential privacy bounds information leaked about an individual row by requiring similar output probabilities on datasets differing in one row.The section describes output perturbation as modifying a statistic with a randomized algorithm before release.Source: C. Differential Privacy · p. 3
  • The Laplace mechanism adds independent Laplace noise to each function output, with the required noise scale determined by the function's sensitivity and privacy parameter.The text defines sensitivity as the maximum L1 change in the output between neighboring datasets.Source: C. Differential Privacy · p. 3

D. ItemKNN-based Recommender Systems

  • ItemKNN identifies each item's nearest neighbors from an item-to-item similarity matrix and uses their weights to predict ratings; for binary ratings, cosine similarity uses co-rating counts.The final recommendations rank items by prediction score and return the top K.Source: D. ItemKNN-based Recommender Systems · p. 3

E. Exponential Weighted Moving Average (EWMA)

EWMA predicts future values from past observations using exponentially decreasing weights for older data. The paper applies private sketch aggregation to recommender training data and describes a system that aggregates co-views so users can derive personalized recommendations.

E. Exponential Weighted Moving Average (EWMA)

  • EWMA predicts the next signal value from past observations, assigning exponentially decreasing weights to older observations.The smoothing coefficient α and the training window determine the weighted observations.Source: E. Exponential Weighted Moving Average… · p. 3
  • The paper's mechanisms privately and distributively estimate training datasets for ItemKNN and EWMA models, as well as median and other frequency statistics, using sketches and differential privacy when needed.The mechanisms combine traditional linear aggregation with sketches for efficiency.Source: E. Exponential Weighted Moving Average… · p. 3

III. PRIVATE RECOMMENDER SYSTEMS FOR STREAMING SERVICES

  • The recommender system aims to provide streaming recommendations without tracking users' preferences and viewing histories.The paper notes that iPlayer does not require users to register or have an account.Source: §III · pp. 3–4

A. Overview

  • Users encode co-view matrices as Count-Min Sketches, encrypt entries with secret-sharing-based blinding factors, and send them to a tally that decrypts and broadcasts aggregate counts.Users use the aggregate to estimate the global similarity matrix and derive personalized ItemKNN recommendations.Source: A. Overview · p. 4

B. Protocol

The protocol has users sketch and encrypt their inputs, then lets the tally aggregate the ciphertexts and return aggregate sketch entries for recommendations. If users drop out, the tally can recover the aggregate for those who reported; groups help manage scale.

Protocol

  • Users publish public keys, encode their co-view inputs as Count-Min Sketches, and send the tally encrypted sketch entries masked by blinding factors that sum to zero.The tally aggregates the ciphertexts and broadcasts aggregate sketch entries for users to recover an estimate of the global matrix and derive recommendations.Source: B. Protocol · p. 4

Fault Tolerance

  • When users drop out, the tally identifies the reporting subset and obtains new blinding factors from those users to recover their aggregate sketch entries.Recovery assumes all users in Uon submit the requested values.Source: B. Protocol · pp. 4–5, Figure 1 · p. 5

Groups

  • Groups of 100–1,000 users are proposed to reduce missed contributions and manage protocol complexity at iPlayer-scale peaks.Aggregates from different groups can be combined in the clear by the tally.Source: B. Protocol · p. 5

Security Analysis

  • The scheme inherits honest-but-curious security under the CDH assumption, but malicious active users could invalidate aggregation values.The authors leave verifiable tools such as zero-knowledge proofs and commitments, and consideration of a malicious tally, for future work.Source: B. Protocol · p. 5

C. Prototype Implementation

The prototype provides tally functionality as a Node.js web application and user functionality as browser JavaScript, with a standalone Android app also available. Its cryptographic layer uses Ed25519 and SHA-256.

Prototype Implementation

  • The tally runs as a Node.js web application using Express.js for MVC organization and Socket.io for bidirectional web-socket connections.It can be integrated by installing and importing a Node module.Source: C. Prototype Implementation · p. 5
  • User functionality runs as JavaScript embedded in a web page without additional user installation, and a standalone Android application is also implemented.The browser implementation is compatible with smartphone browsers.Source: C. Prototype Implementation · p. 5

Cryptographic Operations

  • The cryptographic layer uses an Ed25519 curve implementation with 256-bit points and SHA-256 for cryptographic hashing.The implementation describes Ed25519 security as comparable to a 128-bit security parameter.Source: C. Prototype Implementation · pp. 5–6

Prototype Evaluation

  • Figure 2 plots protocol execution time against increasing user counts while fixing the program count at 700.The figure covers client- and server-side running times.Source: Figure 2 · p. 6

D. Performance Evaluation

The Count-Min Sketch makes private recommendation computation substantially more efficient than operating on the uncompressed co-view matrix. Experiments show its runtime and communication costs alongside bounded accuracy loss under tested settings.

D. Performance Evaluation

  • Encryption and communication per user use O(L) operations or integers, where L = O(log(M^2)); tally aggregation uses O(L·N) linear operations.Sketch encryption uses L integer additions in Zq, while tally computation requires O(L·N) linear operations.Source: D. Performance Evaluation · p. 6
  • For 100 and 1,000 users, encryption takes 2.7 and 27 seconds, while tally aggregation takes 78 and 780ms, respectively.With 700 programs and sketch parameters ϵ = δ = 0.01, runtime grows linearly with user count.Source: D. Performance Evaluation · p. 6
  • At 1,000 users, encryption rises from 21 seconds at 100 programs to 28 seconds at 1,000 programs, while tally aggregation ranges approximately from 600ms to 800ms.The reported step-like plot reflects equal sketch sizes for some nearby program counts.Source: D. Performance Evaluation · p. 6, Figure 3 · p. 7
  • At 1,000 users and 1,000 programs, no-sketch encryption takes almost 50 minutes per user and tally aggregation almost 1.5 minutes, versus 28 seconds and less than one second with the sketch.The reported comparison shows the practical effect of sketch compression on both client and tally execution.Source: D. Performance Evaluation · p. 6
  • With 700 programs, each user sends 20KB rather than 960KB without sketch compression.Table I reports bytes exchanged for different user counts and sketch sizes.Source: D. Performance Evaluation · p. 6, Table I · p. 7
  • With 700 programs and ϵ = δ = 0.01, Count-Min Sketch estimates for the 50 most frequent items are almost indistinguishable from the true population.The reported evaluation uses a synthetic Zipfian dataset simulating one million users and a sketch of size 4,896.Source: D. Performance Evaluation · p. 6
  • Average error over the 50 most frequent items decreases with more users and smaller ϵ; standard deviations are described as infinitesimal.The evaluation fixes M = 700 and δ = 0.01, and varies ϵ among 0.01, 0.05, and 0.1.Source: D. Performance Evaluation · p. 7

IV. PRIVATE AGGREGATE LOCATION PREDICTION

The location-prediction system privately aggregates users’ location statistics as Count-Min Sketches, disclosing aggregate counts rather than fine-grained individual data. On the evaluated taxi data, sketch error is reported as infinitesimal for aggregate statistics and appreciably low for heat-map predictions.

IV. PRIVATE AGGREGATE LOCATION PREDICTION

  • The system discloses aggregate location statistics and uses them to train a model for predicting future movements and heat maps.Users report locations over time to a service provider; heat maps represent aggregate counts of people in an area over a time period.Source: §IV · pp. 7–8
  • On San Francisco taxi traces, hourly location counts show weekly and daily patterns and peaks of roughly 25,000 contributions.The dataset contains 11 million GPS coordinates from 536 taxis over almost a month in May 2008, grouped into 575 hourly epochs.Source: §IV · p. 8
  • For the top 100 popular cells in each time slot, average Count-Min Sketch error is infinitesimal at ϵ = δ = 0.01.The evaluation uses 100 × 100 cells and a Count-Min Sketch of size 3,808.Source: §IV · p. 9
  • For EWMA forecasts over the selected 12 consecutive epochs, lower α values produce more accurate predictions in almost all slots.The past 24 hours of observations are used as input, with prediction MAE compared against ground truth over the 100 most popular cells.Source: §IV · p. 9
  • With α = 0.1, Count-Min Sketch error in heat-map prediction fluctuates but remains appreciably low for every evaluated prediction.The comparison is against prediction based on the real heat maps for the same time slot.Source: §IV · p. 9
  • The evaluation does not report implementation performance for the location system, citing space limits and saying it would mirror Section III.The techniques were implemented in JavaScript, with a Node server module and an open-source Android application built using Apache Cordova.Source: §IV · p. 9

V. GATHERING STATISTICS ON TOR HIDDEN SERVICES

The Tor system privately estimates median statistics from Hidden Service Directory readings, addressing a need for aggregate measurements without exposing individual values. It combines Count Sketch with homomorphic aggregation and an interactive search, trading estimation accuracy against sketch size and privacy.

V. GATHERING STATISTICS ON TOR HIDDEN SERVICES

  • The Tor project needs hidden-service descriptor statistics for design decisions and funders, and uses the median rather than the mean for robustness.The section presents private median estimation as an application of succinct, privacy-preserving statistics.Source: §V · p. 9

A. Private Median Estimation using Count Sketch

  • Count Sketch estimates item frequencies from signed row estimates and supports range estimates as linear sums of sketch entries.Unlike Count-Min Sketch, these estimates do not require nonlinear operations such as taking a minimum.Source: A. Private Median Estimation using… · p. 9
  • Each HSDir builds and encrypts a Count Sketch; authorities homomorphically add the sketches before jointly decrypting intermediate results.The system uses additively homomorphic threshold public-key encryption and authorities that jointly decrypt.Source: A. Private Median Estimation using… · pp. 9–10
  • The authorities halve the known value range iteratively, decrypting the count in the first half to select the next half until one value remains.The search converges in O(log n) steps, but noisy Count Sketch range estimates can make the result differ from the true sample median.Source: A. Private Median Estimation using… · p. 10
  • The protocol is not perfectly private because it reveals the volume of values in intermediate ranges; adding noise can provide differential privacy but may worsen median estimates.The stated sensitivity is at most d, and noisy intermediate results may misidentify the range containing the median.Source: A. Private Median Estimation using… · p. 10

B. Implementation and Evaluation

The evaluation measures median accuracy against sketch size and differential-privacy protection, along with implementation costs. It reports practical computation and acceptable bandwidth overhead, while showing substantial utility trade-offs at smaller sketches and stronger differential privacy.

B. Implementation and Evaluation

  • The reference evaluation includes the London Atlas Dataset and a 1,200-value mixture-distribution problem modeled on Tor’s range and sample-count settings.The mixture contains 1,000 values from a Normal distribution with mean 300 and variance 25, and 200 from one with mean 500 and variance 200.Source: B. Implementation and Evaluation · p. 10
  • For ϵ, δ > 0.15, the estimated median deviates by more than 20% of its true value, while values below 0.025 do not reduce transmitted information.Figure 10 compares Count Sketch size with median-estimation quality.Source: Figure 10 · p. 11, B. Implementation and Evaluation · p. 11
  • 10,898 bytes is the serialized reference Count Sketch size; encrypting one sketch takes 0.001 sec per HSDir, and aggregating 1,200 sketches takes 1.456 seconds per authority.Ten decryption iterations suffice for the reference problem; the authors describe computation as practical and bandwidth overhead as acceptable.Source: B. Implementation and Evaluation · p. 11
  • Differential privacy with parameter ϵ = 0.5 can be provided without significantly affecting the quality of the median estimate; for ϵ < 0.5, the volume of the error grows exponentially.Source: B. Implementation and Evaluation · p. 11
  • The authors conclude that the differential-privacy mechanism offers limited protection that is difficult to increase because utility degrades rapidly as ϵ decreases.The exact value of a meaningful ϵ is described as debated in the literature.Source: B. Implementation and Evaluation · p. 11

VI. RELATED WORK

The related-work discussion contrasts privacy-preserving aggregation, differential privacy, and applications of private statistics. It positions succinct sketches as a way to reduce per-user overhead and identifies private median computation for Tor as a distinct contribution.

A. Privacy-Preserving Aggregation

  • Kursawe et al. provide a low-overhead aggregation protocol that this work adapts to sketches, reducing per-user computation and communication from linear to logarithmic input size.The authors also report recovery from node failures, allowing statistics retrieval and model training when some users go offline or fail to report.Source: A. Privacy-Preserving Aggregation · p. 11
  • Prior aggregation work includes protocols with substantial public-key overhead, more efficient encryption of fewer bits per query, and XOR-based aggregation that assumes non-colluding honest-but-curious servers.The discussion also notes schemes requiring a trusted dealer or discrete-logarithm computation.Source: A. Privacy-Preserving Aggregation · pp. 11–12
  • RAPPOR [34] uses input perturbation for local differential privacy, but requires millions of users to obtain approximate query answers.Source: A. Privacy-Preserving Aggregation · p. 12
  • Elahi et al. address private Tor traffic means, whereas this work uses homomorphic encryption and differential privacy to compute hidden-service medians, an open problem.Source: A. Privacy-Preserving Aggregation · p. 12

B. Privacy-preserving Recommender Systems

The related-work section distinguishes this recommender system from approaches based on trusted computing or differential privacy, and situates the work in participatory sensing and succinct private data representation. The conclusion reiterates the claimed efficiency gains and describes deployed systems for recommendations, location prediction, and Tor median statistics.

B. Privacy-preserving Recommender Systems

C. Participatory Sensing

  • The authors characterize their participatory-sensing technique as scalable and provably secure for collecting user-generated data streams from many users.The related work describes other approaches involving secure function evaluation, anonymity methods, data perturbation, and trusted hardware.Source: C. Participatory Sensing · p. 12

D. Privacy and Succinct Data Representation

  • The authors claim their work first combines Count-Min Sketch with privacy-friendly aggregation for recommendation and future-location models, and first addresses efficient private median statistics.The Tor scheme combines Count Sketch, additively homomorphic threshold decryption, and differential privacy.Source: D. Privacy and Succinct Data… · p. 12

VII. CONCLUSION

  • The conclusion reports reducing per-source communication and computation from linear to logarithmic input size with limited, upper-bounded error, alongside deployed recommendation, location-prediction, and Tor-median systems.Implementations include a JavaScript server-side application, browser and Android clients, and a Python Tor-median scheme.Source: §VII · p. 13

Related papers

Loading 1508.06110v3…