How to Break, Then Fix, Differential Privacy on Finite Computers

on YouTube ↗16m

" summary

Shows that naive floating-point Laplace implementations leak exact counts via precision-based attacks because some floats are unreachable, letting an adversary distinguish 100 vs 101. Tests find multiple open-source libraries affected, two still vulnerable and one fixed (opDP/Growth-like fixes). Presents a provable fix: generate the rounded sample directly using inverse-CDF interval sampling with arbitrary-precision floats/ARB, sampling many bits per iteration so it almost always finishes in one or two steps, preserves privacy without a discretization parameter and works in practice.

AI-written summary · about

" chapters (7)

1. 0:00Differential privacy vulnerabilities
2. 1:33Floating point breaks Laplace
3. 3:39Why standard random number generators fail
4. 5:25Noise precision loss
5. 8:34Fix for floating point issues
6. 12:27Inverse CDF sampling fix
7. 13:32Key takeaways and libraries

" related talks

• 32mYou've got trust issues, we've got solutions: Differential PrivacyVikram Waradpande · PyCon US 2024
• 27mVerified Differential Privacy for Finite ComputersMarco Gaboardi, Arthur Azevedo de Amorim, Vivien Rindisbacher · CoqPL 2023
• 58mLarge-Scale Private Learning, Part IIIIlya Mironov · Data Privacy: Foundations and Applications Boot Camp
• 01h 00mDifferential Privacy: Fundamentals to Forefront ICynthia Dwork · Cryptography Boot Camp 2015
• 43mDifferential Privacy Meets Robust StatisticsSewoong Oh · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 29mSecure, Precise, and Fast Floating-Point Operations on x86 ProcessorsAshay Rane, Calvin Lin, Mohit Tiwari · USENIX Security '16
• 26mA Framework for Adversarial Streaming via Differential Privacy and Difference EstimatorsIdan Attias, Edith Cohen, Moshe Shechner, Uri Stemmer · ITCS 2023
• 38mDemystifying Privacy Preserving ComputingTejas Chopra · Build Stuff 2024