Paper 2024/718
PAC-Private Algorithms
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)
- 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
-
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} }