2026-07-25T12:25:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12106 2024-03-06T10:49:32Z ddc:004 open_access

Separating Local & Shuffled Differential Privacy via Histograms Balcer, Victor Cheu, Albert Differential Privacy Distributed Protocols Histograms Recent work in differential privacy has highlighted the shuffled model as a promising avenue to compute accurate statistics while keeping raw data in users' hands. We present a protocol in this model that estimates histograms with error independent of the domain size. This implies an arbitrarily large gap in sample complexity between the shuffled and local models. On the other hand, we show that the models are equivalent when we impose the constraints of pure differential privacy and single-message randomizers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Victor Balcer and Albert Cheu 2020 Is Part Of LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2020.1 urn:nbn:de:0030-drops-121068 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.1 eng https://creativecommons.org/licenses/by/3.0/legalcode