The Power of Linear Reconstruction Attacks

Introduction

The goal of private data analysis is to provide global, statistical properties of a database of sensitive information while protecting the privacy of the individuals whose records the database contains. There is a vast body of work on this problem in statistics and computer science.

Until a few years ago, most schemes proposed in the literature lacked rigor: typically, the schemes had either no formal privacy guarantees or ensured security only against a specific suite of attacks. The seminal results of Dinur and Nissim and Dinur, Dwork and Nissim initiated a rigorous study of the tradeoff between privacy and utility. The notion of differential privacy (Dwork, McSherry, Nissim and Smith , Dwork ) that emerged from this line of work provides rigorous guarantees even in the presence of a malicious adversary with access to arbitrary side information. Differential privacy requires, roughly, that any single individual’s data have little effect on the outcome of the analysis. Recently, many techniques have been developed for designing differentially private algorithms. A typical objective is to release as accurate an approximation as possible to some high-dimensional function $f$ evaluated on the database $D$.

A complementary line of work seeks to establish lower bounds on how much distortion is necessary for particular functions $f$. Some of these bounds apply only to specific notions of privacy (e.g., lower bounds for differential privacy ). A second class of bounds rules out any reasonable notion of privacy by giving algorithms to reconstruct almost all of the data $D$ given sufficiently accurate approximations to $f(D)$ . We refer to the latter results as reconstruction attacks.

We consider reconstruction attacks against attribute privacy: consider a 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). This setting is widely considered in the applied data privacy literature, partly since it arises with medical and retail data.

Asymptotically, we say that a mechanism is attribute nonprivate if there is an infinite sequence of $n$ for which $\mathcal{M}$ allows $(o(1),o(1))$-reconstruction. Here $d=d(n)$ is a function of $n$. We say the attack $\mathcal{A}$ is efficient if it runs in time $\mbox{poly}(n,d)$.

Instead of simply showing that a setting of $U$ exists, we will normally aim to show that reconstruction is possible with high probability when $U$ is chosen from one of a class of natural distributions.

Such attacks were first considered in the context of data privacy by Dinur and Nissim . They showed that any mechanism which answers (or allows the user to compute) $\Omega(n\log n)$ random inner product queries with $\{0,1\}$ vectors on a database ${\mathbf{s}}\in\{0,1\}^{n}$ with $o(\sqrt{n})$ noise per query is not private. That is, they assume that the mechanism releases $\mathbf{y}=A{\mathbf{s}}+\mathbf{e}$, where $A$ is a random matrix in $\{0,1\}^{\Omega(n\log n)\times n}$ and $\mathbf{e}$ is a noise vector with $\|\mathbf{e}\|_{\infty}=o(\sqrt{n})$. Their attack was subsequently extended to use a linear number of queries , allow a small fraction of answers to be arbitrarily distorted , and run significantly more quickly .

In their simplest form, such inner product queries require the adversary to be able to “name rows”, that is, specify a coefficient for each component of the vector ${\mathbf{s}}$. Thus, the lower bound does not seem to apply to any functionality that is symmetric in the rows of the database (such as, for example, “counting queries”).​It was pointed out in that in databases with more than one entry per row, random inner product queries on the sensitive attribute vector ${\mathbf{s}}$ can be simulated via hashing: for example, the adversary could ask for the sum the function $H(U_{i})\cdot s_{i}$ over the whole database, where $H:\{0,1\}^{d-1}\to\{0,1\}$ is an appropriate hash function. This is a symmetric statistic, but it is unlikely to come up in a typical statistical publication.

Recently, linear attacks were also considered based on range query releases (which, again, are natural, linear queries).

We greatly expand the applicability of linear attacks in “natural” settings. Specifically, we show one can mount linear reconstruction attacks based on any release that gives:

the fraction of records that satisfy a given non-degenerate boolean function (a boolean function over $p$ variables is non-degenerate if its multilinear representation has degree exactly $p$). Such releases include contingency tables as well as more complex outputs like the error rate of certain classifiers such as decision trees; or

the $M$-estimator associated with a differentiable loss function. $M$-estimators are a broad class of estimators which are obtained by minimizing sums of functions of the records (they are also called empirical risk minimization estimators). $M$-estimators include the standard estimators for linear and logistic regression (both these estimators are associated with differentiable loss functions). See Section 4 for definitions.

Our contributions are two-fold. First, we show how these types of releases can be transformed into a (noisy) linear release problem, making them amenable to linear reconstruction attacks. This is already perhaps surprising, since many of the above statistics (like $M$-estimators) are obtained by solving highly nonlinear formulations. After performing this transformation, we can apply polynomial-time methods (like least squares or LP decoding) on this linear release problem to estimate the sensitive data.

Second, we show how to analyze these attacks under various distributional assumptions on the data. This gives lower bounds on the noise needed to release these statistics attribute privately. Specifically, we consider a setting in which the same statistic (either 1 or 2 above) is released about how the sensitive attribute relates to all subsets of (constant) size $k$ (out of a total of $d$) nonsensitive boolean attributes. For a subset $J\subseteq[d]$ of size $k$, let $U|_{J}$ denote the submatrix of $U$ consisting of the columns in $J$.

The $\binom{d}{k}$ entries for a statistic are obtained by evaluating the same statistic on $(U|_{J}|{\mathbf{s}})$ for all sets $J$ of size $k$. Specifically:

Consider a mechanism which releases, for every set $J$ of size $k$, a particular $M$-estimator evaluated over $(U|_{J}|{\mathbf{s}})$. We show that if the mechanism adds $o(1/(\lambda\sqrt{n}))$ noise per entry and if $d=\Omega(n)$, then it is attribute non-private. Here, $\lambda$ is the Lipschitz constant of the loss function gradient. The loss function also needs to satisfy a mild variance condition. For the case of linear and logistic regression estimators, $\lambda=\Theta(1)$ for bounded data, and so the noise bound is $o(1/\sqrt{n})$.

