Lower bounds in differential privacy

Introduction

This is a paper about private data analysis, in which a trusted curator holding a confidential database responds to real vector-valued queries. Specifically, we focus on the practice of ensuring privacy for the database elements by adding appropriately generated random noise to the answers, releasing only these noisy responses. A line of study initiated by Dinur and Nissim examines the amount of distortion needed to prevent privacy violations of various kinds [DN03]. Dinur and Nissim did not have a definition of privacy; rather, they had a notion that has come to be called blatant non-privacy; the modest goal, then, was to add enough distortion to avert blatant non-privacy. Since that time, the community has raised the bar by definining (and achieving) powerful and comprehensive notions of privacy [DN03, DMNS06, DKM+06], and the goal has been to preserve $(\varepsilon,0)$-differential privacy and its relaxation, $(\varepsilon,\delta)$-differential privacy. A final goal considered herein, attribute privacy, has a more complicated description, but may be thought of as preventing blatant non-privacy for a single data attribute [KRSU10] in the presence of a certain kind of contingency table query.

The results in the literature vary according to several parameters, including the number $n$ of elements in the database, the size $d$ of the universe from which data elements are drawn, the “amount” and type of privacy desired, and for the purposes of the current work, the arity $k$ of the query. In this paper we strengthen and unify these bounds.

As corollaries of our work, we obtain several “structural” results regarding different types of privacy guarantees:

We separate so-called counting queries from arbitrary low-sensitivity queries, proving the latter requires more noise, or distortion, than does the former;

We separate $(\varepsilon,0)$-differential privacy from its well-studied relaxation $(\varepsilon,\delta)$-differential privacy, even when $\delta\in 2^{-o(n)}$ is negligible in the size $n$ of the database, proving the latter requires less distortion than the former;

We demonstrate that $(\varepsilon,\delta)$-differential privacy is much weaker than $(\varepsilon,0)$-differential privacy in terms of mutual information of the transcript of the mechanism with the database even when $\delta\in 2^{-o(n)}$ is negligible in the size $n$ of the database.

To describe our results even at a high level we must outline the privacy-preserving database model, the notion of distortion or noise that may be employed in order to preserve privacy, and the meaning of the goals of the adversary: blatant non-privacy, violation of $(\varepsilon,0)$-differential privacy, violation of $(\varepsilon,\delta)$- differential privacy, and attribute non-privacy.

Typically, the curator of a database receives questions to which it responds with potentially noisy answers. There are two possible settings here. One is that the queries are received by the curator one at a time. The other situation is that all the queries are received by the curator at once and it then publishes (noisy) answers to all of them at once. The former is called the interactive setting and the latter is called the non-interactive setting. All our lower bounds are in the non-interactive setting making them applicable to the interactive setting as well.

We now formally introduce the definition of mechanism and privacy.

We next state the definition of $\epsilon$-differential privacy (introduced by Dwork et al. in [DMNS06]) and $(\epsilon,\delta)$-differential privacy (introduced by Dwork et al. in [DKM+06]).

The mechanism is said to be $(\epsilon,\delta)$-differentially private if

Typically, $\delta$ is set to be negligible in $n,k$.

We remark that we do not define the notion of noise very precisely here as the notion of noise depends on the context. However, in the context of differential privacy, we use the following definition of noise.

While differential privacy is a very strong notion of privacy, sometimes one can show that even very modest definitions of privacy get violated. One such notion is that of blatant non-privacy. We say that a mechanism $M$ for answering $F$ over databases of size $n$ and universe size $d$ is blatantly non-private, if there is an attack $A$ such that w.h.p. over the answer $y$ returned by the mechanism $M$, $A(y)$ differs from the database only at $o(1)$ fraction of the places. Yet another very weak notion of privacy that is interesting to us is that of attribute non-privacy. The formal definition follows :

where $Y\circ x$ simply denotes the obvious concatenation of $Y$ and $x$. $A$ need not be computationally efficient and the constant $1/10$ is arbitrary and can be replaced by any positive constant.

