Distributed Differentially Private Data Analytics via Secure Sketching
Authors: Jakob Burkhardt
Hannah Keller
Claudio Orlandi
Chris Schwiegelshohn
Venue: ICML 2025 poster (2025)
Keywords: differntial privacy
sketching
secure multiparty computation
Primary area: social_aspects->privacy
TL;DR: We present efficient mechanisms for differentially private data analysis in a distributed setting via cryptographic protocols and linear sketching.

Abstract: We introduce the *linear-transformation model*, a distributed model of differentially private data analysis. Clients have access to a 
trusted platform capable of applying a public matrix to their inputs. Such computations can be securely distributed across multiple servers using simple and efficient secure multiparty computation techniques. The linear-transformation model serves as an intermediate model between the highly expressive *central model* and the minimal *local model*. In the central model, clients have access to a trusted platform capable of applying any function to their inputs. However, this expressiveness comes at a cost, as it is often expensive to distribute such computations, leading to the central model typically being implemented by a single trusted server. In contrast, the local model assumes no trusted platform, which forces clients to add significant noise to their data. The linear-transformation model avoids the single point of failure for privacy present in the central model, while also mitigating the high noise required in the local model. We demonstrate that linear transformations are very useful for differential privacy, allowing for the computation of linear sketches of input data. These sketches largely preserve utility for tasks such as private low-rank approximation and private ridge regression, while introducing only minimal error, critically independent of the number of clients.

Distributed Differentially Private Data Analytics via Secure Sketching
Jakob Burkhardt Hannah Keller'
Claudio Orlandi
Chris Schwiegelshohn'
Abstract
auxiliary information. In the classic central model of differ- ential privacy, clients submit their data trusted central server, which processes the data and releases a (necessarily) noisy version of the result. Analysts can then use this re- sult to perform queries on the data. Informally, differential privacy guarantees that the analyst cannot confidently deter- mine whether any individual contributed their data, except with some small probability.
We introduce the a distributed model of differentially private data analysis. Clients have access to a trusted platform capable of applying a public matrix to their inputs. Such computations can be securely distributed across multiple servers using simple and efficient secure multiparty computation techniques. The finearttranfformation model serves as an interme- diate model between the highly expressive central model and the minimal local model. In the cen- tral model, clients have access trusted plat- form capable of applying any function to their inputs. However, this expressiveness comes at a cost, as it is often prohibitively expensive to dis- tribute such computations, leading to the central model typically being implemented by a single trusted server. In contrast, the local model as- sumes no trusted platform, which forces clients to add significant noise their data. The linear- transformation model avoids the single point of failure for privacy present in the central model, while also mitigating the high noise required in the local model. We demonstrate that linear trans- formations are very useful for differential privacy, allowing for the computation of linear sketches of input data. These sketches largely preserve utility for tasks such as private low-rank approximation and private ridge regression, while introducing only minimal error, critically independent of the number of clients.
model,
The central model requires trust that the server will not re- veal any individual's 's data and cannot be compromised by external actors. However, universally trusted servers may not exist in practice. In situations where privacy is critical but trusting a single server not feasible, alternative ap- proaches are available: One such approach is to use secure multiparty computation (MPC) techniques distribute the central server's computations across multiple servers. Under the assumption that a subset of these servers are honest, this setup guarantees the same level of privacy as the central model. However, MPC techniques often introduce signifi- cant computational overhead, especially when distributing complex or expressive computations.
Another option is avoid relying on external servers al- together. In this case, each client must publish their data in a locally differentially private manner, by adding noise directly to their data. While this removes the need for a trusted server, results in lower utility due to the increased noise. This approach is known as the local model of differ- ential privacy (Kasiviswanathan et al., 2008), an example of which is randomized response (Warner, 1965).
Both the central and local models of differential privacy have strengths and drawbacks. The central model typically yields higher utility but requires strong trust in a single server or the costly use of MPC. The local model, by contrast, requires no trust in external parties but suffers from reduced utility. These tradeoffs have motivated significant research into finding middle ground between these two models. One promising direction is to limit the expressiveness of the class of functions F that can be executed in trusted manner. While this restriction allows for more efficient distributed implementation, it is only useful if the DP mechanism built around such functions can still achieve good accuracy.
1. Introduction
Differential Privacy (DP) (Dwork et al., 2006b) has become the de-facto standard for ensuring the privacy of individu- als whose data is used in data analytics. DP offers strong, provable guarantees, such as composability and resilience to
'Aarhus University, Denmark. Correspondence to: Hannah Keller <hkeller@@e au.d
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
A notable example of such restricted expressiveness the class of functions known as shuffles, where a central entity

---

