On the Geometry of Differential Privacy

Introduction

The problem of Privacy-preserving data analysis has attracted a lot of attention in recent years. Several databases, e.g. those held by the Census Bureau, contain private data provided by individuals, and protecting the privacy of those individuals is an important concern. Differential Privacy is a rigorous notion of privacy that allows statistical analysis of sensitive data while providing strong privacy guarantees even in the presence of an adversary armed with arbitrary auxiliary information. We refer the reader to the survey of Dwork [Dwo08] and the references therein for further motivation and background information.

We consider the following general setting: A database is represented by a vector $x\in\Re^{n}$. The queries that the analyst may ask are linear combinations of the entries of $x$. More precisely, a multidimensional query is a map $F\colon\Re^{n}\rightarrow\Re^{d}$, and we will restrict ourselves to linear maps $F$ with coefficients in the interval $$. Thus$F$is a$d\times n$matrix with entries in$$. In this work, we assume throughout that$d\leqslant n$. A mechanism is a randomized algorithm which holds a database$x\in\Re^{n}$, receives a query$F\colon\Re^{n}\to\Re^{d}$and answers with some$a\in\Re^{d}.$Informally, we say a mechanism satisfies differential privacy in this setting if the densities of the output distributions on inputs$x,x^{\prime}\in\Re^{n}$with$\|x-x^{\prime}\|_{1}\leqslant 1$are point wise within an$\exp(\varepsilon)$multiplicative factor of each other. Here and in the following,$\varepsilon>0$is a parameter that measures the strength of the privacy guarantee (smaller$\varepsilon$being a stronger guarantee). The error of a mechanism is the expected Euclidean distance between the correct answer$Fx$and the actual answer$a.$

In this work, we use methods from convex geometry to determine a nearly optimal trade-off between privacy and error. We will see a lower bound on how much error any differentially private mechanism must add. And we present a mechanism whose error nearly matches this lower bound.

As mentioned, the above setup is fairly general. To illustrate it and facilitate comparison with previous work, we will describe some specific instantiations below.

Suppose we have a database $y\in[n]^{N}$, containing private information about $N$ individuals. We can think of each individual as belonging to one of $n$ types. The database $y$ can then naturally be translated to a histogram $x\in\Re^{n}$, i.e., $x_{i}$ counts the number of individuals of type $i$. Note that in the definition of differential privacy, we require the mechanism to be defined for all $x\in\Re^{n}$ and demand that the output distributions be close whenever $\|x-x^{\prime}\|_{1}\leqslant 1$. This is a stronger requirement than asserting this property only for integer vectors $x$ and $x^{\prime}$. It only makes our upper bounds stronger. For the lower bounds, this strengthening allows us to ignore the discretization issues that would arise in the usual definition. However, our lower bounds can be extended for the usual definition for small enough $\varepsilon$ and large enough $N$ (see Appendix B). Now, our upper bound holds for any linear query on the histogram. This includes some well-studied and natural classes of queries. For instance, contingency tables (see, e.g., [BCD+07]) are linear queries on the histogram.

Private bits.

In the setting looked at by Dinur and Nissim [DN03], the database $y\in\{0,1\}^{N}$ consists of one private bit for each individual and each query ask for the number of $1$’s amongst a (random) subset on $[N]$. Given $d$ such queries, one can define $n\leqslant 2^{d}$ types of individuals, depending on the subset of the queries that ask about an individual. The vector $y$ then maps to a histogram $x$ in the natural way with $x_{i}$ denoting the number of individuals of type $i$ with their private bit set to $1$. Our results then imply a lower bound of $\Omega(d/\varepsilon)$ per answer for any $\varepsilon$-differentially private mechanism. This improves on the $\Omega(\sqrt{d})$ bound for $d=N$ from [DN03] for a weaker privacy definition (blatant non-privacy). A closely related rephrasing is to imagine each individual having $d$ private $\{0,1\}$ attributes so that $n=2^{d}$. The $d$ queries that ask for the $1$-way marginals of the input naturally map to a matrix $F$ and Theorem 1.1 implies a lower bound of $\Omega(d/\varepsilon)$ noise per marginal for such queries.

One can also look at $x$ itself as a database where each individuals private data is in $$; in this setting the dimension of the data$n$equals the number of individuals$N$. Our results lead to better upper bounds for this setting.

1 Our results

Recall, the term error refers to the expected Euclidean distance between the output of the mechanism and the correct answer to the query $F$.

As it turns out, when $F$ is a random Bernoulli $\pm 1$ matrix our upper bound matches the lower bound up to constant factors. In this case, $K$ is a random polytope and its volume and average Euclidean norm have been determined rather recently. Specifically, we apply a volume lower bound of Litvak et al. [LPRN05], and an upper bound on the average Euclidean norm due to Klartag and Kozma [KK09]. Quantitatively, we obtain the following theorem.

Let $\varepsilon>0$ and $d\leqslant n/2.$ Then, for almost all matrices $F\in\{-1,1\}^{d\times n}$,

any $\varepsilon$-differentially private mechanism $M$ has error $\Omega(d/\varepsilon)\cdot\min\{\sqrt{d},\sqrt{\log(n/d)}\}$.