We give tight lower bounds on noise for ensuring $(\varepsilon,\delta)$-differential privacy for $\delta>0$. This proof relies on a lemma due to [MMP+10] showing that $(\varepsilon,\delta)$-differentially private mechanisms yield a certain kind of unpredictable source. On the other hand, any mechanism that is blatantly non-private cannot yield an unpredictable source. Thus, if the noise is insufficient to prevent blatant non-privacy then it cannot provide $(\varepsilon,\delta)$-differential privacy. We subsequently use the lower bounds of [DN03, DMT07] for preventing blatant non-privacy to get lower bounds on the distortion for $(\epsilon,\delta)$ differential privacy.

We show new lower bounds for blatant non-privacy for the case when the size of the universe is smaller than the size of the database. In particular, we show that there is a counting query such that if the distortion added on at least $1/2+\eta$ fraction of the answers is bounded by $o(n/\sqrt{d})$ (for some $\eta>0$), then there is an attack which recovers a database different from the original database by $o(n)$. Our analysis makes use of a result on large deviation of Rademacher sums.

Lower bound by volume arguments

We now recall the volume based argument of Hardt and Talwar [HT10] to show lower bounds on the noise required for $\epsilon$ differential privacy.

While the line of reasoning in the proof is same as that of [HT10], we do the proof here as the argument in [HT10] works only for counting queries i.e., when $F$ is a linear transformation. On the other hand, the statement and proof of our result works for any query $F$.

However, we can also say that because the noise added by the mechanism $M$ is at most $\eta$,

Also, because the mechanism $M$ is $\epsilon$-differentially private and $\|x_{i}-x_{j}\|_{1}\leq\Delta$, then

This leads to a contradiction if $\Delta\leq(s-1)/\epsilon$ thus proving the assertion.

In this subsection, we prove the following theorem.

Before starting the proof, we make a couple of observations. First of all, note that the statement of the theorem does not give any lower bound for $1\geq\epsilon>1/40$. However, any mechanism which is $\epsilon$-differentially private for $\epsilon$ in the aforementioned range is also $\epsilon^{\prime}$-differentially private for $\epsilon^{\prime}=10/9$. Hence, the noise lower bounds for $\epsilon^{\prime}$-differential privacy for $\epsilon^{\prime}=10/9$ are also applicable for the range of $1\geq\epsilon>1/40$. It is easy to see that up to constant factors, the lower bounds with $\epsilon^{\prime}=10/9$ are optimal for $\epsilon$ in the aforementioned range.

Secondly, we note that it is enough to add noise $O(k/\epsilon)$ to maintain $\epsilon$-differential privacy (using the Laplacian mechanism). Also, because the databases are of size $n$, it is enough to add noise $O(n)$ to maintain $\epsilon$-differential privacy for any $\epsilon\geq 0$. Thus, as long as $k=O(d)$, our lower bounds are tight up to constant factors. Next, we do the proof of Theorem 2.2.

For every $x_{i}$, there is a coordinate $i$ in the mapping.

The $i^{th}$ coordinate of $\mathcal{L}(z)$ is $\max\{n^{\prime}/30-\|x_{i}-z\|_{1},0\}$.

The map $\mathcal{L}$ is $1$-Lipschitz i.e., if $\|z_{1}-z_{2}\|_{1}=1$, then $\|\mathcal{L}(z_{1})-\mathcal{L}(z_{2})\|_{1}\leq 1$.

Proof: We observe that for any $z_{1},z_{2}$ such that $\|z_{1}-z_{2}\|\leq 1$, if $A$ denotes the set of coordinates where at least one of $\mathcal{L}(z_{1})$ or $\mathcal{L}(z_{2})$ are non-zero, then $A$ is either empty or is a singleton set. Given this, the statement in the claim is obvious, since the mapping corresponding to any particular coordinate is clearly $1$-Lipschitz.

Now consider any $x_{h},x_{j}\in S$ such that $h\not=j$. Because of the way $\mathcal{L}$ is defined, it is clear that for any $r_{i}$,

