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 -