The statements above are based on the least squares attack. For most settings, we show the LP decoding attack can also handle a constant fraction of entries with arbitrarily high noise (the exception is the setting of general $M$-estimators).

Casting the releases as a system of linear equations requires two simple insights which we hope will be broadly useful. First, we note that when ${\mathbf{s}}=(s_{1},\ldots,s_{n})$ is boolean, then any release which allows us to derive an equation which involves a sum over database records can in fact be made linear in ${\mathbf{s}}$. Specifically, suppose we know that $\sum_{i}g_{i}(s_{i})=t$, where $t$ is a real number and $g_{i}$ is an arbitrary real-valued function that could depend on the index $i$, the public record $U_{i}$, and any released information. We can rewrite $g_{i}(s_{i})$ as $g_{i}(0)+s_{i}(g_{i}(1)-g_{i}(0))$; the constraint $\sum_{i}g_{i}(s_{i})=t$ can then be written as $\sum_{i}s_{i}\cdot(g_{i}(1)-g_{i}(0))=t-\sum_{i}g_{i}(0)$, which is affine in ${\mathbf{s}}$. This allows us to derive linear constraints from a variety of not-obviously-linear releases; for example, it allows us to get linear attacks based on the error rate of a given binary classifier (see Section 3).

The techniques just mentioned give rise to a variety of linear reconstruction attacks, depending on the type of released statistics. We can provide theoretical guarantees on the performance of these attacks in some settings, for example when the same statistic is released about many subsets of the data (e.g., all sets of a given size $k$) and when the data records themselves are drawn i.i.d. from some underlying distribution. The main technique here is to analyze the geometry of the constraint matrix $A$ that arises in the attack. For the case of non-degenerate boolean functions, we do so by relating the constraint matrix to a row-wise product of a matrix with i.i.d. entries (referred to as a random row product matrix, see Section 3.2.1), which was recently analyzed by Rudelson (see also ). The results of showed that the least singular value of a random row product matrix is asymptotically the same as that of a matrix of same dimensions with i.i.d. entries, and a random row product matrix is a Euclidean section. Our results show that a much broader class of matrices with correlated rows satisfy these properties.

In Section 2, we introduce some notation and review the least squares and LP decoding techniques for solving noisy linear systems. In Section 3, we present our results on evaluating non-degenerate boolean functions. As mentioned earlier, we first reduce the release problem to a linear reconstruction problem (Section 3.1), and then the attacks works by using either least squares or LP decoding techniques. The analysis requires analyzing spectral and geometric properties of the constraint matrix that arises in these attack which we do in Section 3.2. In Section 4, we present our results on releasing $M$-estimators associated with differentiable loss functions. For clarity, we first discuss the attacks for the special cases of linear and logistic regression estimators (in Section 4.1), and then discuss the attacks for the general case (in Section 4.2).

Preliminaries

Let $M$ be an $N\times n$ real matrix with $N\geq n$. The singular values $\sigma_{j}(M)$ are the eigenvalues of $\sqrt{M^{\top}M}$ arranged in non-increasing order. Of particular importance in this paper is the least singular value $\sigma_{n}(M)=\inf_{\mathbf{z}:\|\mathbf{z}\|=1}\|M\mathbf{z}\|$. The unit sphere in $n$ dimensions centered at origin is denoted by $S^{n-1}=\{\mathbf{z}\,:\,\|\mathbf{z}\|=1\}$.

1 Background on Noisy Linear Systems.

Noisy linear systems arise in a wide variety of statistical and signal-processing contexts. Suppose we are given a matrix $A$ and vector $\mathbf{z}$ such that $\mathbf{z}=A{\mathbf{s}}+\mathbf{e}$, where $\mathbf{e}$ is assumed to be “small” (in a sense defined below). A natural approach to estimating ${\mathbf{s}}$ is to output $\hat{\mathbf{s}}=\mbox{argmin}_{{\mathbf{s}}}\,\|A{\mathbf{s}}-\mathbf{z}\|_{p}$ for some $p\geq 1$. We will consider $p=1$ and $2$; we summarize the assumptions and guarantees for each method below. When it is known that ${\mathbf{s}}\in\{0,1\}^{n}$, the attacker can then round the entries of $\hat{\mathbf{s}}$ to the nearer of $\{0,1\}$ to improve the estimate.

Widely used in regression problems, the least squares method guarantees a good approximation to ${\mathbf{s}}$ when the Euclidean norm $\|\mathbf{e}\|$ is small and $A$ has no small eigenvalues. It was first used in data privacy by Dwork and Yekhanin . For completeness, we present the entire analysis of this attack (in a general setting) here.

Let $A=P\Sigma Q^{\top}$ be the singular value decomposition of $A$. Here, $P$ is an orthogonal $m\times m$ matrix, $\Sigma$ is a diagonal $m\times n$ matrix, and $Q$ is an orthogonal $n\times n$ matrix. Let $\mathbf{0}_{n\times(m-n)}$ be an $n\times(m-n)$ matrix with all entries zero. Define

In the context of privacy, the “LP decoding” approach was first used by Dwork et al. . (The name stems from the fact that the minimization problem can be cast as a linear program.) The LP attack is slower than the least squares attack but can handle considerably more complex error patterns at the cost of a stronger assumption on $A$. Recently, De gave a simple analysis of this attack based on the geometry of the operator $A$. We need the following definition of Euclidean section.

Note that by Cauchy-Schwarz, the first inequality, $\sqrt{m}\|A{\mathbf{s}}\|\geq\|A{\mathbf{s}}\|_{1}$, always holds. We remark that when we say $A$ is Euclidean, we simply mean that there is some constant $\alpha>0$ such that $A$ is $\alpha$-Euclidean.

