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) onebit 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 (boundedcommunication) multimessage 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 InformationTheoretic Cryptography (ITC 2020)},
pages = {15:115:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771511},
ISSN = {18688969},
year = {2020},
volume = {163},
editor = {Yael Tauman Kalai and Adam D. Smith and Daniel Wichs},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12120},
URN = {urn:nbn:de:0030drops121208},
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 InformationTheoretic Cryptography (ITC 2020) 
Issue Date: 

2020 
Date of publication: 

04.06.2020 