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 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 - PICS: Private Intersection over Committed (and reusable) Sets
USENIX Security 26 - PICS: Private Intersection over Committed (and reusable) Sets
Aarushi Goel, Rutgers University; Peihan Miao and Phuoc Van Long Pham, Brown University; Satvinder Singh, Purdue University
Private Set Intersection (PSI) enables two parties to compute the intersection of their private sets without revealing any additional information. While maliciously secure PSI protocols prevent many attacks, adversaries can still exploit them by using inconsistent inputs across multiple sessions. This limitation stems from the definition of malicious security in secure multiparty computation, but is particularly problematic in PSI because: (1) real-world applications—such as Apples PSI protocol for CSAM detection and private contact discovery in messaging apps—often require multiple PSI executions over consistent inputs, and (2) the PSI functionality makes it relatively easy for adversaries to infer additional information.
We propose Private Intersection over Committed Sets (PICS), a new framework that enforces input consistency across multiple sessions via committed sets. Building on the state-of-the-art maliciously secure PSI framework (i.e., VOLE-PSI [EUROCRYPT 2021]), we present an efficient instantiation of PICS using lightweight cryptographic tools. Our protocol achieves strong receiver-side input consistency (i.e., the receiver uses the exact committed set) and weak sender-side input consistency (i.e., the sender cannot inject new elements into the committed set but can potentially use a subset of the committed set). We implement our protocol to demonstrate concrete efficiency. Compared to VOLE-PSI, our communication overhead is a small constant between 1.57 - 2.04× for set sizes between 216-224, and the total end-to-end running time overhead is 1.22 - 1.98× across various network settings.
View the full USENIX Security 26 program at https://www.usenix.org/conference/usenixsecurity26/technical-sessions USENIX Security 26 - PICS: Private Intersection over Committed (and reusable) Sets](https://i.ytimg.com/vi/Q6rhdJr_J4M/mqdefault.jpg)

