Shuffling-Aware Optimization for Private Vector Mean Estimation

We study $d$-dimensional unbiased mean estimation in the single-message shuffle model, where each user sends a single privatized message and the analyzer only observes the shuffled multiset of reports. While optimal mechanisms are well understood in the local differential privacy setting, the corresponding notion of optimality after shuffling has remained largely unexplored. To address this gap, we introduce the recently proposed shuffle index and use it to formulate the post-shuffling mechanism design problem as an explicit optimization problem. We then establish a lower bound on the achievable mean squared error in terms of the shuffle index, which implies that mechanisms that are optimal under LDP can become suboptimal once shuffling is applied. Finally, we construct an asymptotically optimal mechanism in the high privacy regime, which as a consequence achieves a privacy-utility trade-off nearly identical to that of the central Gaussian mechanism.

This paper studies how to estimate the average of many people's data without exposing any one person's information. One simple privacy-preserving approach is for each person to randomize their own data before sending it, but this can substantially reduce accuracy. If the randomized messages are then shuffled so that they can no longer be linked to specific people, privacy can improve and less noise may be needed. We study how to design the best one-message-per-person method for this shuffled setting. We show that methods that are best before shuffling may no longer be best after shuffling, and we propose a new method that is essentially optimal when strong privacy is required. The resulting accuracy is nearly the same as in an idealized setting where a trusted party collects the data and adds Gaussian noise to the final average.