SoK: Metric Differential Privacy in Theory and Practice
Authors: Xinpeng Xie (University of North Texas), Chenyang Yu (University of North Texas), Yan Huang (University of North Texas), Yang Cao (Institute of Science Tokyo), Chenxi Qiu (University of North Texas)
Volume: 2026
Issue: 4
Pages: 415–437
DOI: https://doi.org/10.56553/popets-2026-0128
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.
Keywords: Metric Differential Privacy, Differential Privacy, Systematization of Knowledge
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