The following theorem gives a sufficient condition under which LP decoding gives a good approximation to ${\mathbf{s}}$. The time bound here was derived from the LP algorithm of Vaidya , which uses $O(((N_{1}+N_{2})N_{2}^{2}+(N_{1}+N_{2})^{1.5}N_{2})N_{3})$ arithmetic operations where $N_{1}$ is the number of constraints, $N_{2}$ is the number of variables, and $N_{3}$ is a bound on the number of bits used to describe the entries of $A$. In our setting, the LP has $n$ variables, $m$ constraints, and $N_{3}$ could be upper bounded by $mn$, and therefore the LP could be solved in $O(m^{2}n^{3}+m^{2.5}n^{2})$ time.

Releasing Evaluations of Non-Degenerate Boolean Functions

In this section, we analyze privacy lower bounds for releasing evaluations of non-degenerate boolean functions. We use the following standard definition of representing polynomial (see Appendix A for a background about representing boolean functions as multilinear polynomials).

A polynomial $P^{(f)}$ over the reals represents a function $f$ over $\{0,1\}^{k+1}$ if $f(x_{1},\ldots,x_{k+1})=P^{(f)}(x_{1},\ldots,x_{k+1})$ for all $(x_{1},\ldots,x_{k+1})\in\{0,1\}^{k+1}$.

A function $f:\{0,1\}^{k+1}\to\{0,1\}$ is non-degenerate iff it can be written as a multilinear polynomial of degree $k+1$.

If $f$ is non-degenerate, then it depends on all of its $k+1$ variables. Note that non-degenerate functions constitute a large class of functions.​A simple counting argument shows that among the $2^{2^{k+1}}$ boolean functions over $k+1$ variables, $2^{2^{k+1}}-\binom{2^{k+1}}{2^{k}}$ are non-degenerate. For example, it includes widely used boolean functions like AND, OR, XOR, MAJORITY, and depth $k+1$ decision trees .

Let $f:\{0,1\}^{k+1}\to\{0,1\}$ represent the function that we want to evaluate on a database $D$. Let $D=(U|{\mathbf{s}})\in(\{0,1\})_{n\times(d+1)}$, where $U\in(\{0,1\})_{n\times d}$ and ${\mathbf{s}}\in\{0,1\}^{n}$. Let $U=(\delta_{i,j})$, i.e., $\delta_{i,j}$ denotes the $(i,j)$th entry in $U$ (with $1\leq i\leq n$ and $1\leq j\leq d$). Let

Note that $J$ allows repeated entries.​We allow repeated entries for convenience of notation. Our results also hold if we use the more natural $J\subseteq[d]$, $|J|=k$. Let $D|_{J}$ be the submatrix of $D$ restricted to columns indexed by $J$. For a fixed $J$, define $F(D|_{J})$ as

Note that $F(D|_{J})$ is an integer between to $n$. Let $\Sigma_{f}(D)$ be the vector obtained by computing $F$ on all different $D|_{J}$’s: $\Sigma_{f}(D)=(F(D|_{J}))\mbox{ where }J\in\{1,\ldots,d\}^{k}$. Note that $\Sigma_{f}(D)$ is a vector of length $d^{k}$. The goal is to understand how much noise is needed to attribute privately release $\Sigma_{f}(D)$ (or $\Sigma_{f}(D)/n$) when $f$ is non-degenerate.

Let $f:\{0,1\}^{k+1}\to\{0,1\}$ be a non-degenerate boolean function. Then

any mechanism which for every database $D\in(\{0,1\})_{n\times(d+1)}$ with $n\ll d^{k}$ releases $\Sigma_{f}(D)$ by adding $o(\sqrt{n})$ (or releases $\Sigma_{f}(D)/n$ by adding $o(1/\sqrt{n})$) noise to each entry is attribute non-private. The attack that achieves this non-privacy violation runs in $O(d^{k}n^{2})$ time.

there exists a constant $\gamma>0$ such that any mechanism which for every database $D\in(\{0,1\})_{n\times(d+1)}$ with $n\ll d^{k}$ releases $\Sigma_{f}(D)$ by adding $o(\sqrt{n})$ (or releases $\Sigma_{f}(D)/n$ by adding $o(1/\sqrt{n})$) noise to at most $1-\gamma$ fraction of the entries is attribute non-private. The attack that achieves this non-privacy violation runs in $O(d^{2k}n^{3}+d^{2.5k}n^{2})$ time.

For convenience of notation, in this section, we work mostly with the transpose of $U$. Let $T=U^{\top}$. So $T$ is a $d\times n$ matrix.

1 Reducing to a Linear Reconstruction Problem.

In this section, we reduce the problem of releasing $\Sigma_{f}(D)$ for a database $D$ into a linear reconstruction problem. First, we define a simple decomposition of boolean functions. Consider a non-degenerate boolean function $f\,:\{0,1\}^{k+1}\to\{0,1\}$. Now there exists two function $f_{0}\,:\,\{0,1\}^{k}\to\{0,1\}$ and $f_{1}\,:\,\{0,1\}^{k}\to\{0,1\}$ such that

Define $f_{2}(\delta_{1},\ldots,\delta_{k})=f_{1}(\delta_{1},\ldots,\delta_{k})-f_{0}(\delta_{1},\ldots,\delta_{k})$. Therefore,

Note that $f_{2}$ is a function from $\{0,1\}^{k}\to\{-1,0,1\}$. Since both $f_{0}$ and $f_{1}$ are both boolean functions and can be represented as multilinear polynomials over the variables $\delta_{1},\ldots,\delta_{k}$, therefore $f_{2}$ also could be represented as a multilinear polynomial over the variables $\delta_{1},\ldots,\delta_{k}$. Since $f$ is represented by a multilinear polynomial of degree $k+1$, therefore, the multilinear polynomial representing $f_{2}$ has degree $k$ (if it has any lower degree, then $f$ could be represented as multilinear polynomial of degree strictly less than $k+1$, which is a contradiction). To aid our construction, we need to define a particular function of matrices.

