Creating a Public Repository for Joining Private Data
Authors: James Cook
Milind Shyani
Nina Mishra
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential privacy
machine learning
linear queries
TL;DR: A non-interactive protocol to share a dataset in a differentially private way that nonetheless allows joins with other datasets on sensitive identifiers

Abstract: How can one publish a dataset with sensitive attributes in a way that both preserves privacy and enables joins with other datasets on those same sensitive attributes? This problem arises in many contexts, e.g., a hospital and an airline may want to jointly determine whether people who take long-haul flights are more likely to catch respiratory infections. If they join their data by a common keyed user identifier such as email address, they can determine the answer, though it breaks privacy.  This paper shows how the hospital can generate a private sketch and how the airline can privately join with the hospital's sketch by email address. The proposed solution satisfies pure differential privacy and gives approximate answers to linear queries and optimization problems over those joins. Whereas prior work such as secure function evaluation requires sender/receiver interaction, a distinguishing characteristic of the proposed approach is that it is non-interactive. Consequently, the sketch can be published to a repository for any organization to join with, facilitating data discovery. The accuracy of the method is demonstrated through both theoretical analysis and extensive empirical evidence.

Creating a Public Repository for Joining Private Data
James Cook
Milind Shyani Amazon mshyani Gamazon com
Nina Mishra Amazon nmi mmishra@amazon..comm
Independent Researcher' falsifian@falsiff org
Abstract
How can one publish dataset with sensitive attributes in way that both preserves privacy and enables joins with other datasets on those same sensitive attributes? This problem arises in many contexts, e.g., hospital and an airline may want to jointly determine whether people who take long-haul flights are more likely to catch respiratory infections. If they join their data by common keyed user identifier such as email address, they can determine the answer, though breaks privacy. This paper shows how the hospital can generate private sketch and how the airline can privately join with the hospital's sketch by email address. The proposed solution satisfies pure differential privacy and gives approximate answers to linear queries and optimization problems over those joins. Whereas prior work such secure function evaluation requires sender/receiver interaction, a distinguishing characteristic of the proposed approach is that it is non-interactive. Consequently, the sketch can be published to repository for any organization join with, facilitating data discovery. The accuracy of the method is demonstrated through both theoretical analysis and extensive empirical evidence.
Introduction
Given a sensitive dataset keyed by individual identities (which must never be revealed), how can we publish private version of it that can nonetheless be joined by identity to another dataset to produce approximate answers to questions about the join? Can a sender publish this private version to repository so that receivers can both approximate joint distributions and train MI. models, without any interaction between the sender and the receiver?
There are inter-organizational scenarios where answering these questions is valuable. For example, a healthcare provider may have clinical records keyed by patient email address and private column such as "has cancer". A company wants to determine if employees who work near toxic waste sites have higher incidence of cancer. We show how two companies can privately join their data in order to build such predictive models. With the rise of data marketplaces, it is more common for organizations seek to "decorate" their data by adding new columns from other organizations, while preserving privacy. intra-orgunizational scenarios also abound. Within large organization, it is common that data collected one team hidden from other teams. With a central repository, not only is data discovery possible, but more private joins can be performed to assess predictive power.
The Repository Setting. stylized view the problem is shown in Fig. One party, the sender holds a dataset Ds with two columns: unique identifier to join on, and a value from a small finite domain (in this case, has cancer encoded +1). S would like share Ds privacy-preserving way with many other organizations without explicitly interacting with each one. To this end, S uploads a private representation of Ds to a public repository. Party one of many possible receivers. and holds dataset which has a column with unique identities to join on, and any number of other columns, e.g., latitude and longitude of where their employees work. R's goal to perform a joint
WWrk done while employed by Amazon.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Receiver
Private Count Sketch
Name
Work Location (Iatitud_longittddy
Priuste to
Sender $
Bob
(34.93,
Name
Cancer?
Sox spengee
(39.73, 75.13)
Alice
Repostory
Skatth It's
Carol
-1
Nome
Work Location
Cancer +1
Cancer-1 -1
Ed
+1
Bob
[34.93, -11.22)
0
Carol
(40.83, -80.44)
-1
Private 5
Private to
Figure I: stylized illustration of the Repository Problem. The sender uploads a private count sketch capturing people who do and do not have cancer. The receiver R uses the sketch decorate their data (work location) with a noisy version S's cancer column. Two noisy columns are generated: one for cancer (+1) and another for not (-1). R can then build an ML model to predict if employees who work near a toxic waste site are more likely to develop cancer.
computation - red box in Fig. It involves the inner join that would normally include only people in both datasets. But, for privacy, the receiver R does not know about the existence of Alice; and even though David is not in S's data, R still receives label, which noise. This paper studies how R can learn functions over the inner join of and S, e.g., does work location predict cancer positivity.
Problem statement Joint computation of linear queries and optimization are described in Subprob- The dataset representations should be compatible with both problems simultaneously.
lems 2 and 1.3
Problem 1.1. Given a dataset Ds with a unique identity column and one value column with a small finite domain, publish repository single differentially private representation of Ds which can be combined with any other dataset Dr. (so long as Dr has column of unique identities for joining)
solve Subproblems 1.2 and 1.3
linear query involves applying some function f to each element the join and outputting the sum Subproblem 1.2 (Linear Queries). Let I be a real-valued function. Define
SunOOverJoinsg.ee(Y)
Σ
D
<dEids(Dn)nids((s)
where ids(D) is the set of identities that appear in D and Diid] is the value associated with id in D. Given access to DR and differentially private representation of find estimate & so that
Pr[ SunOverJoinng [J)] p4] <
In an optimization query, the goal is to find a function f in class of functions F that approximately minimizes Sum MumnOveJJonnp.... (f). Supervised learning with a loss function is special case. Subproblem 1.3 (Optimization Queries). Given class F of real-valued functions, let fopt arg min Sum (f), Given access to DR and a differentially private representation of Ds, find function f such that
SumOverJoin Pr/SumOOveJJiinpp.pee777
(Jopt) > p1] <
Contributions. Problem 1.1 is solved by building upon work on private count sketches. This paper makes the following contributions. (1) Method. We show how to apply the private count sketch to enable sender to share their data privately, enabling receiver to approximately join it with their own dataset on individual identifiers estimate linear queries and learn functions. The identities of the individuals in the sender's data are not revealed. A distinguishing characteristic of the method is that the algorithms are non-interactive, and hence are repository ready. (2) Analysis. non-trivial mathematical analysis in the form of theorems bounding the error. For linear queries, Problem I.2

---

