Differential Privacy and Sublinear Time Are Incompatible Sometimes

We start the construction of our lower bound with the privacy lower bounds based on fingerprinting codes [8]. For a set of $n$ users and a parameter $c\le n$, an $(n,d,c)$-FPC consists of two algorithms $(Gen,Trace)$. The algorithm $Gen$ on input $n$ outputs a codebook $C\in {\{0,1\}}^{n\times d}$ where each row is a codeword of user $i\in [n]$ with code length $d=d(n,c)$. It guarantees that if at most $c$ users collude to combine their codewords into a new codeword $c^{\prime }$ and the new code satisfies some (mild) marking condition – namely that if every colluder has the same bit $b$ in the $j$-th bit of their codeword, then the $j$-th bit of $c^{\prime }$ must also be $b$ – then the $Trace$ algorithm of the fingerprinting code can identify at least one colluder with high probability.³³3The idea of fingerprinting codes becomes colorful when imagining a publisher who distributes advance copies to press and wants to add watermarks that are robust, e.g., against pirated copies that result from averaging the copies of multiple colluders. To see that the marking assumption is a mild condition, consider that the codeword is hidden in the much larger content. Bun et al. [8] used fingerprinting codes to show that the output of any accurate algorithm for the one-way marginal problem must satisfy the marking condition for sufficiently large $d$, and therefore, at least one row (i.e., individual) from the database is identifiable – making this algorithm not private. In more detail, given a fingerprinting code $(Gen,Trace)$, suppose a coalition of $n$ users builds dataset $D\in {\{0,1\}}^{n\times d}$ where each row corresponds to a codeword of length $d$ from the codebook $Gen$. For $j\in [d]$, if every user has bit $b$ in the $j$-th bit of their codeword then the one-way marginal answer for that column will be $b$. It is shown that any algorithm that has non-trivial accuracy for answering the one-way marginals on $D$ can be used to obtain a codeword that satisfies the marking condition. Therefore, using $Trace$ on such a codeword leads to identifying an individual in dataset $D$. Since an adversary is able to identify a user in $D$ based on the answer given by the algorithm, this clearly violates DP.

In our model, an algorithm only sees a subset of the entries in the entire database via attribute queries. Suppose a coalition of $c\le n$ users belongs to a dataset $D\in {\{0,1\}}^{n\times d}$ where each row corresponds to a codeword of length $d$. As a warm-up, let us first assume that an algorithm that solves the one-way marginal problem on input $D\in {\{0,1\}}^{n\times d}$ always queries for entire rows and that an adversary can simulate a query oracle to the algorithm’s queries, i.e., respond with rows that exactly correspond to the set of $c$ colluders (for more details see Section 5.1). To apply a fingerprinting code argument to such an algorithm, an adversary must identify a row from this subset of $c$ rows by examining the output of the algorithm. However, since the accuracy guarantee of the algorithm applies (only) to the whole dataset, we cannot make the same argument as above to conclude that the marking condition holds for the subsample of rows. In other words, we need to ensure that the output of an accurate algorithm that only sees a subsample of rows can also satisfy the marking condition. The techniques of [8] do not ensure such a property.

In order to achieve the property described above, we need to ensure that any attempt of the algorithm to spoil the marking condition would contradict its accuracy guarantees. We achieve this property by padding $O(d)$ additional columns to the codebook $C$ to obtain $C^{\prime }\in {\{0,1\}}^{n\times d^{\prime }}$, where $d^{\prime }=O(d)$, so that (codebook) columns whose output could be modified to violate the marking condition and (padded) columns whose modification would violate the accuracy guarantee are indistinguishable in the subsample with good probability. Padded columns have been used to define a variant of a fingerprinting code in previous work to achieve smooth DP lower bounds [22]. In our work, we not only need a variant of FPC with padded columns, but we also need to permute the rows of the codebook (see Section 4 for the construction). This is because we need to define a sampling procedure with certain properties for the adversary to obtain a dataset on $c$ rows from a distribution over databases of $n$ rows, and one way to do so is permuting the rows of the codebook and outputting the first $c$ rows (e.g., see Theorem 15 and Theorem 27).