the $K$-norm mechanism is $\varepsilon$-differentially private with error $O(d/\varepsilon)\cdot\min\{\sqrt{d},\sqrt{\log(n/d)}\}.$

We remark that Litvak et al. also give an explicit construction of a mapping $F$ realizing the lower bound.

Notice that the bound in the previous theorem differs from the lower bound by a factor of $L_{K}.$ A central conjecture in convex geometry, sometimes referred to as the “Hyperplane Conjecture” or “Slicing Conjecture” (see [KK09] for further information) states that $L_{K}=O(1).$

Unfortunately, in general the polytope $K$ could be very far from isotropic. In this case, both our volume-based lower bound and the $K$-norm mechanism can be quite far from optimal. We give a recursive variant of our mechanism and a natural generalization of our volume-based lower bound which are nearly optimal even if $K$ is non-isotropic.

While we restricted our theorems to $F\in^{d\times n}$, they apply more generally to any linear mapping $F.$

Our mechanism is an instantiation of the exponential mechanism and involves sampling random points from rather general high-dimensional convex bodies. This is why our mechanism is not efficient as it is. However, we can use rapidly mixing geometric random walks for the sampling step. These random walks turn out to approach the uniform distribution in a metric that is strong enough for our purposes. It will follow that both of our mechanisms can be implemented in polynomial time.

The mechanisms given in Theorem 1.2 and Theorem 1.5 can be implemented in time polynomial in $n,1/\varepsilon$ such that the stated error bound remains the same up to constant factors, and the mechanism achieves $\varepsilon$-differential privacy.

2 Previous Work

Queries of the kind described above have (total) sensitivity $d$, and hence the work of Dwork et al. [DMNS06] shows that adding Laplace noise with parameter $d/\varepsilon$ to each entry of $Fx$ ensures $\varepsilon$-differential privacy. Moreover, adding Laplace noise to the histogram $x$ itself leads to another private mechanism. Thus such questions can be answered with noise $\min(d/\varepsilon,\sqrt{n}/\varepsilon,N)$ per entry of $Fx$. Some specific classes of queries can be answered with smaller error. Nissim, Raskhodnikova and Smith [NRS07] show that one can add noise proportional to a smoothed version of the local sensitivity of the query, which can be much smaller than the global sensitivity for some non-linear queries. Blum, Ligett and Roth [BLR08] show that it is possible to release approximate counts for all concepts in a concept class $C$ on $\{0,1\}^{m}$ with error $O((N^{2}m{\rm VCDim}(C)/\varepsilon)^{\frac{1}{3}})$, where ${\rm VCDim}(C)$ is the VC dimension of the concept class. Their bounds are incomparable to ours, and in particular their improvements over the Laplacian mechanism kick in when the number of queries is larger than the size of the database (a range of parameters we do not consider). Feldman et al. [FFKN09] construct private core sets for the $k$-median problem, enabling approximate computation of the $k$-median cost of any set of $k$ facilities in $\Re^{d}$. Private mechanisms with small error, for other classes of queries have also been studied in several other works, see e.g. [BDMN05, BCD+07, MT07, CM08, GLM+10].

3 Overview and organization of the paper

In this section we will give a broad overview of our proof and outline the remainder of the paper.

Section 2 contains some preliminary facts and definitions. Specifically, we describe a linear program that defines the optimal mechanism for any set of queries. This linear program (also studied in [GRS09] for the one-dimensional case) is exponential in size, but in principle, given any query and error function, can be used to compute the best mechanism for the given set of queries. Moreover, dual solutions to this linear program can be used to prove lower bounds on the error. However, the asymptotic behavior of the optimum value of these programs for multi-dimensional queries was not understood prior to this work. Our lower bounds can be reinterpreted as dual solutions to the linear program. The upper bounds give near optimal primal solutions. Also, our results lead to a polynomial-time approximation algorithm for the optimum when $F$ is linear.

Indeed, using several results from convex geometry, we observe that our lower and upper bounds match up to constant factors when $F$ is drawn at random from $\{-1,1\}^{d\times n}$. As it turns out the polytope $K$ can be interpreted as the symmetric convex hull of the row vectors of $F.$ When $F$ is a random matrix, $K$ is a well-studied random polytope. Some recent results on random polytopes give us suitable lower bounds on the volume and upper bounds on the average Euclidean norm. More generally, our bounds are tight whenever $K$ is in isotropic position (as pointed out in Section 6). This condition intuitively gives a relation between volume and average distance from the origin. Our bounds are actually only tight up to a factor of $L_{K},$ the isotropic constant of $K.$ A well-known conjecture from convex geometry, known as the Hyperplane Conjecture or Slicing Conjecture, implies that $L_{K}=O(1).$

The problem is that when $F$ is not drawn at random, $K$ could be very far from isotropic. In this case, the $K$-norm mechanism by itself might actually perform poorly. We thus give a recursive variant of the $K$-norm mechanism in Section 7 which can handle non-isotropic bodies. Our approach is based on analyzing the covariance matrix of $K$ in order to partition $K$ into parts on which our earlier mechanism performs well. Assuming the Hyperplane conjecture, we derive bounds on the error of our mechanism that are optimal to within polylogarithmic factors.

