Multi-attribute privacy protection adapts to data types and dependencies
Beyond Monolithic Perturbation: Heterogeneous Mechanism Design for Multi-Attribute Metric Differential Privacy
Cryptography and Security
Summary
Protecting privacy in data that mixes different types of information, like numbers and categories, is tricky because the data pieces often relate to each other in complex ways. The authors propose a new way to protect such data that groups related attributes and chooses the best privacy method for each group instead of using one method for all. This approach balances privacy and usefulness better and is faster to compute than fully customized optimization. They test their method on real examples and find it improves results compared to simpler approaches.
What this means in practice
- •For data privacy engineers: Design privacy protections for mixed-type user data that better balance privacy and accuracy while managing computational resources.
- •For healthcare data teams: Improve anonymization of patient records containing various data types to maintain data utility for health analytics under privacy constraints.
Authors
Ruiyao Liu, Michael Oluwole, Chenxi Qiu
Abstract
Multi-attribute user records are inherently heterogeneous, often combining continuous, categorical, and binary attributes, and they frequently exhibit strong cross-attribute dependencies. Designing high-utility metric differential privacy (mDP) mechanisms for such records is challenging. Simple predefined mechanisms, such as distance-based noise, may be poorly aligned with task-specific utility loss, whereas fully optimization-based mechanisms can be computationally prohibitive for multi-attribute records. We propose Dependency-aware Heterogeneous Data Perturbation (DepHDP)}, a framework for multi-attribute mDP that combines dependency-aware attribute grouping with heterogeneous perturbation design. Rather than applying a one-size-fits-all mechanism, DepHDP selects an appropriate perturbation strategy for each attribute or attribute group, choosing between efficient predefined mechanisms, such as Laplace or Exponential mechanisms, and optimization-based designs. This selection is guided by both domain size and a predefined-noise adequacy criterion, which quantifies whether task-induced utility loss can be well explained by perturbation magnitude. To support scalable end-to-end optimization, DepHDP estimates group-level utility loss through sampling and lightweight surrogate modeling, and jointly optimizes privacy-budget allocation and group-wise mechanism design under a global $\ell_p$-metric mDP constraint. Across three case studies, DepHDP improves privacy--utility trade-offs over uniform baselines at lower computational cost than full-record OPT on evaluated domains.