SLDP: Semi-Local Differential Privacy for Density-Adaptive Analytics
This work addresses privacy-preserving analytics for data analysts, offering a solution to a known bottleneck in LDP, though it appears incremental as it builds on existing privacy models.
The paper tackles the challenge of density-adaptive domain discretization under Local Differential Privacy (LDP) by proposing a novel Semi-Local Differential Privacy (SLDP) framework that decouples privacy cost from refinement iterations, enabling high-resolution grids without extra privacy budget.
Density-adaptive domain discretization is essential for high-utility privacy-preserving analytics but remains challenging under Local Differential Privacy (LDP) due to the privacy-budget costs associated with iterative refinement. We propose a novel framework, Semi-Local Differential Privacy (SLDP), that assigns a privacy region to each user based on local density and defines adjacency by the potential movement of a point within its privacy region. We present an interactive $(\varepsilon, δ)$-SLDP protocol, orchestrated by an honest-but-curious server over a public channel, to estimate these regions privately. Crucially, our framework decouples the privacy cost from the number of refinement iterations, allowing for high-resolution grids without additional privacy budget cost. We experimentally demonstrate the framework's effectiveness on estimation tasks across synthetic and real-world datasets.