Some complications arise, since we need to repeat the privacy and optimality analysis of our mechanisms in the presence of approximation errors (such as an approximate covariance matrix and an approximate separation oracle for $K$). The details can be found in Section 8.

We would like to thank Frank McSherry, Aaron Roth, Katrina Ligett, Indraneel Mukherjee, Nikhil Srivastava for several useful discussions, and Adam Smith for discussions and comments on a previous version of the paper.

Preliminaries

1 Differential Privacy

A mechanism $M$ is a family of probability measures $M=\{\mu_{x}\colon x\in\Re^{n}\}$ where each measure $\mu_{x}$ is defined on $\Re^{d}$. A mechanism is called $\varepsilon$-differentially private, if for all $x,y\in\Re^{n}$ such that $\|x-y\|_{1}\leqslant 1$, we have $\sup_{S\subseteq\Re^{d}}\frac{\mu_{x}(S)}{\mu_{y}(S)}\leqslant\exp(\varepsilon),$ where the supremum runs over all measurable subsets $S\subseteq\Re^{d}$.

A common weakening of $\varepsilon$-differential privacy is the following notion of approximate privacy.

A mechanism is called $\delta$-approximate $\varepsilon$-differentially private, if for all $x,y\in\Re^{n}$ such that $\mu_{x}(S)\leqslant\exp(\varepsilon)\mu_{y}(S)+\delta$ for all measurable subsets $S\subseteq\Re^{n}$ whenever$\|x-y\|_{1}\leqslant 1$,

The definition of privacy is transitive in the following sense.

If $M$ is an $\varepsilon$-differentially private mechanism and $x,y\in\Re^{n}$ satisfy $\|x-y\|_{1}\leqslant k$, then for measurable $S\subseteq\Re^{d}$ we have $\frac{\mu_{x}(S)}{\mu_{y}(S)}\leqslant\exp(\varepsilon k).$

We will consider mappings $F$ which possess the Lipschitz property, $\sup_{x\in B_{1}^{n}}\|Fx\|_{1}\leqslant d.$ In this case, we will say that $F$ has sensitivity $d$.

Our goal is to show trade-offs between privacy and error. The following standard upper bound, usually called the Laplacian mechanism, is known.

When it comes to approximate privacy, the so-called Gaussian mechanism provides the following guarantee.

2 Isotropic Position

We say a convex body $K\subseteq\Re^{d}$ is in isotropic position with isotropic constant $L_{K}$ if for every unit vector $v\in\Re^{d}$,

For every convex body $K\subseteq\Re^{d}$, there is a volume-preserving linear transformation $T$ such that $TK$ is in isotropic position.

For an arbitrary convex body $K$, its isotropic constant $L_{K}$ can then be defined to be $L_{TK}$ where $T$ brings $L$ to isotropic position. It is known (e.g. [MP89]) that $T$ is unique up to an orthogonal transformation and thus this is well-defined.

We refer the reader to the paper of Milman and Pajor [MP89], as well as the extensive survey of Giannopoulos [Gia03] for a proof of this fact and other facts regarding the isotropic constant.

3 Gamma Distribution

4 Linear Programming Characterization

A mechanism is specified by a distribution $\mu_{x}$ on $\mathcal{R}$ for every $x\in\mathcal{D}$. Assume for simplicity that $\mathcal{D}$ and $\mathcal{R}$ are both finite. Thus a mechanism is fully defined by real numbers $\mu(x,a)$, where $\mu(x,a)$ is the probability that the mechanism outputs answer $a\in\mathcal{R}$ on databases $x\in\mathcal{D}$. The constraints on $\mu$ for an $\varepsilon$-differentially private mechanism are given by

The expected error (under any given prior over databases) is then a linear function of the variables $\mu(x,a)$ and can be optimized. Similarly, the worse case (over databases) expected error can be minimized, and we will concentrate on this measure for the rest of the paper. However these linear programs can be prohibitive in size. Moreover, it is not a priori clear how one can use this formulation to understand the asymptotic behavior of the error of the optimum mechanism.

Our work leads to a constant approximation to the optimum of this linear program when $F$ is a random in $\{-1,+1\}^{d\times n}$ and an $O(\log^{3/2}d)$-approximation otherwise.

Lower bounds via volume estimates

In this section we show that lower bounds on the volume of the convex body $FB_{1}^{n}\subseteq\Re^{d}$ give rise to lower bounds on the error that any private mechanism must have with respect to $F$.

A set of points $Y\subseteq\Re^{d}$ is called a $r$-packing if $\|y-y^{\prime}\|_{2}\geqslant r$ for any $y,y^{\prime}\in Y,y\neq y^{\prime}$.

We will now assume that $M=\{\mu_{x}\colon x\in\Re^{n}\}$ is an $\varepsilon$-differentially private mechanism with error $cd\sqrt{d}R/\varepsilon$ and lead this to a contradiction for small enough $c>0$. For this we set $\lambda=d/2\varepsilon$. By the assumption on the error, Markov’s inequality implies that for all $x\in X$, we have $\mu_{x}(B_{x})\geqslant\tfrac{1}{2},$ where $B_{x}$ is a ball of radius $2cd\sqrt{d}R/\varepsilon=4c\lambda R\sqrt{d}$ centered at $Fx$. Since $Y=FX$ is an $\Omega(\lambda R\sqrt{d})$-packing, the balls $\{B_{x}:x\in X\}$ are disjoint for small enough constant $c>0$.