Finally, we overcome the assumption that the algorithm queries for entire rows by applying a secret sharing scheme to the padded codebook (see Section 5.2). In particular, an adversary can encode each row $x_i\in {\{0,1\}}^{d^{\prime }}$ with respect to a random polynomial of degree $2d^{\prime }-1$ as a share of size $2d$. The shares are defined by the $d$ codebook values and $d$ random values from the field. For each query of the algorithm, the adversary answers with a share from the second half. Information theory implies that the algorithm can only recover the $d$ codebook values after querying for all $d$ random value shares. Thus, we obtain a derivate of the one-way marginal problem that requires the algorithm to query an entire row to reveal the padded code book row. While there exist a DP algorithm (Theorem 24) and a sublinear-time algorithm (Theorem 25) for this derived problem as well, we show that there exists no sublinear-time DP algorithm (up to a log factor) that can query for arbitrary entries in the database.

On input $D_H\in {({\{0,1\}}^d)}^n$, an algorithm can query the random oracle $H$ through row queries, i.e., given a row index $i\in [n]$ of $D_H$, the answer given is $H(i)\in {\{0,1\}}^d$. We note that our final result in this subsection will still be presented in the form of attribute queries as 1 row query translates to $d$ attribute queries.

Observe that there exists an $(\epsilon ,\delta )$-DP algorithm for ${𝒫}_{RO}(D)$ that on input $D_H$, queries the entire dataset via row queries to the random oracle $H$, i.e., it makes $dn=O(d\sqrt{d})$ queries. After obtaining the rows to the underlying dataset $D$ it releases the one-way marginals using the Gaussian Mechanism (see Lemma 9). We also note that there exists a sublinear non-DP algorithm for ${𝒫}_{RO}(D)$ which makes $O(d\log d)$ queries, which is a simple corollary of Hoeffding bounds. Our goal in this section is to prove the lower bound below. Recall that $n\in \mathrm{\Omega }(\sqrt{d})$, so the problem size is $\mathrm{\Omega }(d\sqrt{d})$.

We present a high level overview of the proof of Theorem 14 here. We first show that given an $(n,d,c)$-FPC, there exists a distribution on $c$ rows from which an adversary $ℬ$ can sample and create an $n$-row input instance for an algorithm $𝒜$ that accurately solves ${𝒫}_{RO}$ (see Theorem 15). Next we argue that the rounded output of $𝒜$, denoted as $𝐚$, is a feasible codeword for the sample of $c$ rows as long as $𝒜$ is accurate in a non-trivial manner and $𝐚$ is feasible for the entire dataset (see Lemma 17). The adversary $ℬ$ can then use the output from $𝒜$ to (potentially) reidentify an individual from the coalition of size $c$. Next we relate these claims back to DP through Lemma 18, which states that if there exists a distribution $𝒞$ on $c\le n$ row databases according to Theorem 15, then there is no $(\epsilon ,\delta )$-DP algorithm $𝒜$ that is $(1/3,1/3)$-accurate for ${𝒫}_{RO}$ with $\epsilon =O(1)$ and $\delta =o(1/c)$. Finally, invoking the Tardos construction for fingerprinting codes in Theorem 7 gives us our lower bound.

Let $(Gen,Trace)$ be the promised $(n,d,c)$-fingerprinting code in the theorem statement. We first construct a PR-PPC $(n,d,c,\mathrm{\ell })$-FPC with $\mathrm{\ell }:=100d$ (see Section 4 for details).

The distribution ${𝒞}_{𝒮}$ on $c$-row databases is implicitly defined through the sampling process below

1. 1.

   Let $C^{\prime }\leftarrow Ge{n}^{\prime }(n,100d)$ (see Algorithm 1) where $C^{\prime }\in {\{0,1\}}^{n\times d^{\prime }}$ and $d^{\prime }=d+100d=101d$. Note that $Ge{n}^{\prime }$ also outputs ${\pi }_R$ which is a public permutation on rows.

2. 2.

   Let $C_S^{\prime }=(x_1,\mathrm{\dots },x_c)\in {\{0,1\}}^{c\times d^{\prime }}$ be the first $c$ rows of $C^{\prime }\in {\{0,1\}}^{n\times d^{\prime }}$

