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.15
URN: urn:nbn:de:0030-drops-121208
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12120/
Ghazi, Badih ;
Golowich, Noah ;
Kumar, Ravi ;
Manurangsi, Pasin ;
Pagh, Rasmus ;
Velingker, Ameya
Pure Differentially Private Summation from Anonymous Messages
Abstract
The shuffled (aka anonymous) model has recently generated significant interest as a candidate distributed privacy framework with trust assumptions better than the central model but with achievable error rates smaller than the local model. In this paper, we study pure differentially private protocols in the shuffled model for summation, a very basic and widely used primitive. Specifically:
- For the binary summation problem where each of n users holds a bit as an input, we give a pure ε-differentially private protocol for estimating the number of ones held by the users up to an absolute error of O_{ε}(1), and where each user sends O_{ε}(log n) one-bit messages. This is the first pure protocol in the shuffled model with error o(√n) for constant values of ε.
Using our binary summation protocol as a building block, we give a pure ε-differentially private protocol that performs summation of real numbers in [0, 1] up to an absolute error of O_{ε}(1), and where each user sends O_{ε}(log³ n) messages each consisting of O(log log n) bits.
- In contrast, we show that for any pure ε-differentially private protocol for binary summation in the shuffled model having absolute error n^{0.5-Ω(1)}, the per user communication has to be at least Ω_{ε}(√{log n}) bits. This implies (i) the first separation between the (bounded-communication) multi-message shuffled model and the central model, and (ii) the first separation between pure and approximate differentially private protocols in the shuffled model. Interestingly, over the course of proving our lower bound, we have to consider (a generalization of) the following question that might be of independent interest: given γ ∈ (0, 1), what is the smallest positive integer m for which there exist two random variables X⁰ and X^1 supported on {0, … , m} such that (i) the total variation distance between X⁰ and X^1 is at least 1 - γ, and (ii) the moment generating functions of X⁰ and X^1 are within a constant factor of each other everywhere? We show that the answer to this question is m = Θ(√{log(1/γ)}).
BibTeX - Entry
@InProceedings{ghazi_et_al:LIPIcs:2020:12120,
author = {Badih Ghazi and Noah Golowich and Ravi Kumar and Pasin Manurangsi and Rasmus Pagh and Ameya Velingker},
title = {{Pure Differentially Private Summation from Anonymous Messages}},
booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)},
pages = {15:1--15:23},
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/12120},
URN = {urn:nbn:de:0030-drops-121208},
doi = {10.4230/LIPIcs.ITC.2020.15},
annote = {Keywords: Pure differential privacy, Shuffled model, Anonymous messages, Summation, Communication bounds}
}
|
Keywords: |
|
Pure differential privacy, Shuffled model, Anonymous messages, Summation, Communication bounds |
|
Collection: |
|
1st Conference on Information-Theoretic Cryptography (ITC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.06.2020 |
