Paper 2024/718

PAC-Private Algorithms

Mayuri Sridhar, Massachusetts Institute of Technology
Hanshen Xiao, Massachusetts Institute of Technology
Srinivas Devadas, Massachusetts Institute of Technology

Provable privacy typically requires involved analysis and is often associated with unacceptable accuracy loss. While many empirical verification or approximation methods, such as Membership Inference Attacks (MIA) and Differential Privacy Auditing (DPA), have been proposed, these do not offer rigorous privacy guarantees. In this paper, we apply recently-proposed Probably Approximately Correct (PAC) Privacy to give formal, mechanized, simulation-based proofs for a range of practical, black-box algorithms: K-Means, Support Vector Machines (SVM), Principal Component Analysis (PCA) and Random Forests. To provide these proofs, we present a new simulation algorithm that efficiently determines anisotropic noise perturbation required for any given level of privacy. We provide a proof of correctness for this algorithm and demonstrate that anisotropic noise has substantive benefits over isotropic noise. Stable algorithms are easier to privatize, and we demonstrate privacy amplification resulting from introducing regularization in these algorithms; meaningful privacy guarantees are obtained with small losses in accuracy. We also propose new techniques in order to canonicalize algorithmic output and convert intractable geometric stability verification into efficient deterministic stability verification. Thorough experiments are included, and we validate our provable adversarial inference hardness against state-of-the-art empirical attacks.

Available format(s)
Publication info
PAC PrivacyDifferential PrivacyBlack-box Security ProofInference HardnessMembership Attack
Contact author(s)
mayuri @ mit edu
hsxiao @ mit edu
devadas @ mit edu
2024-05-10: approved
2024-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mayuri Sridhar and Hanshen Xiao and Srinivas Devadas},
      title = {PAC-Private Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2024/718},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.