Distributed Differentially Private Data Analytics via Secure Sketching
(or distributed system) randomly permutes the messages from clients before they reach the analysing server. This is known as the shuffle model (Bittau et al., 2017; Erlingsson et al., 2019; Cheu et al., 2019). The shuffle model has been used to implement many peitrentiilly-privatt mechanisms with reasonable utility (Erlingsson et al., 2019; Cheu et al., 2019). Surprisingly, the shuffle model is more expressive than initially expected: with a trusted shuffler, any function can be securely computed in two rounds under the assump- tion of an honest-majority (Beimel et al., 2020).
the Laplace mechanism, as well as (e, deiffferrrttt pri- vacy with slightly higher utility, via protocols based on the Gaussian mechanism.
Low Rank Approximation. We are given a data ma- trix A E Raxd Our goal is to compute an orthogo- nal projection X E RRdxrr minimizing the error OPT = minx A AXX le. where |I-I|r denotes the Frobenius norm of matrix. In the LTM, we give a (e, differentially private mechanism with multiplicative error (1 + a) and additive error O(kd8/2a=3 log 8-1). We also present a differentially private mechanism with multiplicative error (1 + a) and additive error ((1:3 (k/3///22 ar - -1)) State of the art central model mechanisms (Dwork et al., 2014; Hardt & Roth, 2012) have no multiplicative error and additive error ( which is optimal in terms of k and d. For the local model, we are only aware of the result by (Arora et al., 2018), which has multiplicative error of O(log n log d) and additive error O(k2n dpoly( 1 log 8 "')). There are several related questions we will survey in more detail in Appendix
We therefore ask the following:
What is the least expressive class of func- tions F that needs to be securely implemented in order to achieve computationally efficient distributed differential privacy with ulility comparable to that of the central model?
Question 1.1.
1.1. Our Contribution
In this work, we investigate the power of the linear- transformation model (LTM) for differentially-private mech- anisms. In this model, the clients only have access to a trusted platform for performing arbitrary linear transforma- tions of their collective inputs. Linear functions can be distributed extremely efficiently with secure computations. However, it is also known that the expressiveness of this class of functions is strictly limited.
Ridge Regression. We are given a data matrix A Roxd a target vector b E R and regularization param- eter À > 0. Our goal is to find x E Idd minimizing minx | - bll + A ||x|2, where ||-II denotes the Eu- clidean norm of a vector. Each row of the data matrix, as well as the corresponding entry of b resides with a client. Assume that A 2 poly(s d,, log 1/6). In the LTM, there exists an (c, 5) differentially private mechanism that can compute an & with error (1 + o(1)) AlIAx b1j² + A Xope [1²) + poly(= d,, log 1/0). Unlike the low rank approximation problem, we are not aware of other papers achieving comparable bounds in any model. Regression has been studied in the context of empirical risk minimization and some results also exist for comparing closeness of the computed predictor & and that optimal Xopt- While we view the low rank approximation mechanisms as our main result, we nevertheless believe this work can serve a starting point for achieving bounds for ridge regression in terms of cost in any model including the central model.
We demonstrate the benefits of this linear transformation model (LTM) by showing that it can be used, in combina- tions with linear sketches to construct private summaries of a data set with noise comparable to that of central differen- tially private mechanisms. As in the local model, each client adds some amount of noise to their data before passing it onto the linear sketch. We then release the linear transform of the data. The benefit of having trusted linear sketch is that the noise can be combined, thereby significantly reduc- ing the amount of noise per client. All of our mechanisms require only a single round of communication from clients to server.
We demonstrate the effectiveness of this model by exemplar- ily applying it to problems in numerical linear algebra. A particularly powerful and expressive class of linear sketches with numerous linear algebra applications (Woodruff, 2014) (JI.) transforms. In this paper, we focus on low rank approximation and regularized lin- ear regression. Our contribution is to show how to design mechanisms for these problems, with the most widely used tL-transforms as the underlying secure sketch. For these problems, we achieve utility comparable to that of the cen- tral model with local privacy guarantees, assuming the JI.- transform is computed securely.
Table provides a comparison of the utility bounds for the problems in the local, central, shuffle and LTM models. To the best of our knowledge, there are no results on low rank approximation in the shuffle model.
are
As warm-up to illustrate the potential inherent in the LTM, and to also highlight the comparison to the other models, we consider the basic problem of computing histograms and frequency of moments. More related work on problems related to low rank approximation and regression, as well as applications of linear sketching to differentially private mechanisms can be found in Appendix F.
For both of the following problems, we have the option of achieving e differential privacy, via protocols based on
2

---

Distributed Differentially Private Data Analytics via Secure Sketching
Table SOTA utility bounds for various models for frequency estimation and low rank approximation. Our bounds for low rank
approximation have a multiplicative error O(1 + as), which we omitted for space. Shuffle
Local
LTM (this work)
Central
((vn)
(Bassily et al., 2020)
( (Ghazi et al., 2021)
Frequency Est
((ynn
(Bassily & Smith, 2015)
(Ollog n log' d), (d))
(Arora et al., 2018)
Ō kdd/2 8 1 og
@(KVdE- (Dwork et al., 2014)
Low-Rank App
N.A.
((ynn) (Bassily & Smith, 2015)
2. Preliminaries
their data to some randomized algorithm. We say that two datasets are neighboring if one can be obtained from the other by the the replacement of single individual with another individual.
Notation, Column vectors are written in bold lowercase letters b and matrices in bold upperease letters A. The transpose operator over vectors and matrices is bT and AT. For any vector b, we denote by ||b|| v 2. 6 its lg fn-norm. For any matrix A, we denote by ||A|| P - V Σ,E, A its Frobenius norm. We denote the inner product between vectors (a. b) = a a.bb Two vectors a, b are orthogonal if their inner product is O. An orthogonal matrix A is a real square matrix where the columns have unit Euclidean norm and are pairwise orthogonal
Definition 2.2 (Differential Privacy in the central model (Dwork et al., 2006b)). Let E 2 0 and E [0, 1]. A random- ized mechanism M : X + y (c, diiffeerrrtl private, if for all neighboring data sets x, x X and all outputs S y it holds that
Pr(M(x) E S] S E Pr[M((') E ES 5
where the probabilities are over the randomness of M. If 8 = 0, then we simply say that the mechanism is e- differentially private.
Subspace Preserving Sketches. We consider subspace- preserving sketches in this work, which are sparse Johnson- Lindenstrauss transforms. Of particular interest for us are algorithms that compute a subspace approximation of A without prior knowledge of A. Such algorithms are known as oblivious subspace embeddings. We will use a family of such embeddings known as oblivious sparse morm-upproximating projections originally due to (Nelson & Nguyén, 2013), but since improved upon in several sub- sequent works.
A probability distribution F is infinitely divisible if for any positive integer n, there is a random variable S, which can written as S,, = Σie(n] X, such that each of the X, are random variables, independent and identically distributed, and Sn has the probability distribution F.
3. Privacy Guarantees in the LTM
We consider a model in which the trusted component can perform any public linear transformation of the inputs. The model includes three algorithms: (1) R X' + y a ran- domized encoder that takes single user's data and outputs randomized message, (2) T )" - ) is the idealized trusted component that performs a public linear transfor- mation of its inputs, and (3) A :: ) + Z is an analysis function that takes the results messages and estimates some function from these messages.
Definition 2.1 (OSNAP (Nelson & Nguyên, 2013).). Let Deketch be a distribution over random matrices 1-1,0,13mxx where s entries of each column, chosen uniformly and independently for each column, are set to +1 with equal probability, and all other entries are set to If s == 1, we write Deketch We say that S Daketda is an (a, B, s, m) OSNAP for n orthogonal matrix W if with probability 1 - B, for all a, E Rd and some precision parameter
Note that standard definitions of differential privacy in the shuffle model only require T({((11),... R(x,)) be differ- entially private. This implicitly assumes that all clients are honest and do not collude with the adversary, in particular they are assumed not to leak the output of their randomizers publicly. This implies that existing definitions of differential privacy in the shuffle model could be satisfied even by (arti- ficial) mechanisms in which a single client adds the whole
WWW - wTb I a ||al|||Wb||
We give bounds on available choices of (a, 8, s, m) for subspaces of rank k in Table 3 in the appendix.
Differential Privacy. Differential privacy (Dwork et al., 2006b) offers privacy guarantees to individuals contributing
3

---

Distributed Differentially Private Data Analytics via Secure Sketching
noise while the others do not randomize their messages at all. This is clearly very weak privacy guarantee: in setting in which a large number of clients participate in a differen- tially private data analysis, it is unrealistic to assume that the adversary does not control even a single client. Luckily, to the best of our knowledge, no proposed mechanisms in the literature suffer from these vulnerabilities, still this coun- terexample shows that the existing definition is not robust enough, and we therefore formalize notion of differential privacy where we explicitly tolerate that a bounded number of clients might collude with the adversary. This refined definition could be applied to both the shuffle model and our model to ensure that the privacy guarantee holds even when a bounded number of clients might collude with the adversary. Similar observations were also made by (Talwar et al., 2023).
G
c
AORALEMOLL FOUD
C
Figure 1. Adversary's View
Algorithm Linear Transformation Model
1: Input: Individual input vectors X1,--.,X, representing values in RR Each client i E [m] locally computes R(x;) on their input X₃-
We assume that up to l' < n clients and / < k servers may collude in the semi-honest model, sharing information with each other while following the protocol.
Definition 3.1 (Trusted Computation Model for Differential Privacy). A tuple of algorithms P- = (R, T, A) is (c, 5)- differentially private given corrupt clients Coor if the out- put (I,,,....,,, = T(((=1),....... R(,,,), as well as cor- rupted parties' randomizer output R(xx) for all x. E Ceor satisfy (e, Jdddffeerenti privacy.
3: Each client secret shares the resulting value using linear secret sharing scheme, and sends one share to each server.
4: The servers jointly compute function T on the matrix, which results from concatenating all n vector secret shares.
The resulting matrix product is published and then taken input to any analysis function A.
Multi-Central Model of Differential Privacy, (Steinke, 2020) introduce the multi-central model, which exactly de- fines this split-trust model that instantiates the trusted com- putation model above. They allow a semi-honest adversary that honestly follows the protocol to corrupt up to all but one servers and all but one client. We also operate in the same semi-honest setting, but define parameters /. and /' for the number of tolerated server and client corruptions.
6: Output: Output A(T(R(x)), ... R(x,))
S Soor of up to < I corrupt servers and for all possible S, all coalitions Ceor of t' n corrupt clients and all neighboring datasets and x':
The view View Ccor.Sear (z) of the adversary consists of all the information available to the corrupted clients Coor and servers Scor plus the final output of the honest, uncorrupted servers. This view excludes only internal information of the trustworthy servers and clients. The resulting protocol is (c, 6) diifferrential private in the multi-central model if the adversary's 's view is (e, d) -iindittinguuihable from the output on a neighboring dataset.
R.I.AA
R.I.AA Pr[View Soon Coor (x) S]
S PriView Swor (x') E S]+
R.I.A
where the probability is over all the randomness in the algo- rithms (R, II, A).
Algorithm I describes how clients and servers jointly com- pute the linear transformation, allowing the transformed data to be published and used for analysis.
Figure 1 further illustrates what is contained in the adver- sary's view. If one server and one client are corrupted, the adversary's 'ss view contains all incoming and outgoing mes- sages from that server and that client marked in red in the figure.
With this definition, we can give our first result showing that differential privacy is retained given a bounded number of corruptions. The proof can be found in Appendix D.
Definition 3.2 (Instantiation of Trusted Computation Model for Differential Privacy with MPC). Let II be a k-party MPC protocol that computes f : R. + R with perfect security, tolerating t corruptions. A tuple of algorithms P = (R, II, A) is (c, diiiffeeryytially private if for all coalitions
Lemma 3.3. P (R,T, is (c, -)diffferentially pri- vate with t' corrupt clients, and if 11 is a perfectly secure k-party MPC protocol that computes T correctly while tol- erating t corrupt servers, then P = (R, A) is (E,8)- differentially private.
4

---

Distributed Differentially Private Data Analytics via Secure Sketching
3.1. Frequency Moments
To illustrate the possibilitties inherent to the LTM, we con- sider simple application by way of estimating frequency moments. For simplicity, assume in this section that all clients are trustworthy, i.e. t' = 0, but the arguments can be straightforwardly extended to deal with arbitrary values of t'. Here, each client is given a number [-A, A] and our goal is to estimate Fi = -i=1 |a:]**. if all entries are either 0 or 1, is not possible to estimate Fi without incurring an additive error of the order vni, that is the estimated value Fi- Fi = O(vr) for any privacy preserving local mechanism (Bassily & Smith, 2015). In contrast, simply computing F3 and adding an appropriate amount of noise yields an additive error that only depends on A, e and 8.
reb (x) x" + g g
Dds
(I)
We define second alternative to this randomizer function, which instead outputs Odt if < 8m ln(dm/0) + t':
n < &m 1mfdmmmm/ /0) +
RD(()) = redousexx) else
(2)
In the local model, even
RRndd + Rmxd This function takes as a parameter a matrix S E {-1,0, 1 and takes as input a matrix A E Rmxde, which corresponds to the vertical concatenation or stacking of n outputs from randomizer function R. We parse A the horizontal concatenation of matrices A; E Rn for E [s]. Let be the largest number of con-zero entries in a column of S. Then S can be decomposed such that S = Vs Σ; S, where S. E 0, 1|mx* is a matrix with only one non-zero entry per column, and the assignment of non-zero entries to indeces i is done uniformly at random. Ts outputs the sum of matrix products
Transformation function Ts
We now consider the LTM. X* denote the vector of client entries with x = | I. We observe that Fs = fx( x''x*, Suppose that every client samples gi from a distri- bution, and we denote x the vector of noisy client entries with x = |- + gt. To guarantee differential privacy, we can use a differentially private additive noise mecha- nism 1a 1x*(*) = f& (x) + G. where the noise distribution is infinitely divisible and G = EEejm] 9t-
Js Eiels] S,A,
Many different infinitely divisible distributions can be used at this stage. One example is the geometric distribution, since the sum of negative binomial random variables follows a geometric distribution, which can be used in differentially private mechanisms (Ghazi et al., 2020). The Laplace dis- tribution, which is commonly used for 8-DP mechanisms, is also infinitely divisible, since a zero-centered Laplace distribution can be formulated tween Gamma distributions. Other possible options are stable distributions, a subset of infinitely divisible distribu- tions for which each Si and G follow the same distribution, such as Gaussian or Cauchy. We provide parameter choices and an error bound examples for the Gaussian and Laplace distributions in Appendix B.
Ts(A) = V8
Σ S.A. .E(+)
(3)
We also define Ty RRaddm Rmxdd where S is dense matrix rather than sparse one, we set m. Then S can be decomposed such that S = fm Σ m S. where S, E {-1,0, 1 J is a matrix with only one non- zero entry per column and exactly n m non-zero entries per row.
sum of differences be-
Analysis function A. A takes matrix in R well as any public values, and outputs some data analysis. Examples include low rank approximation and linear regression.
We now evaluate the noise distribution necessary to guar- antee differential privacy in this model. We find that for sufficiently large n, we can apply the infinite divisibility of distributions to divide the noise into number of pieces corresponding the number (n - (')/2m of honest clients ex- pected to contribute to any entry of a column in the resulting noisy matrix product. The concentration bound, formulated in Lemma D. and used to bound this number of honest clients, contributes to the necessary value of 5. Composition theorems can be applied on the columns of the resulting ma- trix product to yield the final differential privacy guarantee. We will later see that adding suitable noise to data results in only a small error in the resulting error for regularized linear regression and low rank approximation.
3.2. Privacy Preserving Mechanism for Oblivious Johnson Lindenstrauss Transforms
We instantiate the trusted computation model for differ- ential privacy for specific choices for the functions in tu- ple (R, T, A). We will show how to guarantee differential privacy for the tuples (Fegase TTgense A) and (Rp, Ts, A), which we will refer to as the dense sketching mechanism and the sparse sketching mechanism, respectively.
Randomizer function RD R2d >> dRdd The randomizer takes as input a d-dimensional row vector x, copies times and concatenates the result to form x². Then noise is sampled independently from distribution D and added to each of the ds entries in the resulting vector.
We are now ready to state our privacy guarantees in the LTM.
5

---

Distributed Differentially Private Data Analytics via Secure Sketching
Theorem 3.4. Let & 2 0, 8 E (0,1), m E [n], l' < n, E [m]. Let S ~ Deketch with non-zero entries per col- umn. Also let noise 9i be sampled from symmetric distri- bution D such that Lie((n-ett)/(mm 9i = G. G follows distribution D' that defines an additive noise mechanism that satisfies (e/ (sd), (/(ss -oddddmmmmee ex--mmxpp((n s-t') (8mm)))))- DP for function fA) = (SA), + f n ~ D on input A E Bandd where the subscript refers to one column of SA. Then as long as input values are bounded above by n, the sparse sketching mechanism (RD, Ts, A), as defined by equations 2 and 3 and for any A, is (E, 8) -iiffeerrntially private in the trusted computation model for differential privacy with l' corrupt clients.
3.3. Cryptographic Assumptions and Relations to the Shuffle Model
The LTM can be securely distributed using simple cryp- tographic techniques for secure multiparty computation (MPC), such as linear secret-sharing (LSS). MPC ensures that no adversary corrupting all but one server learns more than the computation'ss 's output. (Dwork et al., 2006a) first explored combining differential privacy and MPC, focus- ing on distributed noise generation requiring server inter- action. (Cheu & Yan, 2023) establish lower bounds for non- non-interactive multi-server mechanisms, while (Damgárd et al., 2023) propose an interactive MPC protocol for selec- tion in distributed trust models.
One additive mechanism to which this can easily be ap- plied is the Gaussian mechanism. To do so, D is a normal distribution with variance:
The linear transforms can be non-interactively computed locally by servers and are also known to all participating parties, that is, once initiated, the output of the protocol is fully deterministic. Linear transforms can be computed non- interactively by servers and are publicly known, making the protocol fully deterministic once initiated. This enables implementing the LTM with multiple central servers under the minimal assumption that at least one server remains honest. Using LSS has key advantages: clients send a sin- gle message per server proportional to the input size and sparsity of the transformation matrix S, servers commu- nicate only with the data analyst, and the total workload scales only with the number of servers and matrix sparsity. Since LSS supports tem remains secure even against quantum adversaries. We describe the type of secret-sharing scheme used for secure linear transformations in Appendix H.
48 1/² In
1.25 5/d-m m exp( am
md
0²_
(4)
8
t')
If we would like to obtain a result for mechanisms with ō = O, we can instead use rehme and use a dense sketching matrix S E (-1,1) mmxx
Theorem 3.5. Let E 2 0, 10, m E [n], t' < n, E (m]. Let S ~ 1-1,11mmx be dense, uniformly sampled matrix. Also let R add noise 9i sampled from a symmetric distribution D such that Eieln/m-e1 9: = G. G follows a distribution D' that defines an additive noise mechanism that satisfies (e/mm)), 8/ ) for func- tion f(A) = (SA); + n. for n ~ Dm on input A E Raxd where the subscript refers to one column of SA. Then as long as input values are bounded above by n, dense sketch- ing mechanism ( (Rei T A), as defined by equations and 3 and for any A, (E,5) diifferreni private in the LTM for differential privacy with t! corrupt clients.
nnermatiio-thhoreeee security, our sys-
Secure aggregation and the shuffle model are two instanti- ations of intermediate trust models for differential privacy. Secure aggregation (Goryczka & Xiong, 2017; Bonawitz et al., 2017: Mugunthan et al., 2019; Apple & Google, 2021; Talwar et al., 2023) is a special case of the LTM, where the linear transformation applied is a sum, which is useful in federated learning. The shuffle model (Bittau et al., 2017; Erlingsson al., 2019; Cheu al., 2019) can be distributed among multiple servers using cryptographic protocols such as mixnets.
To instantiate this second theorem, D can be chosen as the distribution formulated as the difference of two samples of gamma distribution
Implementing shuffles requires servers to communicate over a chain, increasing latency. In MPC-based shuffles, cach server must sequentially shuffle and randomize the cipher- texts, leading to a round complexity proportional to the number of servers involved. In contrast, the LTM enables all servers to perform their computations in parallel, result- ing in lower round complexity and latency.
1 n/m - v. 2mm22
(5)
The proofs can be found in Appendix D. Corollary 3.6 below follows directly from Theorem 3.4 and Lemma 3.3.
Corollary 3.6. Let (Rn, Ts, A) be the tuple of algorithmss above. It's is computed correctly using an MPC protocol Is with perfect security tolerating semi-hones corrup- tions, then the tuple of algorithms (R,,Ils, A) is (5, differentially private with t' corrupt clients.
Regarding the computational cost, servers in the LTM only perform simple linear operations on secret shares, such as matrix-vector multiplications, which are highly efficient. On the other hand, MPC-based shuffles typically rely on
6

---

Distributed Differentially Private Data Analytics via Secure Sketching
mix-nets or similar constructions, where each server per- forms, for every data point, multiple expensive public-key operations (e.g., modular exponentiations with large moduli and exponents). This introduces an overhead that is orders of magnitude higher compared to simple matrix multiplica- tions.
constant 1]
1 sup x
[G
0². -|x||1 (v log 1/3)
m
+ (k: + log 1/3)).
and
The total amount of data transmitted is comparable between the two models, but the size of individual messages differs substantially. In the LTM, secret shares can be small as the plaintext itself; for example, when working with 64- bit types, each share is just 64 bits per server. In contrast, MPC-based shuffles transmit ciphertexts that are signifi- cantly larger due to the inherent expansion of public-key encryption. For example, even with elliptic curve FlGamal, each ciphertext would be at least 512 bits. As result, the total communication volume in MPC shuffles is larger.
s GG S n 2no² dd log 1/3
Related, though slightly weaker bounds can also be derived for the Gamma/Laplace mechanism. While is possible to derive bounds for sparse Rademacher sketches, we focus the dense constructions these yield differentially pri- vate mechanisms (as opposed to (e, 6) differentially private mechanisms).
v (-1,0, be an (a,, 3, m,mmm,m)) m) OSNAP with S = -m = S, where S, (-1,0,1)mx has exactly one non-zero entry per now and r2/m non-zero entries per column. Let L Jon Eig(m] S where every matrix T; E Band has inde- pendent entries X, - Y, where X,, Y₁ T(m/n,br b). Then with probability at least foror some absolute constant b and
Lemma 4.2. Let S E
1
Finally, shuffles require computationally intensive public- key cryptography, which in turn requires computational as- sumptions. In contrast, LSS enables efficient, unconditional security and deterministic computation."
4. Numerical Linear Algebra in LTM
In this section we give the utility guarantees of our mecha- nism. We start with giving generic distortion bounds relating the spectrum of the noisy matrix to the spectrum of the origi- nal non-private matrix. Parameterizations of this mechanism depend on the underlying class of subspace embeddings. In this utility analysis, we limit outselves to OSNAPs with m and chosen according to (Cohen, 2016); other trade-offs are possible and can be found in Appendix C. Applications to specific problems such as regression and low rank approx- imation are given towards the end of the section.
L 1 S mmmm2 log? m B
We first begin with our utility results for low rank approx- imation. Using the Gaussian mechanism, we obtain the following guarantee.
Theorem 4.3. Let e 2 0, 8 E (0, 1' < n/2. Let S Dekettch Define Ag an algorithm that com- putes argminx rank k.e.ke.x - AXXT An instan- tiation of the trusted computation model (Rp, As) specified in Equations 2 and 3, using noise distribution D ~ N'(00 o²) according to Equation 4, computes or- thogonal projection X' that with probability 1- 3 achieves a multiplicatiie error (1 + ((a))) and additive error k/2/2 log 3/2 (1/3) log 12 (1/6) for the low rank approximation problem.
Here we present the formal utility statements for ridge re- gression and low rank approximation. All proofs can be found in the Appendix E.
We will use the following spectral bounds for both linear re- gression and low rank approximation. We believe that there may be further applications and that the bounds themselves are therefore of independent interest.
Using dense Rademacher sketches and the Gamma/Lappace mechanism, we instead obtain the following guarantee.
Lemma 4.1. Let S E
1 1-1,0,13mxn be an Vs
Theorem 4.4. Let E 2 O, δ E (0, 1' < nn22. Let S ~ Dikatch Define A as an algorithm that computes argminx mink k.cRnxa || AXXT An instantiation of the trusted computation model (Reggme, TTgense AAk) specified in Equations 1 and 3, using noise distribution D as the difference between two independent I random variables parameterized by Equation 5, computes an orthogonal pro- jection X' that with probability 1 - B with multiplicative error (1 + O(as)) and additive error O k2 2/2
(a. B, m. 8) OSNAP with S 1-1,0.1mxx0 has exactly one non-zero entry per row. Let G = E S,G, where every matrix G; E Raxd has independent Gaussian entries (00, Further, let V be set of d-dimensional vectors lying in k-dimensional sub- space. Then with probability at least 1- - for some absolute
= J. EvEls) S, where S, E
Vs
'The linear transformations we use random but public and sampled before the computation.
E loog og
7

---

Distributed Differentially Private Data Analytics via Secure Sketching
10a
the other hand adds the sum of mn samples from Lap(O, 1/e) to every entry in SA. As a baseline for the central model, we implemented MOD-SULQ (Chaudhuri et al., 2012), ap- proach where A A A is perturbed by adding Gaussian noise. We measure the error in terms of the excess risk;
10
10-
10-6
10-8
+ AA - AX'X F
A AXOPT X 1
0.25
0.50
0.75
1,00
where Xorr denotes the optimal solution and X' denotes the solution after adding noise to the training data. We vary the privacy parameter E and k based on the dataset at hand. For each dataset measure & for the central model, the Laplace mechanism and the Gaussian mechanism with E (1. 0.9, 0.8, 0.7, 0.6, 0.5, 0}. by reporting the average v over 20 runs of the algorithms per dataset.
Ceutral
Local
Garas LTM
Laplace LTM
Figure 2. Error & as function of privacy parameter e, with n = 500000, d 50 and & 5. The standard deviations are depicted by the vertical black lines and the y-axis is logarithmic in db.
Datasets. We evaluate our mechanism on synthetic and real datasets, enabling us to vary the number of sampled points n and interpolating between datasets of different sizes.
For ridge regression, we achieve the following bound.
Theorem 4.5. Let 2 0, 10. < n and a be chosen as described in Theorem D.3. Let S ~ Dakerchh Define A that performs linear regression on the sketched noisy inputs, oulputting argming || Ax bil² + X||x||², where the error is measured by minx| - bll² + A||x|? An instantiation of the LTM (Rp, Ts, Ax) specified in Equations 2 and 3, us- ing noise distribution ~ (0, o²)) according to Equation 4, which tolerates i' corrupted clients, computes linear re- gression parameters for any as
The synthetic datasets have large spectral gap from the kth to the (k + 1)st singular value with random bases, which emphasizes the performance difference between the various private mechanisms. The parameters of the four real- world datasets from the UC Irvine Machine Learning Repository are given in Table 2. For more thorough descriptions on the datasets, see Appendix G.2.
> with probability 1 3 with multiplicatiie error 1 + 0 (as+p- p p²) and additive d' d'07"" lox" $ lox
Utility, Figure 3 shows our results for two privacy regimes (s E (0.1, 0.53) with synthetic data and Table 2 shows the error for e = 0.05 with real-world datasets. In all chosen parameter settings for synthetic data, we observe that as n grows, the error in the LTM asymptotically approaches the error in the central model, both on real and synthetic data sets (see Figure 3 and Table 2). Table 2 shows that real-world datasets, our Gaussian approach performs significantly better than the Gaussian mechanism in the local model and is very close to the central MOD-SULQ (Chaudhuri et al., 2012) mechanism. Both with synthetic and real-world datasets, our Laplace approach performs bet- ter than the local model, though not as significantly as the Gaussian approach. However, this is the price of achieving pure e-differential privacy with 8 0. Finally Figure 2 shows our results for a varying privacy budget e. As ex- pected, the error in the LTM stays between the one in the local and the central model, while it is decreasing in all models.
error Ô (p + )²), where p
5. Experimental Evaluation
In this section we present an empirical evaluation of differ- ential privacy mechanisms for the low-rank approximation problem in the central, the local and LTM models. The local and LTM mechanisms we consider are algorithmically identical up to their noise rate. An immediate question thus is, for which parametrizations of the noise rate we still achieve acceptable utility. In addition we implement Gamma/Laplace based LTM mechanism, evaluate the price of achieving pure --differential privacy. Additionally, experimentally evaluated the minimal computational overhead introduced by the use of MPC for distributing the execution of the LTM. In Appendix G we provide additional experiments for the ridge regression problem as well as a more in depth description of the low-rank approximation experiments.
Running Time. The only overhead of the LTM over the local model is the execution of the linear transform in MPC, and comes from distributing A + G, E Rexd among the servers for i E [s] and then performing matrix multiplica- tions (A + G.) in MPC, where S ,,....,S, S, is a decom- position of some S E mm chosen according to (Nelson & Nguyên, 2013; Cohen, 2016) with sparsity 8. We imple-
Setup. Our Gaussian mechanism in the LTM adds noise sampled from (/(0, x²) to every entry in input data matrix A. The variance o² depends on privacy parameters and and is chosen proportional to -P for p E [0, 1]. This en- ables us to interpolate between the local model (p = 0) and the LTM (p- = 1). The Laplace mechanism in the LTM on
8

---

Distributed Differentially Private Data Analytics via Secure Sketching
Central
0.75
0.75
Gaus LTM
P 0.9
0.50
es7or
0.50
p 0.8
p D.7
0.25
0.25
p 0.6
p =
0.00
10 10 0.00
Local (p
10
10
10
10
Laplare LTM
11
Figure 3. Plots depicting the asymptotic behavior of error 1 for E E {0.1, 0.5) (left, right), with d = 50 and & = 5. The gray line depicts the error the local mechanism, and orange and lime lines depict our approach using Gaussian Laplacian noise respectively. The other lines resemble different values of when using Gaussian noise. The standard deviations are depicted by the vertical black lines and the z-axis is logarithmic the number clients n2.
Table Experimental evaluation of error vi on real-world datasets. Here we in the setting where 0.05. For elaborate version of the table, including standard deviation, see Table 9 in the appendix.
Dataset
d
k
Local
LTM Laplace
LTM Gauss
Central
Power (Hebrail & Berard, 2012)
2049280
6
3
1.2
X 10
4.0 x 10
2.1 10
1.8 x 10-6
Elevation (Kaul, 2013)
434874
2
1
1.2 10
1.5 x 10-2
4.7 x 10
4.5 x 10-8
Ethylene (Fonollosa, 2015)
4178504
18
5
5.9
10
5.8 x 10
2.4 x 10
7.9 x 10-6
Songs Maaiie,, 2011)
515345
89
15
5.6
x 10-7
5.6 x 10-7
5.6 x 10-7
5.6 x 10-7
mented our approach in MP-SPDZ (Keller, 2020) and pro- vide our results in Appendix G.I. Notably, for even with one million clients, the computation on each server lasts less than 2 seconds, which shows that securely dis- tributing in the LTM using MPC techniques a practically relevant approach.
References
Achlioptas, D. Database-friendly random projections:
lhanson-lindenstrauge with binary coins. J. Com- pul. Syst. Sci., 66(4))671-687, 2003. doi: 10.1016/
50002-00000(3300025544 URL https: http://oooorrooo//////////.. 10 10.1016/S0022-000 -000 (03) 00025-4 4.
Acknowledgments
Apple and Google. Exposure Notification Privacy- preserving Analytics (ENPA). White paper, 2021.
Jakob Burkhardt and Chris Schwiegelshohn are partially supported by the Independent Research Fund Denmark (DFF) under Sapere Aude Research Leader grant No 1051- 00106B. This work was also supported by the European Re- search Council (ERC) under the European Unions's Horizon 2020 research and innovation programme under grant agree- ment No 803096 (SPEC); the Danish Independent Research Council under Grant-ID WFF-2064400011 (YOSO); DFF- 3103-00077B (CryptoDigi) and the Danish Independent Research Council under Grant-ID 1051-001068 (ACBD).
Arora, R., Braverman, V., and Upadhyay, Differentially private robust low-rank approximation. In Advances in Neural Information Processing Systems, 2018.
Arora, S., Hazan, E., and Kale, S. fast random sampling algorithm for sparsifying matrices. In Díaz, J., Jansen, K., Rolim, D. P., and Zwick, U. (eds.), Approximation, Ran- domization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop Approxi- mation Algorithms for Combinutorial Optimization Prob- lems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, vol- ume 4110 Lecture Notes in Computer Science, pp. 272- 279. Springer, 2006. doi: 10. 10.1007//183002// 26. URL https: doii org 1011111110111111
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
26.
Balcan, M.-F, Du, S. S., Wang, Y., and Yu, A. W. An improved gap-dependency analysis of the noisy power method. In Feldman, V., Rakhlin, A., and

---

Distributed Differentially Private Data Analytics via Secure Sketching
Shamir, O. (eds.), 29th Annual Conference on Learn- ing Theory, volume 49 of Proceedings of Machine Learning Research, pp. 284-309, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. UtIp:tts::/ httphhtsss//ppocccce wwwppoodddnngge iag..ngsm...... ml press/v49/ Salcan16a.htar html.
Blum, A., Dwork, C., McSherry, F., and Nissim, K. Prac- tical privacy: the sulq framework. In Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SICARR Symposium on Principles of Database Systems, PODS "05, pp. 128-138, New York, NY, USA, 2005. Asso- ciation for Computing Machinery. ISBN 1595930620. doi: 10. 10.1145/1065117711665588 URL https: /doi. org/ 10. /0g/10.
Bassily, R. and Smith, A. D. Local, private, efficient protocols for suceinct histograms. In Servedio, R. A. and Rubinfeld, R. (eds.), Proceedings of the Forty- Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland. OR, USA, June 14- 17, 2015, pp. 127-135. ACM, 2015, doi: 10.1145/ 7746539.27446667
10651144
Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., and Seth, K. Practical secure aggregation for privacy- preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communica- tions Security, CCS, 2017.
URL https: http:::/ddoi.rrgg/ 1145/2746552 274 6632.
Bassily, R., Smith, A. D.. and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2014.
Cai, T. T., Wang, Y., and Zhang, L. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statisties, 49(5): 2825 2850, 2021. doi: https: /tt:///o.... org / 1 0 1 21 4 21 -A052005
URL
Bassily, R., Nissim, K., Stemmer, U., and Thakurta, A. Prac- tical locally private heavy hitters. J. Mach. Learn. Res., 21:16:1-16:42, 2020. URL https:: happ:://jmrrorrt papers/v21/11 786. ht.lltml..
Chaudhuri, K., Sarwate, A. D., and Sinha, K. Near-optimal differentially private principal components. In Bartlett, P. L., Pereira, F. C. N., Burges, C. J. C., Bottou, L., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pp. 998- 1006, 2012. neurips, . cttps///cccaappp//////aaa/a (7706620cc..22200666ffeeeee html.
Becchetti, L., Bury, M., Cohen-Addad, V., Grandoni, F., and Schwiegelshohn, C. Oblivious dimension reduction for k- means: beyond subspaces and the johnson- lindenstassd lemma. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, 2019.
URL https::/proceedee
Beimel, A., Haitner, I., Nissim, K., and Stemmer, U. On the round complexity of the shuffle model. In The- ory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part 11, pp. 683-712, Berlin, Heidelberg, 2020. Springer- ISBN 778-3-0300-64377-5 doi: 10.100779788333000-44478888222 URL https://doi. 0ttp:/0..007/998----9---66------
Cheu, A. and Yan, C. Necessary Conditions in Multi-Server Differential Privacy. In 14th Innovations in Theoretical Computer Science Conference (ITCS), 2023.
Cheu, A., Smith, A., Ullman, J., Zeber, D., and Zhilyaev, M. Distributed differential privacy via shuffling. In Advances in Cryptology EUROCRYPT. 2019.
Bertin-Mahieux, T. YeanPredictionMSDD. Machine Learning Repository, 2011. http::/d6b..rr/1024442/2550
UCI
DOI:
Bittau, A., Erlingsson, Ú. Maniatis, P., Mironov, I., Raghu- nathan, A., Lie, D., Rudominer, M., Kode, U., Tinnes, J., and Seefeld, B. Prochlo: Strong Privacy for Analytics in the Crowd. In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP, 2017.
Clarkson, K. I. and Woodruff, D. P. Numerical lin- ear algebra in the streaming model. In Mitzenmacher, M. (ed.), Proceedings of the 41st Annual ACM Sympo- sium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 June 2, 2009, pp. 205-214. ACM, 2009, doi: 10.1 10.11455/53364141555665 URL https: c/doiioorg.. 10.
Blocki, J., Blum, A., Datta, A., and Sheffet, O. The johnson- lindenstrauss transform itself preserves differential pri- vacy. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pp. 410-419. IEEE Com- puter Society, 2012. doi: 00.1109/FOCC.20122.61 URL https://dol: http:///o.oooo.....// .rgg/1.. /FOCs. w0l.oc...02.....
Clarkson, K. L. and Woodruff, D. P. Low rank approxi- mation and regression in input sparsity time. In Bonch, D.,, Roughgarden, T., and Feigenbaum, J. (eds.), Sym- posium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pp. 81-90. ACM,
2012.67.
10

---

Distributed Differentially Private Data Analytics via Secure Sketching
2013. doi: 10.1 10.1145/248360824486666 URL https: w0../......../ //doi.org/10
Erlingsson, U., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., and Thakurta, A. Amplification by Shuf- fling: From Local to Central Differential Privacy via Anonymity. In Proceedings of the 2019 Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), 2019.
201.4888888888888888888 24888200.
Cohen, M. B. Nearly tight oblivious subspace embeddings by trace inequalities. In Krauthgamer, R. ), Proceed- ings of the Fwenty-Sevente Annual ACM-SIAM Sympo- sium on Discrete Algorithums, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 278 778-.87.00 SIAM. 2016. doi: 00.113771.97811111973333 CH21, URLhttps. https://
Fonollosa, J.
Gas sensor array under dynamic gas mix- tures. UCI Machine Learning Repository, 2015. DOI:
https://bb..rrg/1.2444422
Foulds, J., Geumlek, J., Welling, M., and Chaudhuri, K. On the theory and practice of data analysis. In Proceedings of the Thirty-Second Confer- ence on Uncertainty in Artificial Intelligence, UAI' 16, pp. 192-201, Arlington, Virginia, USA, 2016. AUAI Press. ISBN 9780996643115.
bayesian
Cohen, M. B., Elder, S., Musco, C., Musco, C., and Persu, M. Dimensionality reduction for k-means clus- tering and low rank approximation. In Servedio, R. A. and Rubinfeld, R. (eds.). Proceedings of the Forty- Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14- 17, 2015. pp. 163-172. ACM, 2015. doi: 10.1145/ 2746539.2746669, URL attps://doi.oo 1145/2746553 .29.992..44555 2746569.
Ghazi, B., Kumar, R., Manurangsi, P., and Pagh, R. Private counting from anonymous messages: Near- optimal accuracy with vanishing communication over- head. In Proceedings of the 37th International Con- ference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Ma- chine Learning Research, pp. 3505-3514 PMLR, 2020. URL httphhtt/p/pett http:::/proceeding... mlr www..press//ee press/v119/ ghazi20a.html.
Cramer, R., Damgård, I. B., and Nielsen, J. B. Secure Multiparty Computation and Secret Sharing. Cambridge University Press, 2015.
Damgård, I., Keller, H., Nelson, B., Orlandi, C., and Pagh, R. Differentially private selection from secure distributed computing. In The Web Conference, WWW, 2023.
Ghazi, B., Golowich, N., Kumar, R., Pagh, R., and Vel- ingker, A. On the power of multiple anonymous mes- sages: Frequency estimation and selection in the shuf- fle model of differential privacy. In Canteaut, A. and Standaert, F. (eds.), Advances in Cryptology EURO- CRYPT 2021 40th Annual International Conference the Theory and Applications of Cryptographic Tech- niques, Zagreb, Croatia, October 17-21, 2021, Proceed- ings, Part III, volume 12698 of Lecture Notes in Com- puter Science, pp. 463-488. Springer, 2021. doi: 1001/ 978-3-030-77883-33 16. URL https: /ttp://doi.orrgooo 10. 00w.100777----000--211
Dimitrakakis, C., Nelson, B., Mitrokotsa, A., and Rubin- stein, B. P. Robust and private bayesian inference. In Algorithmic Learning Theory, pp. 291-305, Cham, 2014. Springer International Publishing. ISBN 978-3- 319-11662-4.
Dwork, C. and Roth, A. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoreti- cal Computer Science, 2014.
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology- EURO- CRYPT, 2006a.
Ghazi, B., Kamath, P., Kumar, R., Manurangsi, P., and Sealfon, A. On computing pairwise statistics with local differential privacy. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise to sensitivity in private data analysis. In Theory of Cryptography, 2006b.
Dwork, C., Talwar, K., Thakurta, A., and Zhang, L. Analyze gauss: optimal bounds for sevaacy-prservingg principal component analysis. In Shmoys, D. B. (ed.), Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 June 03, 2014, pp. 11-20. ACM, 2014.
Goryczka, S. and Xiong. L. A Comprehensive Compar- ison of Multiparty Secure Additions with Differential Privacy. IEEE Transactions on Dependable and Secure Computing, 2017.
doi:
URL https: : /ooi 2591883.
Hardt, M. and Price, E. The noisy power method: A meta algorithm with applications. In Ghahramani,

---

Distributed Differentially Private Data Analytics via Secure Sketching
Z., Welling, M., Cortes, C., Lawrence, N., and Wein- berger, K. (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL https://prroeddingg.. neurips. cc laaeer_fileseee papper_iileespppper//////////
Keller, M. MP-SPDZ: versatile framework for palti-party computation. In Ligatti, J., Ou, X., Katz, J., and Vigna, G. (eds.), CCS '20: 2020 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, USA, November 9-13, 2020, pp. 1575-1590. ACM, 2020. URL satttpss///ii /doi.
729 22286688 3eeeeaade111551111111111 pdf.
Paper.
doi: 10.1144/33372297 org /1g/ www.e1111333222 3 3417872.
Hardt, M. and Roth, A. Beating randomized response on incoherent matrices. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12, pp. 1255-1268, New York, NY, USA, 2012. Associa- tion for Computing Machinery. ISBN 9781450312455. doi: 10. 145/2213397.22214088 URL https://do.. 0tg/10.00 11110.11452220 DtT/20..145/221377.22211
Kenthapadi, K., Korolova, A., Mironov, I., and Mishra, N. Privacy via the johnson-lindenstraus transform. J. Priv. Confidentiiality 5(1), 2013. doi: 10.29012JJC.VSI1..00 URL https: /do.i http://doooooorg//////// 22000.29122220 /ttp///p/pp..../////////////c v5i1. 625.
Kifer, D., Smith, A. D., and Thakurta, A. Private convex optimization for empirical risk minimization with applica- tions to high-dimensional regression. In The 25th Annual Conference on Learning Theory, COLT, 2012.
Hardt, M. and Roth, A. Beyond worst-case analysis in private singular vector computation. In Proceed- ings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '13, pp. 331-340, New York, NY, USA. 2013. Association for Computing Machinery. ISBN 9781450320290. doi: 10.1145/ 2488650.
Laurent, B. and Massart, P. Adaptive estimation of a quadratic functional by model selection. Annals of statis- tics, pp. 1302-1338, 2000.
URL https://doi.orgee 1145/2488608 2488650.
Liang, Y., Balcan, M., Kanchanapally, V., and Woodruff, D. P. Improved distributed principal component analysis. Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N. D., and Weinherger, K. Q. (eds.), Advances Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec. Canada, pp. 3113-3121, 2014. URL https: htttps:/pproceedingg
Hebrail, G. and Berard, A. Individual houschold electric power consumption. UCI Machine Learning Repository, 2012. DOL: https///bb.orr/1024333353333
Høgsgaard, M. M., Kamma, L.,, Larsen, K. G., Nelson, J., and Schwicgelshohn, C. Sparse dimensionality reduction revisited. CoRR, abs/2302.06 656 2023. doi: 10.48550/ ARXIV:2302.06165. URL https: / 48550/arxiv 1tt:0//axiv.2302.... 2302. 061 65.
peuripps.cc/ppper/221////ss 7394760ade57a00eea133666666 (ww.://0000011166------------ Abstract. html.
Kane, D. M. and Nelson, J. Sparser -innssstnliddesstruuuss transforms. In Rabani, Y. (ed.), Proceedings of the Twenty-Thin Third Annual ACM-SIAM Symposium on Dis- crete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pp. 1195-1206. SIAM, 2012. doi: 10.1137/ 1.9781611973099.g9 94. URL https: /ttp///o.o/.....////////////.../ 1137/1. 9781 97886119999999999
Liu, X., Kong, W., and Oh, S. Differential privacy and robust statistics in high dimensions. In Conference on Learning Theory, 2022.
Melis, L., Danezis, G., and De Cristofaro, E. Efficient private statistics with succinet sketches. 02 2016. doi: 10. 10.147722ndss.221122377.
Kapralov, M. and Talwar, K. On differentially pri- vate low rank approximation, pp. 1395-1414.
Meng. X. and Mahoney, M. W. Low-distortion sub- space embeddings in input-sparsity time and applica- tions to robust linear regression. In Boneh, D., Rough- garden, T., and Feigenbaum, J. (eds.), Symposium on Theory of Computing Conference, STOC' 13, Palo Alto, CA, USA, June 1-4, 2013, pp. 91-100. ACM, 2013. doi: 10.1 141/248880088888 2488621. URL https: /doi. org 10. 114 /145/24881181 2488621.
doi: 10.1137/1 1113771.978111117110000000 https:://euuie http://ewwssssa.......... sww.. www.:.aammaaaa.aa......... 9T55:/1.77861199999
URL
101.
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. What can we learn privately? In 49th Annual IEEE Symposium on Foundations of Com- puler Science, FOCS, 2008
Kaul, M. 3D Road Network (North Jutland, Den- mark). UCI Machine Learning Repository, 2013. DOI: http://doo..r/1102245///CC
Milionis, J., Kalavasis, A., Fotakis, D., and loannidis, S. Differentially private regression with unbounded covariates. Camps- Valls, G., Ruiz, F. J. R., and
12

---

Pisier, G. The volume of convex bodies and Banach space geometry. Cambridge Tracts in Mathematics. 94, 1999. Distributed Differentially Private Data Analytics via Secure Sketching
Valera, I. (eds.), Proceedings of The 25th Interna- tional Conference on Artificial Intelligence and Statis- tics, volume 151 of Proceedings of Machine Learn- ing Research, Pp. 3242-3273 PMLR, 28-30 Mar 2022. wtw.ttts::/ htwp.httpps:/rroeeedd.oo http///oocedd/ege/ wew.ceeiiigg...e mm prrss/ #151/milioniee hmmml
Sheffer, O. Old techniques in differentially private linear regression. In Garivier, A. and Kale, S. (eds.), Proceed- ings of the 30th International Conference on Algorithmic Learning Theory, volume 98 of Proceedings of Machine Learning Research, pp. 789-827. PMLR, 22-24 Mar 2019. htthttps: httpppppooeee...ee/// mlr presss/ v98 httsssfffeeettee 9a html.
Minami, K., Arai, H., Sato, I., and Nakagawa, H. Differential privacy without sensitivity. In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Process- ing Systems, volume 29. Curran Associates, Inc., 2016. URL httpss//ppooeeddngs.rrrrrttt ec ce/paper_fileeeeee a [iappp__ffilee/pppee///00/LLLLL Paper.
Stausholm, N. M. Improved differentially private eu- clidean distance approximation. In Libkin, L., Pich- ler, R., and Guagliardo, P. (eds.), PODS'21: Proceed- ings of the 40th ACM sium on Principles of Database Systems, Virtual Event, China, June 20-25, 2021, pp. 42-56. ACM, 2021a. doi: 10. 10.114552452022334588883 URL https: /doi. 3
Sympo-
pdf.
Stausholm, N. M. Improved differentially private eu- clidean distance approximation. In Libkin, L., Pich- ler, R., and Guagliardo, P. (eds.), PODS'21: Proceed- ings of the 40th ACM SIGMOD-SSGAATTSSIN sium on Principles of Dutabase Systems, Virtual Event, China, June 20-25. 2021, pp. 42-56. ACM, 2021b. URL https:::: //oii. 3458328
Mugunthan, V., Polychroniadou, A., Byrd, D., and Balch, T. H. Smpai: Secure multi-party computation for fed- erated learning. In Proceedings of the NeurlPS 2019 Workshop on Robust Al in Financial Services, 2019.
Sympo-
Nelson, J. and Nguyên, H. L. Osnap: Faster numerical linear algebra algorithms via sparser subspace embed- dings. In 54th Annual IEEE Symposimm on Foundations of Computer Science, FOCS, 2013.
doi: 10.1 10.1145/345202213455333 org /1g/10.. 10
Steinke, T. Multi-central differential
culli--cetraldiffffeeentta privacy, 2020. URL https: http:ss//aaxiv.orrg httpr//ab////000 05401.
Nikolov, A. Private query release via the johnson- lindenstrauss transform. In Bansal, N. and Nagarajan, V. (eds.), Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms,, SODA 2023, Florence, Italy, Jan- uary 22-25, 2023, pp. 4982-5002. SIAM, 2023. doi: URL https://
Talwar, K., Wang. S., McMillan, A., Jina, V., Feldman, V., Basile, B., Cahill, A., Chan, Y. S., Chatzidakis, M., Chen, J., Chick, O., Chitnis, M., Ganta, S., Goren, Y., Granqvist, F., Guo, K., Jacobs, F. Javidbkhht, O., Liu, A., Low, R., Mascenik, D., Myers, S., Park, D., Park, W., Parsa, G., Pauly, T., Priebe, C., Rishi, R., Rothblum, G., Scaria, M., Song, L., Song, C., Tarbe, K., Vogt, S., Winstrom, L., and Zhou, S. Samplable anonymous aggregation for private federated data analysis, 2023. URL https: / //aaiiv... orgg / a abs 2307 15017.
10.1113771978811117755554 doi 111.::..111111.1111111 Pagh, R. and Thorup, M. Improved utility analysis of private countsketch. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 25631 Curran Associates, Inc.,
Upadhyay, J. The price of privacy for low-rank factorization. In Advances in Neural Information Processing Systems, 2018.
2022. URL https::tp///mcc cc/ cc/paper__ae htc/pappe__lllls/pppeeeeeeeeeeee ftteef///pppperr222///eeeee
a47 (77/5ccff11169111199991883333333 pdf.
Patte--Ppprr--aaaaaeeee F... Thakurta, A., and Jain, P. (nearly) opti- mal private linear regression for sub-gaussian data via adaptive clipping. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learn- ing Theory, volume 178 of Proceedings of Machine Learning Research, pp. 1126-1 166. PMLR, 02-05 Jul 2022. URI. //tp:://dr/oceoee/e wwwrroeeeengg......... ngs. ml www.mmmlrrrprrre presss/ v178 //w./aaawneeeaaa.aa/ .tmll.
Sarlós, T. Improved approximation algorithms for large matrices via random projections. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pp. 1433-52,, IEEE Computer Society, 2006. doi: 10.1109/FOCS.200066 URL https://dddt htt//10.110/FFocs.o
Vu, D. and Slavkovic, A. B. Differential privacy for clinical trial data: Preliminary evaluations. In ICDM Workshops 2009, IEEE International Conference on Data Mining, 2009.
13

---

Distributed Differentially Private Data Analytics via Secure Sketching
Wang, D., Gaboardi, M., and Xu, J. Empirical risk minimiza- tion in non-interactive local differential privacy revisited. In Advances in Neural Information Processing Systems, 2a.
A. Differential Privacy Basies
We first define the Gaussian and Laplace mechanisms, which we use later.
Lemma A.1 (The Gaussian Mechanism (Dwork & Roth, 2014)). Let f - RR be a function and let & 2 0 and å E [0, 1]. The Gaussian mechanism adds each of the k components of the output, noise sampled from o?) with
Wang, D., Smith, A. D., and Xu, J. Noninteractive lo- cally private learning of linear models via polynomial approximations. In International Conference Algo- rithmic Learning Theory, 2018b. URL https: /api. semant i wwcccccchhllacccoccoo ar. org/ / CCrpporrrppppccc 6 67856419 9.
o² 2(A₂s)² (1.12//
Wang, D., Hu, L.,, Zhang, H., Gaboardi, M., and Xu, Generalized linear models in non-interactive local dif- ferential privacy with public data. Journal of Machine Learning Research, 24(132)11-57, 2023. URL http: //jmlr. //jmlr.org//////.....///..o http:/ppppss//////// 222222//22222.....2 html.
E2
where A2f max [I f(2')l2 denotes the l sensitivity of function J. The Gaussian mechanism is (e, 6) differentially private.
Wang, Y. Revisiting differentially private linear regres- sion: optimal and adaptive prediction & estimation in unbounded domain. In Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI, 2018.
Lemma A.2 (The Laplace Mechanism (Dwork et al., 2006b)). Let f ; X + R be function and let 2 0. The Laplace mechanism adds to each of the k components of the ouiput, noise sumpled from Lap( Ai f/e), where Auf maxx==)f(z) - f(z') denotes the l sensitiv- ity of function f. The Laplace mechanism is differentially private.
Wang, Y., Fienberg, S. E., and Smola, A. J. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In Proceedings of the 32nd International Conference on Machine Learning, ICML, 2015.
We will use sequential composition of differentially private mechanisms.
Warner, S. L. Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias. Journal of the American Statistical Association, 1965.
Lemma A.3 (Sequential Composition (Dwork et al., 2006b)). Let M, X + V, be an (c,, diffeerrrrrlt private mechanism for i E [k). Then mechanism M X I Y's defined as M(x) = (Mi( Mx(x)) is (> im Es, Ein, -iddffffrrettially private.
Woodruff, D. P. Sketching as tool for numerical linear algebra. Found. Trends Theor. Comput. Sci., 10(1-2):1- 157, 2014. doi: 10. 10.1561/04000000660 URL https: //doi. wellli.orr///oooooo org/ / G. 1561 /4400000060.
B. Frequency Estimation
Zhao, F. Qiao, D., Redberg, R., Agrawal, D., El Abbadi, A., and Wang. Y.-.. Differentially private linear sketches: ef- ficient implementations and applications. In Proceedings of the 36th International Conference on Neural Informa- tion Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871088.
Since Gaussians are popular in differentially private mech- anisms, will describe the parameter choices for this distribution. Let 9: be Gaussian distributed with zero mean and variance o² > 24" 1m(.221/5/88) Then we have F5 = 1x + +g) that Ei Is is Gaussian distributed with zero mean and variance n o² > 24 * (m(1225/)) Thus, assuming a trusted computation of 1T F2 is differentially private estimate of I's with error 24" In(1.25/6)
n.e
+ 9r. We now observe
Zheng, K., Mou, W., and Wang, L. Collect at once, use effectively: making non-interactive locally private learn ing possible. In Proceedings of the 34th International Conference on Machine Learning, ICML, 2017.
5²
We also describe the analogous parameter choices for the Laplace mechanism. Let gi be sample from the distribu- tion defined as the difference between two Gamma distri- butions r 1 22"). Again, we have Fj. 1'(xx" + g)
FA + - E 9I- We now observe that Σ 9 is Laplace dis-
tributed, centered at 0 and with scale 24 e Thus, assuming
trusted computation of 1" g. Fi is differentially private estimate of F& with error 24"
14

---

Distributed Differentially Private Data Analytics via Secure Sketching
C. Sparse Oblivious Subspace Embeddings
Ô [d'e (d'e-Alos log a55aA
dogg-" 3 in both the multiplicative ag
Oblivious subspace embeddings (OSEs) (Sarlós, 2006), al- low for faster approximation algorithms for problems in lin- car algebra. Achlioptas (Achlioptas, 2003) provided the first Johnson-Lindeestrauxs transform with some amount of spar- sity. The first embedding with asymptotically smaller num- ber of non-zeros than dense Johnson-Lindensinn Lindenstrauss trans- forms was probably due to (Kane & Nelson, 2012), who also applied them in the context of subspace embeddings. In a remarkable result, the super-sparse version with only non-zero entries per column, was first analyzed in (Clarkson & Woodruff, 2013) and improved independently in (Meng & Mahoney, 2013; Nelson & Nguyên, 2013), by increasing the target dimension m. In (Nelson & Nguyên, 2013), the transform (Kane& & Nelson, 2012) was studied with a wider range of parameters. Subse- quent works (Cohen, 2016; Høgsgaard et al., 2023) further analyze and improve the relationship between m and s, em- phasizing different parameters. Table 3 provides the exact interplay between and in those works. (Liang et al., 2014) proposes an approach to boost the success probability 3 of an OSE, which gives an alternative to increasing the target dimension.
and additive error. The utility guarantees using the bounds from (Høgsgaard et al., 2023) change only by logarithmic factors compared to those in Theorems 4.3 and 4.5.
D. Privacy Proofs
Proof Sketch of Lemma 3.3. This proof can be seen as anal- ogous to the security proof of Theorem 4 in (Talwar et al., 2023). Recall that each server learns nothing more from perfectly secure multi-party computation protocol other than what is implied by their own input and the output of the function being evaluated. Then there is simulator R.IIIA Scor whose output is (E, 6) indistinguishable RtIIIAA from the adversary's 's view View Seor.Cear (z)). Note that the secret shares that are part of the view the corrupted servers in the protocol are independent of the input values of the corrupted clients, and all can be easily simulated by random sampling.
sparse
A bit more formally, let x be an input dataset, where æ; is the input value contributed by client and ã; is the vector of input shares for server that serves as input to II. There is a mapping from x E X to I E E Denote X = {=x beC.. and X" fa')eec... Then for any two datasets x, x' that differ in one entry x; with i & Conr:
When dealing with rank approximation, we will condition on
as]]s - AXX 13 < |SAA - AXX* I -
S (1 as) - IX
Pr|View R.I.AA
(x) E1
Scor Ccor
< ProSimscordae Coon (J(R(Z1)...... R(an), E ES]
R.H.A.
for all rank is orthogonal matrices X. When dealing with regression, we will condition on
S e Pr(Sim R.I.A.
(f(((z)),... R(2,)),,,,,,)), X') E 5 +8
Scor, Genr
(1-as)lAAx b < |S(AA - -b $ + ass)llXX''- - bbl2
= e Pr(View Soor Coor (x E 5)
R.I.AA
for all x Rdd For the parameters given here, this is true with the probability given in table 3 (assuming k: d in the case of teggeession.. For the case of regression in particular, it is sometimes beneficial to select o:s as large as possible. A sufficiently largest value of ag such that S still provide a subspace embedding guarantee is 1/3. Throughout this paper. we will sometimes bound ag by 1.
Lemma D.1. Let (0,1), and let S ~ Deketch Then
the probability that S has at least (1 - 7) nn and at most (1 +1)) m. non-zero entries in every row is bounded by;
Pr( E [
X
7
< 2m exp
2n
2m
We further will give our utility proofs using the spar- sity/target dimension bounds from (Cohen, 2016). Other tradeoff's are possible, but they have worse bounds for most ranges of parameters. The results in (Meng & Ma- honey, 2013; Nelson & Nguyên, 2013; Høgsgaard et al., 2023) give different trade-offs depending on which set of parameters are considered the most dominant. No- tably, the s = 1 sketches of (Meng & Mahoney, 2013: Nelson & Nguyên, 2013) result in an additive error of Ô K4 -2 log }) for low rank approximation and term a33ze
where X, denotes the number of non-zero entries in row i.
Proof. We only give a proof of the lower bound, as a proof of the upper bound is completely analogous. Let X.j denote the indicator random variable that is 1 if Sij is non-zero and ( otherwise. Note that each entry of S can be thought of as an independent Bernoulli random variable Xuj. and the number of non-zero entries in a row is the sum of n of these random variables. Fixing a row E [m]. we can use a Chernoff bound for sums of Bernoulli random variables to
15

---

Distributed Differentially Private Data Analytics via Secure Sketching
Table 3. Tradd-off between the target dimension m and sparsity of sparse OSEs that are generated such that they have non-zeros entries per column. Here a denotes the accuracy of the OSE and / denotes its fail probability. Variable & is the parameter to k-rank approximation, which can replaced by dimension d for linear regression. The paper by (Achlioptas, 2003) was the first to propose the construction, while its application to preserving subspaces was given by (Clarkson & Woodruff, 2009). Paper
Target Dimension m
Sparsity s
With Probability
(Achlioptas, 2003)
0 k+ log 17B)
m
B
(Nelson & Nguyên, 2013)
O a 0 k (log(k/
1 - B
(Cohen, 2016)
O (og(k//3)
1 - B
(Høgsgaard et al., 2023)
0
0 ( (1/a) + 12// log (k)))
1 2 A2/3
get a concentration bound around the expected number of non-zero entries X2 = Σj=1 Xay in row k. In order to do this, we first need the expected value of Xx:
then the Ro outputs 04, which is entirely independent of the input and is therefore (s, 6) differentially private.
Otherwise, M(A) = Ts( RD (at)aaa.....Rlll Rp(a.)) )) = S(A+ + G) where a, denotes row i of A Raxd and G t D and we now prove that this is (c,5) differentially private.
B[Xx]
Σ
Pr(XXs 1)= m
Note that S, + G) is a d-dimensional vector, when S, refers to the i-th row of S. If (S.(A + G)); is (E/d, 6/d]- DP, then sequential composition (Lemma A.3) gives that M is (s, 5) differentially private.
Thus a Chernoff bound gives us that
Pr (xxx < (1-7)
n2
2-n
<
exp
m
2m
Now consider d and let mechanism M1 : E. + R be defined .M (a) S(a + g) for a E RP, with g D
Applying a union bound over all rows of S then gives us exactly what we were to prove;
S is sampled such that it has only one non-zero entry per column; thus, the columns of S are orthogonal. This means that the entries of (S(a + g)), and (S(a + g)), for j # j', have disjoint support. Therefore, the privacy guarantee can be analyzed independently for each entry of S(a + g).
Pr P3(E [m] : X; < (1 - -7) n
mm) m
Σ
Pr
Xx < (1 - 7) mm
k=1
Denote by E the event that the support of S(a + g)3 has at least z-t' uncorrupted clients, whose set of indices we 2m
72n
< <meepp
2m
(Sa), + (Sg); = (Sa), + Σne(m) S,,akk = (Sa); + ExEN Sy + Σ L Sy.akk. Also note that ΣLEN Sj,ak contains at n=t least 2m terms in event E, the sum of which suffice for guaranteeing DP.
denote N. We can formulate S(a+t),
To prove Theorem 3.4, we first prove a simpler version of the theorem below.
Lemma D.2. Let E 2 0.8 8 E (0, m E [m]. t' < n. Let S Deketch with one non-zero entry per column. m.
Due the fact that D is symmetric, -1 gg follows the same distribution gx. and ΣKEN SJ,.8e follows the same distribution as Ee gs. Due to the infinite divisibility of D', the sum of the first n-t' terms of ΣREN ge are samples from D'.
Also let gs D be samples from a distribution such that E)e((n-()((mm)) 9h- G. G follows a distribution D' that defines an additive noise mechanism that satis- with +8)/8m))) for function Dm on input A E Raxd where the subscript refers to one column of SA. Then as long as input values are bounded above by n, tuple of algorithms (RD, Ts. A), as defined by equations 2 and 3 and for any A, is (c, -iiffferretti private in the trusted computation model for differential privacy with l' corrupt clients.
2m
fies (s/d, 8/d m exp(-(rr - -t')
f(A) (SA);
Then in event F., MI is (e, - m mexp(-(nn (()/8m)) differentially private using the additive noise mechanism that adds noise from D'. Setting 7 = 1/2, Lemma D. gives that E occurs with probability at least 1 mm exp( =-(") ). Sm
Since event E does not occur with probability at most m mexp(-(n - (')/8m), Mi is (e,ō - m exp(-(n t')/8m))) differentially private except with probability m exxp(-(n - t')/8m). Then Mj is (E, diifferrrrtl private.
Proof of Lemma D.2. Let e, 8, RD and T3 be given as de- scribed in the theorem. If 5/d S mexp(-(n - t8)/8m),
16

---

Distributed Differentially Private Data Analytics via Secure Sketching
Lemma D.4. Let E 2 O, 8 E (0,1), m E [n], < n. Let S (-1, O, 1lnxn with one non-zero entry per col- umn and n/m non-zero entries per row. Also let noise gs be sampled from symmetric distribution D such that / 9i = G. G follows distribution D' that de- fines an additive noise mechanism that satisfies (E/d, 8 //d.- DP for function f(A) (SA), +n with
Proof of Theorem 3.4. Let E, 6, RD and Ts be given as de- scribed in the theorem. If 8/d Σ m mxxxpp((n- then the RD outputs 04, which is entirely independent of the input and is therefore (e,6) differentially private.
/8)),
Ts (a,))) V ExE(e) S2(A + G5) where a, denotes row i of A E Baxd and G; + Drxd_ Here, S has been decomposed
Otherwise, (M(A)
Dmm on input A E Baxd, where the subscript refers to one column of SA. Then as long as input values are bounded above by 1, lu- ple of algorithms (H .ss, A). as defined by equations I and and for any A, is (..-)))eeefet private in the trusted computation model for differential privacy with t'.
such that S = - Σ: St, where S, E {-1,0,1) 1) m is a matrix with only one non-zero entry per column.
Vs
We argue (e/s, --D based on Lemma D.2. Note that the non-zero entry per column in each S, is not sampled uniformly at random from all possible rows; rather, for S, is sampled uniformly at random from the remaining n n-i (removing the one that was already chosen to be non-zero, sampling without replacement). Therefore, we replace n. with n when applying Lemma D.2.
Proof of Lemma D.4. Let E, 5, Rehonse and Ts be given as described in the theorem.
We show that M(A) Ts Ts((R())),.... R(an)) S(A + G) where a, denotes row i of A E Runxd and G t- Daxd, is (s, 5) differentially private.
By sequential composition, releasing S,(A + G.) for all i E [s] satisfies (e, 6)-DP, and thus by post-proceess posst-rocsssing the scaled sum of these also (c, 5)DP.
Note that S, + G) is a d-dimensional vector, when S, refers to the i-th row of S. If (S, + G)), is (c/d, 8/d)- DP, then sequential composition (Lemma A.3) gives that M is (c, 5) differentially private.
Corollary D.3. Let 2 O, 8 E (0. E' < n. m E [n]. E [n] and D be the Gaussian distribution ((0 od) with:
Consider d = 1 and let mechanism Mi R" + R" be defined as MM (a) S(a + g) for E R", with g + D
o² n/ (112.25s/ (b/d d m mxpp (n-o-1) md
(n 10-1" 1')
S is sampled such that it has only one non-zero entry per column; thus, the columns of S are orthogonal. This means that the entries of (S(a + g)), and (S(a + g)), for j # j'. have disjoint support. Therefore, the privacy guarantee can be analyzed independently for each entry of S(a + g).
Let S Dekketch. Then as long as input values are bounded above by y, tuple of algorithms (Rd, Ts, A), as defined by equations 2 and 3 and for any A, is (e, 8) -'ddifferentially private in the trusted computation model for differential privacy with l' corrupt clients.
t' Note that the support of S(a + g)z has at least uncorrupted clients, whose set of indices we denote N.
Proof of Corollary D.3. We apply Theorem 3.4, setting D) to Gaussian distribution with the variance specified in the corollary. First note that zero-centered Gaussians are sym- metric around the origin. Due to infinite divisibility of Gaus- sians, -e((nn---)//(m)) 9i = G when g; D is Gaus- sian distributed with variance Eie((e--(11/2m)) o² (2mm) (2m)
We can formulate S(a + g); = (Sa); + (Sg), = (Sa), + Σke(H) Sy.RBI = (Sa); + > Sznge + EREEMJNN Sj,K8.-
Due to the fact that D symmetric, -1 ga follows the same distribution as gk. and ΣKEN Sj.ag follows the same distribution as ΣtEN gk. Due the infinite divisibility of D', the sum of the first a t' terms of Σven Bi samples from D'.
(n- (n-s-th t''o"" t')a²
Notice that the l fz-sensitivity of algorithm Ts is A2Ts maxA.A
|| |SA SA'll2 = 2 where A' E Raxd
Then Mi is diiffediifrrtentialll private.
differ single row, and every entry of A, A' is bounded above by 17.
Based on the Gaussian mechanism (Lemma A.1), the ad- ditive noise mechanism adding Gaussian noise satisfies (e/(sd), (odd),//(st)) 5/(sd) - m exp(-(n (n - (t-)/-mm)) tion f(A)= = (SA), + n with n ~ Lap 2mm2dd/e"" on input A E n where the subscript refers to one column of SA.
Proof of Theorem 3.5. Let e, 5, Regess and Telense be given as described in the theorem.
for func-
We know M(A) = Ts Rp(()) fm EiEmi S, G,) where G, + Daxd. Recall
from Equation 3 that has been decomposed such that
17

---

Distributed Differentially Private Data Analytics via Secure Sketching
- E. S,, where S, E (,1,0,1) mx is a matrix vm with only one non-zero entry per column and n/m non-zero entries per row.
Moreover, with probability at least 1 3
|GI s.. o² nn d. log 1/3.
We argue (e/s,6/s) 3/D) based on Lemma D.4.
Proof. Denote by G, the ith row of G. We start by ob- serving that G. x is Gaussian distributed with mean 0 and variance o² ||x| Thus, we focus our attention con- trolling ||Gx] []|]] that is, we assume that x is a unit vector and that the entries of G are standard normal Gaussian ran- dom variables. The overall claim then follows by rescaling, Consider an E-net N₂ of V, that is, for every x E V with unit norm there exists a vector x' E Nr with |x - x'1 S 8. Such nets exist with |AV,,] S exp(1) llog 1/7) for some absolute constant 7/. see (Pisier, 1999). Suppose Y 1/4. Using concentration bounds for sums of Gaussians (see for example I Lemma 1 of (Laurent & Massart, 2000)), we then have for any ||="|| with probability 1 -
By sequential composition, releasing S; + G:) for all i [s] satisfies (e, ()-P), and thus by post-processing. the scaled sum of these is also 5c.5)
O
Corollary D.5. Let E 2 2, 0, n, m E [n], s E [n],
and let D be the distribution formulated as the difference of two samples of gamma distribution [( mn/mme b) with parameter
b= 1=22mm²d/E
Let S ~ {-1,1]mxn sampled uniformly. Then as long as input values are bounded above by n, (Ref .Ts, A) is E-differentially private in the trusted computation model for differential privacy with t' corrupt clients C².
P 3x' E N₂ Gx' 1| [x|]
2 2( v (log N, + log 1/3) n + (log N₂ + log 1/3))] $ Nyy exp(-(n k + log 1/3) S B.
Proof of Corollary D.5. We apply Theorem 3.5, setting D to the difference between two samples of the gamma dis- tribution [( - 2nmmdd/=).. Note that the resulting dis- and symmetric. Due infinite divisibility of Laplace distributions, Eie(n/m-e") 9:- G when gi D is Laplace distributed with mean zero and scale parameter b- = 21pndd/e.
for some absolute constant 1/.
tribution is centered
We now extend this argument to all vectors, using an ar- gument from (Arora et al., 2006) (Lemma 4 of that ref- erence). Let U be an orthogonal basis of V. Then our goal is to control ||xx|2 = x"U GUz. Define the matrix B == UTG GU - n II where is the iden- tity matrix. Note that B|U" Bx|| is the deviation of |Gx|| around its expectation. Let B Bloop == suPxev |
Notice that the l--seiiitvv of algorithm I's is A,T's = maxA.A || - SAIlI1 = 2mm, where A, A' E Raxd differ in single row, and every entry of A, A' is bounded above by r7.
= n I and that
Based on the Laplace mechanism (Lemma A.2), the ad- ditive noise mechanism adding Laplace noise satisfies e/dm)-DD for function f(A) = (SA), + n with n ~ (O, 2mmmdde)"" on input A E Raaxd where the sub- script refers to one column of SA.
B lop = (Bx, x) = (Bx', x²) + (B(x's + x), x' x)
<2( (log No. + log 1/3) + (log No + log 1/3))
+ BBlop' ||x' + x|||Xx xx|
2 V (log No. + log 1/3) n + (log No + log 1/3))
+ 27 -|B|pppppp
< 2(1 v (log Nv + log 1/3) - + (log Ny + log 1/3))
E. Utility Proofs
+ 1/2. |Bllop
Lemma F.1. Let G Raxd such that all entries in G are independently sampled from normal distribution with mean 0 and variance at most o². Further, let V be set of d- d-dimensional vectors lying in a k-dimensional subspace.
Rearranging
implies that |
4( ([log N. + log 1/8) + (log NN The first claim now follows by rescaling 77.
log 1/3)).
Then with probability at least 1- - B for some absolute con-
stant 1)
For the second claim, we observe that ||G|] has Gaussian distribution with mean 0 and variance d o². The same concentration inequality we applied above also implies that the probability that ||G]| exceeds 2 o02 n d log 1/3 is at most -
sup || G I n-ndd o². ||x|2 + 77. 0² ||x
XEV
(V (k log 1/3) n + (k + log 1/3)).
18

---

Distributed Differentially Private Data Analytics via Secure Sketching
Proof of Lemma 4. 1. We first argue that G is Gaussian dis- tributed. Each G2 has independent Gaussian entries and multiplying& Gaussian with random Rademacher does not change the distribution. Therefore, the entries of S,G, are likewise Gaussian distributed, with mean O and variance at most (1++) " o² 2 m.
Proef of Theorem 4.3. We will use the following inequality, The applications to vector and matrix norms are straightfor- ward corollaries.
m o due to Lemma D.I. Concluding, the variance of the entries of G Eie(s) S,G, is therefore at most 2s o². Applying Lemma E, we then have with
Lemma E.2 (Generalized Triangle Inequality (Becchetti
et al., 2019)). For any two real numbers a, b and any 0
probability 1 -
|G S =02 |x|| + +1 28 00= 2 ||x|2
sup xEV
(1 (1+ )) -a (a- b)2.
m
m
aa2 - 1 S a. a² +
(V (A: log 1/3) + (R: + log 1/3)).
and
Finally, we require the following consequence of subspace embedding properties.
|G|| n. 2sno d. log 1/3
as desired
Proof of Lemma 4.2. We have ||]L max]e|m] F. thus it is sufficient to give high probability bound on ||,,,
Vm
Lemma E.3 (Paraphrased from Definition 1, Lemma 11, and Theorem 12 (Cohen et al., 2015)). S be drawn from an OSNAP distribution. Then for any matrix A E Raxd and any rank k orthogonal matrix X Baxk we have
The entries of S,T, are Laplace distributed entries with mean and scale parameter by infinite divisibility of a Laplace random variable into distributed random variables. Thus the expected value of | is md 212.
|SA - -
|A -AXX" Ip
To prove high concentration, let us consider the moments of the Laplace distribution. For a Laplace random variable L with mean 0 and scale b, we have E[[,22] = (2f) Then due to Hoelder's inequality
Without noise, the low rank approximation outputs Xorr
argminx makk R, A AAX" ||: and after sketch- ing with Gaussian noise of variance o² outputs X' argminx rank kx || A G) (A + G)XXT| Let X' be the matrix returned by the mechanism. We have
md
E
|SD
=E
Σ
L3
t-1
md
md
<
!
I
A - AX'X IF
= (20)1bbe
(md)
S (1 <11
Σ ESA S.A .E(s)
SAXX'
Applying Markov's inequality, then have for any 7 >
P 113 7 md- 26
S (1+
-P || 11: > (7 md. 2
Σ KE(s)
S + - S -AA+A))X))''''
(26) (md)e (2
(7 md 2b (27))
(26)28
+ (1 + as) as)
S.G. S.G.X'X Σ KE[
< (2 Vorl
log 3. this term is at most 3/m. We can therefore conclude that with probability 1 3, max:e[m] S,T, < 4 4og m and thus |L| < 3 nym2 log² m for some absolute constant 7). 3.
For 7 > 462 and
where the first inequality follows from the subspace em- bedding property. By optimality of X' for the low rank approximation problem on Enejal S, A + Ga), we then
LI
19

---

Distributed Differentially Private Data Analytics via Secure Sketching
have
|| AX'X 11 $ (1 + og) | XX
J - AX'XII
1
S (1+as)
+ 11 /
02 o2.n.. nn. d.0o
Σ KE($]
S + G:) S. + G;) X
$ +1+ +1+3aa))14 AXorr 11
1id3/2
+ Ô
log 20 (1/3)== (1g
o
1
+ +1+
Σ
S.G. S,
The stated bound follows by rescaling as by factor of 3.
|E[s]
$ (1+ ag)²
X
Proof of Theorem 4.4. The proof follows the same line of reasoning as Theorem 4.3. The main difference is that upon [ieetm S.G. vss
+ +(L+as)1
Σ
S.G, - XoP
X
EE(2)
F
reaching Equation 6, we must bound +
via Lemma 4.2 rather than using Lemma 4.1. Assum- ing the semi-trusted corruption model with at most t cor- ruptions, each entry of G, consists of X; Yú where X,.Y, ~ r(1/(n - t), b). Consequently, the entries of Eie(m) S.G, are a sum of m- m
+ +1++as)
Σ iE
S.G. - S
n-t matrices where each entry is either 0 or a Laplacian distributed random variable with mean 0 and scale b. Using Lemma 4.2, we therefore have with probability 1 3.
where the inequality follows from Lemma E.3. Now notice that I XOr and I - XTX'T are orthogonal projec- tions, multiplying by which cannot increase the Frobenius norm of matrix. Therefore, for X X' or X Xorri
Σ S.G. |E(m
Σ [E(+)
S.G. - S,G,XX
s
E O((1) mm²
db² log
2 m
n-t
|
E 0(1) .m² dbb log
2 m
Σ S,G,(I-XX)
Σ S.G.
B
iE(4]
iE(+]
where we used n S 2 by assumption. Since S is dense n Rademacher matrix, we have k+log (Achlioptas,
"
Then:
2003; Woodruff, 2014) and s = m. and b 2nm d/s following Equation 5.
|A - AX'X 1FF
Thus we obtain, with probability - 3, a (1 + as) mul- tiplicative approximation using the same calculation as in Theorem 4.3 and a suitable rescaling, and additive approximation.
< (1 + ag) |
XorrxXorrll
0 2/2 E log ag.
+ (1 + as)2-
Σ S,G
(6)
[E(s)
Proof of Theorem 4.5. Let E, 8, RD and Ts be given in the theorem. We consider the output (Ts((D(()))) ..., RD(an))).
Using Lemma 4.1, we have Everar S.G. I|=
2n
In < 8m (n(m//5)) + t', then the RD outputs 04, then the optimal x' = 0d, leading to error || - bll + >||x'||
σ². llog11/3). To simplify the error, observe that for the sketching matrix by (Cohen, 2016) (see Table 3), we set log( (1)3.. Using the bound the variance from Theorem D.3 and plugging this in above, we can simplify the additive and multiplicative errors.
& and m &logk os
|b|² s 1 S 1/ n/min( (dmm/m))) +t'
og
Otherwise, M(A)
(a)) Je Eiets) ( + G.) where a denotes row of A
20

---

Distributed Differentially Private Data Analytics via Secure Sketching
Raxd and G Ni o200022axd is (e,6) differentially pri- vate.
which likewise implies
To streamline the presentation, we give the analysis without corrupted clients. Adding corrupted clients merely changes the analysis along the same lines as Theorem 4.3.
|x'|| -
1 8
Σ
S:((A + G;)xOPT - (b + g:
KE[A]
A
|| ||?
We first the control the terms || Eie(s) S; - -g:)ll and | Xo, - 1:) Using Lemma 4.1 with an added coordinate of 1 to both x' and XOPT, we get
Insertion both bounds back into Equation 9, we obtain
1 ( -:)1 S n. onndlog log 3 iE(s]
Σ
[||x|] +1) (7)
|Axx bbl + A112111
S (1 + +
for either x = XOPT or = x' and for sufficiently large constant 17. Then we have using Lemma E.3
1 Σ Si((A + G.)xorr (b + g.))ll + Al|xOrT 1|?
VE|e]
||Ax' - b1l2 + 1112'112
++ 1
1 no poondlog
no²nd log R
+ 2
+2 1+
$ (1 + ass) (aass||((A SSAxx - -b]1 + 111='112
as
3
as
=(1 +
a1s) - Σ
(Ax'' + A||2'|1
(10)
iE(a]
Σ
S.((A + G.)xoPT - (b g:)
=>1|='113 + (1 + as)
|1 Σ (2 + G. -G, - -b- b.g. -1)
+ A |
(1I)
VE[A]
<(1 + as) aas)
1
We turn our attention to |Eess)) S.((A + xo)xoPT
(b + ):)) Using Lemma E.2 and Equation 7, we have
(1 + as)ll
Σ
S + G - (b + g:))
1
S + G.)xoor (b + g.)))l + X ||xOPT||
:E(s)
+ 11 1
11 Σ
S -B:JIP) + +1112112
as
<(1 + ag) -
Σ
St S: -)12
sE(o]
(
<(1+as)
Σ
S((A+ + G;)x' - (b g:)l
+ (1 ag
1
S, - -g:) + A |Xorr||2
iE|s
AE(+]
(8)
<(1 + as)²
| bl22
1 - go 1 as
+ + 1x-12113
+2. (1
(1xx111
+ 1)
+ 11 1
11 nod log 1 [|xorr]]]]] 1|2 + 1) + A||XopT|| 3
as
(9)
<(1 + ag)²
(llAxor b112 >||XXPT|| 1?)
where the second to last inequality follows by applying Lemma E.2 and the final inequality follows from Equation By optimality of x' for the instance 1 Exe(s) Sa(Ax' +
+ 1
1
nnd log
1
(> | 112 + A)
as
1
nd log 1
< (1 + as)² + 11
G, -bb (b))):))1 + A||ad I2,, we then have
as
X
[| -bll² + > 1| (12)
(b g:)11 + A ||x'||
+ (1+ -1 no 'nd log
1
as
3
1
Σ *E|s)
S.((A G.)XOpT - (b (b+g:)1 12)11)1 + A |
Inserting this into Equation 11 and collecting all the terms,
21

---

Distributed Differentially Private Data Analytics via Secure Sketching
we obtain
shuffle model in more detail in Section 3. For the prob- lems we studied here, there is an abundance of prior work discussed follows.
|| Axx bl2 + 1
32 nopnd log
2
no log 1
+
(12)
as
as
A
There are various ways in which one could formulate the low rank approximation prob- lem. The setting which is most important to is the seminal paper (Dwork et al., 2014), who achieved a worst case ad- ditive error of the order kv for outputting an orthogonal projection matrix V& in the row space of A. This bound is also optimal. In the local model where each client holds a row of the data matrix A, and we wish to output an orthogo- nal projection in the column space of A. (Upadhyay, 2018) gave algorithm with an additive error of the order vn. which matches the lower bound by (Bassily & Smith, 2015) up to lower order terms. This is different from computing a projections in the row space of A considered by (Dwork et al., 2014) and indeed our own results. The only know local algorithm to do likewise in the local model is due to (Arora et al., 2018), with a substantially larger multiplicative and additive error compared to our results. To the best of our knowledge, no single round shuffle protocol improving over the local bounds is known.
Low Rank Approximation:
+ (1 + as)*)) (1))))))
(1) (IAxorT- - bll² + +-Al|xor \||xoprl|?)
noondlog 1
2 noonnd log 1
32 + os
2
os
By our choice of 0² from Theorem D.3 and using the sketching matrix of (Cohen, 2016) (see Table 3), we have g² n E Old log' d ag" log 3 -og }). Thus, we have
||Ax - b112 + 1112211
< <(1 A||OO bll² + \||xorr||% 113)
1+ 15ag
d a'g log" 1 B x- log 1
+
8
Low rank approximation and its sister problem PCA, have seen substantial attention in settings more loosely related to our work. Much of the work on private low rank approxi- mation (Blum et al.. 2005: Chaudhuri et al., 2012; Dwork et al., 2014; Hardt & Roth, 2012; 2013; Hardt & Price, 2014; Balcan et al., 2016; Kapralov & Talwar) considers the data to be fixed, often using Gaussian noise. In addition, a strong spectral gap assumption, typically of the form that the first singular value is substantially larger than the second, is cru- cial to the analysis. We note that all algorithms operating with this assumption do not yield worst case bounds.
A
(aag log
E 'log2 8
+
2
d aag g
log"
1 8 E log
+
x
d aa
10 log
B 8 log²
8-11lo""
8
+
2²
When there is no spectral gap, we compare to the central model exponential mechanism approach from (Chaudhuri et al., 2012), implemented by (Kapralov & Talwar). (Liu et al., 2022) also provide a solution to this problem; however, it is unfortunately computationally intractable.
Note that we can get a constant multiplicative error as long as the regularization factor X depends on sufficiently large polynomial in d, while being independent of n. Generally such a relationship still has good generalization properties when training a regression model. If X is sufficiently large, one should choose ag to be as small as possible, minimizing
Ridge Regression The previous work most related to ours is due to (Sheffet, 2019). The author gave a mechanism that preserved the entire spectrum of a data matrix in a private manner and also showed that the returned regression vector x is close to the optimal x assuming that the matrix is well conditioned.
the tradeoff between og and _ If À is not sufficiently large, one should choose 0g = 1/3 such that S is an obliy- ious subspace embedding, but the target dimension does not have a prohibitively large dependency on the sketch distortion.
Most previous work (Kifer et al., 2012; Cai et al., 2021; Bassily et al., 2014; Wang et al., 2015; 201 8a;;; 2023; Wang, 2018; Varshney et al., 2022; Milionis et al., 2022; Liu et al., 2022; Zheng et al., 2017) study private linear regression in the context of risk minimization, where the algorithm is given i.i.d. samples from some unknown distribution and
F. Related Work
There is substantial work on the shuffle model, which also aims at facilitating differential privacy in a distributed set- ting. We discuss the relationship between the LTM and the
22

---

Distributed Differentially Private Data Analytics via Secure Sketching
aims at computing a solution with good out of sample perfor- mance. Even without privacy constraints risk minimization yields additive error that depends on Another line of work studies varies loss functions, including regression in a Bayesian setting (Minami et al., 2016; Foulds et al., 2016; Dimitrakakis et al., 2014). We are not aware of any prior work on linear regression in the local DP model.
popular and easy use MPC framework, for multiple com- binations of and 8, using S servers from Amazon Web Services 13. la.e instances. We use additive secret sharing over the ring of integers modulo 2 which results in no communication between servers, and semi-honest security against an adversary that corrupts all but one servers.
We fix the dimensionality d = 10 and m
50, and vary the number of clients n E {100000, 250000, 500000, 750000, 1000000), the sparsity 8 E {1, 11,10, 20, 30, 40, 50} of the sketch (which dictates how many linear transformations we need to apply) and the number of servers 5 E (2,3). The data matrix A is generated at random such that all entries are smaller than 232 and the decomposition S S, of some sketch is generated according to our mechanism. Every parameter setting is then evaluated by running the protocol 10 times and averaging over the running times. Table 4 shows the runtime for each server and the total communication load for one particular combination of parameters, which includes three servers: Even with one million clients, the computation on each servers lasts less than seconds. We conclude that the use of MPC in the LTM does not hinder the computational efficiency of our proposed mechanisms, showing that they can easily be used in practice. Table 5 reports communication and time required when running the protocol with two servers, and Table 6 reports time and communication requirements when varying s.
DP via Jobnson-Lindenstrauuss Transforms. The LandsonnLindenstrauuss lemma has been previously used in differential privacy. (Blocki al., 2012) studies the DP guarantee JL transform itself gives in the central model, in the context of cut queries and directional variance queries. (Kenthapadi et al., 2013) and (Stausholm, 2021a) use JL transforms together with Gaussian noise in the context of DP Euclidean distance approximation, to decrease the error. This was subsequently improved in (Stausholm, 2021b), using Laplace noise. The difference to our work that the transform is used to reduce d instead of n. by having every client apply it locally before adding noise. In (Nikolov, 2023) the authors make use of JL transforms to achieve private query release, by applying it before releasing a bundle of queries. (Ghazi et al., 2023) studies pairwise statistics the local model of differential privacy and uses JL transforms to reduce client-sided dimensionality.
Differentially Private Non-Oblivious Sketches. Non- Oblivious sketches, such CountSketch, have also been used in combination with either distributed or central DP. (Zhao et al., 2022; Pagh & Thorup, 2022) provide an analy- sis of differentially private CountSketch in the central model. (Melis et al., 2016) consider differentially private CountS- ketch and Count-Min Sketch in a distributed setting, but they reduce the dimensionality of each input, which can be done by users locally, rather than reducing the dependence on the number of users, as we do.
Table 4. Computation cost Ture and communication cost CAre of the LTM using MPC for varying number of clients n. Here m 100, d = 10, 8 and we are working with S = 3 servers.
n
TMPc (sec)
CMPC (MB)
100000
0. = 0.019
24.024
250000
0.457 : 0.058
60.024
500000
0.861 = 0.102
120.024
750000
1.219 + 0.128
180.024
1000000
1.641 - 0.165
240.024
G. Experimental Evaluation
Find here more in depth descriptions of the experiments we carried out. Section G. provides the running time experi- ments and in Section G.2 we discuss our utility investigation both for ridge regression and low-rank approximation.
Table S. Computation cost TMPC and communication cost CMPC of the LTM using MPC for varying number of clients n. Here m = 100, d = 10, 8 = and we are working with S = =2 servers.
n
TMPC (sec)
OMPC (MB)
100000
0.177 + 0.028
16.016
G.1. Running Time of LTM
250000
0.453 + 0.036
40.016
As mentioned in the main body, the only overhead of the LTM over the local model the execution of the linear trans- form in MPC, and comes from distributing A + +G, E Roxd among the servers for i E [s] and then performing matrix multiplications S, ( (A+ + G.) in MPC, where Si...., S, is a decomposition of some S E mxx chosen according to (Nelson& & Nguyên, 2013; Cohen, 2016) with sparsity s. We implemented our approach in MP-SPDZ (Keller, 2020), a
500000
0.824 = 0.101
80.016
750000
1.240 + 0.157
120.016
1000000
1.683 + 0.130
160.016
G.2. Interpolation between Local and Central DP
In contrast to the central model of differential privacy, the performance of differentially private outputs in the local
23

---

Distributed Differentially Private Data Analytics via Secure Sketching
and locally private algorithm, our LTM model approach adds Gaussian noise sampled from A o²) to every entry of A and b. Our choice of o² is proportionate to varying powers of n P, ranging from p = 1 (the LTM model) to = 0 (the local model).
Table Computation cost Ture and communication cost CMPC of the LTM using MPC for varying sparsity s. Here m = 100,
10, n 500000 and we are working with S 3 servers.
TMPe (sec)
CmP (MB)
1
0.851 = 0.099
80.016
10
6.863 + 0.388
800.016
We generate synthetic data by first sampling every entry in A from (00 1), then sampling XorT such that all entries are sampled from /V N/O, p²), and finally setting b = AXOPT- We vary parameters d E {3, 10, 50), E {0.01, 0.03, 0.05, 0.13. À E {1, 100), and n² E n2,,,n²). For all combinations of those parameters, we generate 17 syn- thetic datasets of sizes (1000) = O,.... ..)) For each of those we then measure & for the SSP mechanism and the Gaussian mechanism with p E 0.9, 0.8, 0.7, 0.6, 0.5, 0), by running the algorithms 30 times per dataset and reporting the average d.
20
13.002 + 0.445
1600.016
30
20.356 + 1.171
2400.016
40
28.023 = 0,660
3200.016
50
33.708 + 1.384
4000.016
model decreases with increasing number of clients n. For regression and matrix factorization problems, our theoretical results for the LTM and the Gaussian mechanism suggest that this performance decrease can be avoided without sacri- ficing privacy under reasonable assumptions. It is natural to ask for which parametrizations of the Gaussian mechanism the performance remains acceptable. If more noise still yields good performance, we can tolerate more corrupted clients. Therefore, we evaluate empirically how the error of ridge regression and low-rank approximation develops as n grows in practice and against synthetic benchmarks.
Real-World Datasets In addition to synthetic datasets, we also evaluated our mechanism for ridge regression on 4 datasets marked suitable for regression the UC Irvine Machine Learning Repository. The following table provides their number of entries and dimensionality d. A more thorough description of the datasets is found below the table.
The experiments described here thus aim to demonstrate that, as the number of clients increases, the asymptotic error of differential privacy mechanisms in the LTM is between the error in the central and local models.
Dataset
72
d
Power (Hebrail & Berard, 2012)
2049280
6
Elevation (Kaul, 2013)
434874
2
G.2.1. RIDGE REGRESSION
Ethylene (Fonollosa, 2015)
4178504
18
Songs (Bertin-Mahieux, 2011)
515345
89
We here investigate the error for the ridge regression prob- lem due to its wide spectrum of possible error bounds from Theorem 4.5, depending on problem parameters, as well as due to its singular dependency on a multiplicative error. Therefore, we use approximation factor as an error measure:
The first dataset consists of electric power consump- tion measurements in one household (Hebrail & Be- rard, 2012) and the feature we try to predict is sub gub.metering in..3. We ignore the date and time fea- tures and the data points that had missing values. This leaves us with 6 features (plus the one we are predict- ing) and 2049280 data points.
|Ax'= - b + X||x1|1 AxorT - b + X| XOPT
where XOPT denotes the optimal solution and x' denotes the solution after adding noise to the training data.
The Elevation dataset (Kaul, 2013) consists of 434874 open street map elevation measurements from North Jutland, Denmark. We predict the elevation from the longitude and latitude features.
We evaluate the error for synthetic datasets, as well as for four real-world datasets. It is not possible to interpolate between two different datasets in order to gain insights into asymptotic behaviour. For synthetic datasets, varying the number of sampled points allows us interpolate between datasets of different sizes. Real-world datasets are useful to gauge the relative performance of our mechanisms, and to benchmark our synthetic datasets against the behavior of the mechanisms in practice.
The Ethylene dataset (Fonollosa, 2015) contains record- ings of sensors exposed to mixture of gas. We trained on the part where the sensors were exposed to mix- tures of Ethylene and CO in air. The feature we are predicting is the last one TGS2620, which leaves us with = 18 and n = 4178504.
Setup. As a baseline for the central model, we imple- mented the so-called Sufficient Statistics Perturbation (SSP) algorithm (Vu & Slavkovic, 2009). Operating between SSP
The Songs dataset 89 audio features that are meant to predict the release year of a song.
2011), consists of
24

---

Distributed Differentially Private Data Analytics via Secure Sketching
Software and Hardware All in the main body described mechanisms, are implemented in Python 3.6.9 making use of numpy. Experiments were executed on an Ubuntu 18.04 LTS machine, with an Intel Core 17-10510U CPU clocked at 1.8GHz and 16GB of RAM.
Theorem 4.5 improve with increasing X, they do not affect the dependency on Thus, we view the experiments as confirmation that the theoretical bounds, while potentially improvable, express the correct asymptotic relationship be- tween parameters and approximation bounds.
Results and Interpretation. Figure 4 provides our exper- imental results based on synthetic data, and Table 7 shows the error resulting from real-world datasets. As expected, our approach performs asymptotically better than the Gaus- sian mechanism in the local model, but worse than SSP in the central model. We also found that as n increases, the error of our approach asymptotically approaches the error in the central model. For p 0.9, 0.8, 0.7, 0.6, the error eventually decreases for a sufficiently large for the privacy regimes we considered (s E {0.01, 0.03, 0.05, ).
G.2.2. LOW-RANK APPROXIMATION
In addition to the error in ridge regression, we investigate the error when performing low-rank approximation. Com- pared to ridge regression, the additive error plays a more significant role (sce Theorem 4.3), so we measure the error in terms of the excess risk as opposed to the approximation factor:
e A AX'X
18
-1A 2 AAXor XXorXXpprl bprIl?
n2
For p = 0.5 though we saw a significant jump towards the local model in terms of asymptotic behaviour. In all the settings we considered, p = 0.5 showed an asymptotic increase of the error. We tested on synthetic datasets of up to 40 million, and the error also increases in this regime.
where XOPT denotes the optimal solution and X' denotes the solution after adding noise to the training data. Again, we evaluate the error for synthetic datasets as well as four real-world datasets. We utilize the same software, hardware and world datasets for ridge regression (see Table 8). For thorough description of the datasets, consult the above section on ridge regression. We ignore the feature we were predicting when performing ridge regression i.e. matrix A is the same in both settings.
Table 7 shows the results we got by applying the local, our mechanism and SSP on real-world data. They include standard deviations, though for many of the results those are so small that they appear as 0 in the table. We found, that our mechanism performs significantly better than the Gaussian mechanism for local privacy. In most it even performs so good, that there is basically no difference the central model.
Setup. for ridge regression, our mechanism in the LTM adds Gaussian noise sampled from (N0, to every entry of A, dependent on privacy parameters E and 8. By choos- ing a² proportional to n P for E [0, 1]. we interpolate between the local model (p 0) and the central model. We also implement a Gamma/l Laplace based mechanism in the LTM, which adds the sum of m samples from Lap(0. 1/E) to every entry in SA, in order to investigate the 8 = 0 regime in the LTM. As baseline for the central model, we imple- mented MOD-SUL.,, an approach presented by (Chaudhuri et al., 2012), where A A is perturbed by adding Gaussian noise.
Table 7. Experimental evaluation of error á on real-world datasets, including standard deviations. Here we are in the setting where e = 0.03 and A = 10.
Dataset
Local
Our
Central
Power
2.364 = .007
1.055 + .000
1.001 .001
Elevation
1.939 + .008
1.000 + .000
1.000 .000
Ethylene
3.125 = .002
1.000 + .000
1.000 + 000
Songs
20.64 + .016
1.000 + .000
1.000 + 000
We generate synthetic data by first producing a matrix A' where every entry is sampled from (0, 1) and then chang- ing its singular values such that there are exactly k big ones and the rest are small. More specifically, we set A = U'E', where U'E'V' is the SVD of A and Σ is a diagonal matrix with the first k values set to / /n/k and the rest set to 1/n. We vary parameters E (0.05, 0.1, 0.5} and A E {5, 10) for d = 50. For all combinations of parameters. we generate 17 synthetic datasets of sizes ( (1000--.51; = O...., 16). For each of those we then measure v for the central mechanism, the Laplace mechanism and the Gaus- sian mechanism with p E {1, 0.9, 0.8, 0.7, 0.6, O.5. 0}. by running the algorithms 20 times per dataset and reporting the average tb.
Varying A On Figure 5, we provide plots for the same setting of parameters as on Figure 4 (d = 10 and n²² = n). Though, we also vary x E (1, 10, 100) here. The experi- ments show that varying X does not change the asymptotic behavior of any of the mechanisms we investigated, in the sense that a variance proportional to -0.6 or lower even- tually had decreasing error, while variance proportional to n. 0.5 produced increasing errors. The increase of À does however produce a significantly lower error in all settings (note the y-axes on the figure). Our theoretical results like- wise predict this behaviour, as while the error bounds of
25

---

Distributed Differentially Private Data Analytics via Secure Sketching
20
6-
15
error x10+
error x103
4-
10
2
5
0-
0
200000
400000
600000
0
200000
400000
600000
6
10
error X 100
error X 102
4
5
0
200000
400000
600000
200000
400000
600000
n
n
central
p 0.9
p 0.7
0.5
(LTM)
= 0.8
p 0.6
0 (local)
Figure Plots depicting the asymptotic behavior of errо & for e E {0.01, 0.03, 0.05, 0.1} (top left, top right, bottom left, bottom right). with d = 10, À = 10 and μ²² = n. The grey line depicts the error of the local mechanism, the blue line does it in the central model and orange one depicts our approach. The other lines resemble different values of p. most cases standard deviations are so small, that it is not possible to see those.
26

---

Distributed Differentially Private Data Analytics via Secure Sketching
A
À 10
100
600000
400000
40000
4000
200000
20000
2000
01
200000
600000
400000
200000
400000
6000000
600000
6000
400000
40000
4000
2000000
400000
600000
0
200000
400000
600000
200000
400000
600000
60000
2-000
400000
40000
4000
200000
20000
2000
0
2000000
2000000
2000000
400000
600000
600000
60000
6000
1000001
400000
1000
2000
200000
400000
500000
200000
400000
500000
200000
400000
600000
Figure 5. Plots depicting the emror increases, for {0.01, 0.03, 0.05, 0.1) (top bottom) and À (1, 10, 100) (left to right). middle row depicts the same choice of parameters as Figure
27

---

Distributed Differentially Private Data Analytics via Secure Sketching
Results and Interpretation. Figure 6 shows our experi- mental results for some of the parameters mentioned above, based synthetic data and Table 9 provides the error re- sulting from real-world datasets summarized in Table 8. As expected and in par with ridge regression, our approach performs better than the Gaussian mechanism in the local model but worse than MOD-SULQ in the central model. We observed that as n grows, the error of our approach asymptotically approaches the error in the central model. In the privacy regimes we considered (e E {0.05, 0.1, 0.5)), the error of intermediate mechanisms (p E [0, I), decreases with increasing n as well.
such that the security of distributed protocol does rely any computational assumption.
Since the linear transformation is public, servers can apply the transformation locally to their secret shares without any need to communicate with each other. Each server then re- veals their shares the resulting linear transformation, such that the linear sketch can be revealed in the clear. For more details on MPC based on secret sharing, see e.g., (Cramer et al., 2015).
Table 9 shows the experimental results of rumning our mech- anisms, the Gaussian mechanism in the local model and MOD-SULQ in the central model on real-world data. The k's we used for the individual datasets provided in Ta- ble& 8. Similar to ridge regression, we found that our Gaus- sian mechanism in the LTM performs significantly better than the Gaussian mechanism in the local model. Both with synthetic and real-world datasets, our Laplace approach also performs better than the local model, though not as signifi- cantly the Gaussian approach. However, this is the price of achieving pure e-differential privacy with 8 0.
Table 8, Parameters of real-world datascts.
Dataset
n
d
k
Power (Hebrail & Berard, 2012)
2049280
6
3
Elevation (Kaul, 2013)
434874
2
1
Ethylene (Fonollosa, 2015)
4178504
18
5
Songs (Bertin-Mahieux, 2011)
515345
89
15
H. Distributed Computation of Linear Sketches
The linear transformation we consider is motivated by ef- ficient secure distributed cryptographic tools from secure multi-party computation; in particular, we can linear secret-sharing. We require this secret sharing scheme to be information-theoretiooi
secure. We use an additive secret sharing scheme, such that clients CI,..., Cn gener- ate shares of their noisy inputs x=1 "e...,,""* ,,, where & is the number of servers that compute the linear transforma- tion. We use [x'] denote a secret sharing of some client Ct's noisy input x² for some [n]. For some field F of size and some prime number p. [x*] consists of shares rf. rf....,,i f such that Σ5= 25 = x'. To split a secret into shares, client can sample k random field el- ements æf,.... .., zff1 and compute the last secret share r' -|= ztj. Therefore, it also seems intuitive that an adversary that sees all but one of the shares knows noth- ing about the input. For every j E [bt], server S, receives {x) hen from the respective parties. We define these shares
28

---

Distributed Differentially Private Data Analytics via Secure Sketching
0.8
0.75
0.6
enror
eгτоr
0.50
0.4
0.25
0.2
0.00
0.0
10
10
10
10
10
10s
0.8
0.75
0.6
error
0.50
eтτor
0.4
0.25
0.2
0.00
0.0
103
10a
105
10
10
105
Central
p 0.8
= 0.5
Gauss in LTM (p 1)
p 0.7
Local (p 0)
p 0.9
p = 0.6
Laplace in LTM
Figure 6. Plots depicting the asymptotic behavior of error vi for E (0.1, 0.5} (top, bottom) and E {5, 10) (left, right), with 50. The gray line depicts the error of the local mechanism, and the orange and lime lines depict our approach using Gaussian and Laplacian noise respectively. other lines resemble different values of p when using Gaussian noise. The standard deviations are depicted by the vertical black lines and the z-axis is logarithmic in the number of clients
29

---

Distributed Differentially Private Data Analytics via Secure Sketching
Table Experimental evaluation of error ii real-world datasets, including standard deviations. Here are in the setting where
8 0.05.
Dataset
Local
LTM Laplace
LTM Gauss
Central
Power
(1.206 = 0.651) 10 10-2
(4.036 = 2.448) x 10
(2.108 + 2.400)
10-1
(1.763 0.621) X 10
Elevation
(1.193 = 0.896)
10-1
(1.520 = 4.484) x 10-2
(4.718 + 4.201)
10
(4.465 + 4.836) x 10 8
Ethylene
(5.877 + 1.256)
10-4
(5.821 + 1.074) x 10-4
(2.420 + 0.486)
x 10-6
(7.901 + 1.909)
x 10-6
Songs
(5.617 + 0.283) x 10-7
(5.629 + 0.311) x 10-7
(5.556 + 0.347) X 10-7
(5.613 + 0.324) x 10-7
30


Reviews:
[{"review_id": "lZWfjgGCwo", "reviewer": "Reviewer_sQPT", "summary": "The authors present a new model for differential privacy, the linear transformation model (LTM). This model interpolates between the local model of DP, that does not require a trusted central server, and the central model of DP that does. Some other intermediate models have been proposed, the most well studied being the shuffle model. \n\nThe LTM works by having each user perform a local calculation on their data then add noise to it and report it to an intermediate server. This server collects all the perturbed data from the users then applies a linear transformation to it. This transformed data is then processed in order to solve some task (such as low rank approximation). This is analogous to the shuffle model, replacing a shuffle with a linear transformation. The natural choice for a transformation is a linear sketch.\n\nThe authors show that this linear sketch can be computed securely with techniques from multi-party communication (MPC). The shuffle model can also be implemented via MPC, but the implementation is less practical because it is more computationally expensive and includes a chain of communication between servers increasing latency.\n\nThe authors show that under this new model, several tasks from numerical linear algebra can be solved by algorithms that satisfy LTM-DP while having error that does not scale with the number of clients. The specific tasks in question are Low-Rank approximation and Ridge regression. Experiments demonstrate that the LTM algorithm for ridge regression gives lower error than the local-DP algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback and thoughts.\n\n>  One modification that would be informative would be a plot of error versus privacy budget for the various methods. The privacy budgets used in the paper are 0.1 and 0.5, which are fairly narrow\n\nRegarding the choice of privacy budgets in the experiments, we chose to include results for $\\epsilon=0.1$ and $\\epsilon=0.5$ as those show a clear separation in the error between different mechanisms in the LTM. Note that increasing $p$ while keeping $n$ fixed can be interpreted as increasing the privacy budget of our Gaussian noise mechanism, so Figure 2 shows that an increase of privacy budget above 0.5 decreases the error drastically in all settings. We will include a plot that explicitly shows the error versus privacy budget in the final version.\n\n> The sketch parameters are underexplored, it seems natural to ask if there is some relationship between the optimal sketch parameters for a particular privacy budget or number of clients\n\nWith respect to the sketch parameters, we would like to point out that one strength of the LTM is its modularity, in the sense that any sketch can be used when suitable for the data analytics task at hand. We explore different such sketches from the literature and list their parameters in Table 3 in the appendix.\n\n> You mention that the MPC protocols needed for shuffle are not practical while the MPC protocols for the LTM are. Can you explain this quantitatively, how much more communication/computation is needed for MPC shuffle?\n\nWe acknowledge that we did not sufficiently substantiate the claim that MPC-based shuffles are more expensive than the LTM-based approach for readers who are not familiar with MPC. Due to space constraints, we could not include a full quantitative comparison, but we clarify here the key differences:\n1. Round Complexity: In MPC-based shuffles, each server must sequentially shuffle and randomize (or re-encrypt) the ciphertexts, leading to a round complexity proportional to the number of servers involved. This sequential dependency significantly increases the protocol’s latency. In contrast, the LTM enables all servers to perform their computations in parallel, resulting in lower round complexity and latency.\n2. Computational Overhead: In the LTM, servers only need to perform simple linear operations on secret shares, such as matrix-vector multiplications, which are highly efficient. On the other hand, MPC-based shuffles typically rely on mix-nets or similar constructions, where each server performs, for every data point, multiple expensive public-key operations (e.g., modular exponentiations with large moduli and exponents). This introduces an overhead that is orders of magnitude higher compared to simple matrix multiplications.\n3. Communication Complexity: The total amount of data transmitted is comparable between the two models, but the size of individual messages differs substantially. In the LTM, secret shares can be as small as the plaintext itself; for example, when working with 64-bit types, each share is just 64 bits per server. In contrast, MPC-based shuffles transmit ciphertexts that are significantly larger due to the inherent expansion of public-key encryption. For example, even with elliptic curve ElGamal, each ciphertext would be at least 512 bit. As a result, the total communication volume in MPC shuffles is larger.\n\nFinally, we emphasize that MPC protocols, in general, tend to incur significant communication and computational costs when dealing with non-linear operations (e.g., multiplications on secret-shared data). The LTM model avoids this overhead by relying exclusively on linear operations on secret-shared data, which are much cheaper to compute.\n\n> What other tasks do you expect to be a good fit for the LTM? Do you expect that the LTM will be a strict upgrade over the shuffle algorithm or will there be tasks less related to numerical linear algebra that will be solvable with less error under the shuffle model.\n\n**Good Fit for the LTM:** Currently, we expect many problems beyond numerical linear algebra to be addressable in the LTM. A promising example are certain clustering tasks like k-median clustering, which we are currently working on.\n\n**Comparison to Shuffle:** We do not believe that the LTM will be an upgrade over the shuffle model, rather it is a complementary model with incomparable strengths and weaknesses.\nProving a separation between the two models would be interesting and potentially challenging.", "claims_and_evidence": "Most of the claims in this work are theoretical - these are addressed in the theoretical claims section. The claim that LTM algorithms will give lower error than local-DP algorithms is also supported by experiments on real and synthetic data. These experiments corroborate the theory. One claim with fairly weak support is that the MPC procedures needed for the shuffle model are much more expensive than those needed for the LTM. This may be obvious to someone with more MPC background, but it would be good to have this justified more quantitatively either with asymptomatic expressions for the communication/computation needed for these protocols or with experiments.", "methods_and_evaluation_criteria": "The experimental methods and evaluation criteria are sensible given the theoretical nature of the claims.", "theoretical_claims": "The main theoretical claims are the privacy and utility results of the ridge regression and low-rank approximation algorithms. The tools used in this analysis are clear (infinitely divisible noise distributions and oblivious sparse norm-approximating projections) and the results are broadly in line with what I would expect given the combinations of these tools. However, I did not have time to carefully review the proofs to check their validity.", "experimental_designs_or_analyses": "One modification that would be informative would be a plot of error versus privacy budget for the various methods. The privacy budgets used in the paper are 0.1 and 0.5, which are fairly narrow.", "relation_to_broader_scientific_literature": "This work is most closely related to other intermediate DP definitions such as the shuffle model and secure aggregation (which is an instance of LTM). As far as I know, the shuffle model has not been implemented much in practice. The LTM seems promising in that it is clearly stronger than the central model while not being as restrictive as the local model and being easier to implement than the shuffle model.", "essential_references_not_discussed": "I do not believe that there are essential references not discussed in this paper.", "other_strengths_and_weaknesses": "Strengths\n\nI find the writing of this paper to be very clear and informative. This manuscript does a great job of giving the reader the necessary background about differential privacy models, linear sketching, and multi-party communication\n\nThe connection between LTM and linear sketching is very natural and I expect that many tasks from numerical linear algebra will be a good fit for this model\n\nThe experiments on real datasets give me confidence that these methods will be useful in practice\n\nWeaknesses\n\nThe sketch parameters are underexplored, it seems natural to ask if there is some relationship between the optimal sketch parameters for a particular privacy budget or number of clients", "other_comments_or_suggestions": "No other comments", "questions_for_authors": "You mention that the MPC protocols needed for shuffle are not practical while the MPC protocols for the LTM are. Can you explain this quantitatively, how much more communication/computation is needed for MPC shuffle?\n\nWhat other tasks do you expect to be a good fit for the LTM? Do you expect that the LTM will be a strict upgrade over the shuffle algorithm or will there be tasks less related to numerical linear algebra that will be solvable with less error under the shuffle model.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Pg73GTWEnN", "reviewer": "Reviewer_ANhV", "summary": "The paper introduces the Linear Transformation Model (LTM), a new differential privacy (DP) trust model between central DP, where a single party is trusted, and local DP, where no party is trusted. In the LTM, a linear computation can be used to transform a set of private inputs of parties before they are revealed. This is especially suitable to Multiparty Computation (MPC) techniques based on a set of servers where at least one of them does not collude with the adversary, as linear computations can be performed efficiently with such cryptographic tools. \n\nThe paper shows the accuracy gain of the LTM with respect to the Local Model of DP. In addition, it provides arguments of its better suitability with respect to the Shuffle Model, which also lies in between central and local DP.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and questions.\n\n> I am not convinced that the utility analysis of Section 4 completely characterizes this gain. The term \n$\\alpha_S$ which impacts the accuracy of the protocol is only analyzed order-wisely, while it should be more concretely quantified.\n\nRegarding the concrete quantification of $\\alpha_S$, we are unsure if the reviewer means the possible values of  $\\alpha_S$ that can be chosen and the concrete constants in our analysis. If the question’s focus is on the constants in our theorem statements, for low rank approximation the constant leading  $\\alpha_S$ is 1. For linear regression, we give the constants resulting from our analysis in Equation 12 in the appendix for linear regression. However, the final constants depend on the analysis of the chosen sketching constructions, which is taken from previous work. The target dimension of sketching constructions of related work from Table 3 have been analyzed up to absolute constants, but the absolute constants themselves are not known. If the focus of the question is rather on the exact value of $\\alpha_S$, we remark that $\\alpha_S$ can be chosen to be any number in (0,½), so one can trade off multiplicative and additive error to get a best possible tradeoff.\n\n> Experimental Designs Or Analyses:  I am not sure that all the approximation error that impacts the accuracy is included in the comparison. (see the previous comments on $\\alpha_S$).\n\nRegarding the value of $\\alpha_S$ in the experiments, it is not possible in general to experimentally determine which part of a cost function comes from a multiplicative error and which comes from an additive error. We can use the worst case bounds as a baseline, but these might not be tightly analyzed. The results presented in the experiments implicitly set the multiplicative error to a small constant and measure the excess risk, which is the closest approximation of a possible additive error.\n\n>  Table 1 ignores the effect of $\\alpha$ for space. However I think it is important to find a strategy to concisely include this effect.\n\nThe comparisons in Table 1 are with respect to additive error, since there is no multiplicative error in the central model. Multiplicative errors and additive errors cannot be fairly compared to each other, so we simply remark on the existence of our approach’s multiplicative error in the Table caption. These errors are analyzed in the proofs of the theorems in Section 4.\n\n>  At the beginning of Section 3 the paper argues that the shuffle model is weaker…\n\nWe apologize for the confusion caused by the statement in Section 3 — this was not our intention. Our point was not to argue that the shuffle model is inherently weaker, but rather to highlight that the standard formalization of differential privacy in the shuffle model does not, as stated, account for the case of colluding clients. Our motivation for introducing a refined definition was simply to ensure that the privacy guarantee holds even when a bounded number of clients might collude with the adversary, as we believe this is important for the applicability of the definition to real world scenarios. We fully agree with the reviewer that this refinement can naturally be applied to both the shuffle model and the LTM, and our comment should not be interpreted as a point of comparison between the two models. It is solely about the formalization of the security notion itself. As noted in the paper, similar observations have already been made in prior work (e.g., Talwar et al., 2023), fully in line with the reviewer’s comment. We will make sure to revise the text to clearly reflect this intention.", "claims_and_evidence": "- The main claim of the paper is that the LTM provides substantial accuracy advantages with respect to local DP. \n\nI am partially convinced about this claim. It is clear that performing a secure linear transformation can lead to a significant privacy amplification. However, I am not convinced that the utility analysis of Section 4 completely characterizes this gain. The term $\\alpha_{S}$ which impacts the accuracy of the protocol is only analyzed order-wisely, while it should be more concretely quantified. \n\nTherefore I am not sure about the magnitude of the gain. \n\n- As a second claim, the paper argues that the LTM is more convenient than the Shuffle Model in terms of computation and communication cost. I am convinced by the authors in this point.", "methods_and_evaluation_criteria": "Empirical evaluation criteria seems reasonable.", "theoretical_claims": "I have checked the proofs of Theorems 3.4 and 3.5, which seem correct.", "experimental_designs_or_analyses": "In general the paper seems experimentally sound. However, some parts of it are hard to follow so I am not sure that all the approximation error that impacts the accuracy is included in the comparison (see the previous comments on $\\alpha_{S}$).", "relation_to_broader_scientific_literature": "I think the paper is adequately related to broader scientific literature. \n\nThe paper positions fairly well with respect to shuffle DP. However, certain statements seem unfair. For example, at the beginning of Section 3 the paper argues that the shuffle model is weaker because it assumes that all parties are honest and do not collude with the adversary. This seems easy to fix in the shuffle model: in the presence of corrupted parties, one can only consider the honest subset of parties to be part of the effective shuffle.", "essential_references_not_discussed": "To the best of my knowledge, there are no essential references missed in the paper.", "other_strengths_and_weaknesses": "As said before, the paper is in general hard to follow and theorems 3.4 and 3.5 could be more clearly stated. In mathematical statements, some conditions rely on parameters that are not previously defined. For example, $n$ depending on $m$ in the randomizer function of Sec 3.2", "other_comments_or_suggestions": "Table 1 ignores the effect of $\\alpha$ for space. However I think it is important to find a strategy to concisely include this effect.", "questions_for_authors": "Please address my concerns with respect to the characterization of the error induced by $\\alpha_S$ both in theory and in the empirical evaluation.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZRUv6plcZE", "reviewer": "Reviewer_yySS", "summary": "The authors introduce the linear-transformation model (LTM) for distributed differentially private data analytics. The main question that the authors aim to address is \"what is the least expressive F need to be securely implemented such that distributed DP utility is comparable to that of the central model\". In LTM, the key idea is to leverage efficient secure multiparty computation (MPC) techniques to implement the linear transformation in a distributed setting. Interestingly, the authors have provide a new definition (Definition 3.1) Trusted Computation Model for Differential Privacy when there are colluded clients (with Adversary). The authors also discussed the usage of LTM for tasks such as estimating frequency moment and low-rank approximation. They support their contributions with detailed theoretical utility and privacy guarantees and also an empirical evaluation using real-world datasets (Table 2) demonstrating the error is close to that of the central setting.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and questions.\n\nWe will incorporate the useful editorial suggestions about our Figures in the final version.\n\n>  What happens with lager privacy budget?\n\nWe discuss our choice of privacy budget $\\epsilon$ in the experiments in our answer to reviewer sQPT as well. We chose relatively small values, to showcase the separation of different mechanisms in the LTM, which is more prominent when more noise is added. Increasing $p$ for our Gaussian noise mechanism in the LTM while fixing $n$, can be interpreted as increasing $\\epsilon$, so Figure 2 shows that increasing $\\epsilon$ decreases the error significantly in all settings and for all values of $n$.\n\n> Please consider to add an explicit threat model.\n\n We will further clarify the threat model in the next revision and make it explicit already at the beginning of Section 3. Specifically, in our privacy analysis, we assume that up to $t’ < n$ clients and up to $t < k$ servers may collude and share information with each other, while otherwise following the protocol honestly. This type of adversarial behavior is commonly referred to as passive, semi-honest, or honest-but-curious in the cryptography literature.", "claims_and_evidence": "I find most of the claims to be supported.", "methods_and_evaluation_criteria": "Section 5 evaluate the proposed approach for low rank approximation and the evaluation is convincing for small epsilon values.", "theoretical_claims": "Didn't check all the proofs in detail, but the result looks correct.", "experimental_designs_or_analyses": "I'm wondering what happens when the privacy budget is large (when $\\epsilon > 1$)?", "relation_to_broader_scientific_literature": "This work has good potential to influence future research in improving the privacy-utility trade-offs of differential privacy using crypto tehcniques.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "The idea is sound and the author provide detailed theoretical analysis for the proposed algorithms.", "other_comments_or_suggestions": "D1. Please move Figure 1 to page 2.\nD2. Please either user different line style/ticks for all figures. For example, it is super hard to read Figure 2 based only on the color coding.", "questions_for_authors": "Q1: What happens with lager privacy budget?\n\nQ2: Please consider to add an explicit threat model.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WbPlrnKKl9", "reviewer": "Reviewer_5GUZ", "summary": "In this paper the authors are attempting to find a way to build solutions that have utility as high as in case of central DP, but have as little assumptions as in case of local DP. \n\nThe most common example of such an approach is privacy amplification by shuffling. However, the number of mechanisms that could use shuffling is limited. Hence, the paper proposes to use linear transformations instead of shuffling. The paper further suggests some applications of this idea to linear regression and low-rank approximation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and questions.\n\n> The discussion of shuffle model and other deployments where the central server is replaced by MPC is lacking details.\n\nRegarding missing details on replacing trust in a central server by MPC, ​​we made an extensive comparison in Section 3.3. A complete introduction for MPC is out of scope, but we give some details for our constructions in the appendix. If the reviewer thinks specific points are missing, we would be grateful for pointers.\n\n> Your definition of corrupted clients / servers seems unusual to me since it assumes that they are faithfully following the protocol and we just know their result without privacy protections. Is this correct? (If yes, I would suggest calling them spoofed or something similar.)\n\nThe privacy guarantees will hold even if a large fraction of corrupted parties deviate from the protocol description. We currently only require the semi-honest assumption for the utility guarantees.", "claims_and_evidence": "The evidence sufficiently supports the claims.", "methods_and_evaluation_criteria": "Methods and evaluations are appropriate for the problem at hand.", "theoretical_claims": "The proofs presented in the paper are correct.", "experimental_designs_or_analyses": "The experimental design seems valid.", "relation_to_broader_scientific_literature": "While this is the first paper discussing use of MPC to replace linear transformations in the central DP model, it is not the first paper (as admitted by the paper itself) that discusses the idea of using MPC to avoid assumptions on central aggregators. \nThe paper proposes alternative algorithms for low-rank approximation and for ridge regression which are better than the one achievable in the local model, but worse than the central model (which is not a surprise).", "essential_references_not_discussed": "The paper doesn't lack any specific reference; however, the discussion of shuffle model and other deployments where the central server is replaced by MPC is lacking details.", "other_strengths_and_weaknesses": "The concept of decentralizing the traditional central server model and replacing it with an MPC protocol is a driving force behind the current push to apply DP in real-world scenarios.\n\nGiven this trend, the design of algorithms that can be easily translated into straightforward MPC protocols is of paramount importance. Unfortunately, the paper under review tackles problems that lack immediate, real-world applications. This disconnect between the theoretical focus of the paper and practical applicability makes it challenging to argue convincingly for the significance of its results. Especially considering that the theoretical results are not very complex either.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Your definition of corrupted clients / servers seems unusual to me since it assumes that they are faithfully following the protocol and we just know their result without privacy protections. Is this correct? \n(If yes, I would suggest calling them spoofed or something similar.)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces the Linear Transformation Model (LTM) for distributed differentially private data analytics, as an intermediate model between the central and local models of differential privacy. The core idea is to leverage efficient secure multiparty computation (MPC) techniques to apply a public linear transformation, such as a linear sketch, to the data contributed by different clients. This approach aims to avoid the single point of trust in the central model while mitigating the high noise requirements of the local model. The paper demonstrates the utility of the LTM for tasks like private low-rank approximation and private ridge regression, showing that it can achieve error that does not scale with the number of clients.
While the reviewers found the model rather natural, more details were deemed needed for the comparison between LTM and the shuffle model as well as MPC-based alternatives. Also, the writing of the paper can be improved to make it easier to follow (including by adding a more explicit specification of the threat model). Moreover, concerns were raised about the comprehensiveness of the utility analysis (since the privacy budgets considered are quite low).
Addressing the above concerns, in particular by adding a more detailed comparison to alternative approaches as well as an explicit threat model, would be preferable before the paper is ready for publication at ICML.
Decision: Accept (poster)