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

We obtain a new protocol for binary counting in the varepsilon-shuffle-DP model with error O(1/varepsilon) and expected communication tildeOleft(fraclog nvarepsilonright) messages per user. Previous protocols incur either an error of O(1/varepsilon1.5) with O_varepsilon(logn) messages per user (Ghazi et al., ITC 2020) or an error of O(1/varepsilon) with O_varepsilon(n2.5) messages per user (Cheu and Yan, TPDP 2022). Using the new protocol, we obtained improved varepsilon-shuffle-DP protocols for real summation and histograms.