Fingerprinting Codes and the Price of Approximate Differential Privacy

Introduction

Consider a database $D\in\mathcal{X}^{n}$, in which each of the $n$ rows corresponds to an individual’s record, and each record is an element of some data universe $\mathcal{X}$ (e.g. $\mathcal{X}=\{0,1\}^{d}$, corresponding to $d$ binary attributes per record). The goal of privacy-preserving data analysis is to enable rich statistical analyses on such a database while protecting the privacy of the individuals. It is especially desirable to achieve $(\varepsilon,\delta)$-differential privacy [DMNS06, DKM+06], which (for suitable choices of $\varepsilon$ and $\delta$) guarantees that no individual’s data has a significant influence on the information released about the database. A natural way to measure the tradeoff between these two goals is via sample complexity—the minimum number of records $n$ such that there exists a (possibly computationally unbounded) algorithm that achieves both differential privacy and statistical accuracy.

Some of the most basic statistics are counting queries, which are queries of the form “What fraction of individual records in $D$ satisfy some property $q$?” In particular, we would like to design an algorithm that takes as input a database $D$ and, for some family of counting queries $\mathcal{Q}$, outputs an approximate answer to each of the queries in $\mathcal{Q}$ that is accurate to within, say, $\pm.01$. Suppose we are given a bound on the number of queries $|\mathcal{Q}|$ and the dimensionality of the database records $d$, but otherwise allow the family $\mathcal{Q}$ to be arbitrary. What is the sample complexity required to achieve $(\varepsilon,\delta)$-differential privacy and statistical accuracy for $\mathcal{Q}$?

Of course, if we drop the requirement of privacy, then we could achieve perfect accuracy when $D$ contains any number of records. However, in many interesting settings the database $D$ consists of random samples from some larger population, and an analyst is actually interested in answering the queries on the population. Thus, even without a privacy constraint, $D$ would need to contain enough records to ensure that (with high probability) for every query $q\in\mathcal{Q}$, the answer to $q$ on $D$ is close to the answer to $q$ on the whole population, say within $\pm.01$. To achieve this form of statistical accuracy, it is well-known that it is necessary and sufficient for $D$ to contain $\Theta(\log|\mathcal{Q}|)$ samples.For a specific family of queries $\mathcal{Q}$, the necessary and sufficient number of samples is proportional to the VC-dimension of $\mathcal{Q}$, which can be as large as $\log|\mathcal{Q}|$. In this work we consider whether there is an additional “price of differential privacy” if we require both statistical accuracy and $(\varepsilon,\delta)$-differential privacy (for, say, $\varepsilon=O(1)$, $\delta=o(1/n)$). This benchmark has often been used to evaluate the utility of differentially private algorithms, beginning with the seminal work of Dinur and Nissim [DN03].

These results show that the price of privacy is small for datasets with few attributes, but may be large for high-dimensional datasets. For example, if we simply want to estimate the mean of each of the $d$ attributes without a privacy guarantee, then $\Theta(\log d)$ samples are necessary and sufficient to get statistical accuracy. However, the best known $(\varepsilon,\delta)$-differentially private algorithm requires $\Omega(\sqrt{d})$ samples—an exponential gap. In the special case of pure $(\varepsilon,0)$-differential privacy, a lower bound of $\Omega(d)$ is known [HT10]. However, for the general case of approximate $(\varepsilon,\delta)$-differential privacy the best known lower bound is $\Omega(\log d)$ [DN03]. More generally, there are no known lower bounds that separate the sample complexity of $(\varepsilon,\delta)$-differential privacy from the sample complexity required for statistical accuracy alone.

In this work we close this gap almost completely, and show that there is indeed a “price of approximate differential privacy” for high-dimensional datasets.

We establish this lower bound using a combinatorial object called a fingerprinting code, which was originally introduced by Boneh and Shaw [BS98] for the problem of watermarking copyrighted content. Specifically, we use Tardos’ construction of optimal fingerprinting codes [Tar08]. The use of “secure content distribution schemes” to prove lower bounds for differential privacy originates with the work of Dwork et al. [DNR+09], who used “traitor-tracing schemes,” which are a cryptographic analogue of information-theoretic fingerprinting codes, to prove computational hardness results for differential privacy. Extending this connection, Ullman [Ull13] used fingerprinting codes to construct a novel traitor-tracing scheme and obtain a strong computational hardness result for differential privacy.In fact, one way to prove Theorem 1.1 is by replacing the one-way functions in [Ull13] with a random oracle, and thereby obtain an information-theoretically secure traitor-tracing scheme. Here we show that a direct use of fingerprinting codes yields information-theoretic lower bounds on sample complexity.

Next, we consider the sample complexity of answering an arbitrary set $\mathcal{Q}$ of counting queries to within error $\pm\alpha$. As above, if we assume the database contains samples from a population, and require only that the answers to queries on the sampled database and the population are close, to within $\pm\alpha$, then $\Theta(\log|\mathcal{Q}|/\alpha^{2})$ samples are necessary and sufficient for just statistical accuracy. When $|\mathcal{Q}|$ is large (relative to $d$ and $1/\alpha$), the best sample complexity for differential privacy is again achieved by the private multiplicative weights algorithm, and is $O(\sqrt{d}\log|\mathcal{Q}|/\alpha^{2})$. For pure differential privacy, a lower bound of $\Omega(d\log|\mathcal{Q}|/\alpha^{2})$ is known [Har11]. On the other hand, the best known lower bound for approximate differential privacy is $\Omega(\max\{\log|\mathcal{Q}|/\alpha,1/\alpha^{2}\})$, which follows from the techniques of [DN03]. To resolve this gap, we give a composition theorem that allows us to obtain a nearly optimal lower bound by combining Theorem 1.1 with (variants of) the existing sample complexity lower bounds. The result shows that the private multiplicative weights algorithm achieves nearly-optimal sample-complexity as a function of $|\mathcal{Q}|,d$, and $\alpha$.

We remark that the condition that $d\geq 6\log(1/\alpha)$ is both necessary (up to the constant factor) and fairly mild. Necessary because the noisy histogram algorithm (see, e.g. [Vad16]) requires $n=O(2^{d/2}\sqrt{\log|\mathcal{Q}|}/\alpha)$ samples, which is better than the conclusion of the lower bound when $d<2\log(1/\alpha)$. Mild because differential privacy cannot be satisfied for large query sets unless $\alpha\gtrsim 1/\sqrt{n}$, so the condition is no stronger than assuming $n\lesssim 2^{d/3}$, in which case the number of samples is exponential in the dimension. Similarly, the condition $s\geq d/\alpha^{2}$ is also necessary, since adding independent noise to each query requires only $n\gtrsim|\mathcal{Q}|^{1/2}/\alpha$ samples.

