Improved Summation from Shuffling

Abstract

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}$.

References in corpus (2)

• Scalable and Differentially Private Distributed Aggregation in the Shuffled Model
• Differentially Private Summation with Multi-Message Shuffling

Cited by in corpus (5)

• On the Power of Multiple Anonymous Messages
• Aggregation and Transformation of Vector-Valued Messages in the Shuffle Model of Differential Privacy
• Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
• Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning
• Differential Privacy in the Shuffle Model: A Survey of Separations