Search papers, labs, and topics across Lattice.
This paper introduces a novel single-message shuffle differential privacy protocol called Adaptive Shuffler-based Piecewise (ASP) for accurate distribution estimation of numerical data under the pure shuffle model. ASP employs a parameter-optimized randomizer based on a tighter mutual information bound and an Expectation Maximization with Adaptive Smoothing (EMAS) algorithm for robust distribution recovery. Experiments demonstrate that ASP significantly outperforms existing methods in utility, message complexity, and robustness against data poisoning attacks, particularly at small epsilon values.
A new shuffle-DP protocol achieves 10x better utility and 3x better robustness against data poisoning for distribution estimation, all while using a single message per user.
Shuffler-based differential privacy (shuffle-DP) is a privacy paradigm providing high utility by involving a shuffler to permute noisy report from users. Existing shuffle-DP protocols mainly focus on the design of shuffler-based categorical frequency oracle (SCFO) for frequency estimation on categorical data. However, numerical data is a more prevalent type and many real-world applications depend on the estimation of data distribution with ordinal nature. In this paper, we study the distribution estimation under pure shuffle model, which is a prevalent shuffle-DP framework without strong security assumptions. We initially attempt to transplant existing SCFOs and the na\"ive distribution recovery technique to this task, and demonstrate that these baseline protocols cannot simultaneously achieve outstanding performance in three metrics: 1) utility, 2) message complexity; and 3) robustness to data poisoning attacks. Therefore, we further propose a novel single-message \textit{adaptive shuffler-based piecewise} (ASP) protocol with high utility and robustness. In ASP, we first develop a randomizer by parameter optimization using our proposed tighter bound of mutual information. We also design an \textit{Expectation Maximization with Adaptive Smoothing} (EMAS) algorithm to accurately recover distribution with enhanced robustness. To quantify robustness, we propose a new evaluation framework to examine robustness under different attack targets, enabling us to comprehensively understand the protocol resilience under various adversarial scenarios. Extensive experiments demonstrate that ASP outperforms baseline protocols in all three metrics. Especially under small $\epsilon$ values, ASP achieves an order of magnitude improvement in utility with minimal message complexity, and exhibits over threefold robustness compared to baseline methods.