Finally, we consider the sample complexity of the natural and well studied class of $k$-way marginal queries, also known as $k$-way conjunction queries (see e.g. [BCD+07, KRSU10, GHRU11, TUV12, CTUW14, DNT13]). A $k$-way marginal query on a database $D\in(\{0,1\}^{d})^{n}$ is specified by a set $S\subseteq[d]$, $|S|\leq k$, and a pattern $t\in\{0,1\}^{|S|}$ and asks “What fraction of records in $D$ has each attribute $j$ in $S$ set to $t_{j}$?” The number of $k$-way marginal queries on $\{0,1\}^{d}$ is about $2^{k}\binom{d}{k}$. For the special case of $k=1$, the queries simply ask for the mean of each attribute, which was discussed above. We prove that the lower bound of Theorem 1.2, which applies to worst-case queries, also holds for the special case of $k$-way marginal queries when $\alpha$ is not too small.

We remark that, since the number of $k$-way marginal queries is about $2^{k}\binom{d}{k}$, the sample complexity lower bound in Theoem 1.3 essentially matches that of Theorem 1.2. The two theorems are incomparable, since Theorem 1.2 applies even when $\alpha$ is exponentially small in $d$, but only applies for a worst-case family of queries.

We now describe the main technical ingredients used to prove these results. For concreteness, we will describe the main ideas for the case of $k$-way marginal queries.

Fingerprinting codes, introduced by Boneh and Shaw [BS98], were originally designed to address the problem of watermarking copyrighted content. Roughly speaking, a (fully-collusion-resilient) fingerprinting code is a way of generating codewords for $n$ users in such a way that any codeword can be uniquely traced back to a user. Each legitimate copy of a piece of digital content has such a codeword hidden in it, and thus any illegal copy can be traced back to the user who copied it. Moreover, even if an arbitrary subset of the users collude to produce a copy of the content, then under a certain marking assumption, the codeword appearing in the copy can still be traced back to one of the users who contributed to it. The standard marking assumption is that if every colluder has the same bit $b$ in the $j$-th bit of their codeword, then the $j$-th bit of the “combined” codeword in the copy they produce must be also $b$. We refer the reader to the original paper of Boneh and Shaw [BS98] for the motivation behind the marking assumption and an explanation of how fingerprinting codes can be used to watermark digital content.

We show that the existence of short fingerprinting codes implies sample complexity lower bounds for $1$-way marginal queries. Recall that a $1$-way marginal query $q_{j}$ is specified by an integer $j\in[d]$ and asks simply “What fraction of records in $D$ have a $1$ in the $j$-th bit?” Suppose a coalition of users takes their codewords and builds a database $D\in(\{0,1\}^{d})^{n}$ where each record contains one of their codewords, and $d$ is the length of the codewords. Consider the $1$-way marginal query $q_{j}(D)$. If every user in $S$ has a bit $b$ in the $j$-th bit of their codeword, then $q_{j}(D)=b$. Thus, if an algorithm answers $1$-way marginal queries on $D$ with non-trivial accuracy, its output can be used to obtain a combined codeword that satisfies the marking assumption. By the tracing property of fingerprinting codes, we can use the combined codeword to identify one of the users in the database. However, if we can identify one of the users from the answers, then the algorithm is not differentially private.

Theorems 1.2 and 1.3 are proven by using this composition technique repeatedly to combine our lower bound for $1$-way marginals with (variants of) several known lower bounds that capture the optimal dependence on $\log|\mathcal{Q}|$ and $1/\alpha^{2}$.

The connection between fingerprinting codes and differential privacy lower bounds extends to arbitrary families $\mathcal{Q}$ of counting queries. We introduce the notion of a generalized fingerprinting code with respect to $\mathcal{Q}$, where each codeword corresponds to a data universe element $x\in\mathcal{X}$ and the bits of the codeword are given by $q(x)$ for each $q\in\mathcal{Q}$, but is the same as an ordinary fingerprinting code otherwise. The existence of a generalized fingerprinting code with respect to $\mathcal{Q}$, for $n$ users, implies a sample complexity lower bound of $n$ for privately releasing answers to $\mathcal{Q}$. We also show a partial converse to the above result, which states that some sort of “fingerprinting-code-like object” is necessary to prove sample complexity lower bounds for answering counting queries under differential privacy. This object has similar semantics to a generalized fingerprinting code, however the marking assumption required for tracing is slightly stronger and the probability that tracing succeeds can be significantly smaller than what is required by the standard definition of fingerprinting codes. Our partial converse parallels the result of Dwork et al. [DNR+09] that shows computational hardness results for differential privacy imply a “traitor-tracing-like object.” We leave it as an open question to pin down precisely the relationship between fingerprinting codes and information-theoretic lower bounds in differential privacy (and also between traitor-tracing schemes and computational hardness results for differential privacy).

2 Other Related Work

There have been attempts to prove optimal sample complexity lower bounds for $k$-way marginals. In particular, when $k$ is a constant, Kasiviswanathan et al. [KRSU10] and De [De12] prove a lower bound of $\min\{|\mathcal{Q}|^{1/2}/\alpha,1/\alpha^{2}\}$ on the sample complexity. Note that when $\alpha$ is a constant, these lower bounds are $O(1)$.

In addition to the general computational hardness results referenced above, there are several results that show stronger hardness results for restricted types of efficient algorithms [UV11, GHRU11, DNV12].

2.2 Subsequent Work

Subsequent to our work, Steinke and Ullman [SU15a] refined our use of fingerprinting codes to prove a lower bound of $\Omega(\sqrt{d\log(1/\delta)}/\varepsilon)$ on the number of samples required to release the mean of each of the $d$ attributes under $(\varepsilon,\delta)$-differential privacy when $\delta\ll 1/n$. This lower bound is optimal up to constant factors, and improves on Theorem 1.1 by a factor of roughly $\sqrt{\log(1/\delta)}\cdot\log d$. They also improve and simplify our analysis of robust fingerprinting codes.

Our fingerprinting code technique has also been used to prove lower bounds for other types of differentially private data analyses. Namely, Dwork et al. [DTTZ14] prove lower bounds for differentially private principal component analysis and Bassily, Smith, and Thakurta [BST14] prove lower bounds for differentially private empirical risk minimization. In order to establish lower bounds for privately releasing threshold functions, Bun et al. [BNSV15] construct a fingerprinting-code-like object that yields a lower bound for the problem of releasing a value between the minimum and maximum of a dataset.

Dwork et al. [DSS+15] observe that the privacy attack implicit in our negative results is closely related to the influential attacks that were employed by Homer et al. [HSR+08] (and further studied in [SOJH09]) to violate privacy of public genetic datasets. Using this connection, they show how to make Homer et al.’s attack robust to very general models of noise and how to make the attack work without detailed knowledge of the population the dataset represents.

