Optimal Lower Bound for Differentially Private Multi-party Aggregation

By T-H. Hubert Chan, Elaine Shi, Dawn Song. 2012

120 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Science Applications, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

In Privacy & Security

Citations in the corpus

Privacy Amplification by Decentralization (2020, background): “Unfortunately, LDP comes at a great cost in utility: for real summation with n users, the best possible error under LDP is a factor √ n larger than in the centralized (trusted curator) model of DP (Chan et al., 2012a).”
On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “( In contrast, separations between central DP and DP local are well-known, even for basic functions such as binary summation [11].)”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “For numerous basic tasks, including binary summation and histograms that we study in this work, errors are at least on the order of √ n, where n is the number of users (Beimel et al., 2008; Chan et al., 2012).”
Private Summation in the Multi-Message Shuffle Model (2020, neutral): “The real summation problem has been extensively studied in the diﬀerentially privacy literature, eg. it is well-known that the optimal achievable errors in the central and local model are respectively Θ (cid:15) (1) [10] and Θ (cid:15) ( √ n ) [5, 7].”
Pure Differentially Private Summation from Anonymous Messages (2020, background): “Nevertheless, the local model suﬀers from large estimation errors that are known to the be on the order of √ n , where n is the number of users, for a variety of problems including summation, the focus of this work [BNO08, CSS12].”
Distributed Differential Privacy via Shuffling (2018, background): “[8] show that estimating the sum of bits, one held by each player, requires error Ω( √ n/ε) in the local model, while an error of just O(1/ε) is possible the central model.”
Heavy Hitters and the Structure of Local Privacy (2017, background): “[6] (see also [17, 34]) who obtained a lower bound of ⌦( p n) on the error:”
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, background): “In contrast, for the more privacy-stringent local setting (Kasiviswanathan et al., 2008) (also Warner, 1965) where each message sent by a user is supposed to be private, the smallest error is known to be ⇥ " ( p n ) (Beimel et al., 2008; Chan et al., 2012).”
Distributed Differentially Private Averaging with Improved Utility and Robustness to Malicious Parties (2020, background): “√ Unfortunately, the best possible error for the estimated average with n users is a factor of O ( n ) larger than in the centralized model of DP where a trusted curator aggregates data in the clear and perturbs the output [22].”
Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers (2019, background): “In contrast, under the LDPmodel, at least Ω( √ n/ε) additive expected error must be incurred by any ε-DP program [16, 28, 36], owing to the randomness of each data owner.”
Locally Differentially Private Heavy Hitter Identification (2017, background): “This is also true with all existing frequency oracles under LDP, and is a fundamental accuracy cost one has to pay in order to achieve LDP [8].”
Privacy and Robustness in Federated Learning: Attacks and Defenses (2020, methodology): “In contrast, under the LDP model, at least Ω( √ n/ ) additive error in expectation must be incurred by any -DP mechanism for the same task [114], [120].”
Accuracy-Privacy Tradeoffs for Two-Party Differentially Private Protocols (2013, unknown): “[5], and of McGregor et al.”
The Complexity of Differential Privacy (2017, background): “[25] proved that the 1/ √ n decay is in fact optimal:”
On the Power of Multiple Anonymous Messages (2019, unknown): “We also note that an anti-concentration lemma qualitatively similar to our Lemma 10 was used by Chan et al. [23, Lemma 3] to prove lower bounds on private aggregation, but they operated in a multi-party setting with communication limited by a sparse communication graph.”