Let $h$ be a function from $\{0,1\}^{k}\to\{-1,0,1\}$. Let $T_{(1)}=(\delta^{(1)}_{i,j}),T_{(2)}=(\delta^{(2)}_{i,j}),\ldots,T_{(k)}=(\delta^{(k)}_{i,j})$ be $k$ matrices with $\{0,1\}$ entries and dimensions $d\times n$. Define a row function matrix (of dimension $d^{k}\times n$) $\Pi_{h}(T_{(1)},\ldots,T_{(k)})$ as follows. Any row of this matrix will correspond to a sequence

of $k$ numbers, so the entries of $\Pi_{h}(T_{(1)},\ldots,T_{(k)})$ will be denotedThe definition assumes a certain order of the rows of the matrix $\Pi_{h}(T_{(1)},\ldots,T_{(k)})$. This order, however, is not important, for our analysis. Note that changing the relative positions of rows of a matrix doesn’t affect its eigenvalues and singular values. by $\pi_{J,a}$, where $a\in\{1,\ldots,n\}$. For $J=(j_{1},j_{2},\ldots,j_{k})$ the entries of the matrix $\Pi_{h}(T_{(1)},\ldots,T_{(k)})$ will be defined by the relation

The row product matrices from (see Definition 6) is a particular example of this construction where the function $h(\delta_{1},\delta_{2},\ldots,\delta_{k})=\delta_{1}\cdot\delta_{2}\cdot\ldots\cdot\delta_{k},$, which implies that $\Pi_{h}(T_{(1)},\ldots,T_{(k)})=T_{(1)}\odot\dots\odot T_{(k)}$, where $\odot$ is the row-product operator from Definition 6.

Let $D=(U|{\mathbf{s}})$ be a database, and let $T=U^{\top}$. Let $U=(\delta_{i,j})$. Consider any fixed $J=(j_{1},\ldots,j_{k})\in\{1,\ldots,d\}^{k}$. Now for this $J$, there exists an entry in $\Sigma_{f}(D)$ equaling $\sum_{i=1}^{n}f(\delta_{i,j_{1}},\ldots,\delta_{i,j_{k}},s_{i})$. Now consider the matrices $\Pi_{f_{2}}(T,\ldots,T)$ and $\Pi_{f_{0}}(T,\ldots,T)$. Consider the rows in $\Pi_{f_{0}}(T,\ldots,T)$ and $\Pi_{f_{2}}(T,\ldots,T)$ corresponding to this above $J$. Let this be the $l$th row in these matrices. Then the $l$th row of the matrix $\Pi_{f_{0}}(T,\ldots,T)$ has $n$ entries equaling $f_{0}(\delta_{i,j_{1}},\ldots,\delta_{i,j_{k}})$ and the $l$th row of the matrix $\Pi_{f_{2}}(T,\ldots,T)$ has $n$ entries equaling $f_{2}(\delta_{i,j_{1}},\ldots,\delta_{i,j_{k}})$ for $i=1,\ldots,n$. Since

where $\Pi_{f_{0}}(T,\ldots,T)_{l}$ and $\Pi_{f_{2}}(T,\ldots,T)_{l}$ denote the $l$th row of matrices $\Pi_{f_{0}}(T,\ldots,T)$ and $\Pi_{f_{2}}(T,\ldots,T)$ respectively and $\mathbf{1}_{n}$ denotes the vector $(1)^{n}$. Now define a vector $H_{f}(D)$ whose $l$th element ($1\leq l\leq d^{k}$) is

The length of vector $H_{f}(D)$ is $d^{k}$. The above arguments show that all the entries of $H_{f}(D)$ are contained in the vector $\Sigma_{f}(D)$. Since every row in these $\Sigma_{f}(D)$ correspond to some $J$, it also follows that all the entries of $\Sigma_{f}(D)$ are contained in the vector $H_{f}(D)$, implying the following claim.

$\Sigma_{f}(D)=H_{f}(D)$.​Under proper ordering of both the vectors.

The privacy mechanism releases a noisy approximation to $\Sigma_{f}(D)$. Let $\mathbf{y}=(y_{1},\ldots,y_{d^{k}})$ be this noisy approximation. The adversary tries to reconstruct an approximation of ${\mathbf{s}}$ from $\mathbf{y}$. Let $b_{f_{i}}=\langle\Pi_{f_{0}}(T,\ldots,T)_{i},\mathbf{1}_{n}\rangle$, and $\mathbf{b}_{f}=(b_{f_{1}},\ldots,b_{f_{d^{k}}})$. Given $\mathbf{y}$, the adversary solves the following linear reconstruction problem:

In the setting of attribute non-privacy the adversary knows $T$, and therefore can compute $\Pi_{f_{2}}(T,\ldots,T)$ and $\Pi_{f_{0}}(T,\ldots,T)$ (hence, $\mathbf{b}_{f}$). The goal of the adversary is to compute a large fraction of ${\mathbf{s}}$ given $\mathbf{y}$. The definition of iterated logarithm $(\log_{(q)})$ is given in Definition 8. In the below analysis, we use a random matrix $\mathbf{T}$ and the least singular value lower bound on a random row function matrix from Theorem 3.9. We use boldface letters to denote random matrices.