3. 3.

   Output $C_S^{\prime }$

Next we define the privacy adversary $ℬ$.

Adversary $ℬ$ receives $C_S^{\prime }$ as input and does the following:

1. 1.

   Create a database $D=(r_1,\mathrm{\dots },r_n)\in {\{0,1\}}^{n\times d^{\prime }}$ where each row $r_i\in {\{0,1\}}^{d^{\prime }}$ consists of 0/1 entries sampled independently and uniformly at random.

2. 2.

   Given oracle access to randomized algorithm $𝒜$ which solves ${𝒫}_{RO}$ on input $D$, $ℬ$ simulates the answer to the distinct $i_j$-th row query (where $j\in [c]$) made by $𝒜$ to random oracle $H$ as follows:

   1. (a)

      Return $H(i_j):=r_{i_j}\oplus x_j$.

3. 3.

   Let $𝐚$ be the output of $𝒜(D)$ where $𝐚\in {[0,1]}^{d^{\prime }}$. Round each entry of $𝐚$ to $\{0,1\}$, call this new vector $\overline{𝐚}\in {\{0,1\}}^{d^{\prime }}$.

4. 4.

   Output $Trac{e}^{\prime }(\overline{𝐚})$

We focus on proving that Property 1 and Property 2 of the theorem statement are indeed satisfied by adversary $ℬ$.

Recall the notation in Definition 13 where ${𝒫}_{RO}(C^{\prime })$ means that ${𝒫}_{RO}$ releases the one-way marginals of the underlying dataset $C^{\prime }$. We first show that $𝒜$ solving ${𝒫}_{RO}(H(D))$ is perfectly indistinguishable from $𝒜$ solving ${𝒫}_{RO}(C^{\prime })$ in Lemma 16. This is necessary as $Trac{e}^{\prime }$ can only identify an individual in the coalition of size $c$ with respect to the codebook $C^{\prime }$ produced by $Ge{n}^{\prime }$.

We define the following experiments.

1. 1.

   Given $C^{\prime }=(x_1,\mathrm{\dots },x_n)$ where $(C^{\prime },s{t}^{\prime })\leftarrow Ge{n}^{\prime }(\mathrm{\ell })$ with $\mathrm{\ell }=100d$, let $C_S^{\prime }=(x_1,\mathrm{\dots },x_c)$.

2. 2.

   Create a database $D=(r_1,\mathrm{\dots },r_n)$ where $r_i\in {\{0,1\}}^{d^{\prime }}$ are random entries.

3. 3.

   Let $𝐚$ be the output of $𝒜(D)$ where $𝐚\in {[0,1]}^{d^{\prime }}$. Simulate $H$ as follows:

   1. (a)

      Let $i_1,\mathrm{\dots },i_c$ be distinct queries made to $H$. For $j\in [c]$, fix $H(i_j):=r_{i_j}\oplus x_j$

1. 1.

   Given codebook $C^{\prime }=(x_1,\mathrm{\dots },x_n)$ where $(C^{\prime },s{t}^{\prime })\leftarrow Ge{n}^{\prime }(\mathrm{\ell })$ with $\mathrm{\ell }=100d$, let $H(C^{\prime })=(z_1,\mathrm{\dots },z_n)$ (see Definition 13 for $H(\cdot )$ notation).

2. 2.

   Let $𝐚\leftarrow 𝒜(H(C^{\prime }))$ where $𝐚\in {[0,1]}^{d^{\prime }}$.

   1. (a)

      Let $i_1,\mathrm{\dots },i_c$ be distinct arbitrary queries made to $H$. For $j\in [c]$, $H$ returns the following answer $H(i_j):=z_{i_j}\oplus x_j$

