PAC privacy: automatic privacy measurement and control of data processing

DOI10.1007/978-3-031-38545-2_20MaRDI QIDQ6145927zbMATH OpenOpenAlexFDO

Authors Hanshen Xiao, Srinivas Devadas

Publication date 2 February 2024

Published in Advances in Cryptology – CRYPTO 2023 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.03458

zbMATH Keywords

\(f\)-divergenceautomatic security proofinference hardnessinstance-based posterior advantagemembership attackmutual informationPAC privacyreconstruction hardness

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Database theory (68P15) Data encryption (aspects in computer science) (68P25) Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Abstract: We propose and study a new privacy definition, termed Probably Approximately Correct (PAC) Privacy. PAC Privacy 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 Privacy is a simulatable metric that quantifies the instance-based impossibility of inference. A fully automatic analysis and proof generation framework is proposed: 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. Moreover, we show that the produced PAC Privacy guarantees enjoy simple composition bounds and the automatic analysis framework can be implemented in an online fashion to analyze the composite PAC Privacy loss even under correlated randomness. On the utility side, the magnitude of (necessary) perturbation required in PAC Privacy is not lower bounded by Theta(sqrt{d}) for a d-dimensional release but could be O(1) for many practical data processing tasks, which is in contrast to the input-independent worst-case information-theoretic lower bound. Example applications of PAC Privacy are included with comparisons to existing works.

Recommendations

• The algorithmic foundations of differential privacy
• Pufferfish: a framework for mathematical privacy definitions
• Differential Privacy: A Survey of Results
• Differential privacy in new settings
• Differential Privacy

Cites work

• A near-optimal algorithm for differentially-private principal components
• A theory of the learnable
• Algorithmic stability for adaptive data analysis
• Amplification by shuffling: from local to central differential privacy via anonymity
• An Operational Approach to Information Leakage
• Communication Theory of Secrecy Systems*
• Concentrated differential privacy: simplifications, extensions, and lower bounds
• Cryptographic Hardware and Embedded Systems - CHES 2004
• Differentially private empirical risk minimization
• Distributed differential privacy via shuffling
• Gaussian Differential Privacy
• scientific article; zbMATH DE number 2090929 (Why is no real title available?)
• Mutual information analysis: a comprehensive study
• Noiseless database privacy
• On the geometry of differential privacy
• Optimal Noise Adding Mechanisms for Approximate Differential Privacy
• Path ORAM
• Private stochastic convex optimization: optimal rates in linear time
• Probabilistic encryption
• Statistical measurement of information leakage
• The complexity of computing the optimal composition of differential privacy
• Theory of Cryptography

This page was built for publication: PAC privacy: automatic privacy measurement and control of data processing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6145927)