EUVIMEDEUVIMED entdecken
Crossref

Verified Foundations for Differential Privacy

Markus de Medeiros, Muhammad Naveed, Tancrède Lepoint, Temesghen Kahsai, Tristan Ravitch, Stefan Zetzsche, Anjali Joshi, Joseph Tassarotti, Aws Albarghouthi, Jean-Baptiste Tristan

Proceedings of the ACM on Programming Languages · 10.06.2025 · 9 (PLDI) · 1094-1118

DOI: 10.1145/3729294 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 13.06.2025. Verfasst von Markus de Medeiros und 9 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 51 Literaturangaben. Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Differential privacy (DP) has become the gold standard for privacy-preserving data analysis, but implementing it correctly has proven challenging. Prior work has focused on verifying DP at a high level, assuming either that the foundations are correct or that a perfect source of random noise is available. However, the underlying theory of differential privacy can be very complex and subtle. Flaws in basic mechanisms and random number generation have been a critical source of vulnerabilities in real-world DP systems. In this paper, we present SampCert, the first comprehensive, mechanized foundation for executable implementations of differential privacy. SampCert is written in Lean with over 12,000 lines of proof. It offers a generic and extensible notion of DP, a framework for constructing and composing DP mechanisms, and formally verified implementations of Laplace and Gaussian sampling algorithms. SampCert provides (1) a mechanized foundation for developing the next generation of differentially private algorithms, and (2) mechanically verified primitives that can be deployed in production systems. Indeed, SampCert’s verified algorithms power the DP offerings of Amazon Web Services, demonstrating its real-world impact. SampCert’s key innovations include: (1) A generic DP foundation that can be instantiated for various DP definitions (e.g., pure, concentrated, Rényi DP); (2) formally verified discrete Laplace and Gaussian sampling algorithms that avoid the pitfalls of floating-point implementations; and (3) a simple probability monad and novel proof techniques that streamline the formalization. To enable proving complex correctness properties of DP and random number generation, SampCert makes heavy use of Lean’s extensive Mathlib library, leveraging theorems in Fourier analysis, measure and probability theory, number theory, and topology.

Förderung

  • National Science Foundation

Zitieren

APA

Medeiros, M. D., Naveed, M., Lepoint, T., Kahsai, T., Ravitch, T., Zetzsche, S., Joshi, A., Tassarotti, J., Albarghouthi, A., & Tristan, J. (2025). Verified Foundations for Differential Privacy. Proceedings of the ACM on Programming Languages, 9(PLDI), 1094-1118. https://doi.org/10.1145/3729294

Vancouver

Medeiros MD, Naveed M, Lepoint T, Kahsai T, Ravitch T, Zetzsche S, et al. Verified Foundations for Differential Privacy. Proceedings of the ACM on Programming Languages. 2025;9(PLDI):1094-1118. doi:10.1145/3729294

BibTeX
@article{Medeiros2025,
  author = {Medeiros, Markus de and Naveed, Muhammad and Lepoint, Tancrède and Kahsai, Temesghen and Ravitch, Tristan and Zetzsche, Stefan and Joshi, Anjali and Tassarotti, Joseph and Albarghouthi, Aws and Tristan, Jean-Baptiste},
  title = {Verified Foundations for Differential Privacy},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2025},
  volume = {9},
  number = {PLDI},
  pages = {1094--1118},
  doi = {10.1145/3729294}
}
Kostenlos starten →