Improved Summation from Shuffling
This work offers an incremental improvement for protocols in the shuffle model of differential privacy, enhancing efficiency for privacy-preserving data aggregation.
The paper tackles the problem of improving the communication cost in distributed n-party summation using secure shuffling for differential privacy, achieving a reduced message complexity of O(1 + σ/log n) compared to the previous O(log n + σ). For example, with n=10^4 parties sending 12 messages each, it provides statistical security of 2^{-40}.
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^{-σ}$, 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 + σ)$. In this note we give an improved analysis achieving a dependency of the form $O(1+σ/\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}$.