RM2: Answer Counting Queries Efficiently under Shuffle Differential Privacy

Differential privacy (DP) is a leading standard for protecting individual privacy in data collection and analysis. This paper explores the shuffle model of DP, which balances privacy and utility by allowing users to send messages to a trusted shuffler before reaching an untrusted analyzer anonymously. We focus on efficiently implementing the matrix mechanism in shuffle-DP, where efficiency is defined by the number of messages each user sends. Our contributions include a baseline shuffle-DP mechanism that naively adapts the matrix mechanism, followed by an improved mechanism that reduces message complexity while maintaining error levels comparable to central-DP. We demonstrate the versatility of our approach across common query workloads, such as range queries and data cubes, achieving significant improvements in message efficiency. Experimental results confirm that our method outperforms the baseline solution while closely matching the accuracy of central-DP mechanisms.