USENIX Security 26 - Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Pr… @UsenixOrg
USENIX Security 26 - Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Pr…  @UsenixOrg
Uploaded October 2026 | Updated November 2026, 5 days ago
USENIX Security '26 - Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Privacy in Continuous and Fine-Grained Domains

Chenxi Qiu, University of North Texas

Metric Differential Privacy (mDP) generalizes Local Differential Privacy (LDP) by adapting privacy guarantees based on pairwise distances, enabling context-aware protection and improved utility. While existing optimization-based methods reduce utility loss effectively in coarse-grained domains, optimizing mDP in fine-grained or continuous settings remains challenging due to the computational cost of constructing dense perturbation matrices and satisfying pointwise constraints.
In this paper, we propose an interpolation-based framework for optimizing ℓp-norm mDP in such domains. Our approach optimizes perturbation distributions at a sparse set of anchor points and interpolates distributions at non-anchor locations via log-convex combinations, which provably preserve mDP. To address privacy violations caused by naive interpolation in high-dimensional spaces, we decompose the interpolation process into a sequence of one-dimensional steps and derive a corrected formulation that enforces ℓp-norm mDP by design. We further explore joint optimization over perturbation distributions and privacy budget allocation across dimensions. Experiments on real-world location datasets demonstrate that our method offers rigorous privacy guarantees and competitive utility in fine-grained domains, outperforming baseline mechanisms.

View the full USENIX Security '26 program at usenix.org/conference/usenixsecurity26/technical-sessions
USENIX Security 26 - Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Pr…VehicleSec 26 - Short: Investigating Stealthy Latency Attacks Against Camera-Based Object...USENIX Security 26 - Technical Analysis of the Geedge Networks Firewall Source Code LeakSREcon26 Europe/Middle East/Africa - What Userland Utilities Wont Tell You: Uncovering Hidden...VehicleSec 26 - WIP: On the Real-World Applicability of Automotive CAN Intrusion Detection SystemsWOOT 26 - Security Analysis of LTE Connectivity in Connected Cars: A Case Study of TeslaWOOT 26 - SoK: 20 Years of Power, Privilege, and Peril in x86 System Management ModeSREcon26 Europe/Middle East/Africa - How Uber Validates Failover Resilience in ProductionUSENIX Security 26 - Exploring Privacy Negotiation Strategies for Camera-Equipped Smart Home Devic…USENIX Security 26 - PICS: Private Intersection over Committed (and reusable) SetsSREcon26 Europe/Middle East/Africa - Safe, Empowered, Tired: The Human Side of 24x7 Banking SRE...WOOT 26 - Swarm in EM Hay: Particle Swarm-guided Probe Placement for EM SCA
USENIX |

USENIX Security '26 - Interpolation-Based Optimization for Enforcing lp-Norm Metric Differential Pr…

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER