Differentially Private Set Representations
Authors: Sarvar Patel
Giuseppe Persiano
Joon Young Seo
Kevin Yeo
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Data Structure
Primary area: privacy
TL;DR: This paper studies the problem of differentially private mechanism for representing sparse sets.

Abstract: We study the problem of differentially private (DP) mechanisms for representing
sets of size $k$ from a large universe.
Our first construction creates
$(\epsilon,\delta)$-DP representations with error probability of 
$1/(e^\epsilon + 1)$ using space at most $1.05 k \epsilon \cdot \log(e)$ bits where
the time to construct a representation is $O(k \log(1/\delta))$ while decoding time is $O(\log(1/\delta))$.
We also present a second algorithm for pure $\epsilon$-DP representations with the same error using space at most $k \epsilon \cdot \log(e)$ bits, but requiring large decoding times.
Our algorithms match the lower bounds on privacy-utility trade-offs (including constants but ignoring $\delta$ factors) and we also present a new space lower bound
matching our constructions up to small constant factors.
To obtain our results, we design a new approach embedding sets into random linear systems
deviating from most prior approaches that inject noise into non-private solutions.

Differentially Private Set Representations
Sarvar Patel" Google
Giuseppe Persiano" Università di Salerno giuper@gmail.cmm com
Joon Young Sco" Google
sarvar@google.com
jyseo&google.com
Kevin Yeo"
Columbia University, Google kwlyaodgoogle.com com
Abstract
We study the problem of differentially private (DP) mechanisms for representing of size from large universe. Our first construction creates (c, 8)DP representations with error probability of 1/(e" 1) using space at most 1.05ke log(e) bits where the time to construct representation O(k (og(1/8)) while decoding time is ([log(1/8)) We also present second algorithm for pure e-DP representations with the same error using space at most ke log(e) bits, but requiring large decoding times. Our algorithms match our lower bounds on privacy-utility trade-offss (including constants but ignoring factors) and we also present a new space lower bound matching our constructions up to small constant factors. To obtain our results, we design a new approach embedding sets into random linear systems deviating from most prior approaches that inject noise into non-private solutions.
Introduction
Consider the problem of releasing a set S of elements from potentially very large universe U differentially privately manner. The goal to construct differentially private representation of S, denoted by S. The representation S can used to try and determine whether an element u E U belongs to the original input set S. may err two ways. For any u E S, Å may report false negative stating that is not in S. Also, for u & S, Å may report a false negative claiming appears in S. Ideally, we should minimize the error probability for maximal utility while obtaining strong privacy for S. This problem useful for applications where users wish to privately disclose information such as sets bookmarked websites, visited IP addresses, installed mobile apps, etc. One particularly important application is training machine learning models using the above examples feature vectors while maintaining user privacy. As some concrete examples, good solutions to our problem could enable privately training models for web traffic forecasting using user's visited webpages [26], app install predictions with user's installed apps sets [5] and detecting shared IP addresses from user's 's visited IP addresses [17].
naive approach is interpret the universe U bit vector where each element corresponds unique entry of the vector E {0, 1P66,, Encoding S C U works by setting the corresponding coordinates of S to I and the rest O. Then, we can apply randomized response [33] to each entry of v. The noisy vector is then released as the encoding of S. Accessing an element proceeds by reading the value at the corresponding coordinate of the noisy vector v. With this approach, the
The authors are listed in alphahetical order.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

encoding size scales linearly with | In most practical applications, the universe U is very large while the input set is quite small. For example, one can consider S to be set of visited websites. The universe U will be the set of all websites that will be impractically large to store while S will be a much smaller set. Our goal is to design construction whose size and encoding time depends only on the input set S size while maintaining small error matching randomized response.
To tackle this problem, prior works started non-private solutions for efficiently representing sets such as Bloom filters [8]. First, the input set is encoded using the non-private solution. Afterwards, each entry of the resulting representation is perturbed by injecting noise according to some distribution. This approach was studied in [1] where they showed the encoding was private. However, their work lacked any analysis on the error probability beyond empirical evaluation. To our knowledge, no other work has studied DP representations of sets.
Another related line of work considers DP mechanisms for releasing sparse histograms. In this problem, each element of the input set S is also associated with some value. The goal of a query is to decode the value associated with the queried element (if it exists in the input set S). Sparse histograms may also be interpreted as sparse vector problem where the input vector has at most & non-zero entries. Unlike the private set problem, sparse histograms and vectors have been heavily studied. The majority of these works also take the same approach building on top of (potentially) non-private solution and injecting noise to the resulting representation. For example, several works study count sketch [24, 28, 34, 35] and count min-sketch [27. 21] where each entry of the resulting sketch is perturbed by some DP mechanism. To our knowledge, the only work that slightly deviates from this approach is [2], but they still inject noise using randomized response on bit-level representations (and the Laplacian mechanism in certain settings).
One could attempt to use sparse histograms (or vectors) to represents sets. We can associate each element in the input set S with the value To decode, we could round the output decoding of the underlying sparse histogram algorithm to either 0 or 1. Unfortunately, the error probability guarantees are unclear directly using prior analysis. For example, many prior works show that the per-entry error is at most ((1ee). That is, the true value and noise value differ by at most (11/c). However, it is unclear how this can be directly translated into error probability. particular, the exact constants of the per-entry eгror would need to be known to derive a probability bound of whether the decoded output is closer to 0 or 1. As an example, the error probabilities would differ greatly if the per-entry error was at most 1/c as opposed to 100/e c when using rounding. In our work, we present constructions using a completely different approach to avoid this technical obstacle. Our solutions obtain better per-entry error (both theoretically and empirically) than prior sparse histograms.
1.1
Our results
Our main contributions are efficient constructions for differentially private representations of sets that achieve optimal privacy-utility trade-offs and optimal space usage. In particular, our constructions exactly match the utility achieved by randomized response (even up to constants). Our work deviates from prior approaches that aim to construct some representation and perturb using noise. Instead, we embed the input set into a random linear system. Most elements in S are guaranteed to satisfy their corresponding linear constraint in the linear system. In contrast, all elements outside of the element set will be unlikely to satisfy the relevant constraint except with small probability (that is a inspired by retrieval data structures
controllable parameter in our algorithms). Our constructions based on linear systems such as [29, 15, 16. 7J. In particular, one can view our work as generalizations of these techniques for differential privacy. We only consider error probabilities a 1/2. When error is a 2 1/2, the task is trivial. One can encode a random hash function (independent of the set size) that is perfectly private with c 0 and ò (see Appendix F). We present two constructions: one for each of approximate and pure differential privacy.
Theorem 1.1 (Approximate-DP) Let S C U be a set of size k from a universe of size n. For any 0 and 8 > 0, there exists an (e, bDD algorithm for representing S with error probability a = 1/(e" 1) and space of 1.05ke- log(e) bits with three hash functions. The encoding time is O(k log(1/5)) and the decoding time is (log(1/5))
Theorem 1.2 (Pure-DP). Let S C U be set size k from a universe of size n. For any c > O, there exists an e-DP algorithm for representing S with error probability a = 1/(ee + 1) and space of ke log(e) hits with one hash function. The encoding time is O log² k) and the decoding time is (k).

---

We can compare the error probabilitiess achieved by our DP set mechanisms compared to prior works. For private histograms, per-entry expected error is (11ec) as shown in [23]. In contrast, our constructions err with probability 1/(e* 1). Note, we can convert this into the expected per-entry error as 1/(e" + 1). So, we obtain exponentially smaller per-entry error of 1/(e + 1), which is impossible for private histograms. We also perform experimental evaluation in Section 5 to corroborate our error being exponentially smaller compared to private histograms.
Lower bounds. We show that our constructions achieve optimality in two important dimensions: trade-offs between privacy and utility as well as privacy and space. First, we present a lower bound on the best possible trade-off between privacy and utility (that is, error probability). Our pure-DP solution matches this lower bound exactly including constants. Similarly, our approximate- algorithm matches the lower bound (including constants) if we ignore the o factor. We also present a lower bound showing the best possible trade-off between privacy and space (encoding size).
Theorem 1.3 (Urility-privacy trade-off). Let S C U be set of size k. For any c 2 0 and 0 < 8 S 1, any (c. 8)D algorithm for representing S must have error probability a 2 (1 6) + 1).
Theorem 1.4 (Space-privacy trade-off), Let S C U be a set of size k. For any 2 0 and 0 < 8 < 1, any (e, DDP algorithm for representing S with error probability 0 < a < 1/2, the encoding bit size
must be min(12(1 + 5/c() k (og(((/a)) - 1)), log (+))
We can consider the space lower bound restricted to algorithms that obtain the optimal privacy-utility trade-off as well. Therefore. we can set = (1 5)/(c" + 1) into the above lower bound. Assuming standard values of very small ö, we can see that the lower bound becomes (2 log()/a)) = Q c). Note that our constructions use space of 1.05ke log(e) and ke log(e) bits respectively with error probability a = 1/(ee +1). In other words, the space usage asymptotically matches our lower bound for all reasonable parameter choices of 5. In our proof, we work out the exact constants and show that the constant in the lower bound approaches log(e) for larger values of c. In fact, we show that both our constructions exactly match the lower bound up to very small constant of at most 4 that only occurs when e = O. Furthermore, we note our lower bounds also apply to probabilistic filters (such Bloom filters) that could also emit false negative errors.
1.2 Related work
Private filters. Bloom filter [8] is space efficient, probabilistic data structure that can be used to test whether an element is a member of a set. [1] show that flipping each bit of a Bloom filter with probability 1/(1 + et/t) is cDP where t is the number of hash functions. However, their work only experimentally evaluates the utility without any provable guarantees. Additionally, we note that prior works have attempted to analyze the privacy properties of filter data structures without modification. For example, this has been studied for Bloom filters [6]. counting Bloom filters [31] as well as groups of multiple filter data structures [30]. In general, the conclusion is that filter data structures without modification fail to obtain reasonable privacy guarantees. Finally, we note Bloom filters have also been used in other differential privacy contexts such as RAPPOR [20] where the goal is to aggregate discrete value responses from clients with local DP.
Private sparse histograms and vectors. A histogram is a frequency vector where each coordinate may take on real values. It is known that histograms can be made differentially private by adding Laplacian noise to each coordinate [18]. The expected error of each entry is ((1/c) where c is the privacy parameter, and it was shown that this privacy-utility trade-off is essentially optimal [23, 4].
Several works have considered the setting where the histogram is sparse and at most i out of d coordinates are non-zero. The goal is to release representation of the histogram whose size does not depend on d. Compared to the Laplacian mechanism, earlier works either suffered from significantly worse privacy-utility trade-offs [25, 13] or incurred very slow access time [3]. More recently, Aumuller et al. [2] proposed an ALP mechanism that achieves expected error of ((1/e) (matching the lower bound asymptotically) with access time of O(188). The space usage is also very efficient, obtaining ( log(d + u)) bits where u is the upper bound on the value of the entries.
Another line of work considers private versions of count sketch, introduced in [12], which can be viewed as a generalization of the Bloom filter. Each element in the set has an associated frequency, and the goal is to estimate the frequency of any element in the universe. Viewing the set as a sparse vector of frequencies, the basic idea of the count sketch is to transform the sparse vector x E Na to lower dimensional vector via an affine transformation Ax ND, where A is random matrix
3

---

from specific distribution. From Ax, each coordinate x, can be estimated with error that depends on D and the norm of x. Several works [24, 28. 34, 35] analyze the privacy-utility trade-off of the private count sketch with different noise distributions in the context of estimating the frequencies of the elements. Due to the linearity of count sketch, these works also studied the problem in the local model where the histogram is distributed amongst multiple parties. These works consider a more general problem setting than ours. As discussed earlier, is not immediately obvious how the error guarantees of private count sketch will translate to our problem setting.
2 Preliminaries
Notation. Throughout our paper, we will use in to denote natural (base-e) logarithms and use log to denote base-2 logarithms. We denote [x] as the set f1...., _ for any integer x 2 0. We denote all vectors in lower case boldface and matrices in capital case boldface M. We denote x(i] as the i-th entry of x. Similarly, we denote M[i]]]] as the j-th entry of the i-th row vector of M, M[ as the ith row vector, and [:]]]]] as the jth column vector. We denote x(a b] as the subvector of in range [a, 6]. We use x as the transpose of x. We use F to denote the set of all column vectors of length n over a field Ff and p= denote the of all by m matrices over a field F. We use the notation 1es such that 1yes = 1 if and only if E S and lyes 0 otherwise when æ & S. Finally, given a countable set S, we will use S to denote the i-th element in S (in arbitrary order). The subscript is simply used as a label to distinguish the elements.
Differential privacy. The notion of differential privacy (DP) was introduced by [18]. DP algorithms guarantee that small changes to the input will not drastically change the output probability distribution. In other words, two similar (or nearby) inputs will result in very similar output distributions.
Throughout our work, our inputs will be sets S from a universe U, S S U. We measure the distance between two sets S and S" as the symmetric set difference that we denote S&S' SS' +, This is the number of elements that appear in exactly one and S'. One can interpret the symmetric set difference the minimum number of elements that need to be added or removed to obtain S' from S (or vice versa). We say that two input sets are neighboring when their symmetric set difference is will denote the distance between two sets S and S' as
one, that is, SAS' 1. For convenience, |S - S = SAS' to conform with standard differential privacy notation.
We note that one can also interpret the above using & distances between vectors. For every entry и E U, we can denote with a unique integer from the set [[U]]- Suppose, we use function the vector Xs E {0, 1)101 such that xsli] = 1 if and only if there exists E S such that z(u) i. With this interpretation, we note that the symmetric set difference between two sets S and S' SAS', identical to the & distance between the corresponding vectors defined as |xs x |1 Exerrn [xs[i]] xs [i].
2 > [U]]] as this mapping. For any set S S U, we map
We present the definition of differential privacy following standard definitions [19].
Definition 2.1. A randomized algorithm M with domain D is (e, o)ddifferentiilly private if, for all R C Range(M) and for all x, y E D such that jr - y) 1, then
Pr[M(z) E R] Se e Pr(M(y) +6
over the randomness of the algorithm M.
Differentially private set representations. We focus on differentially private algorithms for releasing
sets 5 of size most k. that is, S U such that |S| < 1: for some input parameter i. We will focus on the case where the universe U is substantially larger than the input set S.
Definition 2.2. An algorithm = (II. De.ooe) for representing sets consists of:
. $ Encode(S): The (randomized) encoding takes set S C U and returns encoding S.
b + II.Decode ($, u): The decoding takes encoding S and element u E U and outputs b E (0, 1).
The construction (encoding) time is the running time of Encode and the access (decoding) time is the running time of I1. Decode. The space is the size of encoding S.

---

In other words, algorithm for releasing sets creates an encoding S of a set S S U. Furthermore, the algorithm enables checking whether any element u E U, appears in S using the encoding S.
Next, we define the utility of the differentially private problem through its error probability. An eтror occurs when the decoding algorithm for query q E U returns an answer that is inconsistent with the original input set S.
Definition 2.3. An algorithm II (TI. Encode, II. Decode) for representing sets has error probability at most a if, for any input set 5 _ and any set of queries Q - U,
Pr[vq E Q, les + I..eecoee (S 9) - a 141
where 3 +- IL.Encode(S) and the probability is over the randomness Encode.
For any set queries Q. the probability that all I queries are incorrect is at most pl This is stronger definition than prior works that consider [Q| = 1 because it also ensures independence of incorrect answers. For example, consider any two queries 91 * 92 E U. Each of them must be incorrect with probability at most a by setting Q {91 or Q {92 Furthermore, they must be independent since the probability that they are both incorrect is at most a² by setting Q = (g1,9)) This independence argument may be extended to arbitrary query set with more than queries.
We can also interpret this definition as per-entry expected error used in private histograms that bounds the absolute value between the true and decoded value. Our definition may be viewed as privately encoding an |U|-length binary vector such that E Lyes De.oeede ($, q)ll for any element q E U and encoding $ <- Encodee)(SS. In other words, the expected per-entry error is at most a.
Differentially private sets
In this section, present our main two constructions for differentially private sets. Before present our constructions, we present a framework for building these algorithms using linear systems that satisfy certain properties. In particular, our work is inspired and generalizes prior retrieval data structures based on linear systems such as [29, 15, 16, 7]. Afterwards, we instantiate the linear systems in two different ways to obtain our constructions (although, one could use other linear systems as we will provide some examples later).
3.1 Framework from linear systems
We present a general framework based on linear systems for building DP set mechanisms. We consider linear systems over finite field F with two functions: Row and Solve.
Recall that our problem where & is the input to the algorithm. We assume Row U + flxm is hash function mapping universe elements to row vectors of length m. Here, the parameter m is a function depend on the size of the input set S. Given set S = (si,..., $r} C U of k < k elements, one can le m matrix:
release differentially private representation of S S U such that |S| S i.
and does not
view Row as hashing
Row(s1)
M
Row(sz)
The algorithm Solve takes an matrix M e pp and solution vector E F to compute the solution 1f satisfying Mx b. In particular, Solve will make the assumption that M is the generated output of Row for some set S C U of size k. For our chosen linear systems, Solve will be faster than the naive application of Gaussian elimination. We also make some additional assumptions about Solve. First, we will exclusively focus on the case where the matrix has more columns than rows, k. Secondly, if the input matrix M does not have full rank, then Solve will return 1. Lastly, all free variables will be set to uniformly random elements from F.
We note that Row will generate rows in some structured way depending on the chosen linear system to ensure Solve successfully outputs a solution with high probability assuming the number of columns m is sufficiently larger compared to the number of rows k. In our work, we focus on two constructions:
5

---

random band [15] and Vandermonde matrices. Although, our framework is compatible with any linear system.
We will also use a hash function h U + that maps each element in the universe to elements in F. We will use h to generate the solution vector b in the above linear system. For noised input set S = {s1...... 9k S U, the solution vector will be b = [h(s1),.... [TT))]TT
In our work, we will assume that all hash functions are fully random following prior works includ- ing [28, 34, 35]. In practical implementations, we use cryptographic hash functions to replace this assumption done in the past [14, 34]. Specifically, will assume that h and Row are fully random when necessary (for one of our constructions, Row will be deterministic).
Encoding. Suppose we are given input set S = {s:...., 8& S U of size |S| k. First, we generate random hash function h and (possibly random) row function Row. Next, we will randomly sample subset S' S S such that each element of S will appear in S except with some exclusion probability p (that we pick later during analysis). For convenience, denote S' (s'.....,00 s where k' = [. Encoding works by constructing matrix M using Row and noisy input set S Row(s()))]T Next, a solution vector is created by hashing each of the elements in S' using the hash function h. So, b = [b(s))...... TT Finally, we compute encoding x using Solve for the following linear system:
as M = [Row(s))....
Row(s1)
]
h((1) n((p))
]
Mx =
x 1
Row(s)))
The final encoding will be S (x, h, Row). See Algorithm for formal pseudocode.
Algorithm DPSet. Encode algorithm
Require: S, m: input, exclusion probability p. output length m
Ensure: S DP encoding
Generate random hash function h : U + F.
Generate (random) Row : Flxm.
S' 5"+- 0 for & E S
Algorithm 2 DDSet. algorithm
Add s to S" with probability 1 1-
Require: $ = (x, Row, h, S), Ensure: returns b {0, 1}
end for
M SS'| X matrix xm
if S き 1. then return u E S end if y f Row(u) x
b < length |S'| column vector.
for S| do
M < (Sw())
b (i)
return 1 ly=h(u)
end for
Solve (M, b)
if br * 1 then
return Š - (x, Row, h, L)
else
return (1,1,1,S)
end
We can view the above as using the linear system to embed linear constraints that satisfied by
elements of the noisy input set S'. For every s' E S', we know that Row(s') - x h(ss) assuming Solve succeeded. In contrast, fix any & S'. Then, since h a random hash function. So, elements outside of the set S' are unlikely to be satisfy their corresponding linear constraint. We control this probability by picking the field size [F] accordingly.
see that Pr|/(u)) = Row(u) x] [IF |
We will capture the event of Solve failing using For our pure-DP construction, we guarantee that 8 = 0 and Solve never fails. For our approximate-DP algorithm, we rely on the fact that Solve succeeds with high probability assuming Row randomly generated correct manner. Solve fails, assume that encode simply returns the input set S.

---

Decoding, Suppose we are given an encoding S = (x, h. Row) and an element u E U. Decoding checks whether an element's corresponding linear system satisfied by computing Row(u) x and comparing with hu)). In other words, the decoding algorithm simply returns Row(())xx=h(u)) We present the pseudocode Algorithm 2.
We start by presenting the error probability (utility) with respect to field size [IF) and the exclusion probability p of removing any element. We defer the proof' Appendix A.
Theorem 3.1. If [F] = a- and p a/(1 a.), then Decode has evvrr probability a.
For error probability a, we pick [F] 1/ holds where F is finite field. We note that there is finite field of size q" for any prime q and positíve integer 2 1. For practical purposes, we use the smallest integer q" larger than 1/ax that gives slightly smaller emror probability.
Next, we prove privacy our framework. We defer the full proof to Appendix B.
Theorem 3.2. If Solve erry with probability at most 6, then DPSet is (e,6)-DP with error (e" + +1)-1
Our construction's 's expected per-entry error a = 1/(e*+1) is exponentially smaller than achievable by private histograms where (2(1/e) entor is required [23].
Next, we analyze the encoding size. In general, these are largely dependent on the underlying linear system. The encoding size depends on the number of variables (columns) m in the linear system. Additionally, it also includes representations of the functions and Row.
Theorem 3.3. .pSet.Encode outputs encodings of m field elements and encodings of and Row.
In Appendix E. we outline possible optimization reduce encoding size by picking m closer to the expected size of the sampled set S". This turns out to be more theoretical as we were unable to observe space improvements empirically for reasonable choices of set size k and error probability a.
Computational time. For computation, the majority of the work is done by the underlying linear system. In partieular, DPSet. Encode requires only ((k) time outside of Solve and Row. Similarly, DPSet.Decode requires an execute of Row and the computation will depend on the number of non-zero entries in Row. We analyze the computational costs for our instantiations later.
Larger error of a > 1/2. Our constructions only consider error probabilities a I 1/2. This is implicit as the smallest field has size at least 2. There trivial algorithms to obtain mechanisms with = and = 0 for the case of a 2 1/2 using a random hash function (see Appendix F).
3.2 Approximate differentially private sets
From Section 3.1, our goal essentially boils down to constructing linear system where solution exists and may be efficiently computed with high probability. Furthermore, we want to minimize the number of variables required to ensure small encoding sizes. To this end, we will use the random band row vector construction of [15].
The random band construction is parameterized by the row length m and the band length w. At a high level, each row consists of a single band of w random field elements. The band's location chosen uniformly at random. All m
entries outside of the band will be zero. Formally, the construction uses hash functions h1 : U - [m band's 's starting location and h2(u) (u) is the w elements in the band. Generating a random RoWband is equivalent to generating the two random hash functions h1 and f12. Solveband works by sorting the rows by starting band location and executing Gaussian climination. See Algorithms 3 and 4.
+ 1] and he + xl For U, h1 (u( denotes the
Algorithm 3 RoWband algorithm
Algorithm 4 Solveband algorithm
Require: element E U
Require: M, b: matrix and vector
Ensure: v random band row vector m length of the vector
Ensure: x : solution satisfying Mx
Sort rows by starting band location. Execute Gaussian elimination and set free vari- ables be random elements in F to obtain encoding x.
v + 0 xm (all zero row vector of length m)
h1(1)
v[s : w 1 + hz)
return
return
7

---

At a high level, If k is the number of rows of the matrix, Dietzfelbinger and Walzer [15] showed that if (1 3)k and w (log k) for some constant O, then the matrix generated using the random band row construction has full rank and Solveband runs in ((mw) time except with probability = O(log((/)))))) + log k), then the
O(1/m). Bienstock el al. [7] extended this result to show that,
matrix has full row rank and the linear system can be solved in time ( except with probability
DPSet. Decode takes ((w) time since computing the dot product scales linearly with w, the length of the band. We obtain the following using random band row vectors:
Theorem 3.4. For any > 0, 8 > 0, 3 > 0, there is an (c, 6DP set mechanism with error +1)+ and encodings consisting of (1 + k) field elements and three hash functions. APSet.Encode takes Okkw) time and DPSet. Decode takes (w) time where = =[log(11/) log k).
3.3 Pure differentially private sets
We consider a pure differentially private construction of the framework in Section 3.1 with 0. In Section 3.1, the failure probability of solving the constructed linear system corresponds 5 in the DP definition. To obtain pure DP construction, our goal is to construct a linear system that is solvable with probability 1. So, we want construct matrix M that has full rank with probability 1. To do this, we use the Vandermonde matrix construction (where Row is deterministic) that may be solved in Olk log k)) time as shown in [9]. This construction has another advantages over the random band approach beyond obtaining 8 O. The resulting encodings are smaller with only field elements whereas the other construction requires m = (1 + B)k field elements with 3 > 0. In contrast, decoding times are larger here. See Appendix C for full description and proof.
Theorem 3.5. For any OPSet.Encode takes O log" k) time and oPSet.Decode takes O(k) time.
O, there exists an e-DP set mechanism with error (e" 1)-
Other Constructions. We present two concrete constructions from specific linear systems, but it is possible to plug other linear systems. For example, plugging in [22] would result in a pure DP solution with faster encoding times, but larger encoding sizes compared to Theorem 3.5.
4 Lower bounds
Privacy-utility lower bounds. We start by considering the possibility of improving the error probability (utility) with respect to the desired levels of privacy. Our construction achieved error probability at most 1/(e- + 1) for any choice of 2 0. In other words, for any error a, our construction achieves privacy c = log((1 - aa) We show that this trade-off between c and error probability is optimal even up to constants (ignoring factors). See Appendix D for the proof.
Theorem 4.1. Consider any (E, O)DP algorithm II for sets of size k. Suppose that II has error probability at most a I 1/2. Then, e 2 In((1 a 8)/a.) In other words, for a fixed privacy level 2 0 and 8 2 0, the error probability of II must be (1 5)(e" +1).
Space lower bounds. Next, we move onto determining the necessary space usage of set representa- tions. There exist space lower bounds for probabilistic membership data structures (such as Bloom filters) that have a false positive probability of and no false negatives. It is well known that such data structures require k log(1/a bits of space when given an input of size k. However, these lower bounds only apply when the false negative rate is O. See Broder and Mitzenmacher [10] for the prior lower bound. We present space lower bound for DP mechanisms with non-zero false negatives using a proof through compression that deviates from prior counting arguments (see Appendix D).
Theorem 4.2. Consider any (c. 8 II for sets of size k. II produces s-bit encodings with error probability < a S 1/2, then E 2 8/(e")) ks log(1/o)).
Experimental evaluation
Setup. We implemented DPSet, ALP [2] and DP Count Sketch [34] in C++ using 800 lines of code.
For DPSet, we use the analysis of Bienstock el al. [7] to choose appropriate parameters for 5 < 2-10 with parameter / 0.05. To fit ALP and DP Count Sketch to our problem setting, we round the query results of these mechanisms to the nearest 0 or 1. We target privacy parameter < 2-40 for all
8

---

Unility (Fnvor Prohubility): 22
Uhility (Frnc Probubilityy 21
Utilit (Fnor Prohshility; 22
0.7
0.7
DPSett (Ours)
DPSet (Ouns)
DPSet (Ours)
0.6
ALP
0.6
ALP
ALP
DP Count
Skotch
Count Skouch
0.5
Lower Bound (Ouns)
0.5
Lower Bound (Ours)
0.5
Lower Bound (Ours)
0.4
0.4
0.4
0.3
0.2
0.2
0.2
0.1
0.1
0.5
1.5
2.5
3
3.5
4
4.5
0.5
01.5
1.5
2
2.5
3.5
4.5
0.5
0.5
1.5
2.5
3.5
5.5
Encode Time
Elcodd (ms):
2210
Ensode Time
270
100
1,750
(Chur)
(Ours)
(Durs)
ALP
ALP
1,500
ALP
Skotch
75
Sketch
1,250
Sketch
1.000
50
750
500
26
250
0.5
1
1.5
2
2.5
1.5
4.5
5
0.5
0.5
1
1.5
2
2.5
3.5
4.5
5.5
0.5
1
1.5
2
2.5
3.5
4.
5
5.5
Avg. Decdd Time (me) 232
Avg Decode Time (msit 2
Avg. Deoode Time (ma)
220
0.5
0.5
0.5
DPSat (Ours)
-n- DPSet (Durs)
SPe (Chrs)
ALP
ALP
ALP
Count Skutch
0.4
TIP Count
Stotch
0.3
0.3
0.3
0.2
0.2
0.2
0.1
0.5
1.5
2.5
3
3.5
4.5
5.5
0.5
1.5
2
25
3.5
4.5
5.5
0
0.5
1.5
2.5
3.5
4.5
5.5
Figure 1: Comparisons of of DPSet, ALP, and DP Count Sketch with 5 <
2-
10
'he xraaxi is
privacy parameter e and the y-axis error probability, encoding time (ms) or decoding time (ms).
three constructions. To fairly compare utility, we chose parameters to ensure that encoding sizes are approximately equal for all three constructions (see Appendix G for more details on encoding sizes).
We consider experiments for input sets of size k E {2 2, 220). Each trial picks input sets as k uniformly random 128-bit strings from universe of all constructions are agnostic to the distribution of the input set. We ran all experiments using a Ubuntu PC with 12 cores, 3.7 GHz Intel Xeon W-2135 and 64 GB of RAM. Our experiments enable AVX2 and AVX-512 instruction sets with SIMD instructions. All reported results use single-thread execution the average of at least 1,000 trials with standard deviation less than 10% of the average. The entire experimental evaluations (including setup) took approximately hour of compute time.
2 2128 strings. Although, all three
Utility. To measure utility, query the entire input set of size l well random subset of k elements outside of the set in each trial. We plot our results in Figure along with our lower bound (Theorem 1).. We see that DPSet has much better utility compared to the prior works. Furthermore, our experiments corroborate our theoretical analysis that error probability expomentially decreases in and essentially matches our lower bound of (1 8))(ce + 1) 2 (1 - 2-440/ + 1).
Efficiency. We compare the efficiency of encoding input sets and decoding random elements. For larger input set sizes k and bigger e, our constructions have faster encoding times. In contrast, DPSet has slower encoding for smaller & and 6. For decoding, DPSet has slower times than both prior works. Nevertheless, decoding times of DPSet remain very fast and are less than 0.3 milliseconds.

---

6 Conclusions
In this work, we present constructions of DP sets that are essentially optimal in privacy-utility and space trade-off's nearly matching our lower bounds. The error obtained is exponentially smaller (both theoretically and empirically) than possible for private histograms mostly studied in prior works. Additionally, we experimentally show that our constructions are concretely efficient.
Limitations. A limitation of our work is that we consider sparse sets (as opposed to the more general sparse histograms). Nevertheless, we believe this specific problem has several important applications with the added benefit of exponentially smaller error. Our constructions assume fully random hash functions (following several prior works) and instantiations are limited to finite field sizes. If we assume pseudorandom hash functions (PRFs), our construction obtains computational DP instead.
7 Acknowledgements
The authors would like to thank Rachel Cummings for feedback on earlier versions of this paper.
References
[1] Mohammad Alaggan, Séhastien Gambs, and Anne-Marie Kermarrec. Blip: Non-interactive differentially- private similarity computation on Bloom filters. In Andréa W. Richa and Christian Scheideler, editors, Stabilization, Safety, and Security of Distributed Systems, pages 202-216, Berlin, Heidelberg. 2012. Springer Berlin Heidelberg.
[2] Martin Aumüller, Christian Janos Lebeda, and Rasmus Pagh. Differentially private sparse vectors with low error, optimal space, and fast access. In Proceedings the 2021 ACM SIGSAC Conference Computer and Communications Security, pages 1223-1236, 2021.
[3] Victor Balcer and Salil Vadhan. Differential privacy finite computers. Journal of Privacy and Confiden- riality, 9:2, 2019.
[4] Raef Bassily and Adam Smith. Local, private, efficient protocols for succinct histograms. In Proceedings of the sorty-seventh annual ACM symposium Theory of computing, pages 127-135, 2015.
[5] Narayan Bhamidipati, Ravi Kant, and Shaunak Mishra. A large scale prediction engine for app install clicks and conversions. In Proceedings of the 2017 ACM Conference on Information and Knowledge Management, pages 167-175, 2017.
[6] Giuseppe Bianchi, Lorenzo Bracciale, and Pierpaolo Loreti. "Better Than Nothing" Privacy with Bloom Filters: To What Extent? In International Conference Privacy in Statistical Databases, pages 348-363. Springer, 2012.
[7] Alexander Bienstock. Sarvar Patel, Joon Young Seo, and Kevin Yeo. Near-Optimal oblivious Key-Value stores for efficient PSI, PSU and Volume- Hiddig Multi- (USENIX Security 23), pages 301-318, Anaheim, CA, August 2023. USENIX Association.
In 32nd USENIX Security Symposium
[8] Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. 13(7):422442) Jul. 1970.
Commun. ACM.
[9] Allan Borodin and Robert Moenck. Fast modular transforms. Journal of Computer and System Sciences, 8()):36-3366, 1974.
[10] Andrei Broder and Michael Mitzenmacher. Network applications of Bloom filters: A survey. Internet mathematics, 1(4):485-50) 509, 2004.
[11] Lynne M Butler. The q g-loo-ccocavity of biniooiial coefficients. Journal of Combinatorial Theory, Series A. 54(1):54-63, 1990.
[12] Moses Charikar, Kevin Chen, Martin Farach-Colton Finding frequent items data streams. In Peter Widmayer, Stephan Fidenbenz, Francisco Triguero, Rafael Morales, Ricardo Conejo, and Matthew Hennessy, editors, Automata, Languages and Programmingg pages 693-703, Berlin, Heidelherg, 2002. Springer Berlin Heidelherg.
[13] Graham Cormode, Cecilia Procopiuc, Divesh Srivastava, and Thanh T. L. Tran. Differentially private summaries for sparse data. In Proceedings of the 15th International Conference on Database Theory. ICDT 12, page 211- New York, NY, USA, 2012. Association for Computing Machinery.
10

---

[14] Charlie Dickens, Justin Thaler. and Daniel Ting. Order-invariant cardinality estimaators are differentially private. Advances Neural Information Processing Systems. 35:15204-15216, 2022.
[15] Martin Dietzfelbinger and Stefan Walzer. Efficient gauss elimination for near- matrices with one short random block per row, with applications. In 27th Annual European Symposium on Algorithms (ESA 2019), volume 144, page 39, Schloss
fuer Informatik, 2019.
[16] Peter C. Dillinger and Stefan Walzer. Rihhon filter: practically smaller than Bloom and Xor. CoRR, abs/2103.02515, 2021.
[17] Chen Doytshman. Akanat: How akamai uses machine learning to detect shared ips, 2024.
[18] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, pages 265-284, 2006.
[19] Cynthia Dwork and Aaron Roth. The algorithmic foundations differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):21 2014.
[20] Ülfar Frlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized aggregatable privacy- preserving ordinal response. In Gail-Joon Ahn, Moti Yung, and Ninghui Li, editors, ACM CCS 2014, pages 1054-1067, ACM Press, November 2014.
[21] Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. On the power of multiple anonymous messages: Frequency estimation and selection in the shufile model of differential privacy. In Eurocrypt 2021, pages 463-488, 2021.
[22] Anna C Gilbert, Yi Li. Ely Porat, and Martin J Strauss. For-all sparse recovery in near-optimal time. ACM Transactions on Algorithms (TALG), 13(3):1 1:3):1226,200 2017.
[23] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the forty-secom ACM symposium on Theory of computing, pages 705-714, 2010.
[24] Ziyue Huang, Yuan Qiu, Ke Yi, and Graham Cormode. Frequency estimation under multiparty differential privacy: one-shot and streaming. Proc. VLDB Endow., 15(10))0058-200 jun 2022.
[25] Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. WWW '09, page 171-180. Association for Computing Machinery, 2009.
[26] Oren Anava Maggie, Vitaly Kuznetsov, and Will Cukierski. Web traffic time series forecasting, 2017.
[27] Luca Melis, George Danezis, and Emiliano De Cristofaro. Efficient private statistics with succinet sketches. In 23rrd Annual Network and Distributed System Security Symposiun, NDSS, 2016.
[28] Rasmus Pagh and Mikkel Thorup. Improved utility analysis of private countsketch. In Advances in Neural Information Processing Systems, volume 35, pages 25631-25643, 2022.
[29] Ely Porat. An optimal Bloom filter replacement based on matrix solving. In Anna Frid, Andrey Morozov, Andrey Rybalchenko, and Klaus W. Wagner, editors, Computer Science Theory and Applicutions, pages 263-22 273, Berlin, Hcidelberg, 2009. Springer Berlin Heidelberg.
[30] Pedro Reviricgo, Alfonso Sanchez-Macian, Peter C Dillinger, and Stefan Walzer. On the privacy of multi-versioned approximate membership check filters. IEEE Transactions on Dependable and Secure Computing, 101):1-13, 2023.
[31] Pedro Reviriego, Alfonso Sánchez-Macian, Stefan Walzer, Elena Merino-Gómezz Shanshan Liu, and Fabrizio Lombardi. On the privacy of counting Bloom filters. IEEE Trunsactions on Dependable and Secure Computing, 1488):1488,,499, 2022.
[32] Claude Elwood Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379-425 1948.
[33] Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-49) 1965.
[34] Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. Differentially private linear sketches: Efficient implementations and applications. In Advances in Neural Information Processing Syxtems, volume 35, pages 12691-12704, 2022.
[35] Mingxun Zhou, Tianhao Wang. T-H. Hubert Chan, Giulia Fanti, and Elaine Shi. Locally differentially private sparse vector aggregation. In 2022 IEEE Symposium on Security and Privacy (SP), pages 422 4399 2022.

---

A Proof of correctness of DPSet
We prove the correctness of constructions. First, present lemma about the false positive and false negative rates. Afterwards, we use this to get final error probability.
Lemma A.1. Decode has false positive probability of | and false negative probability of p. p-(1-
F ). Also, the probabilities are independent for each E U.
Proof. First consider false positives. If u & S, then & S'. We know Pr Pr(Row(1) (u) x = h(w)] |F since h is fully random hash function. For false negatives, consider any 8 E S. Note, that Pr[s & S' s S = (1 p). Since DPSet. Decode only returns if L. there is no additional error from DPSet.Encode failing. If $ 5", the decoding will return 1 with probability [ So, the false negative probability s not sampled into S' and the linear constraint being unsatisfied that is p-p(. (1 |P| ") Finally, these probabilities are independent for every q E U following from the fact that sampling each element into S' is independent and that is a fully random hash function.
The error probability is the maximum of the false positive and negative probabilities. Suppose we desired a certain error probability a, we can pick the field size and exclusion probability as follows.
Proof of Theorem 3.1. First, see that |L -1 for the false positives. Then, we pick satisfying a = p (1 () for false negatives to see that = ax(1 - a).
B Proof of privacy of DPSet
In this section, we present the full proof of Theorem 3.2. In particular, we show that it follows directly from the following theorem by plugging in e accordingly. In our proof, we require the randomness of h only for correctness and not privacy.
Theorem B.1. Suppose [F] = a = a1(1- a) and Solve fails with probability fsolve for correctly generated Row. Then, DPSet is (In(2-a), J-Dlve--DDD
Proof. Let S₁ and S2 be the two neighboring sets such that S2 = S U fu). Let Zs, and Zs, be the two random variables denoting the representations output by DPSet. Encode for S₁ and S2. respectively. Let m be the number of variables (length of the encoded vector) in Algorithm 1. Let 17th Row and h be arbitrary, and let (x, Row, h, L). We first show that
a
Pr/Zs, = v
Pr[Zs, =v v]
1 11a) a
Pr|Zs, = vis
PriZs, =
(2)
where the probability is over the random coin tosses performed by DPSet. Encode.
We first prove Equation 1. Let R., be the event where the element u removed during Encode on S2. Recalling that Pr(A..] = p T-a from Algorithm 1, we have
Pr Zs. = v]
Pr[Ru]] Pr PriZs, = =v RRJ + R, Pr|Zs, = Ra
Pr(R,.] Pr(Zs; = =v]+ + Pr Pr Zs, =v R.,
2 Pr(R..] Pr(Zs, = =v 1 Pr Zss vl
where the second equality follows from the fact that the distribution of Zs, is identical to Zs. conditioned on the event R. Rearranging, we get the desired bound.
Next, we prove Equation By again decomposing Pr|Zs, v] conditioned on R. we have Pr = v]
= -Pr[Ry Pr[Zs, = =v -v + R. Pr|Zs, =v Ra
= -Pr[R,,] Pr(Zs, = =v] + Pr Pr Zs, =v R.).
12

---

Before proceeding with the proof, we claim that
Pr = Sa = =v].
(3)
Then plugging in Equation to the above equation, we get
Pr[B.]] Pr = v] + Pr(R.. Pr|Ze [zs = Rul
2 Pr[Ru, Pr|Zs: v + Pr[Ru](a Pr PriZs, = v[)
1 1-20 < 1 a
PriZs, = a- a²
PriZs, = v|
a
We now prove Equation 3 to complete the proof. Let S' and S'2 be random variables denoting the set of elements that survived the removal process in Encode for input S and S2, respectively.
Consider an arbitrary subset S C Sj. We can see that Pr(S'2 2 = S" Uu3 { R.l = Pr(S', = 5"], and so if we show that
Zs, = v (S' S' (u])l s - = S = 5*]
then we can apply the law of total probability to obtain Equation
One way to see why Equation 4 holds as follows. If the left hand side is O, then the bound trivially holds, we may assume that the probability is positive. For any choice of hash functions (that also determine Row), the linear systems generated are uniquely determined by the surviving elements. Thus, conditioned on the event that S¹ S' and S' S {u), the generated linear systems are deterministic. Let L1 and L2 be the corresponding linear systems for S1 and S2, respectively. From the condition, must be that L1 L2 and L2 has exactly one more equation than L1 that is linearly independent of the other rows. In other words, L1 has exactly one more degree of freedom than Le. which corresponds to an extra free variable. By the construction of Algorithm 1, the free variables are independently and uniformly randomly set to values in F. Thus, the probability that this random free variable set to the corresponding value in x (the first component of v) exactly 1/|F/ a. This establishes the inequality (in fact an equality) and completes the proof of Equation 4, from which Equation follows immediately.
From Equation 1 and Equation 2. the proof of the main theorem follows immediately by applying Definition 2.1 and using the failure probability of Solve at most fsolve-
C Pure differentially private subsets
As discussed in Section 3.3, to obtain pure DP construction, our goal is to construct a linear system that is full rank with probability 1. To achieve this goal, will use the Vandermonde matrix construction. Vandermonde matrix is a n x k matrix of the form
"1
U2
22
u2
where each u; F. If n & then this matrix is always full rank for any set of distinct u4-
Suppose that the universe U FF for some finite field F. Let S be the input set and let k = IS]. Then we can construct the matrix in Algorithm using the Vandermonde matrix construction to obtain a pure differentially private construction. The algorithm for constructing the row vector is presented in Algorithm 5. Using [9], the linear system constructed using the Vandermonde matrix can be solved in O(k log2 k)) time. We point to the prior work to find the corresponding Solvevandermonde: Plugging this into the framework of Section 3.1, we immediatcly obtain Theorem 3.5.
13

---

Algorithm 5 RoWaandermodde algorithm
Require: element U = F
Ensure: v Vandermonde matrix row k + |S], size of the input set
return v [1, 2 u
D Proof of lower bounds
We start by proving our lower bound of utility stated in Theorem 4.1.
Proof of Theorem 4.1. Pick any and y that differ in exactly one entry. Without loss of generality, pick the unique index E [n]] such that x[i] = and y[i] = 1. Let Zx and Zy be the random variables denoting the representations output by II for and y respectively. We will consider the probability that II produces representation such that II.Dcc outputs 1 on index for each of Zx and Zy. Note that Decooe Zy DelodeDecodeeZz = 1] S a since x i
since y(i 1. Similarly, we note that O. In other words, we see
1] 2
1 - a - Pr Pr[ Zn, =1]
< e Pr(II.Dccode Zz, +
Se' +
By re-arranging the inequality 1 1- a S a + ò, we get the desired theorem.
To prove our space lower bound stated in Theorem 4.2, we start with proving an intermediate result about the required space for any mechanism (not necessarily differentially private) that has error probability at most a. In particular, the existence of such mechanism enables a very efficient compression algorithm to encode random vectors x with k non-7ero entries.
Lemma D.1. Consider any mechanism IT for binary vectors x E {0, 1}"h with at most k non-zero entries, xx| S k. If II produces representations using bits of space expectation and has error probability at most < S 1/2, then
E 2 (1 2a.kk log (2-1) log k - log log(en/k).
Proof. We will make the assumption that 1I never produces representations larger than log (?) bits on any input and any choice of randomness. Note, this is without loss of generality because a trivial representation of binary vectors with & non-zero entries can be done in log (*) bits with zero error probability. If II violates this assumption, we can modify II to replace any longer encodings with the trivial one that will either maintain or decrease the space usage and error probability.
We consider the following two-party, one-way compression problem between an encoder (Alice) and decoder (Bob). As input, Alice receives input uniformly random vector conditioned that exactly & entries are non-zero, |x|1 = k. Alice's job is to encode x into a single message enabling Bob to correctly decode x. In particular, Alice's goal is to make the message as small as possible. To do this, Alice will utilize the mechanism 11. At a high level, Alice will use 11 to construct a representation x with error probability a. Additionally, Alice will send some auxiliary information that will enable Bob to correctly identify the non-zero entries of x using the answers of II. We present the compression algorithm below.
{0. 1)"
Alice's Encoding: Receives x E {0, 13" such that |x] = and shared randomness R.
1. Construct Z +- 11. Encodee(( R) using randomness R.
2. Set X {i [n] x 1).
3. Initialize A +- 0 and B 0.
4. For all i [n]]
14

---

(a) If De.De R. 0, set A < (t).
(b) Else when Decode Z, R) 1, set B <- (1)
5. Encode [Z] using log log bits.
6. Encode [X n A using log bits.
7. Encode X n A using log ((xna)) bits.
8. Encode X n B using log [XnB]]
[B]
bits.
9. Compute encoding (IZ), Z, AI
Bob's Decoding: Receives Alice's encoding and shared randomness R.
Decode |z] using the first log log (x) bits and using the next [Z] bits.
2. Initialize <- and B + 0.
3. For all i E [n]:
(a) If De,coe R) set A - (i).
(b) Else when De.oec (Z, R) 1, set (i)
4. Decode the size of [X n A| using the next log Additionally, we know that XX n BJ
k X Al.
5. Using knowledge of |A), [x n and X n Bl, decode X and n B.
6. Using knowledge A and B as well as i and O B, we can decode X and, thus, x.
Prefix-freeness. We will later apply Shannon's 's source coding theorem. However, to this, required that Alice's encoding algorithm is prefix-free. That is, any possible encoding cannot be strict prefix of any other possible encoding. First, we note that the last components |X n AIA X n and X n B will always be the same length. We use a fixed length represent |X n n The two sets X A A and X always encode exactly elements. Therefore, the encoding length will only be different for various sizes of Z. However, prefix each encoding with the length IZ]. Therefore, any encodings of different lengths (meaning different length Z will be prefix- free. Finally, is clear that any set of equal length encodings will be prefix-free
Encoding length. The expected length of Alice's encoding is exactly
|A| X (XnA)
BB| [X
log log
+ E(s) log + log
log
B)
k:
as we consider expected space usage 8 and all of A, B, X A and X B are random variables. Next, note that the function f'(a,) b) + (8) is log-concave for the relevant range 2 0 (see [11] for example). Therefore, we can apply Jensen's 's inequality to obtain
LA
1 < log
B
E[A]] [E[XX 0 A1)
B| E|| BI)
E log [X AX
+ log
(X [XXBB]
+ log
Next, we know that XX MXAA++1 + |X
B = le and
|A| + B = n. Therefore, we can rewrite
E[[A]]
E B]
E[|A] E E||X n n ) log
( - (6-E|XnA])
|[ E[AA
log
+log E (IIXnAI)
log
E E
BI)
Next, we see that E[[ S (1 a)n and [ 0 AI] S ak. Given that a S 1/2, we immediately that this is maximized when E[[A|]
a)n and E[| n Al] ak. So, we see that
15

---

E[|A[]] BIX
-- [[- k: (--E(INAI
(u-aa)n) ork
(1-
an
log
+ log
S log
+ log (1 a)k)
Complete the lower bound. To finally complete the proof of the lower bound, we will apply Shannon's source coding theorem [32] that states that the expected length of Alice's prefix-free encoding cannot be smaller than the entropy of Alice's s input conditioned on any shared input. First, we see that
H(x R) H(x)
log
k
Therefore, get that Alice's expected encoding length must satisfy
(1 (1-a)m) log
log log
E(s]
log ks + log
an
log
T1 k
(1 a))
By re-arranging, we see that the following is equivalent by applying linearity of expectation and using Stirling's approximation such that (1) S (en/k)²
E S
log
2 log k log log(en/ (e//))
(11_a))) ak
(1-a)k)
(1-20)6
1-a a
log
2 logg k: - log Loggen///H
1 11-a
2 - 2a)k log
2 log k - loggoogee/HHa
Therefore, get desired lower bound.
To sanity check, we can consider various choices of a. For example, we set a = 1/2, we note that the space lower bound becomes trivially O. In fact, this makes sense there simple algorithms to obtain a = 1/2 that require essentially no space. For example, we can use any random hash function h that outputs random bits and return positive only when h(x) = 0. This obtains 1/2 and essentially ignores the input set. Therefore, we can see that our lower bound is sensible.
the above lemma combined with Theorem 4.1 1 to obtain space lower bound for differentially private mechanisms that already require error probability.
Finally,
Proof of Theorem 4.2. First, apply Theorem 4.1 to get that the emror probability must satisfy
1-8
a 6++1
Note, for all choices 2 and 2 0, we see that a S 1/2. Plugging in the error probability 8) + 1) into Lemma D.I, we get the following
e +
k log (= - O(log k + log log
E
et +1
First, we note that (e 1) + 1) O(1) for all choices of 2 0. For sufficiently large k = 2(log logn), we get that
Els] ((+ e
k. log(1/a)
completing the proof.
16

---

Ficcdding (byles)
Encoding Size (hyies: 2
Encoding
241
224
241
270
255
246
21
2.
24
212
232
212
240
29
DP
26
DiPett
DPSe: (Churs) ALP
29
DP Count Stetch
DP Count Skerch
22
DP Couse Sketch
0.5
1.5
2.5
35
4
4.5
0.5
0.5
1.5
25
3
35
45
5.5
0.5
1.5
25
3.5
4.5
5 6.5
Figure 2: Comparisons of of DPSet, ALP, and DP Count Sketch with d S 2 The xr-axis is privacy parameter e and the y-axis encoding size in bytes.
E Space optimization
In our construction, we set the encoding size m (1 3) in Section 3. This worst-case guarantee to ensure that Solve may always be executed with the condition that the number of columns m satisfies m 2 (1 + 3)n where is the number of rows (i.e., sampled set size 5*). Instead, we can pick closer to the expected size of S' and fail if it goes over.
For example, we can apply known probability tail bounds (such Chernoff bounds) and pick to be closer to (1 - p)l that is the expected size of S'. This increases the failure probability of Solve (and 8) by an additive e - to account for if the number of rows is too large. Let 0 < 7 < be fixed constant. Invoking Chernoff bound, see that the probability that |S (1+ p)kk is bounded above by -O(),, Suppose that assume that [S|] k' 71) [S] and choose
+
m (1 + B)k'. This increases the failure probability of Solve by an additive -O(k) which is very small. As this optimization increases 5, it cannot be used for pure differentially private schemes.
Unfortunately, this ends up being a theoretical improvement as we were unable to empirically observe space efficiency gains in natural settings.
F Trivial algorithm for large error Probability
If we consider the case of large error probabilities 2 1/2, there are trivial algorithms for differen- tially private subsets that use, essentially, no space and has perfect privacy guarantees of In fact, it suffices to simply consider the case with error probability = 1/2.
Consider the following construction that completely ignores the input subset S. Pick random hash function U - 10. We represent the input subset 5 using h. For any element u E U, the decoding algorithm returns =( In other words, the decoding algorithms returns uniformly random bit for each element u É U. It is not hard to see that the error probability of this construction exactly 1/2. As the hash function h is chosen independent of the input subset S, it is quite clear that this trivial algorithm achieves perfect privacy of = 0 and 8 0. Therefore, all the constructions in our work focus on the case when a I 1/2.
Theorem F.1. There exists perfectly secure (0, 0)-DP set mechanism with error probability 1/2 where the encoding consists of single hash function independent of the input set size.
G Experimental evaluation of encoding size
We present graphs in Figure 2 showing the encoding sizes used in our experimental evaluation in Section 5. Recall that, for the purposes of comparing utility, we chose parameters such that all three constructions have similar encoding sizes. Therefore, the encoding sizes are essentially the same for all three constructions: DPSet from our work, ALP from [2] and DP Count Sketch from [34].
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We provide short section discussing limitations of our work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
18

---

The paper provides full set of assumptions relevant to the asserted claims. However, all the proofs are put in the appendix for space.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide detailed information on the experimental setup and the parameters used. We plan to open source the code in the near future well.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
19

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We plan to open source the code in the near future, but at the moment they are not ready to be released publicly.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. wwtpublcc//aeeccccccccccccccecct habbic/ggiidss//// /Coo//eoeeeeeeeee curbbmisssion swiissosisiyyyo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Our experimental evaluation provides detailed setup of the experiment and how the relevant parameters were chosen.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: While we do not explicitly include error bars or confidence intervals, we report all our numbers averaged over least 10 trials with standard deviation less than 10% of the average.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
20

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide detailed information the computer resources used to conduct the experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: attps://neurs //terr///eeuseeeeeeeeeee wtt.ccccpppc/eccc httpppppplllthhleeeeeepeepe csGuidelinest
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction)
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We believe work does not ineur negative socictal impacts, the goal of our work to enhance user privacy. We implicitly discuss how our work may beneficial protect user privacy in the introduction.
Guidelines:
21

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We believe our work poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: All the code was written by in C++ for a fair comparison (e.g. not compare with Python code). The dataset was artificially crafted and no external dataset were used in our experimental evaluations.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
22

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We plan to open source our code in the near future, but no new assets are released the time.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
23

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "99zpQfWHhX", "reviewer": "Reviewer_Gmoe", "summary": "The paper presents new differentially private (DP) mechanisms for representing sets of size k  from a large universe. It introduces two algorithms: one for epsilon, delta -DP representations and the other for pure epsilo-DP representations, with faster decoding. Both algorithms achieve optimal privacy-utility trade-offs and match new space lower bounds up to small constant.", "questions": "* In Algorithm 1, could you explore the failure modes of the algorithm more?\n * Theorem 3.1 - F is introduced, but it is not directly introduced as an input to algorithm 2. There’s some organizational work on that would help with comprehension.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "* The work is novel and appears to be correct, though I did not read and check the proofs for the theorems in great detail.\n* Theorem statements are clear, and are presented in a transparent manner.\n* Experimental results are presented clearly and align with the theoretical work.", "weaknesses": "* I think that the technical work is strong, but that the use case of this kind of work remains a bit unclear to me. If the authors could spend more time motivating the need for DP set representations and specific use cases, this would help contextualize the work better. The authors cite that this is useful for applications where users wish to privately disclosure sets of bookmarked websites - can this example be fleshed out more. What would the privacy attacks, and who would the adversary be? This helps structure the work in the context of local vs central DP, etc.\n* This also connects with the related works, as I find it somewhat difficult to understand the exact use case of DP set representations, it was hard for me to understand what gaps the related works didn’t fill. Even if the related works sections are well-written. \n* Some work in section 3 could be introduced a bit more, for example the work on “Random Band” and “Vandermonde” matrices. I don’t think it’s clear (at least to me)why this design choice was made in the pure versus approximate DP setting. This would help with understanding the gap between the the pure and approximate DP setting as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer Gmoe for their valuable feedback. \n\nTo illustrate the usefulness of our schemes, we will revisit the installed apps use case briefly mentioned in the paper and provide a concrete example. Imagine an analyst at an app software company looking to gather statistics on the percentage of a specific population who have installed apps developed by their company in a differentially private manner. One way to achieve this would be to use the randomized response scheme, which could take the form of the following question on the set of candidate apps: \"Does this device have app Y installed?\". Then, using the probability parameter $p$, the analyst can infer how many devices have installed these candidate apps.\n\nHowever, now imagine that the set of candidate apps is very large, say on the order of thousands (perhaps, the analyst also needs to get statistics on competitors’ apps) . This is much more than the number of apps installed on a typical device. In this case, asking and retrieving answers to the questions may incur significant bandwidth overhead. One could use non-DP sets, but that would directly reveal all installed apps to the analyst.\n\nOne solution to this problem is to employ our scheme. We configure an upper bound $k$ on the number of apps installed on the device (say, 250), then run our encoding algorithm to release the differentially private representations of the apps from the devices (suppose that we ignore devices with more than 250 apps installed, which are considered outliers). The analyst can invoke the decoding algorithm on the candidate apps to determine the distribution of the installed/uninstalled, and derive accurate statistics on the percentage of devices with these apps installed. While the differentially private app representation includes more information compared to a basic randomized response approach (as it encompasses data on other apps), it can offer a practical balance between privacy and utility in certain scenarios. Note that our scheme still ensures that the analyst cannot exactly identify the set of installed apps on each device.\n\nIn response to the reviewer’s suggestion, we will elaborate more on the constructions of “Random band” and “Vandermonde” constructions in the next iteration of our paper. The primary distinction between our pure DP and approximate DP schemes lies in the failure probability associated with the constructed linear systems. When utilizing the Vandermonde matrix construction, the constructed linear system is always solvable, resulting in a pure DP scheme (it never outputs $(\\perp, \\perp, \\perp, S)$). In contrast, using the random band matrix construction introduces a small probability of failing to solve the linear system, leading to a non-zero probability of outputting $(\\perp, \\perp, \\perp, S)$. \n\nWhile outputting $(\\perp, \\perp, \\perp, S)$ in this scenario may appear to be a blatant privacy violation, it is important to note that the probability of this occurring is small, as it is bounded by $\\delta$ in the approximate DP definition. Therefore, it satisfies the approximate DP requirements.\n\nFurthermore, it is crucial to emphasize that outputting $(\\perp, \\perp, \\perp, S)$ solely serves as a convenience in the privacy proof. In practice, alternative measures can be taken to ensure that the set is not disclosed in plaintext. For example, the algorithm can simply retry with new $h$ and $\\mathsf{Row}$ until the constructed linear system is solvable.\n\nFinally, we thank the reviewer for suggesting improvements to the presentation of the paper. We promise to incorporate the feedback in the next iteration of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q3KwfI2Lis", "reviewer": "Reviewer_1hbz", "summary": "The paper addresses the problem of releasing a set $S $ of $ k $ elements from a potentially very large universe $ U $ in a differentially private manner. Here, two input sets $ S $ and $ S' $ are considered neighboring if their symmetric set difference is at most one; that is, $ S $ and $ S' $ differ by adding or removing exactly one element.\n\nThe objective is to publish a concise representation of the elements in $ S $ that allows determining whether an element in $ U $ belongs to $ S $, while minimizing both false positives and false negatives. The paper introduces new algorithms for constructing succinct representations using solutions from random linear systems based on the elements in $ S $.\n\nThe $(\\epsilon, \\delta)$-differentially private construction achieves an error probability of $\\frac{1}{e^\\epsilon + 1}$, uses space of at most $1.05k\\epsilon$ bits, has an encoding time of $O(k \\log(1/\\delta))$, and a query time of $O(\\log(1/\\delta))$ per element.\n\nOn the other hand, the $\\epsilon$-differentially private construction maintains the same error probability, uses space of at most $k\\epsilon$ bits, but requires $O(k)$ query time per element. The space usage of both constructions matches the proposed lower bound up to constant factors.", "questions": "Can the embeddings proposed in this paper be mergable? For example, if we have two representations $ x_S $ and $ x_T $ created by the algorithms in this paper for sets $ S $ and $ T $, can we directly create a representation $ x_{S \\cup T} $ for $ S \\cup T $ using $ x_S $ and $ x_T $?", "limitations": "See weakness.", "rating": 5, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 3, "strengths": "1. The constructions appear novel. Rather than directly randomizing set $ S $, the paper utilizes elements from $ S $ to establish random linear constraints and publishes a solution that satisfies these constraints (demonstrating its existence).\n\n2. The space usage aligns with the lower bound.\n\n3. The algorithms demonstrate efficiency: both approaches exhibit slightly more than linear encoding time, and the approximate differentially private algorithm achieves $ \\tilde{O}(1) $ query time.", "weaknesses": "It seems there's a concern regarding the privacy analysis in the paper, specifically related to the use of the set $ S $ of size $ k $ to generate random linear constraints. Let's clarify and address the issues raised:\n\n1. **Number of Linear Constraints $ m $**: It's mentioned that $ m = (1 + \\beta) k $ for some constant $\\beta$. This implies that the number of constraints $m$ depends on $k$.\n\n2. **Dimension of Published Solution $ x $**: The solution $ x $ that is published has a dimension of $ m $, which is dependent on $ k $ as discussed.\n\n3. **Privacy Concern**: Given the definition of neighboring datasets (differing by adding or removing one element from $ S $), an adversary could potentially distinguish between these datasets by observing the dimension of the output vector $ x $. This suggests a potential privacy vulnerability if the dimension of $ x $ reveals information about the dataset $ S $.\n\nTo address this issue, possible fixes might impact current the error probability and subsequently affect the space usage analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 1hbz for their constructive feedback.\n\nThe reviewer raised a concern about the privacy analysis of our paper, suggesting that the size of the published vector could compromise privacy.\n\nWe want to clarify that the parameter $k$ is an upper bound on the size of the set $S$ to be encoded. In other words, we treat $k$ as an algorithm parameter, and the algorithm only accepts an input set $S$ with $|S| \\leq k$. Therefore, the dimension of the published vector is fixed to $m = (1 + \\beta)k$ for all valid input sets $S$ of size at most $k$, and the privacy proof holds in this scenario.\n\nWe note that this aligns with prior works ([1], [2]) that studied differentially private releases of $k$-sparse vectors. Here, a $k$-sparse vector is defined as a vector with at most $k$ non-zero entries (see first paragraph of Section 2 in [1] and second paragraph of page 2 in [2] for the definition of $k$-sparse vectors). Furthermore, the notion of DP is only defined over $k$-sparse vectors (see Definition 2.1 in [1] for example). Our work can be seen as studying a more specific instance of a differentially private $k$-sparse vector problem where the non-zero entries are restricted to values of one. In prior works, the space usages of the algorithms were stated in terms of $k$ (an upper bound on the number of non-zero entries), which aligns with how we state the space usages of the algorithms in our work (see Table 1 in [1] and [2]).\n\nUpon reviewing our paper more carefully, we acknowledge that this point was not clearly stated. We commit to addressing this in the next iteration of our paper to ensure clarity.\n\nThe reviewer also posed an intriguing question: \"Can the two published vectors $x_S$ and $x_T$ (encoding $S$ and $T$, respectively) be merged as $x_{S \\cup T}$ to encode the union set $S \\cup T$?\" In fact, we have considered this exact problem, but unfortunately, we could not find a suitable solution. For now, we leave this as an interesting open research question.\n\n[1]: https://arxiv.org/pdf/2106.10068\n[2]: https://arxiv.org/pdf/2112.03449", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HipxKGAvaM", "reviewer": "Reviewer_VHxw", "summary": "The paper studies the problem of optimal differentially private representing a set $S$ with size $k$ on universe $U$, under the setting where the set size $k$ is significantly smaller than the universe size $|U|$. In such settings, the authors propose algorithms to compute $(\\varepsilon, \\delta)$-DP set representation with error probability $\\frac{1}{e^\\varepsilon + 1}$, while only consuming $O(k\\varepsilon)$ space and $O(k\\log(1/\\delta))$ encoding/decoding time. The algorithm is based on representing the set via solutions to linear equation systems formed by computing random hash functions on each set member. The authors further prove that under $(\\varepsilon, \\delta)$-DP, their upper bound matches lower bounds in both error probability and space requirement, up to a factor of $\\log(1/\\delta)$.", "questions": "Besides the points listed in the weakness, I have the following questions related to novelty and presentation.\n\n- Is the non-DP variant of the set representation algorithm in the paper proposed in prior literature, or is it a novel algorithm?  This is to understand the novelty of the proposed algorithm.\n- In Theorem 1.1 and 1.2, the pure DP encoding time is $O(k(\\log k)^2)$ while the $(\\varepsilon, \\delta)$-DP encoding time is $O(k\\log(1/\\delta))$. Considering that typically we have $\\delta\\ll 1/k$, this suggests that the pure DP algorithm needs smaller encoding time, which is a bit counterintuitive as pure DP is a stronger requirement. Could the authors clarify why this happens?\n- The decoding Algorithm 2 appears to require new computation for each element of the universe $U$. However, in Theorem 1.1 and 1.2, the decoding time only grows with set size $k$ and does not depend on the universe seize $|U|$. Could the authors clarify this discrepancy?\n\n\nMinor typo:\n- line 221, $n \\geq k$ should be $m \\geq k$, \"full rank\" should be \"full column rank\"", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper has a clear presentation, and the results are relatively complete in matching lower and upper bounds.\n- The approach of encoding set membership via solution to linear equation systems is interesting, and its application to differentially private set representation is novel to the best of my knowledge", "weaknesses": "- I find that one part of the proof for error probability needs more clarification. Specifically, in lines 465-466, the authors write \"the false negative probability is s not sampled into S′ and the linear constraint being unsatisfied that is $p(1-F^{-1})$\". However, to my understanding, this probability should be $(1-p)(1-F^{-1})$. Maybe the authors could clarify more whether this is a typo and whether it affects any results.\n\n- The proof of error probability $\\alpha$ requires the existence of a $1/\\alpha$-finite field, which limits the applicability of the proposed algorithm for small $\\varepsilon$. For example, the algorithm's error upper bound appears to be identical for all $\\varepsilon \\leq \\ln(2)$, as under such settings the smallest finite field that is larger than $1 + e^{\\varepsilon}$ is always $Z_3$.\n\n- Executing the algorithm requires knowledge of an upper bound of the set size $k$, as the algorithm requires to form an underdetermined linear equation system. This may significantly restrict the applicability and optimality of the proposed algorithm when no such knowledge is available.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer VHxw for their valuable and constructive feedback.\n\nWe will first address the reviewer's question regarding the error probability. We think that the proof presented in our paper is accurate. We believe the misunderstanding may arise from the way the pseudocode in Algorithm 1 is structured. In Algorithm 1, we insert each element of set $S$ into set $S'$ with a probability of $1 - p$. Note that this is equivalent to removing each element from $S$ with a probability of $p$ and considering the resulting set as $S'$. Consequently, the probability of a false negative is indeed $p(1 - 1 / |F|)$, because a false negative can only occur if the element is not present in $S'$ (e.g. removed) and the false positive does not occur for this removed element. We will try to rewrite the pseudocode to make this clearer.\n\nThe reviewer raised a question if the non-DP set representation algorithm in our paper had been discussed in earlier research. To clarify, some of the linear systems in our paper have been used to construct non-DP sets while others have not. Random band matrices have been studied as non-DP sets (we mention this in the first paragraph of Section 3). On the other hand, Vandermonde matrices have never been used to build non-DP sets to our knowledge. However, we want to emphasize that the novelty of our work lies in our observation that any linear system with certain properties can be modified to produce differentially private set representations. Our work further proposes a general DP framework based on these linear systems. We believe this observation is highly significant and non-trivial.\n\nWe note that there are also non-DP set data structures (like cuckoo filters) that are not directly compatible with our framework, indicating that our observation is non-trivial. To our knowledge, we are unaware of any method to convert them into DP sets. In particular, there are certain properties unique to the linear system set data structures that we rely on to ensure DP privacy guarantees.\n\nThe reviewer also requested clarification regarding the encoding runtimes of the pure DP and the approximate DP algorithms. Indeed, the results may appear counterintuitive. The distinction between the two algorithms lies in how they solve linear systems.\n\nFor the pure DP algorithm, the Vandermonde matrix's structure allows for the use of an FFT-like algorithm to solve the linear system efficiently. However, this approach is not feasible for the random band linear systems in the approximate DP algorithm, and we thus use the Gaussian elimination instead. While Gaussian elimination typically takes $O(n^3)$ on a general linear system, we emphasize again that the random band linear system’s unique structure allows the linear system to be solved very efficiently n $O(n  \\log(1/\\delta))$, both theoretically i and practically.\n\nIt is worth noting that this difference in matrix structure also impacts the decoding times. The pure DP decoding algorithm has a time complexity of $O(k)$, while the approximate DP decoding algorithm has a time complexity of $O(\\log(1 / \\delta))$. In this respect, the pure DP construction offers pure differential privacy and efficient encoding at the cost of a slower decoding time.\n\nIn relation to the reviewer's third question, we emphasize that the decoding time of $O(k)$ and $O(\\log(1 / \\delta))$ applies to decoding/querying a single element. Consequently, if we query $T \\subseteq U$ elements, the total decoding time becomes $O(|T| \\cdot k)$ and $O(|T| \\cdot log(1 / \\delta))$, respectively. Our formulation of the decoding time is consistent with previous studies on the differentially private $k$-sparse vector problem (e.g. Table 1 in [1]). In these works, the decoding time is expressed in terms of the time required to access a single entry of the $k$-sparse vector. However, we acknowledge that the term “decoding” can be ambiguous, and so we will change it to “access” or “query” instead in the next iteration.\n\n[1]: https://arxiv.org/pdf/2106.10068", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dqKK1XfiTZ", "reviewer": "Reviewer_ys34", "summary": "The paper considers private representations of sets (under the neighboring relation of adding/removing an element). The goal is to answer set membership queries correctly with some nontrivial 1-alpha probability of being correct. (For a universe of size 1 this can be addressed by randomized response, so this problem generalizes releasing a single private bit.) Of course, the privacy guarantee will need to depend on alpha. Previous related work considered histograms (or multisets) and private versions of Bloom filters, but the performance of these past approaches on set membership queries has not been studied. The paper takes an interesting new angle, using ideas from space-efficient filters to get differentially private set representations using small space. It also gives lower bounds that nearly match the upper bound. Experimental comparisons to existing techniques suggest a better privacy-utility trade-off with comparable time usage.", "questions": "- Can you make the privacy proof clearer? I think there are subtleties that should be discussed in the *main part* of the paper. For example, it would be good with a discussion of the probability of returning (⊥,⊥,⊥,S) when the linear system does not have full rank. This seems like a blatant privacy violation, though it happens only with probability 𝛿, so does not contradict approximate DP.\n- Are there not some lower order terms missing in the space usage stated in Theorem 1.1 and 1.2? It seems that if you need to choose the field size a bit larger than 1/alpha, more bits per entry will be needed. Also, if the field size is at least e^epsilon it seems that each entry requires ceiling(epsilon/ln(2)) bits to encode.\n- If you do not sample (i.e., use p=1), could you apply randomized response to the vector b before solving the linear system to achieve DP?\n- If you return (⊥,⊥,⊥,S) with probability 𝛿 even when the linear system is solvable, does it yield pure DP?\n- In some places (e.g. line 470) it is stated that the field size is 1/alpha. I believe you simply need it to be *at least* 1/alpha, as stated in line 261?\n- Theorem 1.4 seems to be missing a condition that alpha is not too close to zero (or that epsilon is not too large)? The proof technique in the appendix does not seem able to show any space bound larger than the entropy of a random set of k elements from a universe of size n.\n- Can you confirm the limitation mentioned below?", "limitations": "It should be made clearer that the DP guarantee relies on the hash functions being fully random while the space guarantees relies on the hash functions being pseudorandom. It would perhaps be more correct to state the results as computational DP.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Strengths:\n- Studies an interesting special case of a well-studied problem (private histograms) and gives better guarantees for this special case\n- An interesting generalization of randomized response to a \"sparse\" setting\n- Literature review is comprehensive and well-written\n- The techniques are interesting and novel", "weaknesses": "Weaknesses:\n- It took me a while to understand why the results hold, the writing could be better\n- It seems that the lower bound in Theorem 1.4 cannot possibly hold as stated (see questions below)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer ys34 for their valuable and comprehensive feedback.\n\nIn response to the reviewer's suggestion, we will improve the clarity of the privacy proof and incorporate additional context within the main body of the paper. We acknowledge the importance of explicitly explaining why returning $(\\perp, \\perp, \\perp, S)$ is acceptable when the linear system cannot be solved, and why this does not violate the definition of approximate differential privacy. It is worth highlighting that returning $(\\perp, \\perp, \\perp, S)$ is only a matter of convenience to simplify the privacy proof. In practice, alternative measures can be taken to prevent the release of the set in plaintext. For example, the algorithm could retry with newly sampled $h$ and $\\mathsf{Row}$ until solving the linear system succeeds.\n\nThe reviewer is correct with our Theorem 1.1 and Theorem 1.2 missing lower order terms. The space usage of the approximate DP scheme should instead be roughly ~$1.05 \\cdot k \\cdot \\epsilon \\cdot \\lg(e)$ bits, and roughly ~$k \\cdot \\epsilon \\cdot \\lg(e)$ bits for the pure DP schemes. We thank the reviewer for pointing this out, and we promise to fix it in the next iteration of our paper.\n\nThe reviewer also raised an interesting question on the possibility of using the randomized response on the RHS vector instead. In fact, we have explored this direction as well, but we encountered some challenges with either the query correctness probability and/or with the privacy proof. However, we agree that this is an interesting modification to the algorithm and worth exploring further in the future.\n\nThe reviewer is correct that the field size just needs to be at least $1 / \\alpha$ instead. We will make this clearer in the next iteration of our paper.\n\nWe appreciate the reviewer's observation that Theorem 1.4 may not hold true when $\\alpha$ is sufficiently small. Our current lower bound states that, in such cases, we would require more than $\\log \\binom{n}{k}$ bits, which is evidently incorrect - we can clearly represent any $k$-subset with 0 error probability with $\\log \\binom{n}{k}$ bits. To address this, we will modify the theorem statements to instead require at least $\\min(\\Omega((1 + \\delta / e^\\epsilon) \\cdot k \\cdot \\log(1 / \\alpha)), \\log \\binom{n}{k})$ bits. This correction will be incorporated in the next iteration of our paper. It is worth noting that our lower bound proof explicitly makes this assumption on Line 537 (but does not state in the theorem statement), and so our lower bound result is not invalidated.\n\nFinally, the reviewer is correct with the limitation of our work. Indeed, our DP guarantee and the space usage do rely on the hash functions being fully random and/or pseudorandom. If we assume pseudorandom hash functions (PRFs), we indeed obtain computational DP.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents interesting novel technical work on a special case of the well-studied problem of releasing histograms under differential privacy. The reviewers had some concerns about the quality of the exposition in the paper, and the clarity of the motivation of the problem they study. The work also has some limitations, e.g., the need for the public upper bound $k$ on the sparsity of the histogram. Nevertheless, the paper is an interesting contribution.
Decision: Accept (poster)