License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2020.1
URN: urn:nbn:de:0030-drops-121068
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12106/
Balcer, Victor ;
Cheu, Albert
Separating Local & Shuffled Differential Privacy via Histograms
Abstract
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.
BibTeX - Entry
@InProceedings{balcer_et_al:LIPIcs:2020:12106,
author = {Victor Balcer and Albert Cheu},
title = {{Separating Local & Shuffled Differential Privacy via Histograms}},
booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)},
pages = {1:1--1:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-151-1},
ISSN = {1868-8969},
year = {2020},
volume = {163},
editor = {Yael Tauman Kalai and Adam D. Smith and Daniel Wichs},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12106},
URN = {urn:nbn:de:0030-drops-121068},
doi = {10.4230/LIPIcs.ITC.2020.1},
annote = {Keywords: Differential Privacy, Distributed Protocols, Histograms}
}
|
Keywords: |
|
Differential Privacy, Distributed Protocols, Histograms |
|
Collection: |
|
1st Conference on Information-Theoretic Cryptography (ITC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.06.2020 |