Let $f:\{0,1\}^{k+1}\to\{0,1\}$ be a non-degenerate boolean function and $n\leq cd^{k}/\log_{(q)}d$ for a constant $c$ depending only on $k,q$. Any privacy mechanism which for every database $D\in(\{0,1\})_{n\times(d+1)}$ releases $\Sigma_{f}(D)$ by adding $o(\sqrt{n})$ (or releases $\Sigma_{f}(D)/n$ by adding $o(1/\sqrt{n})$) noise to each entry is attribute non-private. The attack that achieves this non-privacy violation runs in $O(d^{k}n^{2})$ time.

Consider the least squares attack outlined in Theorem 2.1 on Equation (3). Let $\mathbf{T}$ be a random matrix of dimension $d\times n$ with independent Bernoulli entries taking values and $1$ with probability $1/2$, and let database $D=(\mathbf{T}^{\top}|{\mathbf{s}})$ for some ${\mathbf{s}}\in\{0,1\}^{n}$. For analyzing the attack in Theorem 2.1, we need a lower bound on the least singular value of $\Pi_{f_{2}}(\mathbf{T},\ldots,\mathbf{T})$. The following claim follows from Theorem 3.9. Note that $f_{2}$ is a function over $k$ variables.

For function $f_{2}$ defined above and $n\leq cd^{k}/\log_{(q)}d$ (where $c$ is the constant from Theorem 3.8), the matrix $\Pi_{f_{2}}(\mathbf{T},\ldots,\mathbf{T})$ satisfies

Apply Theorem 3.9 with function $h=f_{2}$. ∎

Claim 2 shows that with exponentially high probability $\sigma_{n}(\Pi_{f_{2}}(\mathbf{T},\ldots,\mathbf{T}))=\Omega(\sqrt{d^{k}})$. Invoking Theorem 3.9 with $m=d^{k}$ and $\beta=o(\sqrt{n})$ shows that with exponentially high probability the adversary fails to recover only $o(n)$ entries of ${\mathbf{s}}$. Noise bound of $o(\sqrt{n})$ for releasing $\Sigma_{f}(D)$ translates into a noise bound of $o(1/\sqrt{n})$ for releasing $\Sigma_{f}(D)/n$. ∎

The LP decoding attack solves a slightly different reconstruction problem than Equation (3). The reason is because $\Pi_{f_{2}}(\mathbf{T},\ldots,\mathbf{T})$ is not a Euclidean sectionIf we take a matrix $\mathbf{T}$ of dimension $d\times n$ with independent Bernoulli entries taking values and $1$ with probability $1/2$, the resulting matrix $\Pi_{f_{2}}(\mathbf{T},\ldots,\mathbf{T})$ is not a Euclidean section. This is because the matrix $\mathbf{T}$ is non-centered (expectation of each entry in the matrix is $1/2$) which makes the $\left\|\Pi_{f_{2}}(\mathbf{T},\ldots,\mathbf{T})\right\|$ to be $\approx d^{k}$ instead of $\sqrt{d^{k}}$. (a property needed for applying Theorem 2.2). However, we show that a related reconstruction problem has all the properties needed for the LP decoding attack. The analysis goes via matrices with $\{1,-1\}$ entries which have the desired properties. We establish the Euclidean section property in Appendix B.

Let $D=(U|{\mathbf{s}})$ be a database, and let $T=U^{\top}$. Let $V=2T-\mathbf{1}_{d\times n}$ where $\mathbf{1}_{d\times n}$ is a $d\times n$ matrix of all $1$’s. Define $g\,:\,\{-1,1\}^{k+1}\to\{-1,1\}$ as

where $g_{1}:\{-1,1\}^{k}\to\{-1,1\}$ and $g_{-1}:\{-1,1\}^{k}\to\{-1,1\}$. Using the notation, $g_{1}=g_{1}(\phi_{1},\ldots,\phi_{k})$ and $g_{-1}=g_{-1}(\phi_{1},\ldots,\phi_{k})$, we get

Define $g_{2}=g_{2}(\phi_{1},\ldots,\phi_{k})=(g_{1}-g_{-1})/2$ and $g_{3}=g_{3}(\phi_{1},\ldots,\phi_{k})=(g_{1}+g_{-1})/2$. Let us denote $\delta_{i}=(1+\phi_{i})/2$. Using the decomposition of $f$ from Equation (1),

Using the notation, $f_{0}=f_{0}(\delta_{1},\ldots,\delta_{k})$ and $f_{2}=f_{2}(\delta_{1},\ldots,\delta_{k})$, and substituting the decomposition of $f$ and $g$ into Equation (4) gives:

Let $D=(U|{\mathbf{s}})$, $T=U^{\top}$, and $V=2T-\mathbf{1}_{d\times n}$. Then

Note that from the earlier established decomposition

The reminder of the proof follows by using Equation (5) along with the definition of row-function matrices (Definition 5). ∎

Then $\Sigma_{f}(D)_{i}=q_{g_{i}}+\langle\Pi_{g_{2}}(V,\ldots,V)_{i},{\mathbf{s}}\rangle$. Let $\mathbf{q}_{g}=(q_{g_{1}},\ldots,q_{g_{d^{k}}})$. We get

Let $\mathbf{y}$ be the noisy approximation to $\Sigma_{f}(D)$ released by the privacy mechanism. Given $\mathbf{y}$, the linear program that the adversary solves is:

The following theorem analyzes this attack using a random matrix $\mathbf{V}$.

Let $f:\{0,1\}^{k+1}\to\{0,1\}$ be a non-degenerate boolean function and let $n\leq cd^{k}/\log_{(q)}d$ for a constant $c$ depending only on $k,q$. Then there exists a constant $\gamma=\gamma(k,q)>0$ such that any mechanism which for every database $D\in(\{0,1\})_{n\times(d+1)}$ releases $\Sigma_{f}(D)$ by adding $o(\sqrt{n})$ (or releases $\Sigma_{f}(D)/n$ by adding $o(1/\sqrt{n})$) noise to at most $1-\gamma$ fraction of the entries is attribute non-private. The attack that achieves this non-privacy violation runs in $O(d^{2k}n^{3}+d^{2.5k}n^{2})$ time.

