PAC Security: Automatic Privacy Measurement and Control of Data Processing
share
We propose and study a new privacy definition, termed Probably Approximately Correct (PAC) Security. PAC security characterizes the information-theoretic hardness to recover sensitive data given arbitrary information disclosure/leakage during/after any processing. Unlike the classic cryptographic definition and Differential Privacy (DP), which consider the adversarial (input-independent) worst case, PAC security is a simulatable metric that accommodates priors and quantifies the instance-based impossibility of inference. A fully automatic analysis and proof generation framework is proposed, where security parameters can be produced with arbitrarily high confidence via Monte-Carlo simulation for any black-box data processing oracle. This appealing automation property enables analysis of complicated data processing, where the worst-case proof in the classic privacy regime could be loose or even intractable. Furthermore, we show that the magnitude of (necessary) perturbation required in PAC security is not explicitly dependent on dimensionality, which is in contrast to the worst-case information-theoretic lower bound. We also include practical applications of PAC security with comparisons.
READ FULL TEXT