Paper 2024/718

PAC-Private Algorithms

Mayuri Sridhar, Massachusetts Institute of Technology
Hanshen Xiao, NVIDIA Research, Purdue University
Srinivas Devadas, Massachusetts Institute of Technology
Abstract

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 propose new techniques in order to reduce instability in 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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. Accepted at IEEE S&P 2025
Keywords
PAC PrivacyDifferential PrivacyBlack-box Security ProofInference HardnessMembership Attack
Contact author(s)
mayuri @ mit edu
hsxiao purdue @ gmail com
devadas @ mit edu
History
2024-10-08: last of 3 revisions
2024-05-10: received
See all versions
Short URL
https://ia.cr/2024/718
License
Creative Commons Attribution
CC BY

BibTeX

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