The proof uses the LP decoding attack outlined in Theorem 2.2 on Equation (7). Let $\mathbf{T}$ be a random matrix of dimension $d\times n$ with independent Bernoulli entries taking values and $1$ with probability $1/2$, and let database $D=(\mathbf{T}^{\top}|{\mathbf{s}})$ for some ${\mathbf{s}}\in\{0,1\}^{n}$ . Let $\mathbf{V}=2\mathbf{T}-\mathbf{1}_{d\times n}$. To use Theorem 2.2, we need to (i) establish that $\Pi_{g_{2}}(\mathbf{V},\ldots,\mathbf{V})$ is a Euclidean section and (ii) establish a lower bound on its least singular value. Since $g_{2}\,:\,\{-1,1\}^{k}\to\{-1,0,1\}$ has a representation as a multilinear polynomial of degree $k$, Theorem B.4 shows that $\Pi_{g_{2}}(\mathbf{V},\ldots,\mathbf{V})$ is with exponentially high probability a Euclidean section. Repeating an analysis similar to Theorem 3.9 shows that the least singular value of $\Pi_{g_{2}}(\mathbf{V},\ldots,\mathbf{V})$ is with exponentially high probability at least $\Omega(\sqrt{d^{k}})$. Hence, with exponentially high probability both of the following statements hold simultaneously: (i) $\Pi_{g_{2}}(\mathbf{V},\ldots,\mathbf{V})$ is a Euclidean section and (ii) $\sigma_{n}(\Pi_{g_{2}}(\mathbf{V},\ldots,\mathbf{V}))=\Omega(\sqrt{d^{k}})$.

Invoking Theorem 2.2 with $\beta=o(\sqrt{n})$, $a=\sqrt{n}$, $b=d^{k}$, and $\sigma=\Omega(\sqrt{d^{k}})$ shows that with exponentially high probability the adversary fails to recover only $o(n)$ entries of ${\mathbf{s}}$. This shows that the mechanism is attribute non-private.

In the running time analysis of Theorem 2.2, $m$ gets replaced by $d^{k}$, and $N_{3}$ by $d^{k}n$ (as the input matrix can be represented using $O(d^{k}n)$ bits). Noise bound of $o(\sqrt{n})$ for releasing $\Sigma_{f}(D)$ translates into a noise bound of $o(1/\sqrt{n})$ for releasing $\Sigma_{f}(D)/n$. ∎

2 Spectral and Geometric Properties of Random Row Function Matrices.

Analysis of our reconstruction attacks rely on spectral and geometric properties of random row function matrices that we discuss in this section. Rudelson and Kasiviswanathan et al. analyzed certain spectral and geometric properties of a certain class of correlated matrices that they referred to as row product matrices (or conjunction matrices). Our analysis builds upon these results. We first summarize some important definitions and useful results from in Section 3.2.1, and establish our least singular value bound in Section 3.2.2. The Euclidean section property is established in Appendix B.

For two matrices with the same number of columns we define the row product as a matrix whose rows consist of entry-wise product of the rows of original matrices.

Rudelson showed that if we take entry-wise product of $k$ independent random matrices of dimension $d\times n$, then the largest and the least singular values of the resulting row product matrix (which of dimension $d^{k}\times n$) is asymptotically the same order as that of a $d^{k}\times n$ matrix with i.i.d. entries. To formulate this result formally, we introduce a class of uniformly bounded random variables, whose variances are uniformly bounded below.

We would also need the notion of iterated logarithm ($\log_{(q)}$) that is defined as:

Let $k,q,n,d$ be natural numbers. Assume that $n\leq cd^{k}/\log_{(q)}d.$ Let $\mathbf{T}_{(1)},\ldots,\mathbf{T}_{(k)}$ be $k$ matrices with independent $\tau$-random entries and dimensions $d\times n$. Then the $k$-times entry-wise product $\mathbf{T}_{(1)}\odot\mathbf{T}_{(2)}\odot\dots\odot\mathbf{T}_{(k)}$ is a $d^{k}\times n$ matrix satisfying

The constants $c,C_{1},c_{1},C_{2}$ depends only on $k$ and $q$.

One of the main ingredients in proving the above theorem is following fact about the norm of row product matrices.

Let $\mathbf{T}$ be a matrix with independent $\tau$-random entries and dimension $d\times n$. Then the $k$-times entry-wise product $\mathbf{T}\odot\dots\odot\mathbf{T}$ is a $d^{k}\times n$ matrix satisfying

The constants $c_{3},c_{4}$ depends only on $k$.

The bound on the norm appearing in the above theorem (asymptotically) matches that for a $d^{k}\times n$ matrix with independent $\tau$-random entries (refer for more details).

2.2 Least Singular Value of Random Row Function Matrices.

We start by proving a simple proposition about functions that can be represented as multilinear polynomials. The main step behind the following proposition proof is the following simple fact about multilinear polynomials. Let $P^{(h)}$ be a multilinear polynomial representing function $h$, and let $(\delta_{1},\ldots,\delta_{k})\in\{0,1\}^{k}$ and $\delta_{i}^{\prime}\in\{0,1\}$ then

Let $h$ be a function from $\{0,1\}^{k}\to\{-1,0,1\}$ having a representation as a multilinear polynomial of degree $k$. Let $P^{(h)}$ denote this multilinear polynomial. Let $(\delta_{1},\ldots,\delta_{k}),(\delta_{1}^{\prime},\ldots,\delta_{k}^{\prime})\in\{0,1\}^{k}$. For $I\subseteq\{1,\ldots,k\}$ let $\delta(I)\in\{0,1\}^{k}$ be the point with coordinates $\delta_{j}(I)=\delta_{j}^{\prime}\text{ if }j\in I;\mbox{ and }\delta_{j}(I)=\delta_{j}\text{ if }j\notin I$. Then

