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^-σ, 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⁴ parties sending 12 messages each provides statistical security 2⁻⁴⁰.