A pair of works [HU14, SU15b] show that fingerprinting codes and the related traitor-tracing schemes imply both information-theoretic lower bounds and computational hardness results for the “false discovery” problem in adaptive data analysis. Specifically, they show lower bounds for answering an online sequence of adaptively chosen counting queries where the database is a sample from some unknown distribution and the answers must be accurate with respect to that distribution. These works [HU14, SU15b] effectively reverse a connection established in [DFH+15, BSSU15], which used differentially private algorithms to obtain positive results for this problem.

Our technique for composing lower bounds in differential privacy has also found applications outside of privacy. Specifically, Liberty et al. [LMTU14] used this technique to prove nearly optimal lower bounds on the space required to “sketch” a database while approximately preserving answers to $k$-way marginal queries (called “frequent itemset queries” in their work).

Preliminaries

We define a database $D\in\mathcal{X}^{n}$ to be an ordered tuple of $n$ rows $(x_{1},\ldots,x_{n})\in\mathcal{X}$ chosen from a data universe $\mathcal{X}$. We say that two databases $D,D^{\prime}\in\mathcal{X}^{n}$ are adjacent if they differ only by a single row, and we denote this by $D\sim D^{\prime}$. In particular, we can replace the $i$th row of a database $D$ with some fixed “junk” element of $\mathcal{X}$ to obtain another database $D_{-i}\sim D$. We emphasize that if $D$ is a database of size $n$, then $D_{-i}$ is also a database of size $n$.

Let $\mathcal{A}:\mathcal{X}^{n}\to\mathcal{R}$ be a randomized algorithm (where $n$ is a varying parameter). $\mathcal{A}$ is $(\varepsilon,\delta)$-differentially private if for every two adjacent databases $D\sim D^{\prime}$ and every subset $S\subseteq\mathcal{R}$,

Let $\mathcal{A}:\mathcal{X}^{n}\to\mathcal{R}$ be a randomized algorithm such that for every $D\in\mathcal{X}^{n}$, every $i,j\in[n]$, and every subset $S\subseteq\mathcal{R}$,

Let $\bot$ denote the fixed junk element of $\mathcal{X}$. Then $\mathcal{A}^{\prime}:\mathcal{X}^{n-1}\to\mathcal{R}$ defined by $\mathcal{A}^{\prime}(x_{1},\ldots,x_{n-1})=\mathcal{A}(x_{1},\ldots,x_{n-1},\bot)$ is $(2\varepsilon,(e^{\varepsilon}+1)\delta)$-differentially private.

Let $D=(x_{1},\ldots,x_{n-1})$ and $D^{\prime}=(x_{1},\ldots,x_{i}^{\prime},\ldots,x_{n-1})$ be adjacent databases. Then for any $S\subseteq\mathcal{R}$, we have

2 Counting Queries and Accuracy

In this paper we study algorithms that answer counting queries. A counting query on $\mathcal{X}$ is defined by a predicate $q:\mathcal{X}\to\{0,1\}$. Abusing notation, we define the evaluation of the query $q$ on a database $D=(x_{1},\ldots,x_{n})\in\mathcal{X}^{n}$ to be its average value over the rows,

When $\beta=0$ we may simply write that $a$ or $\mathcal{A}$ is $\alpha$-accurate for $\mathcal{Q}$.

An important example of a collection of counting queries is the set of $k$-way marginals. For all of our results it will be sufficient to consider only the set of monotone $k$-way marginals.

A (monotone) $k$-way marginal $q_{S}$ over $\{0,1\}^{d}$ is specified by a subset $S\subseteq[d]$ of size $|S|\leq k$. It takes the value $q_{S}(x)=1$ if and only if $x_{i}=1$ for every index $i\in S$. The collection of all (monotone) $k$-way marginals is denoted by $\mathcal{M}_{k,d}$.

3 Sample Complexity

In this work we prove lower bounds on the sample complexity required to simultaneously achieve differential privacy and accuracy.

We will focus on the case where $\varepsilon=O(1)$ and $\delta=o(1/n)$. This setting of the parameters is essentially the most-permissive for which $(\varepsilon,\delta)$-differential privacy is still a meaningful privacy definition. However, pinning down the exact dependence on $\varepsilon$ and $\delta$ is still of interest. Regarding $\varepsilon$, this can be done via the following standard lemma, which allows us to take $\varepsilon=1$ without loss of generality.

For every set of counting queries $\mathcal{Q}$, universe $\mathcal{X}$, $\alpha,\beta\in,\varepsilon\leq 1$. $(\mathcal{Q},\mathcal{X})$ has sample complexity $n^{*}$ for $(\alpha,\beta)$-accuracy and $(1,o(1/n))$-differential privacy if and only if it has sample complexity $\Theta(n^{*}/\varepsilon)$ for $(\alpha,\beta)$-accuracy and $(\varepsilon,o(1/n))$-differential privacy.

One direction ($O(n^{*}/\varepsilon)$ samples are sufficient) is the “secrecy-of-the-sample lemma,” which appeared implicitly in [KLN+11]. The other direction ($\Omega(n^{*}/\varepsilon)$ samples are necessary) appears to be folklore.

The next lemma allows us to generically translate sample complexity lower bounds for constant accuracy into lower bounds that depend on the error parameter $\alpha$. For some sets of queries, such as $1$-way marginals, the dependence we get on $\alpha$ is tight. However, as we will see in Section 5, we can obtain lower bounds with an even stronger dependence on $\alpha$ for specific sets of queries.

Let $\mathcal{Q}$ be a set of counting queries on $\mathcal{X}$ and let $\beta,\varepsilon,\delta>0$. Suppose $(\mathcal{Q},\mathcal{X})$ has sample complexity $n^{*}$ for $(\alpha_{0},\beta)$-accuracy and $(\varepsilon,\delta)$-differential privacy, where $\alpha_{0}\in(0,1)$ is a constant. Then $(\mathcal{Q},\mathcal{X})$ has sample complexity $\Omega(n^{*}/\alpha)$ for $(\alpha,\beta,\gamma)$-accuracy and $(\varepsilon,\delta)$-differential privacy.

The mechanism $\mathcal{A}^{\prime}$ inherits $(\varepsilon,\delta)$-differential privacy from $\mathcal{A}$, since changing one row of $D^{\prime}$ changes one row of the padded database $D^{\prime}$. Now we argue accuracy. Suppose $a_{q}$ is an answer such that $|a_{q}-q(D)|\leq\alpha$. Note that by construction, $q(D)=\frac{1}{m}(nq(D^{\prime})+(m-n)q(x_{0}))$, and hence $q(D^{\prime})=\frac{1}{n}(mq(D)-(m-n)q(x_{0}))$. Thus we have

Taking $n=\lceil m\alpha/\alpha_{0}\rceil$ makes this quantity at most $\alpha_{0}$, completing the proof. ∎