In the Real World, $𝒜$ is provided $D=(r_1,\mathrm{\dots },r_n)$ as input (where $D$ is generated in the same manner as by adversary $ℬ$), while the Ideal World is one in which $𝒜$ takes $H(C^{\prime })$ as input. We show that $𝒜$ learns the same information in the Real World and the Ideal World, i.e., these views are perfectly indistinguishable. Observe that the only difference from the viewpoint of $𝒜$ between the Real World and the Ideal World is that $H$ is simulated in the former via indices fixed by $C_S^{\prime }$ whereas $H$ is queried on arbitrary indices in the latter. Since the rows of $C^{\prime }$ have already been permuted (recall Algorithm 1), by nature of the random oracle $H$, these two instances are perfectly indistinguishable. $◀$

Recall that the security condition of the fingerprinting code (see Definition 5) only holds if $\overline{𝐚}$ is a feasible codeword for the coalition of rows, i.e., $C_S^{\prime }$ in our case. The following lemma states that if $𝒜$ is accurate for ${𝒫}_{RO}(C^{\prime })$, then the rounded output of $𝒜$ is indeed a feasible codeword for both $C^{\prime }$ and $C_S^{\prime }$.

Assuming that $𝒜$ is $(1/3,1/3)$-accurate for ${𝒫}_{RO}(C^{\prime })$, we first show that $\overline{𝐚}$ is a feasible codeword for $C^{\prime }$ with probability at least 2/3. By the accuracy guarantee of $𝒜$, we know that for any column $i_j$ $|{𝐚}_{i_j}-a_{i_j}|\le 1/3$ where $a_{i_j}$ is the actual 1-way marginal for column $i_j$ with probability at least 2/3. Thus for any column $i_j$ of all 1’s in $C^{\prime }$, ${𝐚}_{i_j}\ge 2/3$ which means ${\overline{𝐚}}_{i_j}=1$, thus satisfying the marking condition. A similar argument holds for the case when a column is all 0’s.

Next, using the fact that we use a PR-PPC $(n,d,c,100d)$-FPC and that $\overline{𝐚}\in F(C^{\prime })$ with probability at least 2/3, we can invoke Lemma 12 which states that the feasible sample property is satisfied by our PR-PPC FPC construction. Note that in our case, the sampling algorithm described in Definition 11 is $𝒜$ together with the postprocessing step of rounding the output of $𝒜$. Also, even though $𝒜$ takes the entire dataset as input, it effectively only has access to the rows of the underlying sample via queries to $ℬ$ and thus satisfies the properties required in Definition 11. Lemma 12 states that with probability $\le \frac{1}{100}$, $\overline{𝐚}$ is not a feasible codeword for $C_S^{\prime }$. By a union bound we have that $1-\frac{1}{3}-\frac{1}{100}$, $\overline{𝐚}$ must be a feasible codeword for $C_S^{\prime }$. $◀$

From the above Lemma 17, we have that $𝒜$ is $(1/3,1/3)$-accurate for ${𝒫}_{RO}(C^{\prime })$ implies that $\overline{\text{a}}$ is a feasible codeword for $C_S^{\prime }$. By the security of the fingerprinting code, Corollaries 10 and 16, we have that $\mathrm{Pr}[\overline{\text{a}}\in F(C_S^{\prime })\wedge Trac{e}^{\prime }(\overline{\text{a}})=⟂]\le \xi$. Since $ℬ$ releases the output of $Trac{e}^{\prime }(\overline{𝐚})$, the event ${ℬ}^{𝒜}(C_S^{\prime })=⟂$ is identical to $Trac{e}^{\prime }(\overline{\text{a}})=⟂$. Thus Property 1 of the theorem statement which states that the probability that $ℬ$ outputs $⟂$ is bounded by $\xi$ follows. Property 2 follows directly from the soundness property of the fingerprinting code. $◀$

Suppose $C_S^{\prime }$ is sampled from the distribution on $c$-row databases ${𝒞}_{𝒮}$ and $ℬ$ is the adversary from Theorem 15. From the lemma statement we know that $𝒜$ is $(1/3,1/3)$-accurate, thus using Lemma 17 and Theorem 15, we have that $\mathrm{Pr}[{\pi }_R({ℬ}^{𝒜}(C_S^{\prime }))\in [c]]\ge 1-\frac{1}{3}-\frac{1}{100}-\xi \ge \mathrm{\Omega }(1)$. By an averaging argument, this means that there exists some $i^{\ast }\in [c]$ for which $\mathrm{Pr}[{\pi }_R({ℬ}^{𝒜}(C_S^{\prime }))=i^{\ast }]\ge \mathrm{\Omega }(1/c)$. However, if $\xi =o(1/c)$ by Property 2 in Theorem 15 we have that $\mathrm{Pr}[{\pi }_R({ℬ}^{𝒜}(C_{S_{-i^{\ast }}}^{\prime }))=i^{\ast }]\le \xi =o(1/c)$.