Since $\|x\|_{1}\leqslant\lambda$, it follows from $\varepsilon$-differential privacy with Fact 2.3 that

Since the balls $B_{x}$ are pairwise disjoint,

for $d\geqslant 2$. We have thus obtained a contradiction. ∎

Let $\varepsilon>0$ and suppose $F\colon\Re^{n}\to\Re^{d}$ is a linear map and let $K=FB_{1}^{n}$. Furthermore, let $P$ denote the orthogonal projection operator of a $k$-dimensional subspace of $\Re^{d}$ for some $1\leqslant k\leqslant d.$ Then, every $\varepsilon$-differentially private mechanism $M$ must have

Note that a differentially private answer $a$ to $F$ can be projected down to a (differentially private) answer $Pa$ to $PF$ and $P$ is norm $1$ operator. ∎

where the supremum is taken over all $k$ and all $k$-dimensional orthogonal projections $P$.

Our lower bound used the fact that the mechanism is defined on all vectors $x\in\Re^{d}$. In Appendix B, we show how the lower bound can be extended when restricting the domain of the mechanism to integer vectors $x\in[N]^{n},$ where distance is measured in the Hamming metric.

1 Lower bounds for small number of queries

As shown previously, the task of proving lower bounds on the error of private mechanisms reduces to analyzing the volume of $FB_{1}^{n}.$ When $d\leqslant\log n$ this is a straightforward task.

This lower bound shows that the standard upper bound from Theorem 2.6 is, in fact, optimal when $d\leqslant\log(n).$

The K𝐾K-norm mechanism

In this section we describe a new differentially private mechanism, which we call the $K$-norm mechanism.

Given a linear map $F\colon\Re^{n}\to\Re^{d}$ and $\varepsilon>0$, we let $K=FB_{1}^{n}$ and define the mechanism ${\bf KM}(F,d,\varepsilon)=\{\mu_{x}\colon x\in\Re^{n}\}$ so that each measure $\mu_{x}$ is given by the probability density function

defined over $\Re^{d}.$ Here $Z$ denotes the normalization constant

A more concrete view of the mechanism is provided by Figure 2 and justified in the next remark.

We can sample from the distribution $\mu_{x}$ as follows:

Indeed, if $\|a-Fx\|_{K}=R$, then the distribution of $a$ as above follows the probability density function

which is in agreement with (5). That is, $g(a)=f(a).$

The next theorem shows that the $K$-norm mechanism is indeed differentially private. Moreover, we can express its error in terms of the expected distance from the origin of a random point in $K.$

When $p=1$, $\frac{\Gamma(d+1+p)}{\Gamma(d+1)}=d+1.$

Privacy follows from the fact that the mechanism is a special case of the exponential mechanism [MT07]. For completeness, we repeat the argument.

Suppose that $\|x\|_{1}\leqslant 1$. It suffices to show that for all $a\in\Re^{d}$, the densities of $\mu_{0}$ and $\mu_{x}$ are within multiplicative $\exp(\varepsilon)$, i.e.,

where in the first inequality we used the triangle inequality for $\|\cdot\|_{K}$. In the second step we used that $x\in B_{1}^{n}$ and hence $Fx\in FB_{1}^{n}=K$ which means $\|Fx\|_{K}\leqslant 1.$

Hence, the mechanism satisfies $\varepsilon$-differential privacy. ∎

Matching bounds for random queries

In this section, we will show that our upper bound matches our lower bound when $F$ is a random query. A key observation is that $FB_{1}^{n}$ is the symmetric convex hull of $n$ (random) points $\{v_{1},\dots,v_{n}\}\subseteq\Re^{d}$, i.e., the convex hull of $\{\pm v_{1},\dots,\pm v_{n}\}$, where $v_{i}\in\Re^{d}$ is the $i$th column of $F$. The symmetric convex hull of random points has been studied extensively in the theory of random polytopes. A recent result of Litvak, Pajor, Rudelson and Tomczak-Jaegermann [LPRN05] gives the following lower bound on the volume of the convex hull.

Let $2d\leqslant n\leqslant 2^{d}$ and let $F$ denote a random $d\times n$ Bernoulli matrix. Then,

with probability $1-\exp(-\Omega(d^{\beta}n^{1-\beta}))$ for any $\beta\in(0,\frac{1}{2}).$ Furthermore, there is an explicit construction of $n$ points in $\{-1,1\}^{d}$ whose convex hull achieves the same volume.

We are mostly interested in the range where $n\gg d\log d$ in which case the theorem was already proved by Giannopoulos and Hartzoulaki [GH02] (up to a weaker bound in the probability and without the explicit construction).

The bound in (7) is tight up to constant factors. A well known result [BF88] shows that the volume of the convex hull of any $n$ points on the sphere in $\Re^{d}$ of radius $\sqrt{d}$ is bounded by