A basic application of the Chernoff bound implies that

This implies that we can fix $r_{1},\ldots,r_{k}$ such that the following is true.

For the subsequent part of this paper, we only consider lower bounds on $\epsilon$-differential privacy for $0<\epsilon<1$ as opposed to $\epsilon>1$. This is because the privacy guarantees one gets becomes unmeaningful when $\epsilon$ is large. However, we do remark that the results can be carried in a straightforward way to the regime of $\epsilon>1$ using combinatorial designs (like we did for Theorem 2.2).

The next consequence is a separation of $(\epsilon,\delta)$ differential privacy from $(\epsilon,0)$ differential privacy for $\delta=2^{-o(n)}$. We note that Hardt and Talwar [HT10] had shown such a separation but that was only when $k=O(\log n)$ and $\delta=n^{-O(1)}$. Again, we use the setting of parameters when $k=d$ and $n=k/\epsilon$. The gaussian mechanism of [DKM+06] shows that to maintain $(\epsilon,\delta)$ differential privacy for any $k$ queries, it sufficies to add noise $O(\sqrt{k\log(1/\delta)}/\epsilon)=o(n)$. However, Theorem 2.2 shows that there is a query which requires adding noise $\Omega(n)$ to maintain $(\epsilon,0)$ differential privacy.

The last consequence of our result is more indirect and is explained next.

2 Information loss in differentially private protocols

In [MMP+10], a connection was established between differentially private protocols and the notion of mutual information from information theory. In fact, as [MMP+10] was dealing with 2-party protocols, the connection was actually between differentially private protocols and that of information content [BYJKS04, BBCR10] which is a symmetric variant of mutual information useful in 2-party protocols. In that paper, it was shown that the information content (which simplifies to mutual information in our setting) between transcript of a $\epsilon$-differentially private mechanism and the database vector is bounded by $O(\epsilon n)$. Using the construction used in the previous subsection, we show that in case of $(\epsilon,\delta)$ differentially private protocols (for any $\delta=2^{-o(n)}$), there is no non-trivial bound on the mutual information between the transcript of the mechanism and the database vector. Thus as far as information theoretic guarantees go, the situation is drastically different for pure differentially private protocols vis-a-vis approximately differentially private protocols. The contents of this subsection are a result of personal communication between the author and Salil Vadhan [DV10].

We first define the notion of mutual information (can be found in standard information theory textbooks).

Given two random variables $X$ and $Y$, their mutual information $I(X;Y)$ is defined as

where $H(X)$ denotes the Shannon entropy of $X$.

The next claim establishes an upper bound on the mutual information between transcript of a differentially private protocol and the database vector.

Next, we state the following claim which says that for $(\epsilon,\delta)$ differentially private protocols, even for an exponentially small $\delta$, the mutual information between the transcript and the input can be as large as $n(1-\eta)$ for any value of $0<\epsilon,\eta<1$. In other words, an $(\epsilon,\delta)$ differentially private protocol does not imply any effective bound on the mutual information between the input and the transcript even as $\epsilon\rightarrow 0$ and $\delta$ is exponentially small.

Proof: We first construct $2^{s}$ vectors in $\{0,1\}^{n}$ (for $s={n(1-\eta)}$) with the property that for any $x_{i},x_{j}$ $(i\neq j)$, $\|x_{i}-x_{j}\|_{1}\geq\eta^{2}n/8$. It is easy to guarantee the existence of such a set of vectors by a simple application of the probabilistic method. The distribution $X$ is simply the uniform distribution over the set $\{x_{1},\ldots,x_{2^{s}}\}$. By construction, all the databases in $X$ are of size bounded by $n$.

Note that for the above mechanism $M$, and database $x$, if $Z$ is sampled from $M(x)$, then the distribution of $M(x)-F(x)$ is same as $(Y_{1},\ldots,Y_{k})$ where each $Y_{i}$ is an i.i.d. $\mathcal{N}(0,\sigma)$ random variable. Thus,

