Counting Distinct Elements Under Person-Level Differential Privacy

Thomas Steinke; Alexander Knop

NeurIPS 2023poster2 citations

Counting Distinct Elements Under Person-Level Differential Privacy

Abstract

We study the problem of counting the number of distinct elements in a dataset subject to the constraint of differential privacy. We consider the challenging setting of person-level DP (a.k.a. user-level DP) where each person may contribute an unbounded number of items and hence the sensitivity is unbounded. Our approach is to compute a bounded-sensitivity version of this query, which reduces to solving a max-flow problem. The sensitivity bound is optimized to balance the noise we must add to privatize the answer against the error of the approximation of the bounded-sensitivity query to the true number of unique elements.

differential privacyuser-level privacyperson-level privacysensitivity

BibTeX

@inproceedings{
steinke2023counting,
title={Counting Distinct Elements Under Person-Level Differential Privacy},
author={Thomas Steinke and Alexander Knop},
booktitle={Thirty-seventh Conference on Neural Information Processing Systems},
year={2023},
url={https://openreview.net/forum?id=zdli6OxpWd}
}