Notice, that in our case $K=FB_{1}^{n}\subseteq B_{\infty}^{d}\subseteq\sqrt{d}B_{2}^{d}$ and in fact the vertices of $K$ are points on the $(d-1)$-dimensional sphere of radius $\sqrt{d}$. However, equation (7) states that the normalized volume of the random polytope $K$ will be proportional to the volume of the Euclidean ball of radius $\sqrt{\log(n/d)}$ rather than $\sqrt{d}.$ When $d\gg\log n$, this means that the volume of $K$ will be tiny compared to the volume of the infinity ball $B_{\infty}^{d}$. By combining the volume lower bound with Theorem 3.3, we get the following lower bound on the error of private mechanisms.

Let $\varepsilon>0$ and $0<d\leqslant n/2$. Then, for almost all matrices $F\in\{-1,1\}^{d\times n}$, every $\varepsilon$-differentially private mechanism $M$ must have

We use this paragraph to point out that our lower bound immediately implies a separation between approximate and exact differential privacy.

Theorem 2.7 gives a mechanism providing $\delta$-approximate $\varepsilon$-differential privacy with error $o(\varepsilon^{-1}\sqrt{\log(n/d)})$ as long as $\delta\geqslant 1/n^{o(1)}.$ Our lower bound in Theorem 5.2 on the other hand states that the error of any $\varepsilon$-differentially private mechanism must be $\Omega(\varepsilon^{-1}\sqrt{\log(n/d)})$ (assuming $d\gg\log(n)$). We get the strongest separation when $d\leqslant\log(n)$ and $\delta$ is constant. In this case, our lower bound is a factor $\sqrt{d}$ larger than the upper bound for approximate differential privacy.

2 Upper bound on average Euclidean norm

Let $F$ be a random $d\times n$ Bernoulli matrix and put $K=FB_{1}^{n}$. Then, there is a constant $C>0$ so that with probability greater than $1-Ce^{-O(n)}$,

An application of Jensen’s inequality thus gives us the following corollary.

Let $\varepsilon>0$ and $0<d\leqslant n/2$. Then, for almost all matrices $F\in\{-1,1\}^{d\times n}$, the mechanism ${\rm KM}(F,d,\varepsilon)$ is $\varepsilon$-differentially private with error at most

Approximately isotropic bodies

The following definition is a relaxation of nearly isotropic position used in literature (e.g., [KLS97])

We say a convex body $K\subseteq\Re^{d}$ is in $c$-approximately isotropic position if for every unit vector $v\in\Re^{d}$,

The results of Klartag and Kozma [KK09] referred to in the previous section show that the symmetric convex hull $n$ random points from the $d$-dimensional hypercube are in $O(1)$-approximately isotropic position and have $L_{K}=O(1)$. More generally, the $K$-norm mechanism can be shown to be approximately optimal whenever $K$ is nearly isotropic.

We can see that the previous upper bound is tight up to a factor of $cL_{K}$. Estimating $L_{K}$ for general convex bodies is a well-known open problem in convex geometry. The best known upper bound for a general convex body $K\subseteq\Re^{d}$ is $L_{K}\leqslant O(d^{1/4})$ due to Klartag [Kla06], improving over the estimate $L_{K}\leqslant O(d^{1/4}\log d)$ of Bourgain from ’91. The conjecture is that $L_{K}=O(1)$.

There exists $C>0$ such that for every $d$ and every convex set $K\subseteq\Re^{d}$, $L_{K}<C$.

Assuming this conjecture we get matching bounds for approximately isotropic convex bodies.

Let $\varepsilon>0.$ Assuming the hyperplane conjecture, for every $F\in^{d\times n}$ such that $K=FB_{1}^{n}$ is $c$-approximately isotropic, the $K$-norm mechanism ${\rm KM}(F,d,\varepsilon)$ is $\varepsilon$-differentially private with error at most

Non-isotropic bodies

In this section, we will design a recursive mechanism that can handle such non-isotropic convex bodies. To this end, we will need to introduce a few more notions from convex geometry.

Having defined the covariance matrix, we can describe a recursive mechanism for the case when $K$ is not in isotropic position. The idea of the mechanism is to act differently on different eigenspaces of the covariance matrix. Specifically, the mechanism will use a lower-dimensional version of ${\bf KM}(F,d^{\prime},\varepsilon)$ on subspaces corresponding to few large eigenvalues.

The image of $P_{U}F$ above is a $d^{\prime}$-dimensional subspace of $\Re^{d}.$ We assume that in the recursive call ${\rm NIM}(P_{U}F,d^{\prime},\varepsilon)$, the $K$-norm mechanism is applied to a basis of this subspace. However, formally the output is a $d$-dimensional vector.

To analyze our mechanism, first observe that the recursive calls terminate after at most $\log d$ steps. For each recursive step $m\in\{0,\dots,\log d\}$, let $a_{m}$ denote the distribution over the output of the $K_{m}$-norm mechanism in step 3. Here, $K_{m}$ denotes the $d_{m}$-dimensional body given in step $m.$

The mechanism ${\rm NIM}(F,d,\varepsilon)$ satisfies $(\varepsilon\log d)$-differential privacy.

We claim that for every step $m\in\{0,\dots,\log d\}$, the distribution over $a_{m}$ is $\varepsilon$-differentially private. Notice that this claim implies the lemma, since the joint distribution of $a_{0},a_{1},\dots,a_{m}$ is $\varepsilon\log(d)$-differentially private. In particular, this is true for the final output of the mechanism as it is a function of $a_{0},\dots,a_{m}.$

