The power of linear reconstruction attacks
From MaRDI portal
Abstract: We consider the power of linear reconstruction attacks in statistical data privacy, showing that they can be applied to a much wider range of settings than previously understood. Linear attacks have been studied before (Dinur and Nissim PODS'03, Dwork, McSherry and Talwar STOC'07, Kasiviswanathan, Rudelson, Smith and Ullman STOC'10, De TCC'12, Muthukrishnan and Nikolov STOC'12) but have so far been applied only in settings with releases that are obviously linear. Consider a database curator who manages a database of sensitive information but wants to release statistics about how a sensitive attribute (say, disease) in the database relates to some nonsensitive attributes (e.g., postal code, age, gender, etc). We show one can mount linear reconstruction attacks based on any release that gives: a) the fraction of records that satisfy a given non-degenerate boolean function. Such releases include contingency tables (previously studied by Kasiviswanathan et al., STOC'10) as well as more complex outputs like the error rate of classifiers such as decision trees; b) any one of a large class of M-estimators (that is, the output of empirical risk minimization algorithms), including the standard estimators for linear and logistic regression. We make two contributions: first, we show how these types of releases can be transformed into a linear format, making them amenable to existing polynomial-time reconstruction algorithms. This is already perhaps surprising, since many of the above releases (like M-estimators) are obtained by solving highly nonlinear formulations. Second, we show how to analyze the resulting attacks under various distributional assumptions on the data. Specifically, we consider a setting in which the same statistic (either a) or b) above) is released about how the sensitive attribute relates to all subsets of size k (out of a total of d) nonsensitive boolean attributes.
Recommendations
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Attacks on statistical databases: the highly noisy case
- Topics in Cryptology – CT-RSA 2005
- Private data release via learning thresholds
Cited in
(4)- Non-black-Box Computation of Linear Regression Protocols with Malicious Adversaries
- Linearization Attacks Against Syndrome Based Hashes
- A Survey of Differentially Private Regression for Clinical and Epidemiological Research
- Differentially private outcome-weighted learning for optimal dynamic treatment regime estimation
This page was built for publication: The power of linear reconstruction attacks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741811)