In other words, the probability of ${ℬ}^{𝒜}$ outputting a fixed output $i^{\ast }$ on neighboring input databases $C_S^{\prime }$ and $C_{S_{-i^{\ast }}}^{\prime }$ is different, which violates $(\epsilon ,\delta )$-DP for any $\epsilon =O(1)$ and $\delta =o(1/c)$. We note here that since $𝒜$ can make at most $c$ row queries, the DP guarantee for $𝒜$ must hold for any neighboring sample of $c$ rows. Since $ℬ$ does some postprocessing of the output from $𝒜$, and we have shown that $ℬ$ cannot be $(\epsilon ,\delta )$-DP, this implies that $𝒜$ cannot be $(\epsilon ,\delta )$-DP for any $\epsilon =O(1)$ and $\delta =o(1/c)$. $◀$

On input $D_S$, an algorithm solving the ${𝒫}_{SS}$ problem can make attribute queries to obtain the underlying dataset $D$ and release its one-way marginals. For a row $i\in [n]$, the $i_j$-th attribute query returns the pair of field elements $({\alpha }_{j+d}^{(i)},p({\alpha }_{j+d}^{(i)}))$ of share $S{S}_d(x_i)$ for $1\le j\le 2d$. We note that the prefix of $S{S}_d(x_i)$ given by ${\alpha }_1^{(i)},\mathrm{\dots },{\alpha }_d^{(i)}$ is published separately after an attribute query for the row $i$ has been queried. In other words, the prefix does not count towards the query complexity of the algorithm. ^{added remark}

For completeness, we first show that the Shamir encoding $S{S}_d$ defined in Definition 20 is $(q(d),d,0)$-secure (as defined in Definition 19) where $q(d)=d$.

Let $x\in {\{0,1\}}^d$ and field $𝔽$ s.t. $|𝔽|>4d$. Recall the secret sharing scheme $S{S}_d(x)=({\alpha }_1,\mathrm{\dots },{\alpha }_d,{\{({\alpha }_j,p({\alpha }_j))\}}_{j=d+1}^{3d})$ defined in Definition 20. We describe two experiments below where the Real World experiment simulates the view of the adversary and the Ideal World experiment just randomly outputs field elements. We will show that these two experiments are perfectly indistinguishable, and the security claim follows.

1. 1.

   Query $S{S}_d(x)$ for the first $q(d)=d$ pairs of coordinates and let the answers be the prefix ${\alpha }_1,\mathrm{\dots }{\alpha }_d$ and ${\{({\alpha }_{j+d},z_{j+d})\}}_{j\in [d]}$.

2. 2.

   Output ${\alpha }_1,\mathrm{\dots }{\alpha }_d$ and ${\{({\alpha }_{j+d},z_{j+d})\}}_{j\in [d]}$

1. 1.

   Uniformly sample ${\alpha }_1^{\prime },\mathrm{\dots },{\alpha }_d^{\prime },{\alpha }_{d+1}^{\prime },\mathrm{\dots },{\alpha }_{2d}^{\prime },r_{d+1},\mathrm{\dots },r_{2d}$ from $𝔽$.

2. 2.

   Output ${\alpha }_1^{\prime },\mathrm{\dots }{\alpha }_d^{\prime }$ and ${\{({\alpha }_{j+d}^{\prime },r_{j+d})\}}_{j\in [d]}$

Since by construction, the first $d$ pairs of coordinates returned by $S{S}_d$ and the prefix of size $d$ correspond to $3d$ random field elements, the view of the Real World is therefore just the uniform distribution on $3d$ field elements and thus is identical to that of the view of the Ideal World. $◀$