Differentially Private Summation with Multi-Message Shuffling

By Borja Balle, James Bell, Adrià Gascón, Kobbi Nissim. 2019

48 citations recorded by the source corpus.

In recent work, Cheu et al. (Eurocrypt 2019) proposed a protocol for $n$-party real summation in the shuffle model of differential privacy with $O_{\epsilon, \delta}(1)$ error and $\Theta(\epsilon\sqrt{n})$ one-bit messages per party. In contrast, every local model protocol for real summation must incur error $\Omega(1/\sqrt{n})$, and there exist protocols matching this lower bound which require just one bit of communication per party. Whether this gap in number of messages is necessary was left open by Cheu et al. In this note we show a protocol with $O(1/\epsilon)$ error and $O(\log(n/\delta))$ messages of size $O(\log(n))$ per party. This protocol is based on the work of Ishai et al.\ (FOCS 2006) showing how to implement distributed summation from secure shuffling, and the observation that this allows simulating the Laplace mechanism in the shuffle model.

Subfields: Artificial Intelligence, 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 Privacy & Security

Citations in the corpus

Privacy Amplification by Decentralization (2020, methodology): “We can obtain a similar result for histograms by bounding the privacy loss incurred for each cycle by using ampliﬁcation by shuﬄing (Erlingsson et al., 2019; Balle et al., 2019b; Feldman et al., 2020), similar to what we did for the ring topology (Section 3.2).”
Private Summation in the Multi-Message Shuffle Model (2020, neutral): “This work is partially based on results reported in the technical reports [3, 4].”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “New models for differentially private computation have recently emerged to alleviate the (inevitable) low accuracy of the local model, of which we will discuss the shuffle model [38, 14, 19, 6, 5, 32] and the hybrid model [2].”
Private Aggregation from Fewer Anonymous Messages (2019, methodology): “is σ-secure even for m = Θ ( 1 + σ+log q log n ) messages, improving upon the known bounds of O(log n + σ + log q) [3,15,17].”
Improved Summation from Shuffling (2019, methodology): “Surprisingly, it is shown in [6] that k = O(logm + σ + logn) (see [1] for explicit, small constants) suffices to achieve statistical security σ, in the sense that the server the set of shares submitted by the users cannot distinguish two inputs (x1, .”
Scalable and Differentially Private Distributed Aggregation in the Shuffled Model (2019, neutral): “Concurrently and independently of our work, Balle et al. obtained a result similar to Theorem 1 [3].”
The Power of the Hybrid Model for Mean Estimation (2018, background): “Conversely, the LM users may experience privacy amplification through the combination of their locally-added noise; however, this is solely due to intra-group interaction in the LM, and related topics are currently an active area of research on the LM [5, 6, 16, 19, 26, 33].”
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, background): “Such anonymous summaries are less general than shuffled reports (from which they can be constructed by post-processing), but they can be practically computed using cryptographic means [10], [11], [30] and have seen formal analysis [19], [31].”
Separating Local & Shuffled Differential Privacy via Histograms (2019, background): “This separation was previously shown by [2, 1] for the summation problem.”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, methodology): “Our protocol is built on top of the modular arithmetic protocol of Balle, Bell, Gascón, and Nissim [8], which itself adapts a protocol from Kushilevitz, Ostrovsky, and Sahai [25], so we obtain this distance condition.”
Distributed Differentially Private Averaging with Improved Utility and Robustness to Malicious Parties (2020, background): “[5] Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim.”
Private Heavy Hitters and Range Queries in the Shuffled Model (2019, background): “Frequency estimation (private randomness) [16, 4, 32] B logB b”