For context, we can restate some prior results on differentially private counting query release in our sample-complexity terminology.

For every set of counting queries $\mathcal{Q}$ on $\mathcal{X}$ and every $\alpha>0$, $(\mathcal{Q},\mathcal{X})$ has sample complexity at most

for $(\alpha,0)$-accuracy and $(1,o(1/n))$-differential privacy.

The next theorem shows that, when the data universe is not too small, the private multiplicative weights algorithm is nearly-optimal as a function of $|\mathcal{Q}|$ and $1/\alpha$ when each parameter is considered individually.

for $(\alpha,0)$-accuracy and $(1,o(1/n))$-differential privacy.

4 Re-identifiable Distributions

All of our eventual lower bounds will take the form of a “re-identification” attack, in which we possess data from a large number of individuals, and identify one such individual who was included in the database. In this attack, we choose a distribution on databases and give an adversary 1) a database $D$ drawn from that distribution and 2) either $\mathcal{A}(D)$ or $\mathcal{A}(D_{-i})$ for some row $i$, where $\mathcal{A}$ is an alleged sanitizer. The adversary’s goal is to identify a row of $D$ that was given to the sanitizer. We say that the distribution is re-identifiable if there is an adversary who can identify such a row with sufficiently high confidence whenever $\mathcal{A}$ outputs accurate answers. If the adversary can do so, it means that there must be a pair of adjacent databases $D\sim D_{-i}$ such that the adversary can distinguish $\mathcal{A}(D)$ from $\mathcal{A}(D_{-i})$, which means $\mathcal{A}$ cannot be differentially private.

Here the probability is taken over the choice of $D$ and $i$ as well as the coins of $\mathcal{A}$ and $\mathcal{B}$. We allow $\mathcal{D}$ and $\mathcal{B}$ to share a common state.

Note that, when row $i$ is not in the dataset, then it would be an error for $\mathcal{B}$ to declare that row $i$ is in the dataset, and condition 2 requires that the probability of this error occurring is at most $\xi$.

The common state between $\mathcal{D}$ and $\mathcal{B}$ should be thought of as auxiliary information about the realization of $D$ that may help $\mathcal{B}$ identify a user $i$. Formally, we could model this shared state by having $\mathcal{D}$ output an additional string $aux$ that is given to $\mathcal{B}$ but not to $\mathcal{A}$. However, we make the shared state implicit to reduce notational clutter. The need for this shared state will become apparent when we use fingerprinting codes to construct re-identifiable distributions; in the context of fingerprinting codes, the shared state represents auxiliary information about a codebook that helps the $\mathit{Trace}$ algorithm accuse a guilty pirate.

Lower Bounds via Fingerprinting Codes

In Section 3.1 we give the relevant background on fingerprinting codes and in Section 3.2 we prove our lower bounds for $1$-way marginals.

Fingerprinting codes were introduced by Boneh and Shaw [BS98] to address the problem of watermarking digital content. A fingerprinting code is a pair of randomized algorithms $(\mathit{Gen},\mathit{Trace})$. The code generator $\mathit{Gen}$ outputs a codebook $C\in\{0,1\}^{n\times d}$. Each row $c_{i}$ of $C$ is the codeword of user $i$. For a subset of users $S\subseteq[n]$, we use $C_{S}\in\{0,1\}^{|S|\times d}$ to denote the set of codewords of users in $S$. The parameter $d$ is called the length of the fingerprinting code.

The security property of fingerprinting codes asserts that any codeword can be “traced” to a user $i\in[n]$. Moreover, we require that the fingerprinting code is “fully-collusion-resilient”—even if any “coalition” of users $S\subseteq[n]$ gets together and “combines” their codewords in any way that respects certain constraints known as a marking assumption, then the combined codeword $c^{\prime}$ can be traced to a user $i\in S$. That is, there is a tracing algorithm $\mathit{Trace}$ that takes as inputs the codebook and combined codeword $c^{\prime}$ and outputs either a user $i\in[n]$ or $\bot$, and we require that if $c^{\prime}$ satisfies the constraints, then $\mathit{Trace}(C,c^{\prime})\in S$ with high probability. Moreover, $\mathit{Trace}$ should accuse an innocent user, i.e. $\mathit{Trace}(C,c^{\prime})\in[n]\setminus S$, with very low probability. Analogous to the definition of re-identifiable distributions (Definition 2.10), we allow $\mathit{Gen}$ and $\mathit{Trace}$ to share a common state.As in Definition 2.10, we could model this by having $\mathit{Gen}$ output an additional string $aux$ that is given to $\mathit{Trace}$. However, we make the shared state implicit to reduce notational clutter. When designing fingerprinting codes, one tries to make the marking assumption on the combined codeword as weak as possible.

The basic marking assumption is that each bit of the combined word $c^{\prime}$ must match the corresponding bit for some user in $S$. Formally, for a codebook $C\in\{0,1\}^{n\times d}$, and a coalition $S\subseteq[n]$, we define the set of feasible codewords for $C_{S}$ to be

Observe that the combined codeword is only constrained on coordinates $j$ where all users in $S$ agree on the $j$-th bit.

We are now ready to formally define a fingerprinting code.

where the probability is taken over the coins of $\mathit{Gen},\mathit{Trace}$, and $\mathcal{A}_{\mathit{FP}}$. The algorithms $\mathit{Gen}$ and $\mathit{Trace}$ may share a common state.

We remark that our proof of Theorem 3.5, showing how to construct re-identifiable distributions from a fingerprinting codes, will only require collusion resilience against coalitions $S$ of size $|S|\geq n-1$. Our choice to state Definition 3.1 using resilience against arbitrary coalitions is more consistent with the literature on fingerprinting codes.

Tardos [Tar08] constructed a family of fingerprinting codes with a nearly optimal number of users $n$ for a given length $d$.

As we will see in the next subsection, fingerprinting codes satisfying Definition 3.1 will imply lower bounds on the sample complexity for releasing $1$-way marginals with $(\alpha,0)$-accuracy (accuracy for every query). In order to prove sample-complexity lower bounds for $(\alpha,\beta)$-accuracy with $\beta>0$, we will need fingerprinting codes satisfying a stronger security property. Specifically, we will expand the feasible set $F(C_{S})$ to include all codewords that satisfy most feasibility constraints, and require that even codewords in this expanded set can be traced. Formally, for any $\beta\in$, we define

where the probability is taken over the coins of $\mathit{Gen},\mathit{Trace}$, and $\mathcal{A}_{\mathit{FP}}$. The algorithms $\mathit{Gen}$ and $\mathit{Trace}$ may share a common state.

In Section 6 we show how to construct error-robust fingerprinting codes with a nearly-optimal number of users that are tolerant to a constant fraction of errors.

2 Lower Bounds for 111-Way Marginals