As the following fact shows, the distribution on the right hand side is concentrated around its mean. The fact is possibly well-known but we could not find a reference and hence we prove it in Appendix C.

If $Y_{1},\ldots,Y_{k}$ are i.i.d. $\mathcal{N}(0,\sigma)$ random variables, then,

Here the probability is over the randomness of the mechanism. Putting $\xi=1$ and $\delta=2^{-C(\epsilon,\eta)n}$ for an appropriate constant $C(\epsilon,\eta)$, we get that

As we know, for any $i\not=j$, $\|F(x_{i})-F(x_{j})\|_{2}\geq\eta^{2}n\sqrt{k}/50$. Hence, with probability at least $1-2^{-n}$ over the randomness of the mechanism, for any database $x_{i}\in supp(X)$, if $y$ is sampled from $M(x_{i})$,

Thus, for any $x_{i}$, given $M(x_{i})$, we can recover $x_{i}$ with high probability and hence, we can say

Recall that $I(X;M(X))=H(X)-H(X|M(X))\geq H(X)-1=(1-\eta)n-1\geq(1-2\eta)n$. This completes the proof of the Lemma 2.6.

Lower bound on noise for counting queries

Next, we prove the same result without making any such technical assumptions. Again, our constructions are dependent on combinatorial designs [Pau85]. First, we prove the following simple but useful claim.

where $\Delta^{\prime}=\sqrt{\Delta\cdot a}$.

We now prove a lower bound on the noise required to maintain privacy for random counting queries. As we have said before, Hardt and Talwar [HT10] proved the same result under an additional assumption that the mechanism defined over integral databases can be smoothly extended to fractional databases as well.

Proof: The proof strategy is to come up with databases meeting the hypothesis of Claim 3.1 and use Claim 3.1 to get a counting query $F$. We then use Theorem 2.1 to get a lower bound on the distortion required by any private mechanism to answer $F$. We consider two cases : $k\leq\log d$ and $k>\log d$.

$\forall i$, $\|x_{i}\|_{1}\leq k/80\epsilon$ and $\forall i\not=j$, $\|x_{i}-x_{j}\|_{1}\geq k/160\epsilon$

Again, we have $2^{k/20}$ databases which differ by at most $k/(40\epsilon)$ and hence we can apply Theorem 2.1 to get that to maintain $\epsilon$-differential privacy, any mechanism needs to add $\Omega\left(\frac{\sqrt{k\log(d/k)}}{\epsilon}\right)$ noise.

Lower bounds for approximate differential privacy

In this section, we consider databases which are elements of $\{0,1\}^{n}$ or in other words we consider the case when the universe size $d=n$ and the databases are allowed to have exactly one element of each type. We note that restricting databases to bit vectors is a well-considered model in literature including [DN03, DMT07, MMP+10] among others.

is not $(\epsilon,\delta)$ differentially private. In other words, any mechanism $M$ which with significant probability i.e., $3\sqrt{\delta}$ answers at least $1/2+\gamma$ fraction of the $k$ queries with at most $\eta\sqrt{n}$ noise, is not $(\epsilon,\delta)$ differentially private.

To do the proof of Theorem 4.1, we first need to introduce some definitions previously discussed in [MMP+10]. We do note that the paper [MMP+10] deals with the two-party setting but the relevant definitions and the lemma we use here easily extend to the standard (curator-client) setting of privacy.

A random variable $Y\in\{0,1\}^{n}$ is said to be $\delta$-approximate strongly $\alpha$-unpredictable bit source (for $\alpha\geq 1$) if with probability $1-\delta$ over $i\in[n]$ and $(y_{1},\ldots,y_{i-1},y_{i},y_{i+1},\ldots,y_{n})\leftarrow Y$

The next lemma (proven in [MMP+10] for the two-party setting) roughly says that for any $(\epsilon,\delta)$ private mechanism, conditioned on the transcript of the mechanism, the distribution of the database is a $\delta$-approximate strong $2^{\epsilon}$-unpredictable source. More precisely, we have the following lemma.

