Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient

We obtain a new protocol for binary counting in the $\epsilon$-shuffle-DP model with error $O(1\mathrm{/}\epsilon )$ and expected communication $\tilde{O}\left(\frac{\log n}{\epsilon }\right)$ messages per user. Previous protocols incur either an error of $O(1\mathrm{/}{\epsilon }^{1.5})$ with $O_{\epsilon }(\log n)$ messages per user (Ghazi et al., ITC 2020) or an error of $O(1\mathrm{/}\epsilon )$ with $O_{\epsilon }(n^{2.5})$ messages per user (Cheu and Yan, TPDP 2022). Using the new protocol, we obtained improved $\epsilon$-shuffle-DP protocols for real summation and histograms.