SoK: Metric Differential Privacy in Theory and Practice
TL;DR
This Systematization of Knowledge paper synthesizes a decade of progress on mDP, clarifying mDP's foundations and its connections to central and local DP, and surveying three principal mDP mechanism families: homogeneous distance mechanisms, non-homogeneous distance mechanisms, and optimized perturbation mechanisms.
Abstract
Metric Differential Privacy (mDP) extends classical differential privacy (DP) by replacing Hamming adjacency with application-aware distance metrics, which offers utility-preserving protection for structured and continuous data including locations, trajectories, images, and text embeddings. This Systematization of Knowledge (SoK) paper synthesizes a decade of progress (2013-2025), clarifying mDP's foundations and its connections to central and local DP, and surveying three principal mDP mechanism families: homogeneous distance mechanisms, non-homogeneous distance mechanisms, and optimized perturbation mechanisms. We organize applications across geo-location privacy, text and embeddings, image and voice protection, graphs and network telemetry, and federated/edge settings. We also surface open challenges, including robust composition and adversarial modeling, context-adaptive privacy, high-dimensional scalability, and principled geometry-aware trade-off bounds, and distill practical guidance for selecting metrics, mechanisms, and metrics of utility. The goal is a unified reference and roadmap for deploying scalable, utility-preserving metric privacy in real-world systems.