our main result is Thm. [.I] For optimization queries, Problem 1.3 our main result is Thm. 6.4 proved using a careful combination of tail bounds. (3) Experiments. (a) We conduct three sets of experiments on public data to compare our solutions to exact answers obtained by joining the data directly, with no privacy. With a reasonable privacy parameter (8 = 1) we acheive over 92% accuracy on the EMNIST dataset, and applying logistic regression on the UCI Adult dataset, we lose less than 1 % accuracy compared to training on the original data with no privacy. (b) We compare to related methods. We adapt the protocol of Zhao et al. [39] to allow for joins and show that our approach is more accurate. We also compare with the LabelDP [2]] method on an already-joined dataset, and show that our method performs competitively despite having the harder task of performing a private non-interactive join.
2 Related Work
Privacy. Differential privacy 19 18 is widely used definition that intuitively guarantees that the not in the dataset. One
outcome of a mechanism essentially unchanged whether an individual of the most commonly studied models of privacy in the literature is the curator model where trusted centralized repository holds all personal information. The role of the curator is to answer questions about the data in a differentially private way. In the function release problem, the curator must release a single piece of data which can be used to answer an unlimited number of queries (4 2 14]
In our case, party S plays the role of curator. The private representation they upload to the public repository can be viewed as an example of function release. It does not depend on the structure of R's dataset or the particular function R aims to compute - S has no knowledge of the parties R who might later download it. Therefore, we can view the sketch as function accepting as "query" an entire dataset Dr together with the function to apply to the join.
Private Sketches. Sketching common technique used to summarize a dataset. The technique most relevant to this paper is the Count Sketch [10] which we describe in more detail below. Other influential sketching techniques include count min [16), tug of war 44. locality sensitive hashing 25 and AMS (3]. Private variants of sketching have also been considered wherein, for example, the usual sketch is computed and noise is added. Two examples include the private count sketch 66 39 and the private count min sketch [39]. Count sketch has been used to solve a wide variety of problems, e.g., estimate histograms, frequencies. quantiles or heavy hitters. We add this list of uses the ability to support data joins. Other examples of private sketch work include the Johnson-Lindenstran transform 7 and the loglog sketch [2] neither require additional noise for privacy. Private locality sensitive hashing [15] has been considered in the context of private function release.
We are not aware of past work that uses the count sketch to privately join. Nevertheless, it is possible to adapt prior private sketching work to our framework. However, since these solutions were not designed with our application in mind, they do not perform as well see the experiments in 7..
Local DP. (6 describes an approach in the local model, where each individual publishes their own noisy data. If individual identities are discarded it precludes joins. If the central server in the local model records individual identities, the identities cannnot be published without compromising privacy. While our techniques are similar to past work in local differential privacy, there important differences: we apply them in the repository setting rather than a local DP setting (see Appendix HH for comparison), the frequencies sketched sketched, and our technique enables joins on those private identifiers. We optimize our use of count sketches for this setting (especially in (6) and provide novel experimental and theoretical analysis.
always 0 or 1 because unique identifiers are being
Vertically Partitioned Data. [17 study a scenario where a user interactively queries multiple
independent databases holding vertical partitions of dataset. Other results include [30 31 33 36). Note that in our case, the protocol is non-interactive; each database has an identity column which must be used to join the tables; the identities are private; and some identities may be present in one database and not the other.
Secure F Function Evaluation. In the cryptography community, there is extensive work showing how two parties A, B holding data x A z can jointly compute f( without leaking any information beyond [ xR) [37 23 For interactive, multi-party computation, cryptographic techniques are superior solution. However, this paper is on non-interactive solutions for the repository setting. More comparison can be found in Appendix]]
3

---

3 Preliminaries
Notation Z, N and denote the sets of integers, nonnegative integers and reals. We let be some set of unique identifiers for people e.g. strings representing name and address. For datasets D, D', the join DA D' is defined in Definition 3.1 and [D] E N the number of rows in D.
Datasets A dataset D C U x X is set of pairs (id M, E X); we call X its value domain and its elements rows, In our problem there are two datasets: the sender's 's (Ds) and the receiver's (Dr). The value domain of Ds will always be X {1.kk for some small & E N, but there is no restriction on the value domain DR: X could numbers, text, images, etc. We do not allow any id E U to appear more than once in the same dataset, in particular there are no duplicate rows.
Joins
When the same identity appears in two datasets, we want to combine the associated values. Definition 3.1. The join of S x and D' C U Y is a dataset Da D' C X
defined by
(id, x. v) E Dr = (id, E D (id, y) E D'
This an example of natural join [13,, using the identity column D and D' have in common. Given a function f x Y + R. we define the sum over the join:
Definition 3.2.
SumOverJoin,, (f)
E
f(z, v)
(d
(This is equivalent to the definition in Subproblem 1.2 but written in terms of D Da D'.)
Differential Privacy Let and be positive real numbers and M be randomized algorithm. We say that M is (c, j--differentially private [19] if for all S C Range(M MM) and for all pairs of datasets D₁ and D2 that differ in the addition or removal of one row, (D) E S) S e Pr(M((D2) E 5) 1)++0 where the probability is taken over the coin flips of M. In this work we will always set 8 = in this case we say M is e-differentially private; this is called pure differential privacy.
The two-sided geometric distribution The noise we add ensure privacy will follow the two-sided geometric distribution [22] (see notes in Appendix B.I::
Definition 3.3. The two-sided geometric distribution with parameter a, denoted TGeom (a), is
distribution over with probability mass function Pr[Z = 2| 1-a 1-2al=l.
1+a
Private Count Sketches We use a simplified version of the count sketch [0 as a way to encode dataset D C u x k). It is parameterized by number of buckets b and two hash functions h:ll x {1..k} + (1.bb, U x {1..k} + (-1.+1).
Definition 3.4. Given b, and as above, the count sketch of dataset D cu x {1..k} a vector CountSketch,....() = (CI,.... (ci....,c.) c.) e Zh, where = Eaa s(id,)) y).
Adding noise makes a count sketch differentially private:
Definition 3.5. Given D, b, h and s as in Definition 3.4, and a privacy parameter E > the private
count sketch of D is random vector PrivCounSSetchh,, a, (D) CountSketcho, (D) + Ze z where Ze is vector of b independent samples from TGeom (Definition 3.3
Since adding or removing row from D causes CountSketch,,.. (D) to move distance of in the ε metric, we have 6 3
Proposition 3.6. PrivCoum@Sketchh..eel
is e-differentially private.
It is common to repeat the count sketch with multiple independent hash functions to mitigate error caused by hash collisions when there are fewer buckets than items (b < 11). This is important when the goal is to recover frequencies of repeated items while storing the sketch in as few bits as possible. In contrast, our frequences are all or 0 (present or not), and our goal is to estimate aggregates of many such frequencies. We are not trying compress stream, we take b z at which point

---

we find the error added by Ze dominates the error from hash collisions. We do not repeat the count sketch because would improve eπror only slightly (if at all), and because would complicate our analysis. In 77. we compare to a private sketching method that uses multiple hash functions and Gaussian noise, and find performs worse than Definition 3.5 for our purposes.
Method Overview
We begin with intuitive motivation for the method and then provide an overview of the steps S and take to solve Problem I.1 In $$5 and we explain R's computation in detail.
4.1 Intuition and alternative approaches
Here is a simplified version of our problem. Suppose parties S and R each have set of individuals' names Ds, DR C [A..Z]". wishes to estimate the number of names in common: |Ds Dal- The names are sensitive and cannot be shared directly. Instead, S must publish a differentially private representation = Private Ds) without consulting R, and then R must compute their estimate based on C' and Dr. This is special case of Subproblem T.2 Here are some possible approaches.
Secure function evaluation. In cryptography, this problem called private set intersection cardinal- ity [20 26]32]] 32). Cryptographic solutions are well-studied, but require multiple rounds of interaction. In our repository setting, party publishes single value Private(Ds) and may not interact further. See Appendix for a discussion on this comparison.
Send the hashes. One might try choosing secure hash function h :4 {0, 1}* and sending Private(Ds) = (h(x) : x E Dz}. The problem is that would need to know to compute [Dn 0 Dsl- Knowing would let them test individuals' membership in Ds, compromising privacy.
Dot product of noisy vectors. We can view the sets as vectors Ds, Dn E {0. 13 with one bit for every possible id U. Then DRD DD n DR.. Party S can make their vector s-differentially private by adding noise: Private( Ds) = Ds + Ze. where Ze E Zd vector of independent samples from TGeom(e-5) Party R can estimate Dr n Dsl Private( Ds) S DDR The problem is that U is too big - if identities are r-bit strings, then Private(D)) Ds) takes more than 2" bits to store.
Solution: Private count sketch. The solution we use is modification of the previous one: S sends vector with noise added, but first reduces the dimension using private count sketch.
4.2 Protocol
Our solution to Problem 1.1 has two steps: (1) S publishes a sketch and some parameters (Algorithm) T
figure in Appendix A (2) R downloads the sketch and runs Algorithm 2 (Subproblem 1.2 linear
queries) or Algorithm 3 (Subproblem 1.3, choosing the optimal function from a class).
Although the elements of Ds are pairs (id E u x {1..k,, treat them opaque values for the purpose computing PrivCount PrivCouutSSeetchnn..c (Ds) - so the domain the hash functions h, is U {1..k). The time complexity of Sender is O(IDs + b), assuming that sampling from TGeom (a) and computing the hash functions and all take constant time.
Algorithm Sender
Let {1..k) be the range of Ds's value column, i.e. Ds C x k1.
1: Choose the privacy budget and the number of hash buckets b.
2: h, s + ChooseHasshFncttiooo
3: C' + ---Prrv PreiCConnSSetthh...o
(ss)
4: Publish C E z and the parameters b, h, 8, repository.
Building sketch requires first choosing hash functions h, s with an algorithm Chooselashhuunctinnss
Choosing hash functions
This choice has no effect on privacy: even Var l((x)) = s(x) 1, the private count sketch is differentially private. However, higher-quality hash functions will give more accurate results. Thm. 6..4 assumes and s are sampled uniformly from the set of all functions; in practice, cryptographically secure hash functions should give the same guarantees.
5

---

Linear queries
can use Algorithm 2 estimate SumOverroinDa...D (f), given access their own dataset and the associated parameters k. b, h, sent
Da along with C = PrivCountSeeccch....eee by S. Its time complexity O(k + b), assuming f(a, y) can be computed in constant time. The computation C on lines 2-4 can be explained as follows. For every (id, E {1.kk. R multiplies qiid, y) s(id. y) fzz y) by the entry at index h(id, y) in S's sketch. In expectation this equals f(z. y) if (id, y) E Ds and otherwise. The sum of these values over (id,z) 2) DR. y E [1..k] is QºC, C, and equals SumOverJoin Ds (f) in expectation. Here the expectation is taken over the output of ChooseffashFuncti.
DR and
and the TGeom(a) noise.
Algorithm 2 Recei Raceevverrlnnnarruuuuerss
1: Download C PrivCountSSeecchh..sss (Ds) and the parameters b, h, from the repository.
2: Set q(id, 4, 3) R2 to be s(id, fx, y) entry h(id, y) and 0 everywhere else.
3: Construct Q = Σ (i Ey=1 q (idd, 2; y), the query vector.
4: Return Q²C.
Theorem 5.1. For any datasets DR Cu X Ds Cu x functtin function f: X x {1..K} + R.
privacy purameter e >> O, number of hush buckets b, and accurucy parameter μ > 0, if h and s are drawn from a mutuully 4-way independent hash family, the following holds. Let M be an upper bound 3f( ko be the range of the value column of Ds. DR Xa Dsl, C Then
PriwCountSketchh...ae
C SumOverJoinng..s.. (D) > P
( 2e
Dss
Pr
+
12n²
(1 e---- 62
The probability is taken h, and the noise added PrivCountSketchn...o (Ds)-
We defer the proof to Appendix C
According to the theorem, the size of the join should be sufficiently
large for it to be useful.
Optimization
Suppose R's dataset has id column and several feature columns, and S's has id column and label column. In this section we show how R can train model to predict S's labels from R's features. More generally, if R has a class of functions F which map X Y R, we show how R can select FF which close to the optimal function fopt.
fopt == arg min Sum0Ovet.loimpp....())))) arg min feF
Σ
f(x,y)
fEF
(id.n.))
in the sense that (SumOverJoinDn.... (f) SumnOveJoinpa.no (Fopr) is small.
For example, suppose Ds has labels y E {0, 1} and Dr has feature vectors E Rd and R would like to train a logistic regression model DR D4 Ds. Then R can take F= = [lo 0 E Rd), where to is the logistic loss lo (x. y) = y log(1 + -
e #) (1 y) log(1 + =00))
In 1 and 6.2 we show how to compute the estimate f. assuming we already have a non- non-private optimization algorithm that accepts weighted inputs. (For an alternative without weights, see Ap- pendix E In $6.3 we analyze the loss accuracy due to privacy.
6.1 Evaluating one function
Our optimization method is based on a score & (f) for individual functions f E F, which R computes based on their dataset DR and the sketch C' sent by S. The score is proxy for the true objective SunOverJoinnge
(J). It is less sensitive to noise and hash collisions than the estimate The cost is that & PDr does not actually approximate SumOver De (f).
QTC from $

---

Instead, the two have a linear relationship: PD,,c(f) = 3 SSmmOverJoing D3 (f) for positive number B(DR, Ds. which does not depend on f. (We prove this in the appendix in Lemma D.3 as part of the proof of Thm. 6.4) R does not know B, but does not need to: the 6.. boils down to computing arg min c())
optimization method described
There are two differences between score & &D and the linear estimate Q²C, developed while proving Theorem 6.44 First, we clip coordinates of the sketch C' to be between -1 and 1.
Definition 6.1. For x E R. clip(r) is or if x 2 or x I 11; otherwise clip(z) = z. The clipped version of a vector C' E R is vector with clipped entries: clip(C), = clip(C:).
(Since sketches have integer coordinates, clip(æ) equals the sign sgn(#) E (-1,0,
0.1,1, 1). In 7.2
try sketch with non-integer coordinates.) Second, when h hashes more than one row (id, x) E Dn to the same coordinate of C, we reweight the terms corresponding those rows.
Definition 6.2. The score of E F is defined as follows. Let Na((a) be the number of possible pairs (id, y) where appears in DR. y any value in (1..ki, and h(id, y) a:
s(id, y) (() (1d,))
Df)
Σ
NR(h(id, y))
6.2 Performing the optimization
Here show how R can compute the estimate f E F, given their own dataset DR. the parameters k, b, h, 8, e, and C PrivCountSketchn..... Ds) downloaded from the repository. short, our method is simply to find the function that minimizes the score defined in the previous section:
Definition 6.3. The estimated optimal function in F is f arg min &D).c())-
If F is small finite set, this definition directly leads algorithm: R computes O Dn,c(f) for every f e F and chooses the arg min directly. For larger Fs we will assume has an algorithm NeightedOpt to find the optimal on a weighted dataset. weighted dataset is collection of (w,2,, 2. y) triples where E R is called the weight and (æ. y) is valid input to functions in F. To be precise, WeightedOpt minimizes
SumtvsrDatasot (f))=
Σ (W)s,
f v)
Many algorithms for training machine learning models admit a weight associated with each training example; such algorithm could play the role of WeightedOpt.
now find the optimal function by implementing Algorithm 3 The time complexity of this algorithm is O(k)Da)) + W ([k] (n))), where W W(n) is the run-time complexity of WeightedOpt on a dataset with n elements.
By Definitions 6.2 and 6.3
output Weighted0ps is identical to the estimated optimal function f. The question of whether is any good is addressed 6.3
Algorithm 3 Receiverdppimiize
1: Download C = PrivConntShetchn...dd (s)) and the parameters k. b, h, y) for y 1,...,
2: Wia.y s(id, y) clipp (clli((Chaaa)/NNaaa
3: Construct Đ (b, h, 8, Dn, C*) by creating (Wid,y, x. y) for each element (id, x)) E Dn and
{1..k}.
/ //note: [D] = k) Dxl
4: Return WeightedDpt(D...
6.3 Analysis
Here we analyze the accuracy of our method the context learning a classifier. We state and prove more general result Appendix D and prove the below results in Appendices [D.2] D.3
We bound the classification error of model trained using our method on features from DR and binary labels from Ds (so k 2). Let J be set of classifiers f X {0, 1]. and for f e F let
7

---

Lj E N be the number of classifications errors on DR x Ds. To apply Algorithm 3 we convert this an equivalent problem: let & be the set of corresponding enror functions cx(a, y = lf(x) yl for f E F, so I. SumQ OverJoin D3 (ez). Then we can ask Algorithm 3 to find the best ef E g, which corresponds to the best classifier f.
Theorem 6.4. For any datasets DR _ Ds x function class F, privacy parameter & > O, number of hash buckets b and accuracy parameter 0, if h and are drawn uniformly at random from the set of al a functions U x {1..k} -> {1..b), the following holds. Let Sopt be the classifier that minimizes L,s, and let f be the classifier corresponding to the function ef oulput by Algorithm
3
Let d be the VC dimension of F, n = DR ba Dsl. and
DRl
Dsl
1 4
1/
WR min
Ws = min
n
n
5k| DRL
14
D2s
Then
L Iopt
WR WnWs + p2n -d dogg
Pr
11 exp (-Q
For reference, we define VC dimension in Appendix B.4 Adding assumptions can simplify the bound, This corollary highlights the dependence on the privacy parameter e:
Corollary 6.5. Assume Dn and D have the same set of identities, so the join "perfect" the sense that [Dl = Dsl = D pa Ds Let DR ba Ds| and let d be the VC dimension of F. Assume also that b 2(n). Let fopt be the classifier that minimizes Lg. and let f be the classifier corresponding to the function ej output by Algorithm 3 Then for any μ > O.
L
Ls
Pr
10
S <epp(- dl)gn))
Experiments
The goal of the experiments is evaluate the accuracy of our solutions and quantify the effect of noise and join size on downstream tasks. To simulate parties S and R, for each dataset, we add
unique id to each row, then split its columns into DR with all of the features and Dg with labels.
In 7 we learn a function that, given features x, predicts labels E {1..k} using Algorithm 3 and a private count sketch. Appendix
F we estimate joint distribution using Algorithm 2 In both cases, we find that the test error drops as we increase (meaning the privacy requirement is relaxed) or the sketch dimension, or as the join size increases (DR, Dg have more ids in common). 7.2
compare our results with the private linear queries protocol of Zhao et al. (39]. We also conduct experiments with multi-way joins and with non- non-unique identifiers in Appendix!!
Datasets. Two datasets are used in the experiments. (1) UC Irvine Adult dataset M. We predict if income is greater than 50K based on categorical features such as age, workclass and education. (2) Extended MNIST, for which we predict labels based on images of handwritten digits.
7.1 Optimization: Prediction Findings
We evaluate our method with two machine learning tasks: logistic regression on the UCI Adult dataset, and neural net for Extended MNIST. We capped the cross-entropy loss by replacing predicted probabilities ý with max(ğ, g, 10-4}. This is necessary since Algorithm 3 can produce negative weights, which would lead divergence in the optimization if loss were not bounded.
In each case, we conduct several experiments varying the privacy paramete и and the sketch dimension b. All accuracy numbers are measured on the test set directly, with no Simulated join. The right halves of Figs. 2 and 3 show the results, with different lines for different sketch dimensions b. dashed line shows the test accuracy of a model trained directly on the training set, without privacy.
In practice, cryptographically secure hash functions should give the same guarantees.
3 "Ponomareva al. (29 | suggest e S 1 gives "strong" privacy guarantee and e < 10 is "reasonable".
8

---

Adult Join size. == [P,M0g] 6400.
Adult accuracy [0,MD,]
0.84
Test accuracy
0.92
Test accuracy
0.00
0.80
0.75
0.78
0.75
10-
1 4ppamsial
0.72
0.1 kiDyMDDs
4jpuseng) we privacy
0.62
0.70
0.01
5.1
/ [0, Pa Ds
epsiion
Figure 2: Test accuracy of logistic regression on the UCI Adult salary prediction task ($ 77.1
1.0
IHMST join sioe 2 10, (5ae0aa
EMNIST test accuracy vS. Z- 10, 10 240K.
0.5
0.05
0.90
0.8
0.85
0.7
0.6
0%
19 90% M.Dd
130 182 Drl
Test
0.75
0.90
Ryady 180ax0 01 49
1 Ap%
0.65
0.4
privicy
/ [Da P4 Del
epsilon
Figure 3: Test accuracy of a deep neural net on the Extended MNIST dataset
7.1
Imperfect joins, where Dx has some IDs not present Ds. are simulated by randomly removing most of the rows in the training set, and then adding some back only to DR. The left halves of Figs. 2 3 show the results. The performance drops as this fraction increases, which is expected since unmatched rows in Dr are assigned random labels that add noise to the training. In practice, party would benefit by filtering Dt to contain only identities likely to be in Ds. e.g., if Ds contains people in Ohio, R should also filter Dn to Ohio. Note that on the right panel of Fig. 3 when e = 1, the test accuracy is around 92%, however, on the left panel of Fig. 3 the performance drops to 80% for E 1. This is due to the smaller training set size (240K on the right vs 20K on the left).
We also train a neural net on the EMNIST bymerge dataset consisting of 760K images of handwritten digits and uppercase and lowercase letters, with 47 classes, We conduct this experiment to investigate the effects of large label domain sizes, i.e., large k. Fig. shows test accuracy as a function of the number of labels. For each run, we randomly chose out of 47 classes, and applied our method with g = The figure shows that, as expected, the performance degrades significantly as increases, but the method is still viable with k = 45. Note that in this experiment, the size of the dataset, and thus the join size, changes as we change k.
Our results are consistent with the dependence of Thm. D.2 on the parameters E, b, and ø |DRl/DDR R xa Dsl: test accuracy improves as ε or b increase, |R DR Da Ds| or l decrease. Training details can be found in Appendix G
7.2 Comparison with other methods
To our knowledge, there is no past work on non-interactive private joins in the repository setting. However, can replace our simplified private count sketch (Definition 3.5) with other private sketches. To this end, we incorporate Zhao et al's [39] private linear sketches into our method. Party S generates a sketch of (id, value) pairs as before, but builds the sketch using Algorithms I and 3 from Zhao et al. instead of our Definition 3.5) Then, line 2 of Algorithm 3 is replaced with LinearSketchQuery from Zhao et al.s' Algorithm 2: Wid.y clip Liinearrreeeeehuurryraaaa
y)).
The EMNIST experiment run with different combinations of Zhao et al.'s parameters 7, B. p. Their protocol satisfies p-zCDP; we use Proposition 1,4 of (8) to compare our results by equating p = Je².. The number of hash buckets is related to 7 as b = 1/7 and the number of hash functions (one for us) is given by log (2)3).

---

EMNISTT AiCDe
0.900
0.875
Test accuracy
0.850
3.825
0.800
0.775
0.750
0.725
10
15
40
45
The size of label domain k
Figure 4: Test accuracy as the domain size of the labels, k, increases.
EMNIST test accuracy. Ours vs. Zhac ct al.
EMNIST
Label [DshsDy] 240K
1.0
0.9359
Test accuracy
(Led)
Dem
0.5
0.6
[1-0 A.1:
0.7
0.5
(i--5 2011
1,25/0.5.0.77 75 quantile Ours, d' 30-jDeMtss]
0.4
[1e68.33 AX
Oct, 2.44
Labe-DP
10
10F epsilon
10"1
epsilon
Figure 5: Comparisons with other baselines. The definition of neighboring datasets is different for
LabelDP and ours: 2ouurs R Esboirs roughly. We have taken this into account in the right panel.
Zhao al. describe two sketch implementations, Count-Min and CountSketch. Count-Min sketch is random classifier on EMNIST for S 10, possibly because Count-Min is designed to avoid more important to be correct on average. CountSketch leads to better results, Fig. S For 5 = 0.3, there is one hash function, as with our method, and the remaining differences between the two methods is the kind of added noise (Gaussian vs two-sided geometric), and that LinearSketchQuery omits the denominator N(hhid, y)) on Line 2 Our method provides better results, especially for smaller
underestimating frequencies, whereas in our case
of our Algorithm 3
The accuracy of the model is roughly proportional to the number of correct vs. incorrect labels reconstructed in the join. For the corresponding values of and (p. 8, in the two methods, the number of incorrect labels reconstructed is fewer for the two sided geometric noise than Gaussian. Gaussian noise has thinner tails which is helpful for reducing the probability of large error values but not helpful in our application where queries are in any case clipped to the range [-1,
We also compare with LabelDP 21, which is Local DP protocol that protects the labels. LabelDP is not designed to perform joins, and so we run it without splitting the training set. Results are shown in the right panel of Fig. The definition of "neighbouring datasets" differs in the settings: we use the "add/remove" definiton where a single row is added or removed, but in LabelDP's definition, single value is changed. To account for this, we double the privacy budget for LabelDP, so for example at ε = 1 on the r-axis, we actually give LabelDP a privacy budget of = 2.
The LabelDP method benefits from not needing perform join, and expect it to perform better than our method, where the parties must join using a non-interactive protocol. We were surprised to
method perform better for small and do not understand why this happens.
Future Work. This work focused on when the sender has a single private label column. To broaden applicability, data with multiple columns and data of different types, such as real-valued or text, deserve consideration. New privacy challenges arise the streaming setting where organizations continuously receive new data and discard outdated data.
10

---

Acknowledgments
We would like thank Joan Feigenbaum, Bill Horne, Yonatan Naamad, Aaron Roth, Doug Terry, Tal Wagner, and the anonymous reviewers for helpful feedback, comments and suggestions that improved this paper.
References
[1] Adult. Adult. UCI Machine Learning Repository, 1996.
[2] Alda and B. Rubinstein. The bernstein mechanism: Function release under differential privacy. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
[3] N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1):137-147, 1999.
[4] N. Alon, P. B. Gibbons, Y. Matias, and M. Szegedy. Tracking join and self-join sizes in limited storage. Journal of Computer and System Sciences, 64(3):719-747, 2002.
[5] M. Anthony and L. Bartlett. Neural network learning: Theoretical foundations. cambridge university press, 1999.
[6] R. Bassily, K. Nissim, U. Stemmer, and A. Thakurta. Practical locally private heavy hitters. Mach. Learn. Res., 21:16-1, 2020.
[7] Blocki, A. Blum, A. Datta, and O. Sheffet. The johnson-lindensrraus transform itself preserves differential privacy. In 2012 IEEE 53rd Annual Symposium Foundations of Computer Science, pages 410-419. IEEE, 2012.
[8] M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. M. Hirt and A. Smith, editors, Theory of Cryptography, pages 635-658, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg. ISBN 178-3-662-53641
[9] M. Byali, H. Chaudhari, A. Patra, and A. Suresh. Flash: Fast and robust framework for privacy-preserving machine learning. Cryptology ePrint Archive, Paper 2019/1365, 2019, URL https://eprint. iacr. org/2019/1365 https://eprti iacr org 0rg/2019/136
[10] M. Charikar, K. Chen, and M. Farach-Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pages 693-703. Springer, 2002.
[11] H. Chaudhari, A. Choudhury, A. Patra, and A. Suresh. Astra: High throughput 3pe over rings with application to secure prediction. In Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop, CCSW 19, page 81-92, New York, NY. USA, 2019. Association for Computing Machinery. ISBN 978 1400368261. doi: 10.11453338466.335822
URL hoLLihttp://doiii org 10. 1145/1335/63336 3358922
[12] S. G. Choi, D. Dachman-Solle M. Kulkamn, and A. Yerukhimovich. Differentialll- privatee multi-party sketching for large-scale statistics. Cryptology ePrint Archive, 2020.
[13] E. F. Codd. Further normalization of the data base relational model. Research Report / RJ IBM San Jose, California, RJ909, 1971.
[14] B. Coleman and A. Shrivastava. A one-pass private sketch for most machine learning tasks. arXiv preprint arXiv:2006.09352. 2020.
[15] B. Coleman and A. Shrivastava. A one-pass distributed and private sketch for kernel sums with applications machine learning scale. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 3252-3265. 2021.
[16] G. Cormode and S. Muthukrishnan. improved data stream summary: the count-min sketch and its applications. Journal of Algorithms,, 55(1):58-75, 2005.

---

[17] C. Dwork and K. Nissim. In M. Franklin, editor, Advances in Cryptology CRYPTO 2004, pages 528-544, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. ISBN 978-3-540-28628-
datamining on vertically partitioned databases.
[18) C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4)2211 117-442 2014, doi: 10. 10.156104400000042, URI SRR.http:://do org/10. 156100400000042
[19] Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In S. Halevi and T. Rabin, editors, Theory of Cryptography, pages 265-284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-32732-5.
[20] M. J. Freedman, K. Nissim, and B. Pinkas. Efficient private matching and set intersection. In International conference the theory and applications of cryptographic techniques, pages 1-19. Springer, 2004.
[21] B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, and C. Zhang. Deep learning with label differential privacy, 2021.
[22] A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility-maximizing privacy mechanisms. CoRR, abs/0811.2844 2008. URL http:://rrxii.. http://////abbbb/b//ee/e hat///aaa0011..../1 28411
[23] O. Goldreich. Foundations of cryptography: volume 2, basic applications. Cambridge university press, 2009.
[24] R. Hall, A. Rinaldo, and L. Wasserman. Differential privacy for functions and functional data. The Journal of Machine Learning Research, 14(1):703-727, 2013.
(25] P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604 613, 1998.
[26] L. Kissner and D. Song. Conference, pages 241-257. Springer, 2005.
set operations. In Annual International Cryptology
[27] P. Mohassel and Y. Zhang. Secureml: A system for scalable privacy-preserve machine learning. In 2017 IEEE Symposium Security and Privacy (SP), pages 19-38, 2017. doi: 10.1109/PP.011.12.
[28] A. Patra and A. Suresh. Blaze: Blazing fast privacy- machine learning. Cryptology ePrint Archive, Paper 2020/042, 2020. URL //tpppt:///ppitttt... iacr. org/2020/042 https
//eprint... iacr. . www.orgg/0002/ 2020/042
[29] N. Ponomareva, H. Hazimeh, A. Kurakin, Z. Xu, C. Denison, H. B. McMahan, S. Vassilvitskii, S. Chien, and A. G. Thakurta. How DP-fy ML: A practical guide machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113- 1201, jul 2023. doi: 10. 10.1613/jair 14649. URL httph: /ettps://ao..ooo org 10. 1613% 14649
[30] J. Vaidya and C. Clifton. Privacy preserving association rule mining in vertically partitioned data. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 339-644,222 2002.
[31] Vaidya and C. Clifton. Privacy preseevin k-means clustering over vertically partitioned data. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 206-215, 2003.
[32] J. Vaidya and C. Clifton. Secure set intersection cardinality with application to association rule mining. Journal of Computer Security, 13(4):593-62) 622, 2005.
[33] J. Vaidya, C. Clifton, M. Kantarcioglu, and A. S. Patterson. Privacy-preserving decision trees over vertically partitioned data. ACM Transactions on Knowledge Discovery from Data (TKDD), 2(3):1-27, 2008.
12

---

[34] S. Wagh, D. Gupta, and N. Chandran. Securenn: 3-party secure computation for neural network training. Proceedings on Privacy Enhancing Technologies, 2019:26 49, 2019. URL https://api semanticscholas
httg/CCrpusID:::00 780900069
[35] S. Wagh, S. Tople, F. Benhamouda, E. Kushilevitz, P. Mittal, and T. Rabin. Falcon: Honest- majority maliciously secure framework for private deep learning. Proceedings on Privacy Enhancing Technologies, 2021(1):188220) 208, Nov 2020. ISSN 2299-0988 doi: 10.2478/
popets-2021 2021-0011. URL http: /dx doi org/ 10. 2478/popets 2021-0011
[36] D. Xu, S. Yuan, and X. Wu. Achieving differential privacy in vertically partitioned multiparty learning. In 2021 IEEE International Conference on Big Data (Big Data), pages 5474-5483. IEEE, 2021.
[37] A. C.-C. Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfes 1986), pages 162-167. IEEE, 1986.
[38] Q. Ye, H. Hu, X. Meng, and Zheng. Privkv: Key-value data collection with local differential privacy. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pages 317-331, IEEE, 2019. doi: 10. 10.11000/22009.00001 URL
nttps://doi org/10. 1109/SP 2019. 00008
[39] F. Zhao, D. Qiao, R. Redberg, D. Agrawal, A. E. Abbadi, and Y.-X. Wang. Differentially private linear sketches: Efficient implementations and applications. Neurips, 2022.
13

---

Appendices
A Illustration of Algorithm I
Figure provides a visual depiction of the private count sketch that the sender uploads to the public repository. The noise values Ze are sampled from TGoom( (Def. 3.3). For example, if choose & = (which gives a "strong" privacy guarantee $5.2.1]), then the variance of each Z, is about 1.84.
Private Count Sketch
Sender S's Data
Hash
Noise
Name
Cancer?
0
Ze
h(Bob,+1]
Alice
-1
2
s(Bob,+1)
Ze
Bob
+1
h(Alice, -1)
0
Ze
Carol
h(Carol,-1)
0
+
Ze
Ed
+1
s(Alice,-1)
Zz
h(Ed,+1)
s(Carol,-1)
s(Ed,+1)
Ze
Count Sketch Hash Functions:
(Private Count
Public Repository
h: (Name, Cancer?) > [1,..,b]
Sketch, h, s)
s: (Name, Cancer?) - {-1,+1}
Figure Visual depiction of Algorithm
B Some Useful Definitions and Theorems
B.1 More on the two-sided geometric distribution
We repeat the definition for convenience:
Definition 3.3. The two-sided geometric distribution with parameter a, denoted TGcom is distribution over with probability mass function Pr[Z 2|
1-e !=
1+a
TGeom(a) is the same distribution as the difference between two independent geometric random variables, Geom(p and it provides a convenient way to sample from the distribution when using a library that provides the geometric distribution. From this immediately follows that the expectation and variance of TGeom(a) are given by:
a). This fact can verified directly from the probability mass functions,
Lemma B.1. For Z ~ TGeom (a). E 0 and Var[Z]
2a
(1-a)2-
B.2 Mutually independent hash families
Definition B.2. distribution over pairs of hash functions
(1..b), 8: - 1-1,1]
mutually k-way independent hash family iff for any fixed distinct inputs ø1, ... Ty and outputs yI..... l/2 E {1..b and 21...., 2k E E(-11 [1,,1}.
Pr[vi E (1..k) l((x:) = yı A s(xx) = zd]
2h
In other words, the outputs {1.b)* x 1
s(xx), s((x) are distributed uniformly
14

---

B.3 McDiarmid's Inequality
Theorem B.3 (McDiarmid's Inequality). Let f : 21 Nn + R have the property that for every index E {1.m²} and every pair of sequences Σ, 1 E 21 x ... x Xn that differ only in the i-th coordinate, (Ø) f(7)) I C₁. Then if X1 Ny..... Xn Nn are independent random variables,
then for any 2 0,
2/²²
Pr(I Xn) E[S(X, X.)1 ml 2xxp
Σi=1
B.4 Measuring the complexity of a function class
When analyzing an optimization algorithm, it is useful to have a measure of the complexity of a class of functions. One such measure is the uniform covering number.
Definition B.4 (Covering number in R [5]). An foo p-cover of set S S R" is a set C' S S such that Vo E S 3e E | c/so < μ.. The &o ju-covering number of S, denoted N(u, S, (oo), the cardinality of the smallest such C.
Definition B.5 (Uniform covering number of a function class [5). Given a function f X - R and sequence / (Zi...., Zn) E X", the restriction of to 전 is
flz (f(ma)...., f(.)) R
The restriction of a class of functions F is the set of restrictions of the functions in it:
Flz = (fla : F)
The uniform covering number Nox (M, F,n) is the largest covering number of any restriction Fl to length-n sequence:
(H, max N Fo,, ZEX
The Vapnik- Chervonenkis dimension or VC-dimension is another measure of complexity that applies boolean-valued functions. In the case of boolcan-valued functions, the uniform covering number called the growth function:
X - (0, 1). The growth function of F is function F N N defined by =T(mm)= No ( F, F, m).
Definition B.6 (Growth function (5). Let F. be a class of functions / x
( could be replaced by any number less than 1.) Note that [I>(m) s 2m since there are only 2 possible restrictions flz for length-n sequence F.
Definition B.7 (VC Dimension [5)) Let JF be class of functions f X + 10.1}. The VC dimension of F, denoted VCdim (F), is the largest d such that [d) = 2d.
The VC dimension summarizes the behaviour of the growth function in a way captured by the following lemma:
Lemma B.8 (Theorem 3.7 (l). Let F be a class of boolean-valued functions with VC dimension d. Then for any 2 [1 md + +.
We will make use of a simple connection between the complexity of a collection of classifiers / and of the corresponding set of error functions ey:
Lemma B.9. Let F be class of functions f X + 10,1). For F define e, X {0, + (0, 1) by e (z. 3) = (x) - y). and let G = {eg f F). Then
VCdim(g) VCdim(F)
Proof. Let dg = VCllim(G) and dy = VCdim(F).
First we'll show dg 2 VC). Unpacking the definitions of VC dimension and growth function. see there is क = (I1,.... (dy) dd such that Fl includes every of the 2d sequences in (0, 1345. Let =- ((x1, ......, (Iay, 0)). Observe that for any f E F, Sl. eyl= E {0, 1) Therefore Ge includes all 2dz sequences, and so VCdim(G) 2 dy.
15

---

To show dg 2 (C)im(g), note there is some / ((21, (Ido: Bdoo )) E (X x {0, 10.1 such that G| includes every sequence in {0. 1] Let I (#),.. (dd))
X Given sequence Fla. Indeed, define the sequence s' {0. 1) &dg by s = s Vil. and let ef be function in & (corresponding to some f E F such that e s'. Then for any E (1.dd)) f(;;) = le,(2,) - y/ = | - yi 8,, and so flz = 8. We were able to do this for an arbitrary 8, so Fz includes all 2 sequences, so VCdim((F 2 dg.
s (0. _ we would like to show
C Linear Queries: Proof of Theorem 5.1
We prove Thm. 5.1 repeated here for convenience:
Theorem 5.1. For any datasets DR C D, X funncttton
function f: X {1..K R. privacy parameter & > O, number of hash buckets b, and accuracy parameter > 0, if and are drawn from mutually 4-way independent hash family, the following holds. Let M an upper bound on (f,,, k be the range of the value column of Ds. n DR DA Dsl, C PrivCountSketchn....ee (Ds). Then
(k
2
Dsl 62
Pr
+
12
(1-e-sj²
The probability is taken h, and the noise added PrivCounSShecch.sccl
The proof follows by applying Chebyshev's s inequality to the following lemma: Lemma C.1. If h and are drawn from mutually 4-way independent hash family (Definition B.2 then
E|QTO| SumOverJoinn De
and
Var Var(Q" ( -1)
(1) 2e (e---a +
Dss b
where l is the number of possible values allowed in S's value column, |f supa.y (æ, v). C' PrivCoumtSSetcha.. h.ss (Ds). and the randomness is over the choice of and and the noise from TGeom(e that was added C.
Proof. We write C = Z + EnanneD C(id, y) where C(id, v) is vector with s(id, y) at co- ordinate h(id, y) and everywhere else, and Z is a vector of independent TGeom(e-5) random variables.
For every id, x. y, we have
q(id, x. T C(id,y) f(x,y)
(1)
On the other hand. if (id, y') * (id', y) then E[g(id, x, zz,') T(id'', .)) = 0. This follows from the facts that is independent of and that two-way independent and so E[s(id, y s')s(i'', aadd''' y)] Finally, Elg(id, x, y) Z] is zero, since Z is independent of Q and has expectation zero. So:
Σ (.d. )
E EQQ c EE
Σ
Z
Σ (id',))ED)
C(id'
(i ===1
Σ
Elg(id, x, C v)]
(id,)) DR o'=
(id' Ds
Σ
f(x v)
(id.o.y)
SumOverJoin D3 (f)
Moving on the variance, we have
VarlQ TC] = =E((Q C Su (f))
= =E((A + B SumOvarJoinp...s (
16

---

where = E(Ia,)ED Eg= g(id, x, Z and
B= Σ
Σ
Σ
g(id,z, C''d'''
D y =1=1 (id' y
Using 1 can write
B SSmmOverJoinn (f)
Σ
Σ
Σ
((id, v') # vlladd,, x, 8') C(id', C'idd,
(10,)) Da =1=1 (id' x)EDs
Σ
Σ
Σ
(id, =' ()dss
[id, y/) + (id', vy)l((iddd h(id', s(id, ssidd'''s'''''//l (z,
(2)
where [(id, y/) * (id', y)] denotes a function which is whenever id id' and y' = y and otherwise, and similarly [h(id, s/) = h(id', y)1 is I when the hashes are equal. We write.
VarlQ' cJ + E SumnOerrJinnn..g (1)) E[( SumOverJoinna..s (1))
and compute each term separately.
- 2k D Σ E(,,y) (1 (1-6-8)2 (1-e-5)2
E[A*]
( 9m1
in expectation because each includes a product s(id, y)d'' vz) where (id, y) # (id', v/). The variance of the two-sided geometric distribution comes from
Note that cross terms in A2
Lemma B.
We have
2 E[[A(B SumoverJoinDa,.p... (f)) =
(4)
since (referring to each term includes a product of distinct ID-y pairs s(id, y)s(id', "'iidd,''/a ('ddd y²) which both in expectation since s 3-way independent. Finally, looking
or s(id, (id' at (2). we see
E[(B SumOver (f))==
Σ
C-D- (-D-f(zE)) f(e'.1")
(i
V'E(L.k)
(1d' D)
y" e(..k)
(ia" "')
where C' = [[id, v/) * (id', v)]l(id", v" + (id" s/'] Pr(h(id, v') h(i'', y) A h(id", y"") h(id"" y²"] and
D Eis(d,,, y s(id' siddi y² "'"""("dd"'"""" .V"']
Since is 4-way independent, D is when every pair in {(id, v'), (id', w), (id" y² (id" ,y"" appears at least twice, and otherwise. So, C. D 1/62 when either (id, y²) = (id", v²") o (id', .)) = fid",,"" (id, y/) (id" + (id', y) = (id".2/" and otherwise,
yy")
E (B - SumOverJoinp Da (f))
Σ (R
[(id, + (id', (vl.,,)
b2
V'E(1..))
(sd' EDDs
Σ
[(id, y') + (id', v)lf(z v)f(
6
(1d,z,y)e DreaDs (id' wf DeDDaDs
DD DD DD
(k) Del
(5)
17

---

Combining
3
and 5 gives:
22e
1
Var S|
+ [k] Dsl + DR D4 Dsl?)
(1 ---e2
DDs
<|fl DR R +1)
(1-e-cyz (1-
6a
where for the last inequality we use the fact that DD D4 Dsl S mmin tion identities are unique.
[Ds]} |Dss) since by assump-
D Optimization: Proof and generalization of Theorem 6.4
(Optimization)
Here we state and prove Thm. D.2 generalization of Thm. 6.4 For the proof of Thm. 6.4 itself, see
Section D.2]
Our general optimization theorem states that optimization method, Algorithm from produces close-to-optimal results under certain conditions. Specifically, we show that the estimated optimal function f. which we define in Definition 6.3 and show how to compute in $6.2 has a value close to the true optimum fopt arg min fer Sum Joinno (f). Our bound on the accuracy of given Thm, D.2 depends on a quality score (Definition D.I and the uniform covering number of the function class.
Definition D.1. The quality rating n² ((Dn, Ds, k; b, depends on pair of datasets Dn C and Ds C u x (1..k), integer b >> 0 (number of hash buckets) and a real number > 0 (privacy parameter), and defined as:
DR Ds
<(DR. Ds. b,
ko + +
where
DDRl
|Dsl
V DR Da Ds
DR Da Ds
(1
b
1
b
WR min
5k (Rl
Ws min
5,
14
V
|Ds]
Theorem D.2 (Generalization of Thm. 6.4). Fix a pair of datasets DRy Ds. parameters b (number of hash buckets) and O, bound M >>
class F of functions f X Y M, M) and an error parameter μ > 0. Let C = PrivConntkeethh.
(Ds) be the sketch sent by S, and
fopt = arg min SumOverJoinDr.DD. (f) feF
f = arg min T (D)
fEF
That is, fopt and f are the true fincttion function and the function returned by Algorithm! Then
respectively.
SunOverJoin
SumoOerllinnna..ssSooooo +
Pr
DR De Del
DR Da Dsl
(-s n²² RDDRR Ds ks,k,
S(c + 1) exp
M
where e is the uniform covering number
WWRWS
N=00
.F, DR Da Dsl Ds)
72km
and K. o, Wn, Ws are given in Definition D..
For reference, we define Nop Appendix B.4 We prove Thm. D.2 through a careful combination of tail bounds. It has similarities to classic machine learning results relating empirical loss to expected loss on an underlying distribution, but note that we instead relate two empirical values: the sum of function over true join, versus what we recover from the sketch.
18

---

D.1 Proof of Theorem D.2
Central to the proof the following bound on the error in the score of a single function:
Lemma D.3. Fix pair of datasets DR, Ds. parameters b (number of hash buckets) and >> and a bound M >> O. Then there is real number 3 = ((DR. Ds. b, 2 18 WRWW. where Wa and Ws are as in Definition D.I such that for every function f X x + I-,,
M,M,, M), the value
3 DDr.c(f) approximates SumOverJoinD.r
(f) in the following sense.
Let the hash functions h U (1..b) and :u 1-1,1} be sampled uniformly random, and
let C = PriiCCounSSketchp.... s,e (D Then for every p > 0,
|
t D()
SumOverJoin Do (x)
Pr
2
DR DA Dsl
nl (DDn,, lt Ds, k b,
<4 <xexp
720M2
We first show how to prove Thm. D.2 from Lemma D.3 and then prove Lemma D.3 in D.I.1
Proof of Thm. D.2 from Lemma D.3 The proof can be summarized as chain of two approximate
equalities and one inequality:
SumOOerJoinDa.D...f (f) 8 cf) s $ @Dn.c(fopp)
SumOver.JinDga. (fopt)
where each of the proved by Lemma D.3 and the < follows by the definition of f. Unfortunately. since ff depends on some randomness (the noise added for privacy, and the hash functions), we cannot directly prove the first through application of Lemma D.3 and first find cover of functions, and apply the Lemma to each function the cover.
Let C X be the inner join DR pa Ds excluding the id column. Let C R! be set size e which an Eoo
pWaWs cover of FlJ. 72k
For any f, f E satisfying the "closeness" condition guaranteed by the cover; that is, as long as
v(a,y) E (f(x,)) - f'(x,8)1 <
4k
true, we have
Ig (f) SumOverJoinp,..o Dy (f')
Σ
-
(td.r.y)DDooaD
RWRWSs
< Dx ba Dsl
72kó
11 DR Da Dsl
(6)
and similarly, from Definition 6.2 and the triangle inequality, together with Lemma D.8 3 z n WWW WRWs),
(which says
19 Dp.c(() - -8-1 200) 58-1
Σ
Na(h(id,y))
(1 w=1
|s(id, y) (NooC)) - (xx,))))
18
DD
W R W
72k
DR be Dsl
(7)
(For the last step, recall Φ
[Pn] [DgmDD]
19

---

Let E be the event that every function in V, as well as fopt. has its value approximated by 3-1 times its score within zt
SumoOverdoinDa.DD0)
B 2 D Du Da Dsl
F
(opl)
Dn Da Dsl
4
By combining Lemma D.3 (with 4 in the place of p) with union bound over every f E V VU {fptt
Pr[F]] S4(V + 1) exp (-1² [_ x(DR, Ds, b,
11520M2
Assume E holds and let f be function in V which is close fi that is, V(z.)) JIf(z,y) f", v)l <
Then, using 6 and 7 and the fact that by definition &D (
ake"
SumOveeJJoiDg..DCC
SumOverJoin De (
M 4
D D4 Dsl
DR x Dsl
Dff +
DR Da Dsl
+3 1
DR Dsl
8 8-1 ((ppp)
+3
DR Ds
SumOverJoinp,.Dn (Fopt) +4
D Ds
D.1.1 Proof of Lemma D.3
Restated for convenience:
Lemma D.3. Fix pair of datasets DR. Ds, parameters b (number of hash buckets) and e O, and a bound M O. Then there is real number 3 3 (n, Ds b,e), 2 T8 WnWW,, where Wn and Ws are as in Definition D.I such that for every function f X x - I- 3-1 (F) approximates SumOverJoinp.
M, M,, the value
(f) in the following sense.
Let the hash functions h + {1..b} and s : + 11 be sampled uniformly at random, and let C = PrivCountSketch h.a.e (Ds). Then for every μ > 0,
| D() SumoverJoon,, Do (f)
Pr
2
DR DA Dsl <4exp (- n²² k((RR, R. ks,
720M2
To prove Lemma D.3 we begin by describing the factor 8 in (Definition D.7 and bounding (Lemma D.8). Next, we show 4 (f. has the correct value in expectation (Lemma D.9) and finally complete the proof using combination tail bounds.
technical lemma:
Lemma D.4. For any two nondecreasing sequences 01 2 a2 2 ... 2 an and bj 2 by 2 ... bn
n
m
Σ
bab
a
Σ
b
n
Proof. First, we rewrite each side of the inequality:
1
a.b.
(a,b; + azb;))
2n
=1j==
20

---

and
Σ
Σ
b;
(arb, + tazb;)
2n
== ;=1
suffices to show that each term in the first sum is greater than or equal to the corresponding term in the second sum. To see this, note that
(a,b; + (gbb)) (a:by + aadi) = (a: a;)(b:: - -,,
and d2 aj and b; - by are either both nonnegative or both nonpositive, depending on whether i j.
O
Lemma D.S. Let X = ++ 2im S; where Z.S,...., are independent random variables, and
Z ~ TGeom(e ( for some & > 0 and each S; is drawn from the uniform distribution on {-1,
Then
E[c] =0
and
3 6[ /nl +6 }
E[clip(X + +1] min
Proof. The distribution of X is symmetric around 0: Pr|X = æ] = Pr[X = -x] for any æ. Thus,
Pr[X < 1] = Pr[X 2 1). so E[clip(XX] Pr[X 2 1| Pr(X - 1| 0.
remains to bound E[clip(2 X + 1)). which equals Pr[X 2 0] - Pr[X v 2]. Once again using the symmetry of X, we Pr[ X < 2 Pr[X 2 2). and so
( 1)] Pr[X > 0j Pr[X > 2| Pr[X E [0,
To avoid some repetition, let T = Σ S,. Since T has the same parity as n, we'll pay some attention to parities in what follows. Let = 2k where E {0, } is n's parity. Then
Pr[X E [0,1]]
Σ Pr 22 + PriZ 22 - 10,1H
Pr[T = == +r| +r| PrIz - 2z - E {0, {0,1])
where zu will be chosen later. For integer let a. = Pr(T 22 + r] and b. Pr|Z 22 s)
E(clip(X 1)] Pr {0.1
Σ a.b.
Consider the sequence 2 = 0, -1, 22,2, -3, 3, ... that is and then -i, i for each positive integer Both (a.) and (b.) nondecreasing with respect this order:
4n 2 a_1 > 01 2 a_ 0g 2...
and
bo b- bi 2-
This nondecreasing property of (a.) follows because (T + nn2/2 is binomial random variable with mean n/2, and so its probability mass falls away monotonically from the mode(s) at (T + n)/2 [n/2]. nn/2], ) that is, T = rrr. The nondecreasing property for (b.) follows from the fact that the probability mass of Z falls away monotonically from the mode Z = 0.
Using the above order, we may apply Lemma
D.4 to the sequences (az), (bz), to get:
20
E(clip(X + 1)]
Σ
azb=
Zo
2o
a₂
bz
220 + r +
50
1
AB
2%0 + r +
21

---

where A = Pr(T E -2, trll, = PrIz E 1- - r; 220 + + +1]. From the probability
mass function of TGeomme-5) we directly compute B 1 - (2z We apply Hoeffding's inequality to see
(2z0 + r)2
A > 1 2exp
Taking 2g = [vn gives A > - 2 and B
v + 11 + E, then
B 2 - so we have
2c 3) c
1
E + +1] 2 vn + + 1
n +6
Otherwise (2 +r+1 < 8) we use the fact that for < 6 < where C = v + < and so
1+x+ z
to get B Ce - 0
Ejcli +1) > (1 2e 20 -C= 2²
1
C
=(1 2e- -ex=2) )1 CEEE
>/E
Lemma D.6. If X is a binomially- distriibuedd random variable X ~ Binom(n. p) then
Pr[X 2 max 1}] <
Proof. Let P P 2 max(5np, 1}] = (P 5mp]. Pr[X 2 1]}.
np 3. then using Markov's inequality,
P P 2 1] S E np <
Otherwise (np 2 }), we apply the Chernoff bound in the following form:
E[X]
Pr[x > (1 E[X] <
(1+5)1+3
taking 8 = 4 to get
E up
P Pr(X 5mp] <
56
3
Definition D.7. Given datasets DR, Ds and parameters b, 8, we define
E E(Ppg.c(1))
3(D Ds. b, SumoverrJoimpg.Dee
where is the constant function 1(x, v) 1, and the expectation is taken over the random choice hash functions h, s and the noise from TGeom(e-5) that party S added to C. (Note that SumO SumoOverJoiipp.p Dn, (1) DR > Dsl.)
Lemma D.8. ((DR Ds, e) 2 1 WnWs where Wn and Ws in Defimition D.I
Proof. For any id E l and i E (1..k), define
1
T(DR, C, = Na(h(id, i)) s(id, i) clip(C) ())(a))))
So that
E E( Dn Da Dg
B(Dn, Ds, b,
Σ
Σ
(D,,,
DR pa Dsl
(1d,)) #=1
22

---

It suffices to show that for every (id,x) E DR and i {1..k), if (id, u.) Ds. then
1 WRW's
B(r(DR,C,id,)] 2 18
(8)
and otherwise EDT(DR. C,i, 0.
Suppose (id. 34) & Ds. Then s(id, i) is independent of C and (a(hiid, i)). and the probability
distribution n,, C, id, i) is symmetric about 0, so (D,(DR, C, id, i)] = 0 as required.
Now suppose (id, y:) E Ds. Let Nn (n,h(id,, i)) and define Ns to be the number of rows (id', yyy ".d",yr) E Ds such that h(id", 11) h). Note NR 2 because (id, x) E DR. and Ng 2 because(id, y:) Ds. Then
Del Ds
C,i,
Σ Σ
Pr[NR = nR A Ns =
m==Ing=l
where
Enn,s E[T C,id, = ARANS ns]
Conditioned particular value Ns ng 2 1, siiddd,)CCiiieee i)Cn(aa.) is distributed
1 1 Z + Σ Sj
where Z ~ (G is the noise party S added to for privacy, and , are independent uniform samples from f-1,1), each having the value issdd' i') for some other (id',i') E Ds for which h(id', i') = h(id, i). So, by Lemma D.5
min fE 3 6 V[s -1| +6
1
Enans
In particular, Engin 2 0, so in our effort to lower bound E[T(DR, id, we are free to focus our attention on a subset of the terms:
[B
Bs Σ
E[T(DR,
Σ
Pr[NR = nR A No = nis Em
RR ng=1
2 Pr[NR S BR N & Ba]imin
where we choose
DR
BR min DRR, + max
1
[5|Dsl .11
Bs = min [Dsl. max
b
and Emin the minimum value Eng.ns over all ng S BRg ng S Bs.
Recall that to complete our proof it suffices to prove (8) For this, it suffices to show that
Pr[Nn S BR N Bs) 2 3
(10)
and
Emiin
WnWs
(11)
6
10 follows from Lemma D.6 since NR
Binom(n = &D 1,p = +) and Ns - 1
Binom(n n = |Ds 1,p
It remains prove
23

---

From 9
we have
1
Emin
min
BRl
3 6 [s.
1
6
By considering the cases
Sk Dal < 1 separately it can be seen that [n]
>
b
min( 2 ToE|Dal
WR. It remains only to be shown that
1
min
Ws
Bs
+
We consider two cases. Di
1, then Bg and
E
1
1
min
min
3'
6
Bs
+ 6
3'
12
Otherwise (5iDal
have Bg +
8|Da
2. and so
1
min
min
3 6 /
Bs
11 +
3
5
Ds
6
6
1
min
3
18
5
1
b
min
3' 42
DDsl
In both cases, find
8 min
8
2 min
Ws
3' Bs]
- 1 +6
12 3' 42
Ds
3
as required.
Lemma D.9. For any datasets DR, Ds and parameters b, s, for uniformly random functions u + {1..b} and U + 111,1,,
E E[ 3(DR, Ds, b,,,, SunOOeeroinngg.
where PrivCouutShedlchaaa..c.
Proof.
E(DDac(f]]=
= Σ
Σ f(a,)))
Nn(h(id, i)) s(id, clip(C)mnia..)
(1
Σ
Σ f(x, E C.id,
(2d,))EDn
with 7 defined in the proof of Lemma D.8 As observed in that proof, when (id, vi) & Ds we
have E C, id, 0, and so,
Di
f(a, w) (,idd,
(12)
(1d. D
By the definition of B,
Σ
E C,id, = 3(DR. Ds.b.)) Da Dg
(13)
24

---

Now, observe that T(DR, C, id, 1) has exactly the same distribution for every (id, 2. v. E DR b Ds: it is distributed as 1 (1 + Z EE= St) deseribed in the proof of Lemma D.8 where the NR
random variables NR and Nş are counts of hash collisions with (id, i). So, [ C. id, i)] has the same value for any (id, z, Vi) E DR b< Ds. From 13 we see that value is exactly
3(Dn. Ds. E),, and so from 12 we have
E (
(DD
=B(, Ds; e) SunOverJoinng,
Proof of Lemma We begin with an account of the randomness affecting & Dp,,c()), as being in three parts: hash values h(id, E {1.bb. hash values s(id, i) E {-1,1}, and the noise values Z ~ TGeom(e that were added by party S to each coordinate of the private count sketch C. We define sequence of random variables representing each of these parts.
Let id1, id,...., id U be the identities that appear in DR. Let s = Dsl - DR De Dsl (the number of identities that appear in Ds but not Dr) and let (id', Viy Viy)...... .. (id', Dr, E Ds be the entries in Ds which do not participate in the join DR ba Ds. We define the following random variables:
Haj == h(id;, ~ Uni for = 1,..., [Dal and j E (1..k};
St,j = s(id,.)) Unif((-1,1))) for I,..., Dnl and j E {1..k}:
Hi == (idd i,) Uni.((1..b)) for j = .,....
.
S = s(id), 12) ~ Unif({-1) -10 1}) for 1..... and
Z TGcom(e for E {1..b}.
We will complete the proof in two steps: first, we use Hoeffding's ' inequality to deal with the variables McDiarmid's inequality to deal with the other four kinds of random variable (H, S, H', S'). The value C', defined next, connects the two steps together.
Z₁ and then
Let A be the expected value of o cx) with respect to the random variables Ze:
A 2, ( (f)
Note that A a random variable still depending on the values Hi,j, H1,, Sy and
E[A] = E(PDx.((f)
We have
B c JamO.erJoimpa.De(1) 2 1
Pr
[Dn ba Ds
Pr[ (f) Summ $SummOverJoipa.... (f) Dpl Da Dsll
< SPIl
A
8u DrcaDsl
+ - - (f)
8je DuoaDo
We'll begin with (+). The probability is taken over the choice of h, and Z, but will look the worst-case hash functions h and 8:
< max Pr[| + cl) A
DnlDn h ho, = su]
Ng.80
For fixed functions ho, So. we can write
b Σ
DR.
Xa
a=1
25

---

where X, 0 when Na(a) = 0 and otherwise
clip(C)a
Xa = Na(a)
E (1
[i((id)) = a)s(id, (x,
Here, [)iid, i) - a) is the indicator with value 1 if h(id, i) and 0 otherwise. X. is bounded between - and M, since (R(a) equals the number terms in the sum for which [h(id, i) = al Therefore, changing the value of one variable Za while leaving the others the same changes the corresponding X by at most 2M. Now, &Dn.c(f) depends on at most k Dal random variables Za, namely the for which at least pair (id, hashes to for some id E Dn- We apply Hoeffding's inequality to get.
8 DR P Dsl"
(*) S 2exp
8k DR M
To bound (#) we use McDiarmid's inequality (Thm. B.3 We will view as being a function the random variables (H (St (H)), (S)), described above and call this function r:
r((H,))ess (St,) k.,, (H)),, (5)). : A E, 2. DD.
Changing the value one hash value Hi,; or H: affects at most two of the variables Xa and so changes (#) by at most 4M. Changing the value of one hash value S.j or Sy affects at most of the variables Na, and so changes (#) by at most 2M.. Summing up the squares of these difference have:
values, we get (42 ( M) 20M applying Thm. B.3
1 DR DU Dsl
(#) S 2 exp
40(k|DRl s)M2
Combining these bounds with Lemma D.8 we have
B2 DE D&l
(+) + (#) <4exp
40(k)Dal + 8) M2
WRW 1 DO Dsl 720(k0 + b2
<xexp
required.
D.2 Proof of Theorem 6.4
We prove Thm. 6.4 repeated here for convenience. Recall that F is a set of classifiers, and for function f E F.f:X. + f0, 1}. we define the corresponding error function e v) = [f(x) yl:
for the full context, see $6..
Theorem 6.4. For any datasets DR Cux Ds xu (1..k), function class F, privacy parameter & > O, number of hash buckets b and accuracy parameter μ >> 0, if h and are drawn uniformly at random from the set of al alnnctiioons U x {1.kk} > {1..b), the following holds. Let fopt be the classifier that minimizes L,, and let be the classifier corresponding the function ej output by Algorithm
3
Let be the VC dimension of F, n = DR ba Dsl. and
Drl
Dsl
WR min {
b D
2b
Ws min
{ 4
n
n
5k DRl
14
Then
To
To T.
< exp (-2
WRWS + p²n log
Pr
We prove the theorem by combining Thm. D.2 with standard result relating covering number to VC
dimension (Lemma B.8). as well Lemma B.9 to relate the VC dimension F that of the class g of error functions ey-
In practice, cryptographically secure hash functions should give the guarantees.
26

---

Proof.
Taking M = 1, Thm. D.2 (applied using the function class g = {ez 1 f says:
SumOverJoinpn..D. Ds (eg)
Pr
< 1x=+1)xxpp-(((pp <DRR Ds. k, b,)) Where is the uniform covering number
HWRWs 9.
Noc
72kg
For any f E F, we have Dww...o.ooinnnseee...... = L. so we can rewrite that as:
Lj
Sopt
Pr
> 11 s (c (xx+))x R(DR, Ds, ki (,k,),,)))))))
All that remains is to bound the uniform covering number Note that the range of functions in G is {0, 11, and the Loo distance between points in {0, 1) is always 1. An examination of Definitions
B B.4 and then shows:
If
pWaWe 72kg
2 then S
If Ws 72kg
< 1 then for any 7 E (X x 10, we have NY WW&Ws 72k6
J, (x)) = 1g7l. and
((x.)(xx(0.1)) 1gyl (n)...
So:
(n)
Apply Lemma B.8
<n VCdim(g) +
Apply Lemma B.9 (recall d = VCdim(F)
=n +1
So:
Lbp Lsp 14 S(n + 2) exp(-S2(1² <(Dn. Ds. k. b,e)))
Pr
exp(-S(pp (efp:(DDR... Ds, b, dlogn))
D.3 Proof of Corollary 6.5
We prove Cor. 6.5 repeated here for convenience:
Corollary 6.5. Assume DR and Ds have the same set of identities, so the join "perfect" in the sense that DRl = Dsl DR ba Dsl. Let DR ba Ds and let d be the VC dimension F. Assume also that b Q(n). Let fopt be the classifier that minimizes Ly, and let f be the classifier corresponding to the function e output by Algorithm
3 Then for any > 0.
Dio
Pr
10
< <exp(-Q((''ne - log
n
Proof. By Thm. 6.4 it suffices show
WRWS 2(e)
(14)
① + +b
Where WR, n, Ws, d, are given in the theorem statement. Indeed, since by assumption [Da] [Ds] = we have
ò == = =
and since by assumption = [(()) = (((D))) = 12((Ds)) we have
Wn ((1)) Ws ((s)
and 14 follows.
27

---

E Training a binary classifier with a difference sketch
If R wishes to train a binary classification model to predict labels in {-1, that appear in Ds. the approach described in this section might give better results than the one described in 66. The reconstructed dataset it produces does not have weights, so will work with a broader class of optimization algorithms. Also, the lack of negative weights avoids problem with unbounded loss functions: since the approach in $6.2 can produce a dataset with negative weights, if the loss function is not bounded above, then the training loss may not be bounded below, causing the optimization algorithm to diverge.
Instead of the usual private count sketch, S will send a difference sketch C a, (Ds) defined as follows to R, along with the parameters b, S,E.
Definition E.I. The difference sketch DS (Ds) Zz is only defined when Y = {-1,1}
(so k = 2). It equals PrivCoundSkelchh.p.co (ids - ids (a)s), where ids( y) the collection of identities associated with y in Ds. As usual, the four parameters b, h, e should be published along with DS (Ds).
Based on this and DR. party builds a dataset D D(b, h, 8, DR. C)) which similar to the one described in 66.2 but does not have weights:
Definition E.2. To construct D = D(b, h,s, s, DR. C). for each element (id, x) E DR. R checks whether s ((sa) positive, negative, or zero. If it is positive or negative, R adds the element (a, 1) (x, (1) D, respectively, and if it is zero, does not add anything to D (we say (id, 2) is dropped).
One justification for using the difference sketch is that as b - oo (so there are no hash collisions) and oo (so no noise is added for privacy), D(b, h, DR, C*) approaches the true join DR pa Dg (but without an id column). Besides avoiding negative weights, an advantage of using a difference sketch instead of ordinary private count sketch is that each time R processes only one noise sample perturbs the result (the noise that was added to Ch(iaa), whereas with an ordinary private count sketch, two noise samples would affect the answer (the noise values added to Ci(Ia.1) and C1
element (id, z) DR.
In our experiments, we found the approach from 662 sufficcien We leave the application of difference sketches to future work.
F Experiments with linear queries
We consider the question of how accurately we can estimate a joint distribution using linear queries. Suppose R has a categorical feature race that takes values such white, asian-pac islander and etc., and S has label income <50K or >50K. In [a, we show the true counts of the actual number of people who fall into the combination of race and income, e.g., the fraction of asian pacific islanders who make less than 50K. We use the training set of 32,562 rows of the UCI Adult dataset in this experiment.
Below the true counts in the table are counts estimated by noisy sketches. The estimated count for the above example can be obtained by linear query for which fz. y) for y 0 and asian pac islander. Recall that E { {1..k). and for this example k = with y = 0 and y = 1 corresponding to <50K >5K respectively.
For this experiment, we set a = 1 and the sketch dimension set to 500K. In the event a linear query produces negative answer or O, we change it I to avoid negative fractions. In order to compute the error of the distribution, we compute the average of the absolute difference between the true fraction who make less than 50K for each value of æ and the estimated fraction. Note that a linear query that involves a smaller number of people is more likely to misestimated, e.g., American Indian/Eskimo. Conversely, linear queries that involve larger number of people are better estimated. We expect this outcome. Even if one party held all of the data, i.e., no joins, but we wanted a differentially private answer the TGeom(e =) noise drowns out the signal for a small number of people.
Next, we fix the sketch dimension to 500K and vary the differential privacy parameter e in the top panel of Fig. 7 Note how the error drops with increasing as expected. We also repeat this
28

---

S.come
R: White
R: Asian-Pac
R: Ande-Indiin
R: Other
R: Black
Islander
Eskimo
True counts
S 50K
20699
763
275
246
2737
>50K
7117
276
36
25
387
True fraction < 50K
0.74
0.73
0.88
0.91
0.88
Estimated counts
S 50K
20307.0
774.0
307.0
201.0
2787.0
>50K
7308.0
297.0
36.0
22.0
478.0
Estimated fraction < 50K
0.74
0.72
0.90
0.90
0.85
Estimating the joint distribution when R holds a feature "race" and S holds income >50K. publishes noisy sketch of their data and R downloads the noisy sketch along with the parameters k, b, E. R's goal is to estimate the joint distribution, e.g., what fraction of the Asian Asian-pacific islander population makes less than 50K. The true counts and fraction shown in the top half of the table. The estimated counts are shown in the bottom half. The average error across all feature categories is 0.01. In this table, e 1 and the sketch dimension is 500K.
Table I:
experiment for other categorical variables such as sex, education, marital-status and etc. Note the feature with the highest average error: native-country. This is because there some categories in this feature, c.g., Holland, with just few people in the dataset.
In Fig. 7b), we fix 1.0 and show the effect of the sketch dimension average error. As expected, error drops with increasing sketch dimension.
Joint Avg Erto
Aug function Dimension
0.25
workclaus education
status
0.00
eccupation
accupation
rack
0.15
rafivvee country
STIE OPeT
0.100
native country
0.075
030
005
0.00
0.00
30
10a
10" Scetch Dimension
Figure 7: (a) The average error estimating the joint distribution declines rises, (b) The average еттоr fluctuates with sketch dimension less than 10K, but above 10K is relatively flat. Note that the feature workelass has large number buckets with a few people.
G Training details
G.1 UCI Adult Dataset
R has the features race, education, etc, and S has the label income <50K or >50K. R would like to predict the label column given the feature columns. We one-hot encode the categorical columns for every feature and implement logistic regression in PyTorch with full batch gradient descent for IK epochs with a learning rate of 1 x 10 3 The dataset has 48,845 rows split into a training set of 32,562 rows and test set of 16,283 rows. S creates sketch for rows belonging to the train set; the test set is only used to evaluate the model.
G.2 Extended MNIST
EMNIST is an extension of the widely used MNIST dataset of handwritten characters. We use the 240K (40K) images of digits to train (test) our protocol. The images are 28x28 pixels with labels "0" through "9". The sender S generates private count sketch of the (id, label) pairs and the receiver R possesses the feature vectors. R would like to learn to predict labels given features.
Stochastic gradient descent plays the role of WeightedOpt, and the function f(x, v) is modelled by fully connected neural net with cross-entropy loss with input features x and output labels y. The neural net has 5 hidden layers with dropout, batch norm, residual connections and ReLU
29

---

activations for a total of 1M parameters. In the non-private setting, we train it using the Adam optimizer and learning rate of 10 4 batch size of 128 and obtain a test accuracy of 98.04%. In the presence of privacy, we conduct experiments to quantify the change in accuracy as we vary d, e and D ba Dsl- We use AdamW with a learning rate of 10 and a batch size of 2048 for 200 epochs.
For the experiment involving different in Fig. we use the EMNIST bymerge dataset of 760K images. We train ResNet of IM parameters, using AdamW with a batch size of 1024 and learning rate of 10-6 for 25 epochs. For each experiment, we randomly sample classes from total of 47 different classes, and train the model from scratch.
H Comparison to local differential privacy
The repository setting explored in this work is similar in some ways to local differential privacy, also called randomized response [9]. In the local model, individuals perturb their responses before releasing them, that their privacy is preserved even if the server gathering responses is untrusted.
Definition H.1 (Local differential privacy). Let be a positive real number. A mechanism M is e-locally differentially private it consists of applying some randomized algorithm A to each element of the input and publishing the results:
M( In) (A(x)), A(an))
and that algorithm satisfies, for any two possible private values x. x' X and any S S Range( (A):
Pr[A(x) E S] Pr[A(=') E S]
Se
For example, suppose we wish to estimate the fraction of people who have cancer, with X {-1,+1), where +1 means an individual has cancer. The algorithm could randomly flip an individual's answer with probability 1/(1 + e
A(x) = x, with probability e e((1+e)
(1+e7
-x, with probability 1/(1+e5
and, after gathering the responses, appropriate correction could be applied to the fraction of +1 responses to compensate for the flipped answers.
By contrast, in the repository model, illustrated in Fig. 1 each party holds a dataset of many individuals' responses keyed by unique and sensitive identifiers which must not be revealed. The challenge is for one party to release representation of their entire dataset which is differentially private which another party can combine with their dataset to approximate the result of joining on the private identifiers. This is an instance of function release in the curator model; the definition of "differentially private" in Section Ceotionn]repp replaces Definition H.I
H.1 Is it possible to join on individual identifiers in the local setting?
Ye et al. (38) show how (key, value) pairs can be released in the local model. However, their approach only works well with keys that appear many times, it is not a feasible way to join identifiers which appear at most once each.
A naïve way to adapt our approach to the local model is illustrated in Fig. 8 Each individual holding a pair (id,, y:) could release private count sketch c; PrivCountSketthh,.a (((id, y)}) E Z of just their own data. The sender could then publish the sum C' = Σ C; Z' of these individual (Ds). The problem with this method is that each
responses, instead of PritCountSkcctchu.uuu coordinate of C' has ns independent noise values Ze TGcom(e -5) added to it, compared to just one in the repository setting. This makes it impractical to recover any useful information from C.
Although this example shows the settings are different, there may be better ways to solve this problem the local setting. Moreover, techniques from the local differential privacy literature may be useful, when appropriately adapted to the repository setting.
30

---

Name Alice
Cancer?
Noise
Public Repository
Noise
Name
Cancer?
Noise
(sum sketches)
Noise
Ed
MAlke 11
Noise
Noise
MEG-11
Noise
s|Alica,11)
4*Noise
Noise
Noise
s(Bob,+1] 4-Noise
Nloose
Noise
4+Noise
Name
Cancer?
Noise
Noise
Name
Cancer?
s|Allce,-1]+
It+'gogly
s(Bob,+1)
s(Carol,-1)
Noise
Carol
-1
Noise
+4*Noise
Noise
b 41)
Noise
Noii
Noise
Noise
s(Crrol,11)
Noise
Noise
Noise
Noise
'Noise' is drawn from TGeom(e""1
Figure One interpretation of local DP the joinable setting is that each party individually publishes locally private sketch of their data denoted by "I" in green circle. Next the public repository receives each locally private sketch and sums them up to create one sketch, denoted with "2" In the green circle. Note that the noise in the ensuing summed sketch is now function of the number of users in the database. The centralized setting requires less noise. (There may be other ways of interpreting local DP in the joinable setting, this is only one interpretation.)
the number of users
database grows, noise drowns out the signal.
I Multi-way joins and non-unique identifiers
In this appendix, we conduct some experiments to study multi-way joins and the effects of having non-unique identifiers.
L1 Multi-way joins
In the repository setting the receiver party in principle join with many senders it wants. In 6 we studied the case where the receiver joins with the dataset of one sender. Here we study the case of two senders for the Adult UCI dataset.
As before, we simulate the join setting by adding a unique id to each row of the dataset and split its columns. The receiver has education, one sender has relationship and the other sender has income. The receiver trains logistic regression model using education and relationship as features to predict income (more less than 50K). The test accuracy for different values of is shown in blue on the right side Fig. Note that the E value is per sketch, so the total privacy cost of the three-way join (blue line) is 2s. For comparison, the red line shows test accuracy if the receiver does two-way join using only the income sketch, so their model's 's only feature education. The difference between the red and blue lines shows that for sufficiently high the receiver able to make of the three-way join.
1.2 Non-unique identifiers
We also analyse the case where the identifier is not unique. There are many practical reasons to consider such scenario. For instance if two datasets are being joined on legal name, there will be several rows that correspond to different persons but have the same legal name. Our sketch (Definition 3.5 is well-defined even if values in the id column (legal name here) are repeated. However, our Theorems 5.1 6.446.ono longer apply when identities are not unique, and is possible to construct adversarial examples where false matches steer Algorithms or iin in the wrong direction. Finding a better solution is great direction for future work.
In Fig. 10 we show the performance of our method on the EMNIST dataset. We first add a unique identity to the digits (240K examples), and create sender and receiver datasets with labels and images respectively. Then add extra rows to Dy which duplicate the identities of existing rows, but with
31

---

UCI Adult test accuracy vs. epsilon for multi-way joins
0.82
Test eccuracy
0.78
0.76
....
Non-private, Income from Education Relationship
Non from Education
0.74
Private J-way, Income from Education & Relationship
Private 2-way, Income from Education
epsilon
Figure 9: Test accuracy of logistic regression on the UCI Adult salary prediction task (.7 for three-way join. The receiver R joins his features education, with relationship and income. R then learns logistic regression model to predict income from relationship and educafion. The e value is per-sketch, so the total privacy budget for 3-way join (blue line) 2e.
EMNIST test accuracy with pseudo- srrudd--dentiffers at c=1
0.92
max
0.90
0,25/0 5/0.75 quantile
0.88
Test accuracy
0.86
0.84
0.82
0.80
0.78
7
]D:]/Number unique identitiers
Figure 10: Test accuracy on EMNIST image classification task 77.1 with non- non-unique identifiers. The z-axis refers to the number of times an identifier appears in Ds-
random labels, and apply our method with & = 1. At = no new rows are added and at x 8 each identity appears an average of 8 times in Ds. once with the true label and 7 times with random labels. We left DR unchanged. This simulates situation where "pseudo" identifiers may be repeated but are independent of the data. The test accuracy on the yyaxis shows that our method robust and gives useful results even when the randomly-labelled false matches significantly outnumber the true matches.
Note that assuming duplicate rows have random labels is strong assumption. Again consider the use case where legal name the identifier, and the receiver has the features of biomedical dataset. Different people with the same legal name might have non-trivial correlations. For instance, if particular legal name is predominant amongst males, certain biological features will be correlated amongst the duplicate rows having that legal name. Although, it is possible that this correlation might benefit our method.
Comparison with secure function evaluation
Secure function evaluation (SFE) protocols are cryptographic protocols for two parties holding values A and 2 to jointly compute function fz FB) with neither party learning anything other than
32

---

the value of the function [3 B7 23 If vA and FB are sets with f IA Z then the problem called private set intersection (PSI), and if f IΛ n 23l then it is called private ser intersection cardinality (PSI-CA). These problems can be generalized to joining datasets to answer linear queries or solve optimization problems. Unfortunately, implementations require multiple rounds of communication, and we are unaware of a protocol that would allow efficient large neural PSI is an active area of research, and we expect future developments to increase efficiency. There are some qualitative differences between method and PSI(-CA):
network training [35] [ 28 27 34].
Interaction: Our method requires no interaction. With PSI, two parties mutually agree to estimate the intersection of their inputs. With our method parties do not have to pre-agree on a joint function, and can use the same sketch to estimate joint distributions or train neural networks using stochastic gradient descent.
While the generality of our sketch implies that more functions can be estimated without interaction, this flexibility comes the cost of more noise and therefore lower accuracy than SFE, which can either give exact answers or add just enough noise to satisfy DP.
Exact vs. Approximate Answers:
Simple Implementation:
SFE protocols be quite complex implement. This paper proposes a simple implementation with two hash functions and some noise.
Data Discovery in the Wild: We are targeting a data repository of one-time sketches enabling data discovery in the wild. The proposed method lowers the barrier to private joins. Data repositories such as UCI ML repository and MIMIC (healthcare data) presently, rightly, conceal information about individuals making it challenging to join.
A sketch-based public repository enables fast and easy data discovery.
33


Reviews:
[{"review_id": "YGtQBQl4yL", "reviewer": "Reviewer_eoei", "summary": "Edit: Change from Weak Accept to Accept under the expectation that the reviewer discussions are incorporated into the manuscript.\n\nThe manuscript presumes that two independent parties hold different data related to persons in a repository. As the data is vertically partitioned across the repositories, cross-referencing both repositories by joining on some person identifier yields a richer repository that interrelates more data dimensions which can be useful for data discovery/analysis.\n\nAs sharing personal data with another party could potentially lead to a violation of user privacy, the manuscript adopts the setting where party A sends a differentially private (DP) sketch of their repository to a party B such that party B can generate an approximate/noisy join result where data dimensions coming from party A can be inaccurate. The manuscript proposes a novel DP sketch to improve the accuracy of the approximate/noisy join and compares it to differentially private linear sketches (Zhao et al @ NeurIPS'22).", "questions": "Q1) How do the methods potentially generalise to pseudoidentifiers (e.g. non-unique person names) and multi-way joins with multiple private repositories (see W1).\n\nQ2) Could a private sketch of the 2nd repository (non-private from our point of view) be helpful to guide the sketching of the private repository to improve utility when using it for join with 2nd repository? (see W2)\n\nQ3) What does the last sentence refer to when it mentions multi-dimensional sketches? (could multiple categorical dimensions not simply be merged into one unless there are multi-dimensional range queries over numerical attributes?)", "limitations": "Relevant limitations seem to be discussed.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1) Method proposed in manuscript satisfies pure DP unlike prior work on DP linear sketches that satisfies zCDP (which can only be translated to ADP regimes with delta > 0).\n\nS2) Empirical results are promising: improvement over baseline and reasonable test accuracy for epsilon <= 1.\n\nS3) Claims seem to be substantiated and key concepts are presented clearly.", "weaknesses": "W1) Many-to-many relationships (e.g., pseudo-identifiers) and multi-way join not explicitly considered. \n\nW2) Not clear why the other party could not also receive a private sketch to improve the private sketch they provide to the other party (apart from complicating the setting).\n\nW3) Minor:\n\np.9, l. 326: \"as does private multi-dimensional sketches\" => \"as do private multi-dimensional sketches\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insights. We have done two new experiments based on them, shown in Figure 1 in the attached pdf and described below.\n\n## Many-to-many relationships (W1, Q1)\n\nThe reviewer points out our work is limited to datasets with unique keys. In practice, we imagine repeated keys will be common for two reasons:\n\n1. Identities may not be unique, e.g. when joining on (first name, last name).\n2. Datasets with multiple records per person, e.g. one row for each flight a person has taken.\n\nFor case 1 (non-unique IDs) one solution is to apply our methods as described. Note that the sketch (Definitions 3.3, 3.4) is well-defined even if keys are repeated. However, this approach is theoretically unsatisfactory: Theorems 5.1 and 6.4 no longer apply when identities are not unique, and it is possible to construct adversarial examples where false matches steer Algorithms 2 or 3 in the wrong direction. Finding a better solution is a great direction for future work.\n\nThe left side of Figure 1 in the attached pdf shows the performance of our algorithm in a simulation of case 1. As in the paper, we added a unique identity to digits from the EMNIST dataset (240K examples), and created sender and receiver datasets $D_S, D_R$ with labels and images respectively. Then we added extra rows to $D_S$ which duplicated the identities of existing rows, but with random labels, and applied our method to $D_S, D_R$ with $ε=1$. At $x=1$ no new rows are added and at $x=8$ each identity appears an average of 8 times in $D_S$, once with the true label and 7 times with random labels. We left $D_R$ unchanged. This simulates a situation where pseudo-identifiers may be repeated but are independent of the data. The test accuracy on the y-axis shows that our method is robust and gives useful results even when the randomly-labelled false matches significantly outnumber the true matches.\n\nFor case 2 (multiple records per person), in order to preserve privacy, the noise added to the private count sketch would need to scale with the maximum number of records a person can have. It would be interesting to evaluate our method empirically with this change. It should be possible to adapt Theorems 5.1 and 6.4 to this setting, probably with some loss in the bound depending on the maximum number of rows per person.\n\nDepending on the problem being solved, another approach might be to pre-process datasets to combine each identity's data into a single row. For example, an individual's history of flights could be represented just by the number of flights.\n\nWe will add an appendix discussing this. A new paper (and new insights) would be needed to do the topic justice.\n\n## Multi-way joins (W1, Q1)\n\nJoins of more than two datasets are also common in practice, and we should have addressed this.\n    \nWe can adapt our method to allow multiple senders' datasets. For example, looking at Figure 1 in the paper, suppose we add a second sender with age bucketed as 0-15, 16-45, 46+. Then in addition to the \"Cancer +1\" and \"Cancer -1\" columns, the receiver could add three columns corresponding to these age buckets.\n\nWe tried this experimentally using three columns from the UCI Adult dataset. The receiver has *education*, one sender has *relationship* and the other sender has *income*, and we added identifiers so all three can be joined. We had the receiver train a logistic regression model using *education* and *relationship* as features to predict *income* (more or less than 50K). The test accuracy for different values of ε is shown in blue on the right side of Figure 1 in the attached pdf. Note that the ε value is per sketch, so the total privacy cost of the three-way join (blue line) is 2ε. For comparison, the red line shows test accuracy if the receiver does a two-way join using only the *income* sketch, so their model's only feature is *education*. The difference between the red and blue lines shows that for sufficiently high ε the receiver is able to make use of the three-way join.\n\nWe will add an appendix.\n\n## Using another private sketch to improve the sketch being sent (W2, Q2)\n\nHaving the receiver use some hints from the sender in order to improve their sketch is a great idea. The reason we did not explore this is that we are focussed exclusively on the \"non-interactive\" setting, in which the sender publishes their sketch to a repository not knowing who will download it. If interaction is allowed, then existing work on cryptographic multi-party computation comes into play, and the parties are likely to get more accurate answers by using a cryptographic protocol.\n\nIt would be interesting to explore a \"limited-interaction\" setting in which only two rounds are allowed: R sends a message to S, then S sends a message to R.\n\n## Multi-dimensional sketches (Q3)\n\nOur future work section was too terse. By \"multi-dimensional sketches\" we mean sketching datasets with more than one value column --- e.g. instead of a single label in {1..k}, the sender may wish to sketch several features.\n\nIt is true that multiple categorical columns could be merged into one: for example, a label in {1..3} and a label in {1..5} could be combined into a number in {1..15}. Note the performance of our method degrades as the number of possible labels increases, so this approach can only be taken so far."}, {"review_id": "J8mW6W57j7", "reviewer": "Reviewer_VALz", "summary": "The paper considers the problem of publishing a privacy-preserving version of a dataset consisting of an identifier and a sensitive attribute. Additionally, it should be possible to join this published dataset by the identifiers with another dataset and compute aggregate statistics on the sensitive attributes in the joined database. This is a natural application that comes up in many scenarios, and a key innovation of this paper is the non-interactive nature of the solution. The privacy-preserving database needs to be published only once and can be reused by multiple recipients.  \n\nThe approach followed is quite interesting. A dataset D \\subseteq U \\time {1... k} is processed as follows. For each entry (x,i) \\in D store the value i + noise_i in the published table's h(x) row. In case of collisions, multiple entries are added to the same row. The noise in each row makes it differentially private. \n\nIn addition to computing aggregate statistics, the paper also considers the task of performing learning tasks over the privacy-preserving dataset. \n", "questions": "- Can you please formally define the correctness and privacy properties your system satisfies? \n- For my understanding, what is the magnitude of noise you expect in Z_\\epsilon in Figure 5 of Appendix A for the case where the output of s is \\in {0,1}?", "limitations": "- The paper says that the published database has DP. Can the authors expand on what this means? Typically in DP, aggregate statistics on the database are published. However, here the entire database is published. Thus, one would expect that a much larger noise parameter will be needed. \n- The paper reports an increase in test results accuracy with lower noise. This makes sense but does not provide insight into the appropriate noise level. ", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "+ The application considered is exciting. \n+ The construction is relatively simple to understand. ", "weaknesses": "- The abstract/intro does not talk about the amount of noise needed or the level of accuracy they get. It would be helpful in better understanding the results of the paper. \n- The system does not define the correctness desired in this system. In particular, the joins in the proposed system will create false \"positive matched rows.\" Does this mean that the correctness is quantified for a random receiver dataset? In particular, a particular receiver dataset can have a lot of false positive matches. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for these insightful comments.\n\n## How much noise to add / how to choose ε\n\nThe reviewer points out we did not clearly describe how much noise should be added. Many of the points in the review relate to this topic; we'll address them in this section.\n\n### Specifying noise and accuracy in abstract/intro (Weakness 1, Question 2)\n\nThanks for pointing this out. In our Contributions paragraph (end of Section 1) we will add:\n\n> We find that with a reasonable privacy parameter (ε=1) we acheive over 92% accuracy on the EMNIST dataset, and applying logistic regression on the UCI Adult dataset, we get accuracy within 1% of an algorithm trained on the original dataset with no privacy.\n\n\n$Z_ε$ in Figure 5 in the paper is sampled from TGeom($e^{-ε}$) (Def. 3.3) which for ε=1 has variance 1.84. Our method takes $s(\\cdot,\\cdot)\\in\\{-1,1\\}$, but for $s(\\cdot,\\cdot)\\in\\{0,1\\}$ the answer would be the same (because the sensitivity would still be 1, so we would still sample from TGeom($e^{-ε}$)).\n\n### In the experiments, how much noise is appropriate? (Limitation 2)\n\nOur experiments show accuracy improves with less noise, but how much noise is appropriate?\n\nWhen applying differential privacy, one typically begins by deciding what privacy parameter ε is appropriate. This is a hard question, and the answer depends on the requirements of the party publishing the data. Ponomareva et al. give some practical advice in \"How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy\". In Section 5.2.1, they suggest ε≤1 gives a strong privacy guarantee, ε≤10 gives \"a reasonable level of anonymization for many applications\", and ε>10 is not a sufficient guarantee of privacy.\n\nOnce ε is chosen, the amount of noise necessary to achieve that guarantee is computed according to the particular method being applied. In our case, noise sampled from TGeom($e^{-ε}$) is added to each entry of the sketch (see Defs. 3.3, 3.5); this distribution has variance $2e^{-ε} / (1 - e^{-ε})^2$, which is about 1.84 when ε=1.\n\nTo interpret our results, we suggest fixing ε=1 as a reasonable value; for example, when reading the right-hand side of Figs. 2 and 3, find ε=1 on the x-axis.\n\n### Publishing a database with DP / wouldn't that require a lot of noise? (Limitation 1)\n\nThe reviewer asks what it means to publish a database with DP, since typically only aggregate statistics are published.\n\nTechnically, the answer comes down to the definition of differential privacy (lines 127-131 in Section 3, Preliminaries). We guarantee that for all pairs of datasets $D_1,D_2$ where $D_2$ is $D_1$ with one row added or removed, the output of our method is statistically almost the same on input $D_1$ as $D_2$, in the sense that for any set of outputs S (in our case, an output is a b-dimensional vector of integers as in Def. 3.5), the probability we output a vector in S is almost the same on input $D_1$ vs. $D_2$.\n\nAs pointed out, many DP mechanisms involve publishing a few aggregate statistics with some noise added, but our method does not fall in this category. Instead, we publish a large collection of numbers, often more than there are rows in the dataset. Contrary to intuition, this does not require adding a correspondingly larger amount of noise to each of those numbers. In fact, the noise we add to each entry of the sketch depends only on the privacy parameter ε, and does not scale with the size of the sketch.\n\nThe reason we can do this is that the count sketch has *sensitivity* 1. Adding an individual to the dataset adds or subtracts 1 to just one entry of the count sketch, and leaves the rest of the sketch unchanged.\n\nThis reasoning applies to private count sketches in general; see e.g. \"Differentially private linear sketches\" by Zhao et al.\n\nNote that even though the noise we add to each number in the sketch is small, Algorithms 2 and 3 look at sums of many sketch entries, so the noise in the *outputs* of our algorithms will be large compared with methods that only look at a few aggregate statistics.\n\n## Correctness and privacy properties (Weakness 2, Question 1)\n\n### Correctness\n\nThank you for pointing out that our theorem statements are missing the following information:\n\nOur theoretical guarantees (Theorems 5.1 and 6.4) apply to *any* sender and receiver datasets. We do not assume they are random.\n\nHowever, these theorems do assume the hash functions $h,s$ and noise values $Z$ are chosen randomly independently of the sender and receiver datasets. In particular, we do not allow the datasets to be chosen based on the particular hash functions.\n\nBecause $h$ and $s$ are random, the false positive matched rows will also be random. We have designed our method so that in expectation they contribute 0 to the output of Algorithm 2, or to the score function used in Algorithm 3. This happens because for any two pairs (id,y) and (id',y'), $E[s(id,y)\\cdot s(id',y')] = 0$.\n\nWe will edit the theorem statements to make it clear they are quantified over all possible sender and receiver datasets, but that the randomness must be chosen independently of the datasets.\n\n### Privacy\n\nThe sketch $C$ output by Algorithm 1 is ε-differentially private. We briefly explain this in the sentence immediately after Definition 3.5, but should have made it more prominent, e.g. by marking it as a theorem or proposition or similar."}, {"review_id": "HfLJBZfXsG", "reviewer": "Reviewer_dAeb", "summary": "The authors study the problem of computing a function of a join of two datasets on a user key so that the two datasets are owner by independent parties that never share their data directly. Instead the sender party gives out a DP sketch of the data that is later used by any receiver to compute an approximate answer to the query on the join. This is a very interesting formulation as it allows practical exchanges of information when the data exchanged is so sensitive (e.g., medical condition) that no party would want to participate. Contrary to other works (e.g., MPC, vertifcal Fed learning) this is one shot and does not require iterative algorithms or coordination. \n\nThe method is based on count sketch with added noise for privacy. The sender algorithm algorithm is simple to implement, efficient and elegant. The received algorithm is also straighforward for linear queries. The authors report results also on optimization of arbitrary functions. This requires that an optimizer is known for a weighted dataset ( a mild assumption). The algorithm for optimization is also very elegant requiring only a sketch-based weighting for the examples (and a factor k blow up in the number of examples to generate all possible labels) \n\nThe authors implement their method and test it for learning classification functions for up to k = 10 classes. They use standard public datasets and compare their method with a sketch-based method showing improved results. \n", "questions": "1) what is the largest k for which you find meaningful results in experiments?  \n\n2) Given the lack of baselines for this exact model, can you compare this result with the SOTA baselines in some other relaxed or more restrictive settings e.g., the trust curator model equivalent to running a central Label DP on the join, or local DP baseline (e.g., randomized response on the label)? \n\n\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "+ the problem is very relevant to Neurips\n+ the algorithm proposed are elegant and efficient.\n+ theoretical analysis show utility and privacy guarantees for a wide range of applications", "weaknesses": "- The sender domain must be a small set {1, … k}. So this does not allow arbitrary regression (but is ok for classification in few classes).  The factor k appears in the blow up of space, time and in the utility / privacy tradeoff so it really needed to have small k. \n- The comparison is only with one baseline. I agree that this area is quite new but it would be informative to compare with some other baselines with different computational models. E.g., in the case that a curator can be trusted with the label data the equivalent privacy property is Label DP. It would be interesting to see how the results here compare with the best central label DP algorithm--thus showing the price for not having a trusted curator.\n\nMinor: /NR(h(id, y). Missing closed parenthesis. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the comments and questions, based on which we did two new experiments, shown in Figure 2 of the attached pdf:\n\n## What's the largest $k$ for which we get meaningful results? (Weakness 1, Question 1)\n\nTo investigate the effect of large $k$, we used the EMNIST `bymerge` dataset consisting of 760K images of handwritten digits and uppercase and lowercase letters, with 47 classes. The left side of Figure 1 shows test accuracy as a function of the number of labels $k$.\n\nFor each run, we randomly chose $k$ out of 47 classes, and applied our method with $ε=1$. The figure shows that, as expected, the performance degrades significantly as $k$ increases, but the method is still viable with $k=45$.\n\nNote that in this experiment, the size of the dataset, and thus the join size, changes as we change $k$.\n\n## Comparing to label DP (Weakness 2, Question 2)\n\nThe right side of Figure 2 compares our method to Label-DP for the EMNIST `digits` dataset of 240K handwritten digits.\n\nThe definition of \"neighbouring datasets\" differs in our setting compared to Label-DP: we use the \"add/remove\" definition where a single row is added or removed; for Label-DP it is more appropriate to say a single value is changed. To account for this, we double the privacy budget for Label-DP, so for example at ε=1 on the x-axis, we actually give Label-DP a privacy budget of ε=2.\n\nThe Label-DP method benefits from having a trusted curator who is able to perform the join, and so we expect it to perform better than our method, where the parties must join using a non-interactive protocol. We were surprised to see our method perform better for small ε, and do not understand why this happens."}, {"review_id": "R9vVhsnWKA", "reviewer": "Reviewer_9EP2", "summary": "The paper considers a scenario where a data owner wishes to publish a private view of their data set, so that others can evaluate join (aggregations) against this data, and related questions.  Formally, the problem is to support the following problem: the data owner has a high-dimensional vector which is sparse, and wants to publish an object that will allow others to estimate the inner product of this vector with their own individual vectors.  This is represented by the SumOverJoin problem presented in Subproblem 1.2.  Building on this primitive, the paper then considers how to use this within an optimization setting, i.e., to search for a vector within some subspace that approximately optimizes some loss function.  This is sufficient to pick some approximate models, e.g. logistic regression, with a privacy guarantee.  ", "questions": "Could the optimization results be interpreted in terms of defining a subspace embedding?   I think the result follows if we can argue that the SumOverJoin bound holds for all vectors within a subspace. ", "limitations": "No limitations in the sense of negative societal impacts. \nThe paper could say more about the technical limitations of the approach, e.g., extending to more complex non-linear transformations. ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper sets out a clearly defined problem, and shows how an efficient combination of sketches and noise can be applied to solve it.  The algorithm is very amenable to implementation, and performs well in experiments. \n\nThe proof that the optimization queries are accurate is quite technical and involved, demonstrating technical skill on the part of the authors. ", "weaknesses": "The scenario may be viewed as potentially narrow: the authors describe several alternative approaches that could be used, but which fail due to the requirement that the protocol is non-interactive (e.g., private set intersection approaches).  I like the non-interactive property, but given the promotion of private set intersection protocols, it could be argued that it is not a compelling need,\n\nIt may be debatable how novel the core contribution is: there is precedent for using sketches with DP noise.  However, the extension to optimization queries goes beyond results I have seen before.\n\nA few opportunities for improving presentation, e.g., \n\"we can view the sketch as a function accepting as query an entire dataset\" - I found this hard to parse\n\"we are not trying to compress a stream\"  clarify that the objective is to take an input with n non-zeros over a domain of size D.  The goal is to be proportional to n in size, but sublinear in D.  Maybe discuss more what the solution would be if D were small. \n\"secure hash functions should give the same guarantees\"  Perhaps more precise to say 'give the same performance'\n ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Could the optimization results be interpreted in terms of defining a subspace embedding? I think the result follows if we can argue that the SumOverJoin bound holds for all vectors within a subspace.\n\nThis sounds interesting. Could you say more? Do you mean a subspace in the vector space of functions $f(x, y)$?\n\n> The paper could say more about the technical limitations of the approach, e.g., extending to more complex non-linear transformations.\n\nThis is a good point. Many real-world questions can't be expressed as a linear query. We will expand our future work section.\n\n> A few opportunities for improving presentation, e.g.,  $\\ldots$ Perhaps more precise to say 'give the same performance'\n\nThank you, we will incorporate these suggestions.\n\n>It may be debatable how novel the core contribution is: there is precedent for using sketches with DP noise. However, the extension to optimization queries goes beyond results I have seen before.\n\nWhile there is past work on private sketches, we are not aware of past work on joinable private sketches.  Also, as you correctly point out, we are solving a more general question of joint optimization.\n\n\n### Relation to PSI\n\n> The scenario may be viewed as potentially narrow: the authors describe several alternative approaches that could be used, but which fail due to the requirement that the protocol is non-interactive (e.g., private set intersection approaches). I like the non-interactive property, but given the promotion of private set intersection protocols, it could be argued that it is not a compelling need.\n\nFollowing [1], there have been many nice PSI developments over the last two decades.  These include handling malicious parties [2], ensuring all parties receive the intersection [3], joining and then aggregating over a column [4], other downstream computations on the join [5], secret sharing of the intersection [6] and more.\n\nIndeed, PSI solves a similar, but different problem. Here is a comparison:\n\n- **Interaction.** As you point out, our method requires no interaction. With PSI, two parties mutually agree to estimate the intersection of their inputs. With our method parties do not have to pre-agree on a joint function, and can use the same sketch to estimate joint distributions or train neural networks using stochastic gradient descent. \n\n- **Exact vs. Approximate Answers.** While the generality of our sketch implies that more functions can be estimated without interaction, this flexibility comes at the cost of more noise and therefore lower accuracy than SFE, which can either give exact answers or add just enough noise to satisfy DP.\n\n- **Simple Implementation.**  SFE protocols can be quite complex to implement. This submission proposes a simple implementation with two hash functions and some noise.\n\n- **Data Discovery in the Wild.** We are targeting a data repository of one-time sketches enabling data discovery in the wild.  The proposed method lowers the barrier to private joins. Data repositories such as UCI ML repository and MIMIC (healthcare data) presently, rightly, conceal information about individuals making it challenging to join. \n\n\n\nWe are excited to see the types of data discoveries that will be quickly and easily possible in a sketch-based public repository. We can add an appendix providing more perspective on the strengths and weaknesses of both approaches.\n\n\n\n[1] Freedman, M.J., Nissim, K. and Pinkas, B., 2004, May. Efficient private matching and set intersection. In International conference on the theory and applications of cryptographic techniques (pp. 1-19). \n\n[2] Kissner, L. and Song, D., 2005, August. Privacy-preserving set operations. In Annual International Cryptology Conference (pp. 241-257). \n\n[3] Gordon, S.D., Hazay, C. and Le, P.H., 2022. Fully Secure PSI via MPC-in-the-Head. Proceedings on Privacy Enhancing Technologies.\n\n[4] Ion, M., Kreuter, B., Nergiz, E., Patel, S., Saxena, S., Seth, K., Shanahan, D. and Yung, M., 2017. Private intersection-sum protocol with applications to attributing aggregate ad conversions. Cryptology ePrint Archive.\n\n[5] Buddhavarapu, P., Knox, A., Mohassel, P., Sengupta, S., Taubeneck, E. and Vlaskin, V., 2020. Private matching for compute. Cryptology ePrint Archive.\n\n[6] Falk, B.H., Nema, R. and Ostrovsky, R., 2022, June. A linear-time 2-party secure merge protocol. In International Symposium on Cyber Security, Cryptology, and Machine Learning (pp. 408-427). "}]

Author rebuttal:
Thanks for the thoughtful comments and suggestions. The attached figure includes experiments responding to questions from reviewers eoei and dAeb.

Meta-review: This paper presents a method for producing a non-interactive differentially private sketch of a dataset that can be used to estimate joins with another dataset. The paper is well-written and provides an empirical and theoretical analysis of the algorithms.

The reviewers found this to be an interesting and somewhat surprising result. There was some discussion about how this might compare to an interactive mechanism i.e. how it compares to the baseline of running a differentially private mechanism on the two datasets together rather than separately.

Overall, the reviewers are uniformly supportive of the submission. Thus it seems appropriate for presentation at NeurIPS.
Decision: Accept (poster)