where $1/c_{h}(k)$ is the coefficient of the monomial corresponding to all $k$ variables in the multilinear representation of $h$.

By definition, we know that for all $(\delta_{1},\ldots,\delta_{k})\in\{0,1\}^{k}$, $h(\delta_{1},\ldots,\delta_{k})=P^{(h)}(\delta_{1},\ldots,\delta_{k})$. Since $P^{(h)}$ is a linear function of $\delta_{1}$,

where $\frac{\partial\,}{\partial\delta_{1}}P^{(h)}$ denotes the partial derivative of $P^{(h)}(\delta_{1},\delta_{2},\ldots,\delta_{k})$ with respect to $\delta_{1}$. Repeating this for the other coordinates, we get

The last term in the right hand side is the coefficient of the polynomial $P^{(h)}(\delta_{1},\ldots,\delta_{k})$ corresponding to the monomial $\delta_{1}\cdot\ldots\cdot\delta_{k}$, and we denote it by $1/c_{h}(k)$. ∎

Let $T_{(1)},\ldots,,T_{(k)},T^{\prime}_{(1)},\ldots,T^{\prime}_{(k)}$ be $2k$ matrices with $\{0,1\}$ entries and dimensions $d\times n$. For a set $I\subseteq[k]$ denote $T_{(j)}(I)=T_{(j)}\text{ if }j\in I\mbox{ and }T_{(j)}(I)=T^{\prime}_{(j)}\text{ if }j\notin I$. Then the following holds,

Follows by a simple extension of Proposition 3.6 and using Definitions 5 and 6. ∎

Let $k,q,n,d$ be natural numbers. Assume that $n\leq cd^{k}/\log_{(q)}d$. Consider a $d\times n$ matrix $\mathbf{T}$ with independent Bernoulli entries taking values 0 and 1 with probability $1/2$. Let $h$ be a function from $\{0,1\}^{k}\to\{-1,0,1\}$ having a representation as a multilinear polynomial of degree $k$. Then the matrix $\Pi_{h}(\mathbf{T},\ldots,\mathbf{T})$ satisfies

The constants $c,C^{\prime},c_{1},c_{2}$ depend only on $k$ and $q$.

Let $d=2kd^{\prime}+l$, where $0\leq l<2k$. For $j=1,\ldots,k$ denote by $\mathbf{T}_{j}^{1}$ the submatrix of $\mathbf{T}$ consisting of rows $(2d^{\prime}(j-1)+1),\ldots,(2d^{\prime}(j-1)+d^{\prime})$, and by $\mathbf{T}_{j}^{0}$ the submatrix consisting or rows $(2d^{\prime}(j-1)+d^{\prime}+1),\ldots,2jd^{\prime}$. For a set $I\subseteq[k]$ denote

The last inequality follows since $\forall I$ $\Pi_{h}(\mathbf{T}_{(1)}(I),\ldots,\mathbf{T}_{(k)}(I))$ is a submatrix of $\Pi_{h}(\mathbf{T},\ldots,\mathbf{T})$, which implies that

The entries of the matrices $(\mathbf{T}_{1}^{1}-\mathbf{T}_{1}^{0}),\ldots,(\mathbf{T}_{k}^{1}-\mathbf{T}_{k}^{0})$ are independent $\tau$-random variables. Thus, Theorem 3.4 (note that $d^{\prime}=O(d))$ yields

which along with Equation (8) proves the theorem. Note that $c_{h}(k)$ can be bounded as a function of $k$ alone. ∎

Combining Theorem 3.8 with Cauchy-Schwarz’s inequality, we obtain a lower bound on the least singular value of $\Pi_{h}(\mathbf{T},\ldots,\mathbf{T})$. It is well known that the least singular value of a $d^{k}\times n$ matrix with independent $\tau$-random entries is $\approx d^{k}$. Therefore, we get that in spite of all the correlations that exist in $\Pi_{h}(\mathbf{T},\ldots,\mathbf{T})$ its least singular value is asymptotically the same order as that of an i.i.d. matrix.

The right-hand side probability could be bounded using Theorem 3.8 and the left-hand probability is exactly $\Pr\left[\sigma_{n}(\Pi_{h}(\mathbf{T},\ldots,\mathbf{T}))\leq C^{\prime}\sqrt{d^{k}}\right]$. ∎

Releasing M𝑀M-estimators

Let $D=(U|{\mathbf{s}})$ be a database dimension $n\times d+1$, and let $U$ be a real-valued matrix of dimension $n\times d$ and ${\mathbf{s}}\in\{0,1\}^{n}$ be a (secret) vector. Let $D=(\delta_{i,j})$. Consider the submatrix $D|_{J}$ of $D$, where $J\in\{1,\ldots,d\}^{k}$. Let $\hat{\theta}_{J}$ be the $M$-estimator for $D|_{J}$ defined as

where $U_{(i)_{j}}$ is the $j$th row in $U_{(i)}$. Then $M$-estimators $\hat{\theta}_{i}$ for $i\in[d/k]$ is obtained by solving

This gives a set of constraints over ${\mathbf{s}}$ which the adversary could use to construct $\hat{{\mathbf{s}}}$. For the case of linear and logistic regression, Equation (10) reduces to a form $U_{(i)}^{\top}{\mathbf{s}}-\mathbf{r}=0$, where $\mathbf{r}$ is a vector independent of ${\mathbf{s}}$. For general loss function, we would use the fact that ${\mathbf{s}}$ is binary and use a decomposition similar to Equation (1). The other issue is that the adversary gets only a noisy approximation of $\hat{\theta}_{1},\ldots,\hat{\theta}_{d/k}$ and we overcome this problem by using the Lipschitz properties of the gradient of the loss function.