The above lemma trivially follows from Lemma 20 of [MMP+10] (full version) and hence we do not prove it here. Before, proving Theorem 4.1, we need to recall the following theorem from [DMT07] (Theorem 24 in the paper).

The following corollary follows immediately from Theorem 4.4.

Let $X$ denote the uniform distribution over $\{0,1\}^{n}$. First, using Lemma 4.3, we get that over the randomness of the mechanism $M$ and the choice of $x\in X$, if we sample a transcript $t$ from $M(x,F)$, then for any positive $\mu$, the distribution $X|_{M(x,F)=t}$ is a $\delta_{t}$-approximate strongly $2^{\epsilon+\mu}$-unpredictable sources where $\delta_{t}$ satisfies

for $\beta=3\sqrt{\delta}$. Clearly such a mechanism $M$ is not $(\epsilon,\delta)$ differentially private because with probability at least $\beta=3\sqrt{\delta}$, the algorithm $A$ will be able to predict at least $1-\sqrt{\delta}$ fraction of the positions which contradicts that with probability $1-2\sqrt{\delta}$, the distribution $X|_{M(x,F)=t}$ is a $2\sqrt{\delta}$ -approximate strongly $2^{\epsilon+10}$-unpredictable source.

In this section, we consider attacks on privacy using linear programming. In particular, we use the technique of LP decoding (previously used in [DMT07] in context of privacy) to give attacks which violate even minimal notions of privacy when $1-\epsilon_{0}$ (for some $\epsilon_{0}>0$) fraction of the queries are released with insufficient noise. We do this by establishing a connection between Euclidean sections and use of LP decoding in context of privacy which does not seem to have explicitly appeared in the literature before. We remark that the relation between LP decoding and Euclidean spaces is very well known in context of compressed sensing [CRTV05]. However, in case of privacy, the adversary is allowed to add small error to say $99\%$ of the entries and arbitrary error to the remaining $1\%$ of the entries. In context of compressed sensing however, the adversary is allowed to add error to only $1\%$ of the entries.

where $\beta=\delta-2\sqrt{\delta^{\prime}}$.

Proof: Let $S\subseteq[k]$ and $|S|\leq\delta^{\prime}\cdot k$. Then, by Jensen’s inequality, we can say that

We get the stated result by putting $\beta=\delta-2\sqrt{\delta^{\prime}}$.

Let $S=\{i:|e_{i}|>\alpha\}$. Then, from the above, we get that

We next use $\|A\cdot z-e\|_{\overline{S},1}\geq\|A\cdot z\|_{\overline{S},1}-\|e\|_{\overline{S},1}$ on the right hand side of the above inequality to simplify and get

Combining the above with (3), we get that

Similarly, consider any $c\in\{-1,0,1\}^{d^{\prime}}$ and define $|c|=\sum_{j=1}^{d^{\prime}}|c_{i}|$ i.e., $|c|$ represents the number of non-zero entries in $c$. We note that the set $S$ defined as

Now, for any $c\in\{-1,0,1\}^{d^{\prime}}$ and $z\in\{-1,1\}^{d^{\prime}}$, we define $F_{c}(z)$ as follows :

In other words, $F_{c}(z)$ is $1$ iff the following holds for every $j$ : If $c_{j}=1$, then $z_{j}=1$ and if $c_{j}=-1$, then $z_{j}=-1$.

We now state our main theorem of this section.

is attribute non-private. Further, the algorithm which violates attribute privacy is efficient and uses LP decoding.

Here $\log_{(q)}n$ is an iterated logarithm which is defined precisely later on. However, we wanted to state the main result of this section in the beginning itself before diving into the proof structure.

Before, we glimpse into how they prove their result and our improvement on that, we need to describe the Hadamard product of matrices.

where $A[i,k]$ represents the element in row $i$ and column $k$.