The error analysis of our mechanism requires more work. In particular, we need to understand how the volume of $P_{U}K$ compares to the norm of $P_{V}a.$ As a first step we will analyze the volume of $P_{U}K.$

2 Volume in eigenspaces of the covariance matrix

Our goal in this section is to express the volume of $K$ in eigenspaces of the covariance matrix in terms of the eigenvalues of the covariance matrix. This will be needed in the analysis of our mechanism for non-isotropic bodies.

We start with a formula for the volume of central sections of isotropic bodies. This result can be found in [MP89].

Let $K\subseteq\Re^{d}$ be an isotropic body of unit volume. Let $E$ denote a $k$-dimensional subspace for $1\leqslant k\leqslant d$. Then,

Here, $B_{K}$ is an explicitly defined isotropic convex body.

Observe that the $PK$ contains $E\cap K$ since $P$ is the identity on $E.$ ∎

We cannot immediately use these results since they only apply to isotropic bodies and we are specifically dealing with non-isotropic bodies. The trick is to apply the previous results after transforming $K$ into an isotropic body while keeping track how much this transformation changed the volume.

As a first step, the following lemma relates the volume of projections of an arbitrary convex body $K$ to the volume of projections of $TK$ for some linear mapping $T$.

Let $K\subseteq\Re^{d}$ be a symmetric convex body. Let $T$ be a linear map which has eigenvectors $u_{1},\ldots,u_{d}$ with eigenvalues $\lambda_{1},\ldots,\lambda_{d}$. Let $1\leqslant k\leqslant d$ and suppose $E={\rm span}\{u_{1},u_{2},\dots,u_{k}\},$ Denote by $P$ be the projection operator onto the subspace $E.$ Then,

For simplicity, we assume that the eigenvectors of $T$ are the standard basis vectors $e_{1},\ldots,e_{d}$; this is easily achieved by applying a rotation to $K$. Now, it is easy to verify that $P=PT^{-1}T=SPT$ where $S=\rm{diag}(\lambda_{1}^{-1},\lambda_{2}^{-1},\ldots,\lambda_{k}^{-1},0,\dots,0)$. Thus we can write

Before we can finish our discussion, we will need the fact that the isotropic constant of $K$ can be expressed in terms of the determinant of $M_{K}.$

Let $K\subseteq\Re^{d}$ be a convex body of unit volume. Then,

We conclude with the following Proposition 7.7.

Let $K\subseteq\Re^{d}$ be a symmetric convex body. Let $M_{k}$ have eigenvectors $u_{1},\ldots,u_{d}$ with eigenvalues $\sigma_{1},\ldots,\sigma_{d}$. Let $1\leqslant k\leqslant\lceil\frac{d}{2}\rceil$ with and suppose $E={\rm span}\{u_{1},u_{2},\dots,u_{k}\},$ Denote by $P$ be the projection operator onto the subspace $E.$ Then,

where $\alpha_{K}$ is $\Omega(1/d^{\frac{1}{4}})$. Moreover, assuming the Hyperplane conjecture, $\alpha_{K}\geqslant\Omega(1)$.

Since $\lambda TK$ is in isotropic position and has unit volume, Corollary 7.4 implies that

Thus the required inequality holds with an additional $\lambda^{-\frac{k}{d-k}}$ term. By assumption on $k$, $\frac{k}{d-k}$ is at most $2$. Moreover, $\lambda=L_{K}^{1/d}\leqslant d^{1/d}\leqslant 2$, so that this additional term is a constant. As discussed above, $\alpha_{K}$ is $\Omega(d^{-\frac{1}{4}})$ by [Kla06], and $\Omega(1)$ assuming the Hyperplane Conjecture 6.3. Hence the claim. ∎

3 Arguing near optimality of our mechanism

Our next lemma shows that the expected squared Euclidean error added by our algorithm in each step is bounded by the square of the optimum. We will first need the following fact.

Let $K\subseteq\Re^{d}$ be a centered convex body. Let $\sigma_{1}\geqslant\sigma_{2}\geqslant\dots\geqslant\sigma_{d}$ denote the eigenvalues of $M_{K}$ with a corresponding orthonormal eigenbasis $u_{1},\dots,u_{d}.$ Then, for all $1\leqslant i\leqslant d$,

Let $a$ denote the random variable returned by the $K$-norm mechanism in step (3) in the above description of ${\rm NIM}(F,d,\varepsilon)$. Then,

For simplicity, we will assume that $d$ is even and hence $d-d^{\prime}=d^{\prime}.$ The analysis of the $K$-norm mechanism (Theorem 4.3 with $p=2$) shows that the random variable $a$ returned by the $K$-norm mechanism in step (3) satisfies

Since $\sigma_{d^{\prime}}\geqslant\sigma_{d^{\prime}+1}$, it follows that

The case of odd $d$ is similar except that we define $K^{\prime}$ to be the projection onto the first $d^{\prime}+1$ eigenvectors. ∎

We have to sum up the error over all recursive calls of the mechanism. To this end, let $P_{V_{m}}a_{m}$ denote the output of the $K$-norm mechanism $a_{m}$ in step $m$ projected to the corresponding subspace $V_{m}$. Also, let $a\in\Re^{d}$ denote the final output of our mechanism. We then have,