By combining Theorem 3.5 with Theorem 3.2 we obtain a sample complexity lower bound for $1$-way marginals, and thereby establish Theorem 1.1 in the introduction.

Let $(\mathit{Gen},\mathit{Trace})$ be the promised fingerprinting code. We define the re-identifiable distribution $\mathcal{D}$ to simply be the output distribution of the code generator, $\mathit{Gen}$. And we define the privacy adversary $\mathcal{B}$ to take the answers $a=\mathcal{A}(D)\in^{|\mathcal{M}_{1,d}|}$, obtain $\overline{a}\in\{0,1\}^{|\mathcal{M}_{1,d}|}$ by rounding each entry of $a$ to $\{0,1\}$, run the tracing algorithm $\mathit{Trace}$ on the rounded answers $\overline{a}$, and return its output. The shared state of $\mathcal{D}$ and $\mathcal{B}$ will be the shared state of $\mathit{Gen}$ and $\mathit{Trace}$.

Now we will verify that $\mathcal{D}$ is $(\xi,\xi)$-re-identifiable. First, suppose that $\mathcal{A}(D)$ outputs answers $a=(a_{q_{j}})_{j\in[d]}$ that are $(1/3,\beta)$-accurate for $1$-way marginals. That is, there is a set $G\subseteq[d]$ such that $|G|\geq(1-\beta)d$ and for every $j\in G$, the answer $a_{q_{j}}$ estimates the fraction of rows having a $1$ in column $j$ to within $1/3$. Let $\overline{a}_{q_{j}}$ be $a_{q_{j}}$ rounded to the nearest value in $\{0,1\}$. Let $j$ be a column in $G$. If column $j$ has all $1$’s, then $a_{q_{j}}\geq 2/3$, and $\overline{a}_{q_{j}}=1$. Similarly, if column $j$ has all ’s, then $a_{q_{j}}\leq 1/3$, and $\overline{a}_{q_{j}}=0$. Therefore, we have

By security of the fingerprinting code (Definition 3.3), we have

But the event $\mathit{Trace}(D,\overline{a})=\bot$ is exactly the same as $\mathcal{B}(D,\mathcal{A}(D))=\bot$, and thus we have established the first condition necessary for $\mathcal{D}$ to be $(\xi,\xi)$-re-identifiable.

The second condition for re-identifiability follows directly from the soundness of the fingerprinting code, which asserts that for every adversary $\mathcal{A}_{\mathit{FP}}$, in particular for $\mathcal{A}$, it holds that

Using the additional structure of Tardos’ fingerprinting code, and our robust fingerprinting codes, we can prove minimax lower bounds for an “inference version” of the problem computing the $1$-way marginals of a product distribution.

We can now formally define the problem of inferring the marginals $p$ as follows.

Our lower bound can thus be stated as follows,

The proof has the same general structure that we used to prove Theorem 3.5. Here, we describe additional observations about the structure of the fingerprinting codes used in that proof (see Section 6 for a description of Tardos’ fingerprinting code) that allow it to carry over to the inference version of computing $1$-way marginals.

First, in Tardos’ (non-robust) fingerprinting code, the codebook $D$ is chosen by first sampling marginals $p\in^{d}$ from an appropriate distribution and then sampling $D$ from $\mathcal{D}_{p}^{\otimes n}.$ The robust fingerprinting codes we construct in Section 6 also have this property.To generate a codebook $D^{\prime}$ for our robust fingerprinting code, we sample a codebook $D$ from Tardos’ fingerprinting code and then insert additional columns of all $1$’s or all ’s to $D$ in random locations. Equivalently, we can obtain a codebook $D^{\prime}$ by appending $1$’s and ’s in random locations of $p$ to obtain a vector $p^{\prime}$ and then sampling $D^{\prime}$ from $\mathcal{D}_{p^{\prime}}^{\otimes n}.$ Thus the instances used to prove Theorem 3.5 indeed consist of independent samples from a product distribution, which is what the inference problem assumes.

Next, recall that the proof of Theorem 3.5 shows that any string that is $(\alpha,\beta)$-accurate for the $1$-way marginals of $D$ can be traced successfully. It is moreover the case that any string that is $(\alpha,\beta)$-accurate for the marginals $p$ can also be traced successfully. This is because the rows of $D$ are sampled independently from $\mathcal{D}_{p}$, so accuracy for the $1$-way marginals of $D$ and accuracy for $p$ coincide with high probability, at least when $n=\omega(\log d)$:

Let $p\in^{d}$ and let $D\leftarrow_{\mbox{\tiny R}}\mathcal{D}_{p}^{\otimes n}$. Let $a\in^{d}$ denote the exact $1$-way marginals of $D$. Then for every $\alpha,\eta>0$, and $n=\Omega(\log(d/\eta)/\alpha^{2})$, we have $\|a-p\|_{\infty}\leq\alpha$ with probability at least $1-\eta$ over the choice of $D$.

We remark that Steinke and Ullman [SU15a] showed that accuracy with respect to the marginals $p$ actually suffices to trace regardless of the value of $n$.

These two observations suffice to show that, when $n$ is too small, a differentially private algorithm cannot be accurate for $p$ with high probability over the choices of both $p$ and $D$. Thus, for every differentially private algorithm, there exists some $p$ such that the algorithm is not accurate with high probability over the choice of $D$, which means that the algorithm does not accurately infer the marginals of an arbitrary product distribution. ∎

3 Fingerprinting Codes for General Query Families

In this section, we generalize the connection between fingerprinting codes and sample complexity lower bounds for arbitrary sets of queries. We show that a generalized fingerprinting code with respect to any family of counting queries $\mathcal{Q}$ yields a sample complexity lower bound for $\mathcal{Q}$, which is analogous to our lower bound for $1$-way marginals (Theorem 3.5). We then argue that some type of fingerprinting code is necessary to prove any sample complexity lower bound by exhibiting a tight connection between such lower bounds and a weak variant of our generalized fingerprinting codes.

We begin by defining our generalization of fingerprinting codes. Fix a finite data universe $\mathcal{X}$ and a set of counting queries $\mathcal{Q}$ over $\mathcal{X}$. A generalized fingerprinting code with respect to the family $\mathcal{Q}$ consists of a pair of randomized algorithms $(\mathit{Gen},\mathit{Trace})$. The code generation algorithm $\mathit{Gen}$ produces a codebook $C\in\mathcal{X}^{n}$. Each row $c_{i}$ of $C$ is the codeword corresponding to user $i$. A coalition $S\subseteq[n]$ of pirates receives the subset $C_{S}=\{c_{i}:i\in S\}$ of codewords, and produces an answer vector $a\in^{|\mathcal{Q}|}$. We replace the traditional marking condition on the pirates with the generalized constraint that they output a feasible answer vector. A natural way to define feasibility for answer vectors is to require a condition similar to $(\alpha,\beta)$-accuracy, i.e. an answer vector $a$ is feasible if $|a_{q}-q(C_{S})|\leq\alpha$ for all but a $\beta$ fraction of queries $q\in\mathcal{Q}$. We thus define a generalized set of feasible answer vectors by

When $\alpha=1-1/n$, the generalized set of feasible answer vectors captures the traditional marking assumption by rounding each entry of a feasible answer vector to or $1$.An equivalent way to view a codebook is as a set of $n$ codewords $C\in(\{0,1\}^{|\mathcal{Q}|})^{n}$, where each user’s codeword is $c_{i}=(q(x))_{q\in\mathcal{Q}}$ for some $x\in\mathcal{X}$. Notice that the case where $\mathcal{Q}$ is the class of $1$-way marginals places no constraints on the structure of a codeword, i.e. a codeword can be any binary string. With this viewpoint, the goal of the pirates is to output an answer vector $a\in^{|\mathcal{Q}|}$ with $|a_{q}-\frac{1}{|S|}\sum_{i\in S}(c_{i})_{q}|\leq\alpha$ for all but a $\beta$ fraction of the queries $q\in\mathcal{Q}$.

A pair of algorithms $(\mathit{Gen},\mathit{Trace})$ is an $(n,\mathcal{Q})$-fingerprinting code for $(\alpha,\beta)$-accuracy with security $(\gamma,\xi)$ if $\mathit{Gen}$ outputs a codebook $C\in\mathcal{X}^{n}$ and for every (possibly randomized) adversary $\mathcal{A}_{\mathit{FP}}$, and every coalition $S\subseteq[n]$ with $|S|\geq n-1$, if we set $a\leftarrow_{\mbox{\tiny R}}\mathcal{A}_{\mathit{FP}}(C_{S})$, then

where the probability is taken over the coins of $\mathit{Gen},\mathit{Trace}$, and $\mathcal{A}_{\mathit{FP}}$. The algorithms $\mathit{Gen}$ and $\mathit{Trace}$ may share a common state.

The security properties of Definition 3.12 differ from those of an ordinary fingerprinting code in two ways so as to enable a clean statement of a composition theorem for generalized fingerprinting codes (Theorem 4.6). First, we use two separate security parameters $\gamma,\xi$ for the different types of tracing errors, as in the definition of re-identifiable distributions. Second, security only needs to hold for coalitions of size $n-1$ or $n$. However, this condition implies security for coalitions of arbitrary size with an increased false accusation probability of $n\xi$.

As in Theorem 3.5, the existence of a generalized $(n,\mathcal{Q})$-fingerprinting code implies a sample complexity lower bound of $n$ for privately releasing answers to $\mathcal{Q}$, with essentially the same proof.

In particular, if $\gamma\leq 1/3$ and $\xi=o(1/n)$, then there is no algorithm $\mathcal{A}:\mathcal{X}^{n}\to^{|\mathcal{Q}|}$ that is $(O(1),o(1/n))$-differentially private and $(\alpha,\beta)$-accurate for $\mathcal{Q}$.

We now turn to investigate whether a converse to Theorem 3.13 holds. We show that a sample complexity lower bound for a family of queries $\mathcal{Q}$ is essentially equivalent to the existence of a weak type of fingerprinting code, where the tracing procedure depends on the family $\mathcal{Q}$ and the tracing error probabilities satisfy certain affine constraint. It remains an interesting open question to determine the precise relationship between privacy lower bounds and our notion of generalized fingerprinting codes.

A pair of algorithms $(\mathit{Gen},\mathit{Trace})$ is an $(n,\mathcal{Q})$-weak fingerprinting code for $(\alpha,\beta)$-accuracy with security $(\varepsilon,\delta)$ if $\mathit{Gen}$ outputs a codebook $C\in\mathcal{X}^{n}$ and for every (possibly randomized) adversary $\mathcal{A}_{\mathit{FP}}$ that outputs a feasible answer vector with probability $2/3$, and every coalition $S\subseteq[n]$ with $|S|\geq n-1$, if we set $a\leftarrow_{\mbox{\tiny R}}\mathcal{A}_{\mathit{FP}}(C_{S})$, then

where the probabilities are taken over the coins of $\mathit{Gen}$, $\mathit{Trace}$, and $\mathcal{A}_{\mathit{FP}}$. The algorithms $\mathit{Gen}$ and $\mathit{Trace}$ may share a common state.

That is, we require the false accusation probability $\Pr[\mathit{Trace}(C,a)\in[n]\setminus S]$ to be much smaller than the total probability of accusing any user. Note that a tracing algorithm that accuses a random user with probability $p$ will falsely accuse a user with probability $p/n$ when $|S|=n-1$; however, this does not satisfy Definition 3.14 because we require the gap between the two probabilities to be at least a factor of $e^{\varepsilon}n$.

Observe that taking $\xi<(1-\delta)/2e^{\varepsilon}n$ in Definition 3.12 yields an $(n,\mathcal{Q})$-weak fingerprinting code with security $(\varepsilon,\delta)$. However, Definition 3.14 is weaker than Definition 3.12 in a few important ways. First, security only holds against pirates with a failure probability of at most $1/3$. Second, while Definition 3.12 requires completeness error $\Pr[\mathit{Trace}(C,a)=\bot]<\xi$, a weak fingerprinting code allows $\Pr[\mathit{Trace}(C,a)=\bot]=1-o(1)$ as long as $\Pr[\mathit{Trace}(C,a)\in[n]\setminus S]$ is sufficiently small.

The following theorem shows that the existence of an $(n,\mathcal{Q})$-weak fingerprinting code is essentially equivalent to a sample complexity lower bound of $n$ against $\mathcal{Q}$.

Then there exists an $i^{*}$ such that $\Pr[\mathit{Trace}(C,\mathcal{A}_{\mathit{FP}}(C))=i^{*}]\geq p/n$. By differential privacy,

On the other hand, by the security of the weak fingerprinting code and differential privacy,

This yields a contradiction whenever $\varepsilon^{\prime}\leq\varepsilon/2$ and $\delta^{\prime}\leq\delta/(1+e^{\varepsilon/2}n)$.

We now show the converse direction, i.e. that the high sample complexity of $(\mathcal{Q},\mathcal{X})$ implies the existence of a weak fingerprinting code. We begin with a technical lemma which shows that the high sample complexity of $\mathcal{Q}$ also rules out mechanisms that satisfy only a one-sided constraint on the probability of any event under the replacement of one row:

Let $\varepsilon\leq 1/2$. Let $\mathcal{A}$ be an $(\alpha,\beta)$-accurate algorithm for $\mathcal{Q}$ on databases $D\in\mathcal{X}^{m}$. Suppose we have that for all databases $D\in\mathcal{X}^{m}$, all $i\in[m]$, and all measurable $T\subseteq\text{Range}(\mathcal{A})$ that