The attack in [KRSU10] is an efficient algorithm (is simply matrix inversion) and is basically dependent on showing existence of a Hadamard product of small matrices such that all its singular values are large. In particular, they show the following reduction.

Subsequently, to prove Theorem 5.5, they proved the following lemma.

To describe the main technical result of Rudelson [Rud11], we need to define iterated logarithms.

$\log_{(r)}n=\log_{(1)}\ (\log_{(r-1)}n)$

Theorem 5.11 and Lemma 5.9 immediate imply our main theorem which we restate here for convenience.

is attribute non-private. Further, the algorithm which violates attribute privacy is efficient and uses LP decoding.

Noise lower bounds for blatant non-privacy

In this section, we prove lower bounds on the noise required to prevent blatant non-privacy while answering random counting queries. Dinur and Nissim [DN03], in their seminal paper, had shown that answering $O(n\log^{2}n)$ subset sum queries with $o(\sqrt{n})$ noise results in blatant non-privacy. In other words, they had proven the following theorem.

The algorithm $A$ in the above result is efficient and uses linear programming. Since then, several improvements were made to this result including the results in [DMT07] where the same conclusion was achieved under the weaker hypothesis that

for any $\eta>0$. While the attack was inefficient, they also showed how to use LP decoding to get an efficient attack and they could achieve this under the weaker hypothesis

Before going ahead with the proof, we remark that while both the algorithms $A$ and $B$, as described in the proof are inefficient, the former can be made efficient using linear programming (along the lines of [DN03, DMT07]). We choose not to do it for the sake if simplicity.

we get that for all $x^{\prime}$ such that $\|x-x^{\prime}\|_{1}\geq cn$,

Thus, when we have the query $F$ described above, the algorithm $A$ will never return $x^{\prime}$ if $\|x-x^{\prime}\|_{1}\geq c{n}$ and hence the correctness is proven.

We now come to the second part of the theorem. The algorithm $B$ is described as follows :