Let $\varepsilon>0$. Suppose $F\colon\Re^{n}\to\Re^{d}$ is a linear map. Further, assume the hyperplane conjecture. Then, there is an $\varepsilon$-differentially private mechanism $M$ with error

Efficient implementation of our mechanism

Membership in $K$ can be decided efficiently.

$K$ is bounded, in the sense that $B_{2}^{d}\subseteq K\subseteq dB_{2}^{d}$.

Both conditions are naturally satisfied in our case where $K=FB_{1}^{n}$ for some $F\in^{d\times n}$. Indeed, $K\subseteq B_{\infty}^{d}\subseteq\sqrt{d}B_{2}^{d}$ and we may always assume that $B_{2}^{d}\subseteq K$, for instance, by considering $K^{\prime}=K+B_{2}^{d}$ rather than $K$. This will only increase the noise level by $1$ in Euclidean distance. Notice that $K^{\prime}$ is convex. In order to implement the membership oracle for $K$, we need to be able to decide for a given $a\in\Re^{d}$, whether there exists an $x\in B_{1}^{n}$ such that $Fx=a$. These constraints can be encoded using a linear program. In the case of $K^{\prime}$ this can be done using convex programming [GLS94].

The mixing time of the Grid walk is usually quantified in terms of the total variation (or $L_{1}$) distance between the random walk and its stationary distribution. The stationary distribution of the grid Walk is the uniform distribution over ${\cal L}\cap K$. Standard arguments show that an $L_{1}$-bound gives us $\delta$-approximate $\varepsilon$-differential privacy where $\delta$ can be made exponentially small in polynomial time. In order to get exact privacy ($\delta=0$) we instead need a multiplicative guarantee on the density of the random walk at each point in $K.$

In Appendix A, we show that the Grid Walk actually satisfies mixing bounds in the relative $L_{\infty}$-metric which gives us the following theorem. We also need to take care of the fact that the stationary distribution is a priori not uniform over $K.$ A solution to this problem is shown in the appendix as well.

$M^{\prime}$ is $O(\varepsilon)$-differentially private,

We conclude that the Grid walk gives us an efficient implementation of our mechanism which achieves the same error bound (up to constants) and $\varepsilon$-differential privacy.

The runtime stated in Theorem 8.1 depends only upon $d$ and $\varepsilon^{-1}.$ The polynomial dependence on $n$ only comes in when implementing the separation oracle for $K$ as described earlier. Since we think of $d$ as small compared to $n$, the exact runtime of our algorithm heavily depends upon how efficiently we can implement the separation oracle.

In the non-isotropic case we additionally need to compute the subspaces $U$ and $V$ to project onto (Step 2 of the algorithm). Note that these subspaces themselves depend only on the query $F$ and not on the database $x$. Thus these can be published and the mechanism maintains its privacy for an arbitrary choice of subspaces $U$ and $V$. The choice of $U,V$ in Section 7 depended on the covariance matrix $M$, which we do not know how to compute exactly. We next describe a method to choose $U$ and $V$ that is efficient such that the resulting mechanism has essentially the same error. The sampling from $K$ can then be replaced by approximate sampling as in the previous subsection, resulting in a polynomial-time differentially private mechanism with small error.

First note that for any $i\geqslant d^{\prime}+1$

Generalizations of our mechanism

Moreover, in cases when one does not have a good handle on $K$ itself, one can use any convex body $K^{\prime}$ containing $K$.

Local Sensitivity.

Nissim, Raskhodnikova and Smith [NRS07] define smooth sensitivity and show that one can design approximately differentially private mechanism that add noise proportional to the smooth sensitivity of the query. This can be significant improvement when the local sensitivity is much smaller than the global sensitivity. Notice that such queries are necessarily non-linear. We point out that one can define a local sensitivity analogue of the $K$-norm mechanism by considering the polytopes $K_{x}={\rm conv}\left\{\frac{F(x^{\prime})-F(x)}{\mathit{dist}(x,x^{\prime})}\colon x^{\prime}\in\mathcal{D}\right\}$ and adapting the techniques of [NRS07] accordingly.

References

In this section, we sketch the proof of Theorem 8.1. We will be interested in the mixing properties of Markov chains over some measured state space $\Omega.$ We will need to compare probability measures $\mu,\nu$ over the space $\Omega.$

The relative $L_{\infty}$-distance is defined as

For a Markov chain $P$, we will be interested in the mixing time in the $\infty$-metric. That is the smallest number $t$ such that $\|P_{t}/\pi-1\|_{\infty}\leqslant\varepsilon.$ Here, $P_{t}$ is the distribution of $P$ at step $t$ and $\pi$ denotes the stationary distribution of $P.$ The relevance of the $\infty$-norm for our purposes is given by the following fact.

Suppose $M=\{\mu_{x}\}_{x\in\Re^{n}}$ is an $\varepsilon$-differentially private mechanism $M$ and suppose $M^{\prime}=\{\mu_{x}^{\prime}\}_{x\in\Re^{n}}$ satisfies $\max\{\|\mu_{x}/\mu_{x}^{\prime}-1\|_{\infty},\|\mu_{x}^{\prime}/\mu_{x}-1\|_{\infty}\}\leqslant\varepsilon$ for some $0\leqslant\varepsilon\leqslant 1$ and all $x\in\Re^{n}$. Then, $M^{\prime}$ is $3\varepsilon$-differentially private.

