PAC-Private Algorithms

ePrint Report: PAC-Private Algorithms

Mayuri Sridhar, Hanshen Xiao, Srinivas Devadas

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 …

accuracy algorithms analysis attacks auditing differential privacy eprint report loss offer pac privacy private report verification