Cardinality Estimators do not Preserve Privacy

By Damien Desfontaines, Andreas Lochbihler, David A. Basin. 2018

54 citations recorded by the source corpus.

Abstract Cardinality estimators like HyperLogLog are sketching algorithms that estimate the number of distinct elements in a large multiset. Their use in privacy-sensitive contexts raises the question of whether they leak private information. In particular, can they provide any privacy guarantees while preserving their strong aggregation properties? We formulate an abstract notion of cardinality estimators, that captures this aggregation requirement: one can merge sketches without losing precision. We propose an attacker model and a corresponding privacy definition, strictly weaker than differential privacy: we assume that the attacker has no prior knowledge of the data. We then show that if a cardinality estimator satisfies this definition, then it cannot have a reasonable level of accuracy. We prove similar results for weaker versions of our definition, a nd a nalyze t he p rivacy o f existing algorithms, showing that their average privacy loss is significant, e ven f or m ultisets w ith l arge cardinalities. We conclude that strong aggregation requirements are incompatible with any reasonable definition o f privacy, and that cardinality estimators should be considered as sensitive as raw data. We also propose risk mitigation strategies for their real-world applications.

Subfields: Artificial Intelligence

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

Citations in the corpus

On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “In central DP, it can be easily solved with constant error using the Laplace mechanism [20]; see also [36, 15, 38, 14].”
Efficient Differentially Private F0 Linear Sketching (2020, background): “Our sketch will have an increase in noise when merging sketches, and thus does not satisfy the requirement for cardinality estimators formulated in [14].”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, background): “In particular, [18] showed that the LogLog sketch does not protect privacy from the inside aacker who has access to the sketch.”