where we used that $1+\varepsilon\leqslant e^{\varepsilon}$ for $0\leqslant\varepsilon\leqslant 1.$

Now, let $x,x^{\prime}$ satisfy $\|x-x^{\prime}\|_{1}\leqslant 1$. By the previous inequality, we have

In the last inequality, we used the assumption that $M$ is $\varepsilon$-differentially private. Hence, we have shown that $M^{\prime}$ is $3\varepsilon$-differentially private. ∎

Finally, the bound on the moments of the Gamma distribution from Fact 2.10 implies that the expected running time of this algorithm is polynomial in $d,\varepsilon^{-1}$.

Appendix B Lower bounds for Differential Privacy with respect to Hamming Distance

We can then repeat the proof of theorem 3.3, with minor modifications to handle the non-negative integer constraint.

Let $\varepsilon>0$ and suppose $F\in\{-1,1\}^{d\times n}$ is a linear map and let $K=FB_{1}^{n}$. Then, every $\varepsilon$-differentially private mechanism $M$ for computing $G(w)=Fx(w)$ must have

Now we come up with a similar set $X^{\prime}\in Z_{+}^{n}$. For each $x\in X$, we round each $x_{i}$ randomly up or down, i.e. $\hat{x}_{i}=\lceil x_{i}\rceil$, with probability $(x_{i}-\lfloor x_{i}\rfloor)$, and $\lfloor x_{i}\rfloor$ otherwise. It is easy to check that $E[\hat{x}]=x$. so that with probability $2/3$, $|\hat{x}|_{1}\leqslant 3|x|_{1}$. Moreover, $E[F\hat{x}]=Fx$ and each random choice can change $\|F\hat{x}\|$ by at most $\sqrt{d}$. Thus martingale concentration results imply that with probability $2/3$, $\|F\hat{x}-Fx\|\leqslant 2\sqrt{dn}$. Thus there exists a choice of $\hat{x}$ so that both these events happen. Let $v$ denote the vector $(\lceil d/2\varepsilon\rceil,\lceil d/2\varepsilon\rceil,\ldots,\lceil d/2\varepsilon\rceil)$ and set $x^{\prime}=\hat{x}+v$. This defines our set $X^{\prime}$ which is easily seen to be in $Z_{+}^{n}$. In fact, $X^{\prime}\subseteq v+(\lceil d/2\varepsilon\rceil)B_{1}^{n}$. Moreover, for $\varepsilon<CRd/32\sqrt{n}$, $FX^{\prime}$ is a $CRd\sqrt{d}/8\varepsilon$-packing.

Now assume that $M=\{\mu_{x}\colon x\in\Re^{n}\}$ is an $\varepsilon$-differentially private mechanism with error $CRd\sqrt{d}/32\varepsilon$ and lead this to a contradiction. By the assumption on the error, Markov’s inequality implies that for all $x\in X^{\prime}$, $\mu_{x}(B_{x})\geqslant\tfrac{1}{2},$ where $B_{x}$ is a ball of radius $CRd\sqrt{d}/16\varepsilon$ centered at $Fx$. By the packing property above, the balls $\{B_{x}:x\in X\}$ are disjoint.

Since $\|x^{\prime}-v\|_{1}\leqslant(d/2\varepsilon)$, it follows from $\varepsilon$-differential privacy with Fact 2.3 that

Since the balls $B_{x}$ are pairwise disjoint,

for $d\geqslant 2$. We have thus obtained a contradiction. ∎

Translating the lower bound from Theorem 5.2 to this setting, we get

Let $\varepsilon\in(0,(c\sqrt{(d/n)})\cdot\min\{\sqrt{d},\sqrt{\log(n/d)}\})$ for a universal constant $c$ and let $d\leqslant\log n$. Then there exists a linear map $F\in\{-1,1\}^{d\times n}$ such that every $\varepsilon$-differentially private mechanism $M$ for computing $G(w)=Fx(w)$ must have

We remark that this lower bound holds for $N=\Omega(nd/\varepsilon)$.

Appendix C Dilated Ball containment

Let $A$ be a convex body in $\Re^{d}$ such that $B_{2}^{d}\subseteq A+rB_{2}^{d}$ for some $r<1$. Then a dilation $(1-r)B_{2}^{d}$ is contained in $A$.

Let $z\in\Re^{d}$ be a unit vector. Suppose that $z^{\prime}=(1-r)z\not\in A$. Then by the Separating Hyperplane theorem (see, e.g., [BV04]), there is a hyperplane $H$ separating $z^{\prime}$ from $A$. Thus there is a unit vector $w$ and a scalar $b$ such that $\langle z^{\prime},w\rangle-b=0$ and $\langle u,w\rangle-b\leqslant 0$ for all $u\in A$. Let $v=z^{\prime}+rw$. Then by triangle inequality, $\|v\|\leqslant 1$. Moreover,

This however contradicts the assumption that that $v\in B_{2}^{d}\subseteq A+rB_{2}^{d}$. Since $z$ was arbitrary, the lemma is proved. ∎