Let $d=\mathit{VC}(\mathcal{Q})$ be the VC-dimension of $\mathcal{Q}$ and let

Then there exists a $(6\varepsilon,(e^{2\varepsilon}+e^{5\varepsilon})\delta)$-differentially private algorithm $\mathcal{B}$ on databases of size $n=\lceil m/\varepsilon\rceil$ that gives $(\alpha+\alpha^{\prime},\beta)$-accurate answers to $\mathcal{Q}$ on any database $D^{\prime}\in\mathcal{X}^{n}$ with probability at least $1/2$ .

On input a database $D^{\prime}\in\mathcal{X}^{n}$, consider the algorithm $\mathcal{B}^{\prime}$ that samples a random subset $D$ consisting of $m$ rows from $D^{\prime}$ (without replacement) and returns $\mathcal{A}(D)$. Then by our hypothesis on $\mathcal{A}$, for every $i\in[n]$ and every measurable $T\subseteq\text{Range}(\mathcal{B})=\text{Range}(\mathcal{A})$ we have

On the other hand, a “secrecy-of-the-sample” argument [KLN+11] enables us to obtain the reverse inequality. For a row $k\in[n]$, consider the following two experiments:

Experiment 1: Sample a random subset $D$ of $m$ rows from $D^{\prime}_{-k}$.

Experiment 2: Sample $j\leftarrow_{\mbox{\tiny R}}[n]$, and then sample a random subset $D$ of $m$ rows from $D^{\prime}_{-j}$.

Any database $D$ sampleable under Experiment 1 appears with probability $1/{n\choose m}$, but appears with probability at least

Combining the two inequalities shows that for every database $D^{\prime}\in\mathcal{X}^{n}$ and every $i,k\in[n]$,

By Lemma 2.2, the algorithm $\mathcal{B}(D^{\prime}_{1},\ldots,D^{\prime}_{n-1})=\mathcal{B}^{\prime}(D^{\prime}_{1},\ldots,D^{\prime}_{n-1},\bot)$ is $(6\varepsilon,(e^{2\varepsilon}+e^{5\varepsilon})\delta)$-differentially private.

Finally, uniform convergence of the sampling error of $\mathcal{B}^{\prime}$ implies that it remains an accurate algorithm, and hence so is $\mathcal{B}$. In particular, when $D$ is a random sample of $m$ rows from $D^{\prime}$ and $d$ is the VC-dimension of $\mathcal{Q}$, we have [AB09]:

Taking $\alpha^{\prime}$ as in the theorem statement makes the total failure probability of $\mathcal{B}$ at most $1/2$. ∎

Now we proceed to complete the proof of Theorem 3.15. Suppose $(\mathcal{Q},\mathcal{X})$ has sample complexity greater than $n$ for $(\alpha+\alpha^{\prime},\beta)$-accuracy (with failure probability $1/2$) and $(6\varepsilon,(e^{2\varepsilon}+e^{5\varepsilon})\delta)$-differential privacy. By Lemma 3.16, for every $(\alpha,\beta)$-accurate mechanism $\mathcal{A}$ for $\mathcal{Q}$ there exists a database $D\in\mathcal{X}^{m}$ with $m=\lfloor n\varepsilon\rfloor$, a set $T$, and an index $i$ such that

We now argue that it is without loss of generality to restrict our attention to mechanisms $\mathcal{A}$ whose range is the finite set $I_{m}^{|\mathcal{Q}|}=\{0,\frac{1}{2m},\frac{1}{m},\ldots,1-\frac{1}{2m},1\}^{|\mathcal{Q}|}$. To see this, note that the exact answer to any counting query $q$ on a database $D\in\mathcal{X}^{m}$ is in the set $\{0,\frac{1}{m},\frac{2}{m},\ldots,1-\frac{1}{m},1\}$. Therefore, if an answer $a\in$ satisfies $|a-q(D)|\leq\alpha$, then the value

is a point in $I_{m}$ that also satisfies $|\bar{a}-q(D)|\leq\alpha$. Thus, we will henceforth assume that the mechanism’s output lies in this finite range.

We now apply the min-max theorem from game theory (or equivalently, linear programming duality), to exhibit a fixed distribution on $(D,T,i)$ for which Inequality (3) holds. Specifically, consider a two-player zero-sum game in which Player 1 chooses a triple $(D,T,i)$, where $D\in\mathcal{X}^{m}$, $T\subseteq I_{m}^{|\mathcal{Q}|}$, and $i\in[m]$, and Player 2 chooses a randomized function $\mathcal{A}:\mathcal{X}^{m}\to I_{m}^{|\mathcal{Q}|}$ that is $(\alpha,\beta)$-accurate for $\mathcal{Q}$. Let the payoff to Player 1 be

By inequality (3), the value of this game is greater than $\delta$. So by the min-max theorem there exists a mixed strategy for Player 1 that achieves a payoff greater than $\delta$ against any mixed strategy for Player 2. (Note that we can apply the min-max theorem because we have assumed that the mechanism’s output lies in a finite range.) That is, there exists a distribution $\mathcal{D}$ over triples $(D,T,i)$ such that for any randomized algorithm $\mathcal{A}:\mathcal{X}^{m}\to I_{m}^{|\mathcal{Q}|}$ that takes any $D$ to a feasible vector in $F_{\alpha,\beta}(D)$ with probability at least $2/3$,

Now consider the following code: $\mathit{Gen}$ samples a database $D$, a set $T$, and an index $i$ according to the promised distribution $\mathcal{D}$. The codebook $C$ is $(D_{\pi(1)},\ldots,D_{\pi(m)})$ where $\pi:[m]\to[m]$ is a random permutation. On input an answer vector $a$, the algorithm $\mathit{Trace}$ checks whether $a\in T$. If it is, then $\mathit{Trace}$ outputs $\pi(i)$, and otherwise outputs $\bot$.

To analyze the security of this code, fix a coalition $S$ of $m-1$ users using a pirate strategy $\mathcal{A}_{\mathit{FP}}$. Because the codebook is a random permutation of the rows of $D$, it is equivalent to analyze the original database $D$ and a random coalition of $m-1$ users. Thus the part of the codebook $C_{S}$ given to the pirates is a random set of $m-1$ rows from $D$, i.e. $D_{-j}$ for a random $j\in[m]$ with the junk row at index $j$ removed. The condition that $\mathcal{A}_{\mathit{FP}}$ outputs a feasible answer vector is equivalent to $a=\mathcal{A}_{\mathit{FP}}(C_{S})$ being an $(\alpha,\beta)$-accurate answer vector. Therefore, letting $\mathcal{A}:\mathcal{X}^{m}\to I_{m}^{|\mathcal{Q}|}$ be the algorithm that runs $\mathcal{A}_{\mathit{FP}}$ on its input with the junk row removed, we have

