Improved Summation from Shuffling
By Borja Balle, James Bell, Adrià Gascón, Kobbi Nissim. 2019
23 citations recorded by the source corpus.
A protocol by Ishai et al.\ (FOCS 2006) showing how to implement distributed $n$-party summation from secure shuffling has regained relevance in the context of the recently proposed \emph{shuffle model} of differential privacy, as it allows to attain the accuracy levels of the curator model at a moderate communication cost. To achieve statistical security $2^{-\sigma}$, the protocol by Ishai et al.\ requires the number of messages sent by each party to {\em grow} logarithmically with $n$ as $O(\log n + \sigma)$. In this note we give an improved analysis achieving a dependency of the form $O(1+\sigma/\log n)$. Conceptually, this addresses the intuitive question left open by Ishai et al.\ of whether the shuffling step in their protocol provides a "hiding in the crowd" amplification effect as $n$ increases. From a practical perspective, our analysis provides explicit constants and shows, for example, that the method of Ishai et al.\ applied to summation of $32$-bit numbers from $n=10^4$ parties sending $12$ messages each provides statistical security $2^{-40}$.
Subfields: Numerical Methods & Scientific Computing, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Numerical Methods & Scientific Computing
In Algorithms & Complexity
Citations in the corpus
- Advances and Open Problems in Federated Learning (2019, neutral): “[179] & [45] 1 + log(1/δ) logn logn 1 ε”
- Private Summation in the Multi-Message Shuffle Model (2020, neutral): “This work is partially based on results reported in the technical reports [3, 4].”
- Private Aggregation from Fewer Anonymous Messages (2019, methodology): “Using a reduction of Balle et al. (2019), our improved analysis of the protocol of Ishai et al. yields, in the same model, an (ε, δ)-differentially private protocol for aggregation that, for any constant ε > 0 and any δ = 1 poly(n) , incurs only a constant error and requires only a constant number…”