Return $x^{\prime}$ if $\forall i$, $[|M(x^{\prime},F)_{i}-F(x)_{i}|=o(\theta)$

This means that putting $k=\exp\left(\frac{2d\theta^{2}}{{n}^{2}}\right)\cdot 2d\log n$

Hence, we get that (for all $x^{\prime}$ such that $\|x-x^{\prime}\|_{1}\geq c{n}$)

This shows that algorithm $B$ will never return $x^{\prime}$ if $\|x-x^{\prime}\|_{1}\geq c{n}$ and hence the correctness is proven.

Acknowledgements

First and foremost, I would like to thank Cynthia Dwork for introducing me to the problems discussed in this paper, immense help with the presentation and the technical help. Even though she declined to co-author the paper, without her contributions, this paper would not have existed. This work was almost entirely done during a very enjoyable summer in 2010 at MSR Silicon Valley while the author was a summer intern with her. I would also like to thank Salil Vadhan for his kind permission to include the results of subsection 2.2 in this paper.

The author would like to thank Moritz Hardt and Mark Rudelson for very helpful conversations. The question of getting a lower bound for blatant non-privacy with dependence on universe size came up in a discussion with Moritz Hardt. I would like to thank Mark for answering countlessly many questions about random matrices and anti-concentration. I also had useful conversations about this work with Ilya Mironov, Elchanan Mossel, Omer Reingold, Adam Smith, Alexandre Stauffer, Kunal Talwar, and Salil Vadhan.

I would also like to thank the SODA 2012 and TCC 2012 reviewers for many useful comments including pointing out an error in the earlier proof of Lemma 2.6.

References

Appendix A Construction of databases with large differences

$\forall i$, $\|x_{i}\|_{1}\leq k/80\epsilon$ and $\|x_{i}-x_{j}\|_{1}\geq k/160\epsilon$

Proof: We use construction of combinatorial designs from [Pau85, RRV99]. Namely, the main theorem in [Pau85] states that it is possible to construct sets $S_{1},\ldots,S_{m}\subseteq[d]$ with the following properties :

$\forall i\not=j$, $|S_{i}\cap S_{j}|\leq\rho$

Now, consider the set $A=\{y_{1},\ldots,y_{2^{k/20}}\}$ be the characteristic vectors of the sets $S_{1},\ldots,S_{2^{k/20}}$. Now, we observe that setting $x_{i}=\lfloor(\log(d/k)/80\epsilon)\rfloor\cdot y_{i}$ achieves all the stated conditions.

$\forall x,y\in S$ and $x\not=y$, $\|x-y\|_{1}\geq n/10$

Proof: Consider a set $C\subseteq\{0,1\}^{d}$ with the following two properties.

$\forall x,y\in C$, $x\not=y$, $\|x-y\|_{1}\geq d^{\prime}/9$

$\forall x\in C$, $\|x\|_{1}\leq d^{\prime}$.

Such a set $C$ exists. To see this, consider an error correction code $C^{\prime}\subseteq\{0,1\}^{d^{\prime}}$ with distance $d^{\prime}/9$ and rate $4/5$. Such a code exists via probabilistic method. Now, the set $C$ is constructed as

We claim that the set $S$ satisfies the required conditions. The first and the third parts of claim are obvious. Note that for any $x,y\in S$, $\|x-y\|_{1}\geq(d^{\prime}/9)\cdot\lfloor(1/4\epsilon)\rfloor\geq d^{\prime}/(40\epsilon)\geq n/10$. The penultimate inequality uses that $(1/4\epsilon)\geq 10$.

The above claim worked for $\epsilon<1$. We now prove a claim which works in the regime of $\epsilon>1$.

$\forall x,y\in S$ and $x\not=y$, $\|x-y\|_{1}\geq n/10$

Further, $S$ is in fact a subset of $\{0,1\}^{d}$.

Proof: We observe that the construction of set $S$ is related to the construction of combinatorial designs [Pau85, RRV99] with specific parameters. In particular, the result in [Pau85] allows us to construct sets $S_{1},\ldots,S_{m}\subseteq[d]$ with the following properties :

$\forall i$, $|S_{i}|\leq\lfloor n\rfloor$

$\forall i\not=j$, $|S_{i}\cap S_{j}|\leq\rho\leq\lfloor 4n/5\rfloor$

provided that $d\geq\frac{C^{\prime}\cdot n^{2}\cdot m^{1/\rho}}{\rho}$ (for some large constant $C^{\prime}$). Using the conditions on $d,d^{\prime}$ and $n$, we see that the condition is satisfied provided $C$ is sufficiently large compared to $C^{\prime}$. Clearly, if $x_{1},\ldots,x_{m}$ are characteristic vectors of the sets $S_{1},\ldots,S_{m}$ respectively, then

Appendix B Large deviation of Rademacher sums from their mean

In this section, we prove the following inequality which says that Rademacher sums have large deviations from their mean with significant probability.

An immediate application of the above theorem is the following corollary.

The following theorem about large deviation of Rademacher sums from the mean was proven by Montgomery-Smith [MS90].

To use Theorem B.3 in order to prove the Theorem B.1, we make the following claim.

The theorem immediately follows by plugging the lower bound on $K(y,t)$ from the above claim in Theorem B.3.

Appendix C Concentration of measure for the sum of squares of Gaussians

In this section, we prove a result about the concentration of measure for the sum of squares of i.i.d. $\mathcal{N}(0,\sigma)$ random variables. While this seems to be a well studied distribution in literature, we could not find a usable result on its concentration and hence we prove the following theorem here.

Let $X_{1},\ldots,X_{k}$ be $k$ i.i.d. $\mathcal{N}(0,\sigma)$ random variables. Then,

Proof: Note that by definition, for any $i\in[k]$,

Then, consider the random variable $Z_{i}=\exp\left(\frac{X_{i}^{2}}{4\sigma^{2}}\right)$. We note that

Using independence of the $X_{i}$’s, we get that the above expression is

Putting $\lambda=2(1+\eta)k\sigma^{2}$, we get that the above expression is