On the other hand, the probability that $\mathit{Trace}$ outputs the user $j$ not in the coalition is

because the events $\{j=i\}$ and $\{\mathit{Trace}(C,a)=i\}$ are independent. Thus by (4),

where both probabilities are taken over the coins of $\mathit{Gen},\mathit{Trace}$, and $\mathcal{A}_{\mathit{FP}}$. ∎

A Composition Theorem for Sample Complexity

In this section we state and prove a composition theorem for sample complexity lower bounds. At a high-level the composition theorem starts with two pairs, $(\mathcal{Q},\mathcal{X})$ and $(\mathcal{Q}^{\prime},\mathcal{X}^{\prime})$, for which we know sample-complexity lower bounds of $n$ and $n^{\prime}$ respectively, and attempts to prove a sample-complexity lower bound of $n\cdot n^{\prime}$ for a related family of queries on a related data universe.

Specifically, our sample-complexity lower bound will apply to the “product” of $\mathcal{Q}$ and $\mathcal{Q}^{\prime}$, defined on $\mathcal{X}\times\mathcal{X}^{\prime}$. We define the product $\mathcal{Q}\land\mathcal{Q}^{\prime}$ to be

Since $q,q^{\prime}$ are boolean-valued, their conjunction can also be written $q(x)q^{\prime}(x^{\prime})$.

We now begin to describe how we can prove a sample complexity lower bound for $\mathcal{Q}\land\mathcal{Q}^{\prime}$. First, we describe a certain product operation on databases. Let $D\in\mathcal{X}^{n}$, $D=(x_{1},\ldots,x_{n})$, be a database. Let $D^{\prime}_{1},\ldots,D^{\prime}_{n}\in(\mathcal{X}^{\prime})^{n^{\prime}}$ where $D^{\prime}_{i}=(x^{\prime}_{i1},\ldots,x^{\prime}_{in^{\prime}})$ be $n$ databases. We define the product database $D^{*}=D\times(D^{\prime}_{1},\ldots,D^{\prime}_{n})\in(\mathcal{X}\times\mathcal{X}^{\prime})^{n\cdot n^{\prime}}$ as follows: For every $i=1,\ldots,n,j=1,\ldots,n^{\prime}$, let the $(i,j)$-th row of $D^{*}$ be $x^{*}_{(i,j)}=(x_{i},x^{\prime}_{ij})$. Note that we index the rows of $D^{*}$ by $(i,j)$. We will sometimes refer to $D^{\prime}_{1},\ldots,D^{\prime}_{n}$ as the “subdatabases” of $D^{*}$.

The key property of these databases is that we can use a query $q\land q^{\prime}\in\mathcal{Q}\land\mathcal{Q}^{\prime}$ to compute a “subset-sum” of the vector $s_{q^{\prime}}=(q^{\prime}(D^{\prime}_{1}),\ldots,q^{\prime}(D^{\prime}_{n}))$ consisting of the answers to $q^{\prime}$ on each of the $n$ subdatabases. That is, for every $q\in\mathcal{Q}$ and $q^{\prime}\in\mathcal{Q}^{\prime}$,

Thus, every approximate answer $a_{q\land q^{\prime}}$ to a query $q\land q^{\prime}$ places a subset-sum constraint on the vector $s_{q^{\prime}}$. (Namely, $a_{q\land q^{\prime}}\approx\frac{1}{n}\sum_{i=1}^{n}q(x_{i})q^{\prime}(D^{\prime}_{i})$) If the database $D$ and family $\mathcal{Q}$ are chosen appropriately, and the answers are sufficiently accurate, then we will be able to reconstruct a good approximation to $s_{q^{\prime}}$. Indeed, this sort of “reconstruction attack” is the core of many lower bounds for differential privacy, starting with the work of Dinur and Nissim [DN03]. The setting they consider is essentially the special case of what we have just described where $D^{\prime}_{1},\ldots,D^{\prime}_{n}$ are each just a single bit ($\mathcal{X}^{\prime}=\{0,1\}$, and $\mathcal{Q}^{\prime}$ contains only the identity query). In Section 5 we will discuss choices of $D$ and $\mathcal{Q}$ that allow for this reconstruction.

We now state the formal notion of reconstruction attack that we want $D$ and $\mathcal{Q}$ to satisfy.

for at least a $1-\beta$ fraction of queries $q\in\mathcal{Q}$, $\mathcal{B}_{D}(a)$ outputs a vector $t\in^{n}$ such that

Then we say that $D\in\mathcal{X}^{n}$ enables an $\alpha^{\prime}$-reconstruction attack from $(\alpha,\beta)$-accurate answers to $\mathcal{Q}$.

A reconstruction attack itself implies a sample-complexity lower bound, as in [DN03]. However, we show how to obtain stronger sample complexity lower bounds from the reconstruction attack by applying it to a product database $D^{*}$ to obtain accurate answers to queries on its subdatabases. For each query $q^{\prime}\in\mathcal{Q}^{\prime}$, we run the adversary promised by the reconstruction attack on the approximate answers given to queries of the form $(q\land q^{\prime})\in\mathcal{Q}\land\{q^{\prime}\}$. As discussed above, answers to these queries will approximate subset sums of the vector $s_{q^{\prime}}=(q^{\prime}(D^{\prime}_{1}),\ldots,q^{\prime}(D^{\prime}_{n}))$. When the reconstruction attack is given these approximate answers, it returns a vector $t_{q^{\prime}}=(t_{q^{\prime},1},\ldots,t_{q^{\prime},n})$ such that $t_{q^{\prime},i}\approx s_{q^{\prime},i}=q^{\prime}(D^{\prime}_{i})$ on average over $i$. Running the reconstruction attack for every query $q^{\prime}$ gives us a collection $t=(t_{q^{\prime},i})_{q^{\prime}\in\mathcal{Q}^{\prime},i\in[n]}$ where $t_{q^{\prime},i}\approx q^{\prime}(D^{\prime}_{i})$ on average over both $q^{\prime}$ and $i$. By an application of Markov’s inequality, for most of the subdatabases $D^{\prime}_{i}$, we have that $t_{q^{\prime},i}\approx q^{\prime}(D^{\prime}_{i})$ on average over the choice of $q^{\prime}\in\mathcal{Q}^{\prime}$. For each $i$ such that this guarantee holds, another application of Markov’s inequality shows that for most queries $q^{\prime}\in\mathcal{Q}^{\prime}$ we have $t_{q^{\prime},i}\approx q^{\prime}(D^{\prime}_{i})$, which is our definition of $(\alpha,\beta)$-accuracy (later enabling us to apply a re-identification adversary for $\mathcal{Q}^{\prime}$).