2026-07-23T20:13:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13595 2024-03-06T10:52:24Z ddc:004 open_access

On Distributed Differential Privacy and Counting Distinct Elements Chen, Lijie Ghazi, Badih Kumar, Ravi Manurangsi, Pasin Differential Privacy Shuffle Model We study the setup where each of n users holds an element from a discrete set, and the goal is to count the number of distinct elements across all users, under the constraint of (ε,δ)-differentially privacy: - In the non-interactive local setting, we prove that the additive error of any protocol is Ω(n) for any constant ε and for any δ inverse polynomial in n. - In the single-message shuffle setting, we prove a lower bound of Ω̃(n) on the error for any constant ε and for some δ inverse quasi-polynomial in n. We do so by building on the moment-matching method from the literature on distribution estimation. - In the multi-message shuffle setting, we give a protocol with at most one message per user in expectation and with an error of Õ(√n) for any constant ε and for any δ inverse polynomial in n. Our protocol is also robustly shuffle private, and our error of √n matches a known lower bound for such protocols. Our proof technique relies on a new notion, that we call dominated protocols, and which can also be used to obtain the first non-trivial lower bounds against multi-message shuffle protocols for the well-studied problems of selection and learning parity. Our first lower bound for estimating the number of distinct elements provides the first ω(√n) separation between global sensitivity and error in local differential privacy, thus answering an open question of Vadhan (2017). We also provide a simple construction that gives Ω̃(n) separation between global sensitivity and error in two-party differential privacy, thereby answering an open question of McGregor et al. (2011). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lijie Chen and Badih Ghazi and Ravi Kumar and Pasin Manurangsi 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.56 urn:nbn:de:0030-drops-135953 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.56 eng https://creativecommons.org/licenses/by/3.0/legalcode