On the Power of Multiple Anonymous Messages: Frequency Estimation and Selection in the Shuffle Model of Differential Privacy
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
On the Power of Multiple Anonymous Messages : Frequency Estimation and Selection in the Shuffle Model of Differential Privacy. / Ghazi, Badih; Golowich, Noah; Kumar, Ravi; Pagh, Rasmus; Velingker, Ameya.
Advances in Cryptology – EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. ed. / Anne Canteaut; François-Xavier Standaert. Springer, 2021. p. 463-488 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12698 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - On the Power of Multiple Anonymous Messages
T2 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2021
AU - Ghazi, Badih
AU - Golowich, Noah
AU - Kumar, Ravi
AU - Pagh, Rasmus
AU - Velingker, Ameya
N1 - Publisher Copyright: © 2021, International Association for Cryptologic Research.
PY - 2021
Y1 - 2021
N2 - It is well-known that general secure multi-party computation can in principle be applied to implement differentially private mechanisms over distributed data with utility matching the curator (a.k.a. central) model. In this paper we study the power of protocols running on top of a much weaker primitive: A non-interactive anonymous channel, known as the shuffle model in the differential privacy literature. Such protocols are implementable in a scalable way using known cryptographic methods and are known to enable non-interactive, differentially private protocols with error much smaller than what is possible in the local model. We study fundamental counting problems in the shuffle model and obtain tight, up to polylogarithmic factors, bounds on the error and communication in several settings. For the classic problem of frequency estimation for n users and a domain of size B, we obtain: A nearly tight lower bound of Ω~(min(n4,B)) on the ℓ∞ error in the single-message shuffle model. This implies that the protocols obtained from the amplification via shuffling work of Erlingsson et al. (SODA 2019) and Balle et al. (Crypto 2019) are nearly optimal for single-message protocols.Protocols in the multi-message shuffle model with poly (log B, log n) bits of communication per user and ℓ∞ error at most poly (log B, log n), which provide an exponential improvement on the error compared to what is possible with single-message algorithms. This implies protocols with similar error and communication guarantees for several well-studied problems such as heavy hitters, d-dimensional range counting, M-estimation of the median and quantiles, and more generally sparse non-adaptive statistical query algorithms. For the selection problem on a domain of size B, we prove: A nearly tight lower bound of Ω(B) on the number of users in the single-message shuffle model. This significantly improves on the Ω(B1 / 17) lower bound obtained by Cheu et al. (Eurocrypt 2019). A key ingredient in our lower bound proofs is a lower bound on the error of locally-private frequency estimation in the low-privacy (a.k.a. high ε ) regime. For this we develop new tools to improve the results of Duchi et al. (FOCS 2013; JASA 2018) and Bassily & Smith (STOC 2015), whose techniques only gave tight bounds in the high-privacy setting.
AB - It is well-known that general secure multi-party computation can in principle be applied to implement differentially private mechanisms over distributed data with utility matching the curator (a.k.a. central) model. In this paper we study the power of protocols running on top of a much weaker primitive: A non-interactive anonymous channel, known as the shuffle model in the differential privacy literature. Such protocols are implementable in a scalable way using known cryptographic methods and are known to enable non-interactive, differentially private protocols with error much smaller than what is possible in the local model. We study fundamental counting problems in the shuffle model and obtain tight, up to polylogarithmic factors, bounds on the error and communication in several settings. For the classic problem of frequency estimation for n users and a domain of size B, we obtain: A nearly tight lower bound of Ω~(min(n4,B)) on the ℓ∞ error in the single-message shuffle model. This implies that the protocols obtained from the amplification via shuffling work of Erlingsson et al. (SODA 2019) and Balle et al. (Crypto 2019) are nearly optimal for single-message protocols.Protocols in the multi-message shuffle model with poly (log B, log n) bits of communication per user and ℓ∞ error at most poly (log B, log n), which provide an exponential improvement on the error compared to what is possible with single-message algorithms. This implies protocols with similar error and communication guarantees for several well-studied problems such as heavy hitters, d-dimensional range counting, M-estimation of the median and quantiles, and more generally sparse non-adaptive statistical query algorithms. For the selection problem on a domain of size B, we prove: A nearly tight lower bound of Ω(B) on the number of users in the single-message shuffle model. This significantly improves on the Ω(B1 / 17) lower bound obtained by Cheu et al. (Eurocrypt 2019). A key ingredient in our lower bound proofs is a lower bound on the error of locally-private frequency estimation in the low-privacy (a.k.a. high ε ) regime. For this we develop new tools to improve the results of Duchi et al. (FOCS 2013; JASA 2018) and Bassily & Smith (STOC 2015), whose techniques only gave tight bounds in the high-privacy setting.
U2 - 10.1007/978-3-030-77883-5_16
DO - 10.1007/978-3-030-77883-5_16
M3 - Article in proceedings
AN - SCOPUS:85111430974
SN - 9783030778828
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 463
EP - 488
BT - Advances in Cryptology – EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Canteaut, Anne
A2 - Standaert, François-Xavier
PB - Springer
Y2 - 17 October 2021 through 21 October 2021
ER -
ID: 300922285