Improved Summation from Shuffling
share
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 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 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.
READ FULL TEXT