In the next subsection, we focus on the standard MLE’s for linear and logistic regression. In Section 4.2, we consider general $M$-estimators. Here, we would require an additional variance condition on the loss function. We would use this following standard definition of Lipschitz continuous gradient.

Remark: Also, for any twice differentiable function $G$, $\lambda I\succeq\partial^{2}\,G(\mathbf{x})$ for all $\mathbf{x}$ (where $\partial^{2}\,G(\mathbf{x})$ denotes the Hessian matrix) .

1 Releasing Linear and Logistic Regression Estimators.

In this section, we establish distortion lower bounds for attribute privately releasing linear and logistic regression estimators.

Logistic regression models estimate probabilities of events as functions of independent variables. Let $s_{i}$ be binary variable representing the value on the dependent variable for $i$th input, and the values of $k$ independent variables for this same case be represented as $x_{i,j}$ ($j=1,\ldots,k$). Let $n$ denote the total sample size, and let $\zeta_{i}$ denote the probability of success $(\Pr[s_{i}=1]$). The design matrix of independent variables, $X=(x_{i,j})$, is composed of $n$ rows and $k$ columns.

The logistic regression model equates the logit transform, the log-odds of the probability of a success, to the linear component:

where the notation $\mbox{vert}(\cdot,\ldots,\cdot)$ denotes vertical concatenation of the argument matrices/vectors. Our analysis will require a bound on the Lipschitz constant of the gradient of the log-likelihood function, which we bound using the following claim.

Let $U=(U_{(1)}|,\ldots,|U_{(d/k)})$, where each $U_{(i)}$ is an $n\times k$ matrix (assume $d$ is a multiple of $k$). Let $\hat{\theta}_{i}$ be the solution to the MLE equation

This reduction is very similar to the linear regression case. As before let $U=(U_{(1)}|,\ldots,|U_{(d/k)})$. Let $\hat{\theta}_{i}$ be the solution to the MLE equation

In the following analysis, we use a random matrix for $U$ where each entry of the random matrix is an independent $\tau$-random variable (Definition 7).

Let us first look at the least squares attack. Let $\mathbf{e}=(e_{1},\ldots,e_{d})$ (i.e., $\mathbf{e}$ is the error vector). We have $\mathbf{U}_{(i)}^{\top}\mathbf{U}_{(i)}\leq n$ for all $i\in[d]$ (as $\mathbf{U}$ is a $\tau$-random matrix, all entries in the matrix are at most $1$, and $\mathbf{U}_{(i)}$ is the $i$th column in $\mathbf{U}$). The least squares attack produces an estimate $\hat{{\mathbf{s}}}$ by solving:

The remaining analysis is similar to Theorem 2.1, except that again each error term $e_{i}$ is scaled up by a factor (at most) $n$. Since $\mathbf{U}$ is a $\tau$-random matrix, it is well-known that if $d\geq 2n$, then the least singular value of $\mathbf{U}$ is with exponentially high probability $\Omega(\sqrt{d})$ (see, e.g., ). Therefore, if a privacy mechanism adds $o(\sqrt{n})/n$The $n$ in the denominator is because of the scaling of the noise $\mathbf{e}$. noise to each $\hat{\theta}_{i}$, then the least squares attack with exponentially high probability recovers $1-o(1)$ fraction of the entries in ${\mathbf{s}}$. The time for executing this attack is $O(dn^{2})$ as the attack requires computing the SVD of a $d\times n$ matrix.

The LP decoding attack produces an estimate $\hat{{\mathbf{s}}}$ by solving:

where $\Lambda_{\mbox{log}}=\mathbf{U}_{(i)}^{\top}\mathbf{U}_{(i)}\leq n$ (using Claim 4). Therefore,

The least squares attack produces an estimate $\hat{{\mathbf{s}}}$ by solving:

The remaining analysis follows as in the linear regression case (from Theorem 2.1) and again the errors are scaled by a factor (at most) $n$. Therefore, if a privacy mechanism adds $o(\sqrt{n})/n=o(1/\sqrt{n})$ noise to each $\hat{\theta}_{i}$, then the least squares attack with exponentially high probability recovers $1-o(1)$ fraction of the entries in ${\mathbf{s}}$. The time for executing this attack is $O(dn^{2})$.

The LP decoding attack produces an estimate $\hat{{\mathbf{s}}}$ by solving:

Again like in the linear regression case (using Theorem 2.2), we get that any mechanism that adds $o(\sqrt{n})/n=o(1/\sqrt{n})$ noise to at most $1-\gamma$ fraction of the $\hat{\theta}_{i}$’s is attribute non-private. The time for executing this attack is $O(d^{2}n^{3}+d^{2.5}n^{2})$. ∎

Compared to Theorems 3.2 and 3.3, this above theorem requires a much larger $d$ (about $O(n)$). However, it is possible to reduce to dependence on $d\approx n^{O(1/k)}$ if the released statistic is a degree $k$ polynomial kernel of these regression functions. We defer the details to the full version.

2 Releasing General M𝑀M-estimators.

In this section, we establish distortion lower bounds for attribute privately releasing $M$-estimators associated with differentiable loss functions.

Now the $M$-estimator ($\hat{\theta}_{i}$) between $U_{(i)}$ and ${\mathbf{s}}$ can be found by setting $\partial\,\mathcal{L}(\theta;(U_{(i)},{\mathbf{s}}))=0$. Therefore, $\hat{\theta}_{i}$ is the solution to (ignoring the scaling multiplier $1/n$)

Let $D=(\mathbf{U}|{\mathbf{s}})$, where $\mathbf{U}$ is a $\tau$-random matrix of dimension $n\times d$ .