The Power of Linear Reconstruction Attacks

By Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam D. Smith. 2012

54 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability, Safety, Robustness & Interpretability, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Safety, Robustness & Interpretability

In Privacy & Security

Citations in the corpus

Privacy in Pharmacogenetics: An End-to-End Case Study of Personalized Warfarin Dosing (2014, neutral): “Furthermore, recent theoretical work [24] has shown that in some settings, including certain applications of linear regression, incorporating noise into query results preserves attribute privacy.”
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “[32] show how the results of many convex ERM problems can be combined to carry out reconstruction attacks in the spirit of Dinur and Nissim [16].”
Private Multiplicative Weights Beyond Linear Queries (2014, methodology): “Our approach is inspired by the work of Kasiviswanathan, Rudelson, and Smith [23] who prove lower bounds on the error required for answering certain CM queries.”
Model Inversion Attacks that Exploit Confidence Information and Basic Countermeasures (2015, background): “Kasiviswanathan, Rudel-son, and Smith [22] extended these attacks to releases that are non-linear, such as M -estimators.”
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “[26] show how the results of many convex ERM problems can be combined to carry out reconstruction attacks in the spirit of [13].”
The Unintended Consequences of Overfitting: Training Data Inference Attacks (2017, background): “Linear reconstruction attacks [45, 46, 47] attempt to infer partial inputs to linear statistics, and were later extended to non-linear statistics [48].”
A Methodology for Formalizing Model-Inversion Attacks (2016, background): “The second kind of attack is against attribute privacy, which is a general concept where one studies how much distortion is needed in order to prevent an adversary from inferring sensitive attributes from non-sensitive ones (for concreteness, see for example reconstruction attacks [4], [5]).”
Exposed! A Survey of Attacks on Private Data (2017, methodology): “This general connection was used by Kasiviswanathan et al. (2010, 2013) to get results for k-way marginal releases and several more general kinds of releases, including the logistic regression example at the beginning of this section.”
Privacy Risk in Machine Learning: Analyzing the Connection to Overfitting (2017, background): “Linear reconstruction attacks [52], [53], [54] attempt to infer partial inputs to linear statistics and were later extended to non-linear statistics [55].”