Search papers, labs, and topics across Lattice.
This paper investigates $d$-dimensional unbiased mean estimation in the single-message shuffle model of differential privacy, where the analyzer only observes shuffled, privatized messages. The authors formulate the post-shuffling mechanism design problem as an explicit optimization problem using the shuffle index and derive a minimax lower bound on the achievable mean squared error. They then construct an asymptotically minimax optimal mechanism in the high privacy regime, demonstrating that LDP-optimal mechanisms can become suboptimal after shuffling.
Shuffling data introduces a fundamental shift in the privacy-utility tradeoff for mean estimation, rendering locally differentially private (LDP) mechanisms suboptimal.
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 minimax-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 minimax 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 minimax 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.
