The Power of Linear Reconstruction Attacks
  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.
