DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning Based on Constant-Overhead Linear Secret Resharing
Authors: Alexander Bienstock
Ujjwal Kumar
Antigoni Polychroniadou
Venue: ICML 2025 poster (2025)
Keywords: federated learning
differential privacy
matrix mechanism
cryptography
Primary area: social_aspects->privacy
TL;DR: We achieve better privacy-utility tradeoff for Federated Learning with local differential privacy using the matrix mechanism and novel efficient cryptographic techniques.

Abstract: Federated Learning (FL) solutions with central Differential Privacy (DP) have seen large improvements in their utility in recent years arising from the matrix mechanism, while FL solutions with distributed (more private) DP have lagged behind. In this work, we introduce the distributed matrix mechanism to achieve the best-of-both-worlds; better privacy of distributed DP and better utility from the matrix mechanism. We accomplish this using a novel cryptographic protocol that securely transfers sensitive values across client committees
of different training iterations with constant communication overhead. This protocol accommodates the dynamic participation of users required by FL, including those that may drop out from the computation. We provide experiments which show that our mechanism indeed significantly improves the utility of FL models compared to previous distributed DP mechanisms, with little added overhead.

DMM: Distributed Matrix Mechanism for Differentialy-Prrivte Federated Learning Based on Constant-Overhead Linear Secret Resharing
Alexander Bienstock
Ujjwal Kumar? Antigoni Polychroniadou
Abstract
gradients then aggregated and sent to the central server using different techniques to update the model parameters for the next iteration (e.g.. (McMaaan et al., 2016; Fallah et al., 2020; Sahu et al., 2018)).
Federated Learning (FL) solutions with central Differential Privacy (DP) have seen large improve- ments in their utility in recent years arising from the matrix mechanism, while FL solutions with distributed (more private) DP have lagged behind. In this work, we introduce the distributed matrix mechanism to achieve the cit-offbott-worlddd better privacy of distributed DP and better utility from the matrix mechanism. We accomplish this using novel cryptographic protocol that securely transfers sensitive values across client committees of different training iterations with constant com- munication overhead. This protocol accommo- dates the dynamic participation of users required by FL, including those that may drop out from the computation. We provide experiments which show that our mechanism indeed significantly im- proves the utility of FL models compared to previ- ous distributed DP mechanisms, with little added overhead.
The main privacy metric for FL is differential privacy (DP) (Dwork et al., 2006). Roughly speaking, DP guar- antees that with high probability, one cannot tell whether user participated in given FL execution. There are two different notions of DP that can be considered. In central DP, there centralized server who receives the aggre- gated gradients from the clients in each iteration (perhaps using a Secure Aggregation protocol (Kairouz et al., 202 a; Bonawitz et al., 2017; Liu et al., 2022: Karthikeyan & Poly- chroniadou, 2024; Li et al., 2023)) and then updates the model by adding its own DP noise to these aggregated gradi- ents. See the left side of Figure I for flowchart illustrating the process. In this case, DP holds with respect to those to whom the server sends the updated models (assuming that the server did indeed add noise), but not the server itself. In distributed DP, there may still be a centralized server, however, the clients utilize a Secure Aggregation protocol to release to the server only aggregation of their gradients with their own DP noise already added in. Thus, DP holds with respect to the server as well; in particular, the clients do not need to trust the server to add noise. Indeed, distributed DP is important for particularly sensitive data that cannot be known by anyone else and for which we cannot rely on a central server protect.
1. Introduction
In Federated Learning (FL), machine learning model is trained using data from several end-users/clients. Since such data can often be sensitive, a key challenge in FL. is maintaining utility of the trained models, while preserving privacy of the end-users. FL has experienced an explosion of progress in recent years, both in industry and research.
There has been tremendous progress recently in the area of central DP for FL,, e.g., Phhoquette-Choo et al., 2023a; Dvijotham et al., 2024; McMahan et al., 2024). These works use a sophisticated set of techniques from the DP literature called the matrix mechanism (Hubert Chan et al., 2010; Dwork al., 2010) to achieve excellent privacy-utility trade- offs. Indeed, in this setting, since the central server receives all of the gradients in the clear and samples all noise on its own, it can correlate the noise across iterations in complex manner. Intuitively, this means that noise can be re-used across iterations so that the cumulative noise across all iterations is lower compared to sampling new, fresh noise to hide the gradients in each iteration.
In more detail, in each training iteration of FL, typically central server sends the current model parameters to set of clients, which we call committee, who locally execute step of Stochastic Gradient Descent on their own data to obtain gradients with respect to a loss function. These
'J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE, New York, New York, USA PJ.P. Morgan, Mum- bai, India. Correspondence to: Alexander Bienstock <alex.bienstock @ jpmchase.com>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
On the other hand, in the setting of distributed DP, the

---

DMM: Distributed Matrix Mechanism for Differentially-Prive Federated Learning
Grddacck
Ulere
Dha
Cheere
Server
Fist d Ag
Σ
Dodiier Roois
Chackee dimaiee
FXTT A,
G ond & solee
Badker Breekr dhane
Joemation:
sepdored medil
kooal exeiel
spddaaed aedal
rnporeppted
Figure 1. Left: FL the central DP model. Users in iteration T update the model locally and these updates are aggregated to the server. The server then adds noise itself before sending the updated model to committee T + 1. Right: FL based on DMM in the distributed DP model. Users in iteration receive noise and gradient shares from previous iterations. These parties combine the received shares with shares of their new gradients and freshly sampled noise via a linear combination, f, and send these combined shares to the server who uses them to reconstruct (only) the updated model. Afterward, the gradient and noise shares are reshared to the parties in committee T + 1, ensuring continuity in DMM.
clients just add noise locally to their gradients (Kairouz et al., 2021a; la; Agarwal et al., 2021; Chen et al., 2022). Since clients change in each iteration, the noise cannot be correlated across epochs via the matrix mechanism like in the central DP setting, and so the privacy-utility trade-off of distributed DP pales in comparison to that of central DP thus far.
linear secret resharing protocol, LRP. Indeed, our new techniques are paramount, since the naive way to perform such resharing costs n² communication per secret, instead of (L) per secret, where n is the number of parties in each committee. We can see from Table that this results in communication as low as 25.1 MB per client using our new techniques, and infeasible communication as high as 2.13 TB per client using the naive resharing. See Section 3 for details on the naive secret resharing protocol and our LRP protocol with constant communication overhead.
Our Contributions. In this work, we propose a solution to achieve the "best-of- tributed DP settings, called the Distributed Matrix Mecha- nism (DMM). We achieve privacy against the central server, i.e. distributed DP, while using correlated noise to get privacy-utility trade-offs matching the central DP setting.'
of the central and dis-
2) Given LRP, we can instantiate the matrix mechanism in a distributed fashion to obtain DMM: First, the parties take linear combinations of the secret shared gradients and noise, thus introducing noise correlations across epochs. Then, the parties can reconstruct these aggregrated gradients with (correlated) noise to the server. Finally, users (re Jshare the gradients and noise using LRP. See the right side of Figure I for a flowchart illustrating our approach.
1) DMM starts with linear secret sharing (Shamir, 1979), central technique in the cryptographic literature which has also been used for FL, e.g., (Ma et al., 2023; Shao et al., 2022; Marchand et al., 2022). Secret sharing allows for dealer party to distribute to parties different shares of some secret v, such that any Le (corrupted) parties cannot learn anything about x from all of their shares, while any to + parties, for some k > can use their shares to reconstruct x. These shares are also linear, meaning that if the users have shares of 21 and 22, they can add their shares together to obtain sharing of 13 I T2-
DMM is detailed in Section 4. Importantly, DMM maintains DP even in the presence of corrupted parties who might ma- nipulate their shares of the gradients and noise. Moreover, DMM achieves dropout tolerance: In FI., the gradients from end-users often come from mobile devices, and therefore it may not be guaranteed that such users will stay online for the whole training iteration, even if they are honest. Thus, the protocol must not fail if some (honest) users drop out.
Typically in FL, secret sharing is used by a single set of parties to secret share (noisy) data to the other parties in the set. In our setting, however, we additionally need the noise and gradients from users in a given committee to somehow be reshared to users future committees. Thus, we develop new techniques in this paper to build our constant-overheal
3) We implement the Distributed Matrix Mechanism us- ing our resharing protocol and empirically test its efficacy in training differentially private FL models. For example, in Figure 2, we show that for Stack Overflow Next Word Prediction (Authors, 2019), our approach improves upon the privacy-utility tradeoff of the most accurate prior dis- tributed DP approach, the Distributed Discrete Gaussian
'We note that, just as (Kairouz et al., 2021a) and all other works using Secure Aggregation to obtain DP guarantces via ag- gregated noise, we actually obtain computational DP (Mironov al., 2009).
2

---

DMM: Distributed Matrix Mechanism for Differentially-Privaa Federated Learning
LRP
SecAgg
LRP
Naive SR
SecAgg
Accuracy Fpsioon Stack Overflow Prediction
Comp.
Comp.
Comm.
Comm.
Comm.
Opt.
7.69 s
61.3 ms
4.68 GB
2.13 TB
16.2 MB
Hon.
412 ms
61.3 ms
25.1 MB
11.4 GB
16.2 MB
Aott Rntrwgee Accunacy
Table 1. Clientt computation and communication of our LRP re- sharing protocol, naive secret resharing, and SecAgg per training iteration on Stack Overflow Next Word Prediction for committee size n 64. We give results for both the optimal (Choquette-Chie Choo et al., 2023a) and more efficient Honaker online (Kairouz et al., 2021b; Honaker, 2015) matrix mechanisms. SecAgg is the bot- tleneck of prior distributed DP approaches (Kairouz et al., 2021a) and LRP (as opposed to naive secret resharing) is the bottleneck of DMM (ms == milliseconds; seconds).
Central DP Honaker Online
Car trall DP Bendkr
Local ur DUt
DHM Honaker Online
Optimal
Ppulino
Figure 2. Test accuracies Stack Overflow Next Word Predic- tion across different privacy levels for the distributed DP DDG mechanism (Kairouz al., 2021a), the central DP BandMF and Honaker online mechanisms our distributed DP DMM instantiated with the optimal (Choquette- Choo et al., 2023a) and Honaker online (Honaker, 2015) matrix factorizations. DMM performs 5-6 percentage points better than the prior distributed DP approach and similar (sometimes better) to the prior central DP approaches. We use = 1/N for (s. 5)-DP, where N is the total number of clients selected across training.
(DDG) Mechanism (Kairouz et al., 2021a), and matches that of the best central DP approach (Choquette-Choo et al., 2023a). We show similar results in Figure 4 for Federated EMNIST (Caldas al., 2018). It can also be observed in Ta- bles 1 and 2 that our solution is lightweight. Indeed, DMM adds less than 10 seconds of computation and in some cases less than 2 MB of communication per client compared to the prior distributed DP approach of secure aggregation.
Prooquette-Choo et al., 2023a), and
Related Work. In concurrent work, (Ball et al., 2024) take another approach to our problem, without secret sharing. They instead separately maintain aggregate noise and gradi- ent encryptions across iterations using (linearly homomor- phic) encryption. These encryptions are then added together by the server and decrypted using clients' noisy secret keys (that do not reveal the actual secret keys) in a clever fasion to reveal only the sums with correlated noise in each itcration. They also sketch a solution with dropout resilience. Ball al. do not provide any code or straightforward method for calculating communication costs; however, we expect their communication complexity to be better than ours. Yet, since they rely on computational assumptions for linearly homomorphic encryption, whereas we just use information- theoretic secret sharing techinques, we expect ours to be faster. Moreover, Ball et al. do not have a maliciously secure protocol.
New distributed DP mechanisms for FL, the Skellam Mechanism (Agarwal et al., 2021), and Distributed Mean Estimation (DME), the Poisson Binomial Mechanism (PBM) (Chen et al., 2022), have appeared in the literature re- cently, mostly improving the efficiency of DDG. Indeed, in these works, is shown that th roughly the same privacy-utility tradeoff as DDG is acheived by the Skellam Mechanism, while PBM is not compared empirically to DDG, nor are FL experiments with PBM provided (though they state that their asymptotic error for DME is the same as DDG). We there- fore refer to (Kairouz et al., 2021a) as the state-of-the-art for privacy-utility tradeoff. Furthermore, PBM specifically does not seem suited to our techniques, since it departs from the additive noise paradigm.
A fruitful line of works has used correlated noise, and in particular, the matrix mechanism to improve the privacy- utility tradeoff and memory costs of (central) DP FL for increasingly realistic multi-participation settings (Kairouz et al., 2021b: Denisov et al., 2023; Choquette-Choo et al., 2023b:a; Dvijotham et al., 2024; McMahan et al., 2024). Privacy amplification techniques like shuffling (Erlingsson et al., 2019; Feldman et al., 2022) (Poisson) subsam- pling (Abadi et al., 2016; Zhu & Wang, 2019; Wang et al., 2019) are sometimes used to increase privacy-utility trade- offs; however, these require strong assumptions on how data is processed which are often not suitable for FL in practice and thus should be avoided (Kairouz et al., 2021b).
Several works have considered so-called proactive secret sharing (Ostrovsky & Yung, 1991; Baron et al., 2014; Maram et al., 2019). This setting is similar to ours in which secrets are reshared, however, there the users stay the same in each iteration; just the users that are corrupted changes in each iteration. Papers that study similar model to ours ex- ist, but for more general computations than the special case of aggregation and without a central server that minimizes interaction between clients, and thus are inefficient (Gentry et al., 2021; Bienstock et al., 2023; Choudhuri et al., 2021; Rachuri & Scholl, 2022; Bienstock et al., 2025).
3

---

DMM: Distributed Matrix Mechanism for Differeetially-Priival Federated Learning
2. Preliminaries
2.2. Problem Statement and Security Model
2.1. Differentially Private Federated Learning
For each iteration T' [2*), we have a committee of (dif- ferent) clients Cr. The clients in this committee receive the current model parameters I from the server and some values (secret shares) from the previous committee Cr-1- Each client Pr, uses 0 and their private data to obtain gradients 9r,s and also samples noise TT, from some distribution D. These clients then interact with each other and the server with the goal of revealing only AX, = + to the server, where each entry XT = and ZT Di= Zr, for T' E [T We allow te clients per iter- ation as well as the server to be corrupted by an adversary A; i.e., A can use the values sent to the corrupted parties to try to learn anything besides each AXT. In fact, we handle malicious adversaries that can send arbitrary values to other parties. We allow such adversaries to change each AX, T received by the server by some additive XT factors that are independent of 9r..* Zr,,, for T E [T") of the other clients; thus preserving DP. We also allow ta honest clients per it- eration to drop out; in this case the correct AXr should still be received by the server (with added Xr defined by the adversary). We require ta + to < (1/2 - p)m, for con- stant 0 < μ < 1/2, to guarantee security. In Section C, we formalize this model using a standard simulation-style definition (Goldreich, 2004) and show that such adversaries cannot learn anything besides AX.
In this section, we define some notions important to DPFL. Let T* be the number of training iterations, n the number of parties in each committee, and d model dimension.
Adjacency and Participation Schemas. DP requires notion of adjacent datasets. Two data streams X and X are adjacent if the data associated with any single user is altered, in every iteration in which the user participates. 2 The pattern of when this user participates does not change in these two adjacent streams. A participation schema & contains all possible participation pattems & E 2. with each & C [T*] indicating set of iterations in which single user participates. Let Nbrs be the set of all pairs of neighboring streams X and 2 = {X - X (x, X) E Nbrs) } represent the set of all possible differences between neighboring X.X. We say a D satisfies the participation schema + if the indices of all nonzero rows in each IR? xd matrix U D are subset of some Φ E Ø.
Centralized DP Matrix Mechanism. Let A E R XT' be an appropriate linear query workload (e.g.. prefix sums) that is publicly known to all participants. Matrix mechanisms in the central DP setting use a factorization A- = BC to privately estimate the quantity AX as AX = B(CX + Z), where Z is sampled by the central server from some noise distribution.
2.3. (Packed) Secret Sharing
Each entry of the vector AX corresponds to a model itera- tion that is released. The matrix A is lower-diagonal, which means that the T-th entry of AX only depends on the first T entries of X, for each dimension. Additionally, the T-th entry of AX depends on the first T entries of Z, which means that the noise used in each released model iteration correlated.
Let IF be a finite field. Recall te is the number of maliciously corrupted parties in each committee. A (tz + 1)-out-of-n secret sharing scheme takes as input secret from FF and outputs n shares, one for each party, with the property that it is possible to efficiently recover from every subset of te + 1 shares, but every subset of at most t. shares reveals nothing about the secret z.
We now define the sensitivity of the central DP ma- trix mechanism for particular participation schema 4 with set of neighboring streams Nbrs as sense (C) sup (X xxxx))eerre |[X - |I = supueo ||CU|| ||..3 As in previous works, it is useful to analyze sens (C) when all of the contributions from users are clipped to &s norm at most с = 1. noting that the actual value of sensp (C) scales with c in general. In our work, however, it is useful to explicitly define the sensitivity for contributions of &g norm e == 1 as senst (C). The expected total squared error on A is typically given as L(B, C)= sens. (C)l j and the goal is to find factorization that minimizes this loss.
A secret sharing scheme consists of two algorithms: the first, Share, takes as input the secret and the parameters n and te, and outputs n shares: (2 (z'....,.2) 2))
Share(z, n, tc).
We denote the vector of shares as [æ],, = (2 (z!....,.2) 2²). The second algorithm, Recons, takes as input a set of re- constructing parties r S [n]] and share 2 and outputs a reconstruction value Recons(T, = We will utilize secret sharing schemes which X 2 Recons(T, for some constant X; dependent on and r. If [T] > Le + then these reconstruction values can be simply summed to obtain z = E, 2' The secret sharing scheme we use is also lin- ear, meaning that if the parties compute [21]e, + [Zele.. then invoke Recons to get reconstruction values X; (zt + 25) for big enough set I' of parties, summing these reconstruction values will yield 2 + 22 = Σ, (x + z1). One instantia- tion of secret sharing uses random degree le polynomial fz)), where the secret is stored at (0) and the share of each
We study the more general user-level DP in this work, as opposed to example-level DP. *|I ||r is the Frobenius norm.
4

---

DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning
P, is [i) (Shamir, 1979). Reconstruction uses polynomial interpolation, where the X; are Lagrange coefficients.
tion T (so there are k2 total secrets). The next algorithm, called the resharing algorithm, Reshare, takes as input the k packed shares of party P. of iteration T, which we de- note as the vector zi1,0] = (zi...., = and outputs fresh shares of this vector to the parties of iteration T + 1: [=jaa)] =
Packed secret sharing is an extension of secret sharing, where a secret vector = = (z1...., 2x.) E F* is packed into a single set of (individual) shares. We call lo the packing pa- rameter. We still have that every subset of at most te shares reveals nothing about 2, but we need at least te + k shares to be able to recover z. There are also similar Share and Recons algorithms, and we denote sharing of some vector as [=] = (z), , ................................ )²). In addition, Recons takes as input an index j E [k]] representing the index of the vector to reconstruct. We utilize packed secret sharing schemes in which Xę- x² = Recons(T, j)) for some constant X If [T]] 2 te + k. then 2, can be computed as 2j = =E, X z². The packed secret sharing scheme we use is also linear with respect to vector addition of the underlying secrets. One instantiation of packed secret sharing extends the polyno- mial idea from above-((x) is now degree be + k 1 and each secret 2, is stored at f(-j); everything else stays the same (Franklin& & Yung, 1992).
= Reshare(z11,0 Next, the recovery algorithm, Recover, takes as input the set of dropout parties Dropr of iteration T and the re- shared shares of non-dropout parties of iteration T sent to party Pj of iteration T + 1, (z) ..... (z M,,, for : in E [m|] Dropy. and outputs new shares of the orig- inal secret vectors 21...., 2x for party P3: (s),..., # Recover (Droprr (z f1. V...., (1) The last algo- rithm Recons is also inherited from the underlying linear packed secret sharing scheme.
We present protocol LRP below.
R Outputs [=(1,a] = Share(z(u.))
Recover(Drop, (=fi,,))* ,.... ()); Computes
,....
2/1 Σ, Recoos Drop, (=i,,)),, m)), for
In the following, Le and k will be fixed, so we will simply refer to packed secret sharings as [z].
m E [k]. Then outputs (2f.... 2/)
Now we observe how Recover(-) outputs packed shares of the original secrets.
Recall that (=il,))', so
3. Linear Secret Resharing Protocol
Recons( (nooop Drop, (z(i.M)),, m) = AM
In this section, we present our constant-overhead linear secret resharing protocol, LRP.
P. Moreover, each (=fi.,))² is a share of vector [[1.)] = (z))...., =x))= for a lin- ear packed secret sharing scheme. Thus, are computing new packed shares of the vectors A. (2 (.i z
we can re-write 2/1 = Σ1 Am
We start with the naive n² -e-vveheead protocol, which follows from classical crypto- graphic literature (Ben-Or et al., 1988). Let it be the case that a secret sharing [z] has been generated for parties in a given committee. To reshare this value the parties of the next committee, each party P. in this committee distributes to them sharing [=*] of their share. Since we know it is the case that 2 = Σ; - = Σ, Recons(T", , 2²) and the secret sharing is linear, the parties in the next committee can sim- ply compute their new sharing of z to be [a'] = Σ, A : [2*], and it is clear that z' = z (the parties of this second com- mittee must also know I' the subset of clients who did not drop out in the first committee). The problem with this protocol is of course that it has n² total communication overhead-eate each of n parties has to distribute shares to the next committee.
Naive n2-Overhead Protocol.
Each zú was itself P 's share of vector zę- Thus the packed shares we are computing indeed share the vectors:
Σ Nx
Recons((n)) (rroons(n))\ropp.... mi,
(oanns((n)))DDppp. = =/.m)) m))
(Z1, ........ Z
Security. It is clear that the output of Reshare() reveals nothing to the te corrupted parties, since it just uses Share() of the underlying packed secret sharing scheme, that is secure against te corrupted parties. Since the number of honest parties that do not dropout is least n - ta - te > (1/2 + 11),, it is clear that this protocol is resilient to the ta (honest) dropout parties, if k I 2un. This is because to + k & (1/2 + p)n < n - ta ter so the shares of the parties that do not dropout can still be used to reconstruct
Our -onstant-Overheadd Protocol. We can instead start by using packed secret sharing. Our resharing protocol is pictorially presented and summarized in Figure 3. It works by cleverly batching across many packed sharings. Our resharing protocol consists of four algorithms: it inherits the first algorithm Share from an underlying linear packed secret sharing scheme. Now, let it be the case that k packed secret sharings [=1],-.. [æx], for length-k secret vectors 21. 2g E F are distributed to the n parties of itera-
"Note: the output shares are for length-k secret vectors (=1.my-... 2t.m) for each m E R). instead of (zt,1...., =c,)). for each e E [k).
5

---

DMM: Distributed Matrix Mechanism for Sutterentially-Privatt Federated Learning
Users
Users
Users
[+)] Share(#i)
21
21,1
21,A
[aa] Share(az)
[+fLaj] Reshare
nn
Fm.,1
Fnckk
[xr] Share(z.)
Iteration T
Iteration T+1 Extract:
Combine packed sharings of secret vectors one packing [+j.e]
(4f
(4 (+Baa))
Recover
Figure 3. Constant-Overhcad Linear Secret Resharing Protocol, LRP. At a high level, parties P, in itcration T each receive packed secret sharings [z.]. Then, the parties of iteration T reshare these packed shares by distributing packed sharings of these packed shares to the parties of iteration T' + I, who finally recover packed shares of the original secret vectors 21...., Zn.
in the secret space during Recover. The fact that malicious parties can only cause reconstructed values to be perturbed by an independent value follows from standard facts about secret sharing (Genkin et al., 2014), 4). We formally prove the security and dropout-rrslliency of LRP in Section C.
reshared by party is in the previous iteration. The clients first recover shares of the same:
7, Z
Recover (rroper-rrop--i (2",,,0),........ (Z, (Z)1),)))))
Communication Complexity. Let k 2pm. The commu- nication cost of both Share and Recons is n field elements for k secrets, which is 1/22 per secret. The total commu- nication complexity of Reshare is n² field elements-eate party sends a share to every party in the next iteration. This for 1.2 = 4y²nn secrets, which 1/ 1/4p² per secret. Thus, the communication is at most 1/ 1/4,² per secret (μ < 1/2).
(X²
Recover (X" (1,1)))) ...... (x +
based on iteration dropout clients Dropy-1 received from the server.
Next, as in the distributed setting, the clients will compute their local gradients gr, (clipped, scaled, flattened, and rounded as in (Kairouz et al., 2021a)) and sample žT,; from a noise distribution D. Then, each client will compute some secret shares [æT,5], [gr.]] of their local gradients and noise and distribute them to the other clients of this iteration. Once receiving these shares, the parties (locally) aggregate them: [Z]] (=r.(_)))) and [X]] 1 (9r,,)))
4. Distributed Matrix Mechanism
We now present our Distributed Matrix Mechanism. See Protocol I for a detailed description of πMMM- We will as- sume that each committee has the same number n clients. We write the protocol in terms of batches of gradients of size k?2 where l is the packing parameter: if the model dimen- sion d 2.2 then the parties repeat ΠMMM over batches." 5
The parties then take linear combinations, according to A and B, of the packed shares of gradients and noise of all previous iterations, including this one, to obtain shares of the next output of the matrix mechanism, [AXr] r]. The parties then reconstruct these noisy gradients to the server (which are then unflattened and rescaled by the server (Kairouz et al., 2021a)).
Each iteration of this protocol is completed in two commu- nication rounds. 6 In the T-th iteration, we will assume that the n clients selected have received, for т E [T - 1). (i) [X 11 which are the (aggregated) gradient shares from the first - iterations, reshared by non-dropout party i in the previous iteration; and (ii) p..l. which are the (ag- gregated) noise shares sampled in the first T iterations,
Finally, the clients will reshare their shares 2a,1,a and X [.11 of the aggregated noise and gradients from the first T iterations. The clients reshare the shares according to protocol LRP in Section 3.
'ee also assume that communication between clients in доMм done via authenticated and encrypted channels, routed through the server and using a Public-Key Infrastructure (PKT), as in previ- ous works, e.g., (Bonawitz et al., 2017), etc.
An Optimization. Typically, the matrix A is just the prefix matrix. In this case, the server anyway AX₂
"Note that if there are no dropouts, each iteration can complete in one communication round.
AX T = Xx + (Bir.) B(r-1.)) Z, so we can just
6

---

DMM: Distributed Matrix Mechanism for Differentially-Priee Privatt Federated Learning
Protocol Differentially-Priiee Privvate Federated Learning Protocol д.MM
Subprotocols: LRP (Share, Reshare, Recons, Recover) is secret resharing protocol (See Section 3). Parameters: Packing parameter k E N; number of iterations T"; finite field IF of bit-width m; matrix A E IRT xT" and B, C such that A = BC; noise distribution D.
Inputs: Current iteration T; gradients gr.j........1 -T.jkk E Ih list of dropped clients from iteration T - 1, Dropy-1 (If [Drop--l < le + k; then abort); reshared gradients and noise received from Cr-1 for the first T iterations
{[* Rt (. [Z" Per-
Round 1:
Parties P,:
Sample noise vectors g.......... r E from D.
For each E [k]. distribute packed secret sharings ael = Share (x...)) and gr. = Share(gr...) to the set Cp of clients this training iteration (via authenticated and encrypted channels through the server).
Server:
Receive from each Party Pj in Cr and register dropped clients in list Dropy-
Forward (encrypted) shares [Zr.,ee and [gr...e to the other clients of Cr, along with Drop
Round 2:
Parties Pj:
Receive from server the list of dropped clients from iteration T, Dropy:
For each [k:, aggregate r_, (Enee(i)) Drop,
Dropp, (=),,.e) and [X T. (nne(n) Dorep (e).: then reshare
[z [1,
= Reshare Reshare(Z2..... p1,x)) and [X] T. Reshare X) T.11.M) the set of clients in Cr41 (via authenticated and
encrypted channels through the sever).
If 1:
-For each é [k], compute [Yi,d] = Ap,j [X + Bu.1 [Z1, then send shares Y to the server.
-Fo
T T -1], recover (2 (Z,,,,... 2x,a)
Recover(Dropy-.. (Z.) (1,,))) ..... .., (Z (Z"(1a))) and
(X) T.1 ......11 x Recover (Dro (X",
r. 7. ...., (X
in T. y) obtain shares [2r,]] and [X=,e] for l E [R).
Then again reshare as | = Reshare 2 (1,11) and [x] 7111,)] = Reshare (Xx T(1,AA) to set Cr+1 (via authen- ticated and encrypted channels through the sever).
For each & [k), compute [Yr,s] Σ A [M [x,{] By (2r,e), then send shares Yí to the server.
Server:
Receive from each Party P3 in Cr and register dropped clients in list Dropy-
For each É, f.m [k), compute and output Yr,,m jjj Recons([n) Drop, Y m).
Forward (encrypted) reshares to the clients of Cr+1 and send dropped clients list Dropr clients of Cr+1
reconstruct this it, and do not need reshare the gradients X across iterations, saving factor of two. This is how we compute the communication complexity of our protocol.
et al., 2021b; lb; Honaker, 2015), where C is essentially the binary tree matrix,? This mechanism has the benefit that it allows for implementations with only (dlog (4/))) total communication complexity; in the T-th iteration, the released model can be computed by a sum of at most d log(T) sharings.
Matrix Factorizations and Communication Complexity. We use two different matrix factorizations BC for our experiments. The first is the optimal with respect the loss function C(B, C) sens4. [ for the 6-min-sep- participation schema & this case, in iteration T, the total communication complexity is (d T)/ (4,²), using & = 2pn as above. The second factorization is the Honaker Online mechanism (Kairouz
Security. We formally prove the security of дμрм in Sec- tion C based the security of LRP, i.e., nothing but the noisy gradients revealed to adversary corrupting at
Sroqueette-hhoo et al., 2023a). In
"Ioиm easily any factorization, including BLT's (McMahan al., 2024), which are not open sourced.

---

DMM: Distributed Matrix Mechanism for Differrentilll-Prriatt Federated Learning
most le parties in each iteration and the server. We also prove dropout tolerance and distributed DP even in the pres- ence of corrupted parties that perturb the noisy gradients released to the server by independent values X-
Then ΠMM atlains 3e²² -concennttt DP and accuracy:
T
Σ
E
(X) -A(TH))
X;
1m1
Privacy. We now state the privacy of our protocol when the noise distribution D is the Discrete Gaussian distribu- tion with mean 0 and variance o² //2 .2 o² /22). We note that another option for noise is the Skellam Distribu- tion (Agarwal et al., 2021) that yields roughly the same privacy-utility tradeoff; thus we stick to the more standard Discrete Gaussian. Moreover, our preliminary experiments showed that the Skellam Distribution did not seem to per- form even close to as well emprically as the Discrete Gaus- sian, Another tempting choice to obtain DP is to use the technique of the Poisson Binomial Mechanism (Chen al., 2022), however, that work departs from the additive noise paradigm and thus does not seem applicable for us.
c²A2d [BI|
0
6²
5. Experiments
Here we empirically evaluate DMM for FL on the Stack Overflow Next Word Prediction (SO-NWP) (Authors, 2019) and FEMNIST (Caldas et al., 2018) public benchmarks. We compare to the prior ofate-of-the art for privacy-utility tradeoff with distributed DP, the Distributed Discrete Gaus- sian Mechanism (DDG) (Kairouz et al., 2021a) which also uses privacy amplification via sampling (DMM does not), and central DP, BandMF (Choquette- Chhoo et al., 2023a). Our full experimental setup is described in Section D, and closely follows prior work, including model hyperparame- ters (Kairouz et al., 202 Choquette-Chov et al., 2023a), All experiments are run on machine with an AMD EPYC 7R32 processor and an A10G GPU. See Section D for fur- ther evaluation of our results.
First we explain some parameters: e is the norm to which gradients are clipped, 7 > 0 is used to determine the gran- ularity for the discretization of gradients, 3 determines the bias of the randomized rounding for discretization, and o is the noise scale of the Discrete Gaussians. Details on these steps (from (Kairouz et al., 2021a)) are provided in Section A. The following theorem is proved in Section B.
Privacy Parameters and Selected Hyperparameters. For both matrix factorizations, we measure (C) with respect to the ing Choquette-Choo et al. (2023a, Theorems 2 and 3). For SO-NWP, we use 7 = 2052 and b = 342 (as in (Choquette- Choo et al., 2023a)) and we use T = 2 = 2048 and = 512 for the Honaker factorization, since T needs to be power of two. For FEMNIST, we use T 1445 (similar to (Kairouz et al., 2021a)) and 85 for the optimal factor- ization and T = 20 1024 and 6 64 for the Honaker factorization the reason for smaller bands is that there is less data in the FEMNIST dataset, which means clients have to participate more often.
Theorem 4.1. Consider a query matrix A E TR. xT" along with a fixed factorization A- = BC with A = sens, (C).
sepppatiiiippiioonnn schema us-
Let T 10 Ek=
-2n 7 A and
72 2og (1/3) (ct 7 vaa)
(++
d
8 = min
4
(c+
Then μOMM satisfies 1 conccennetre DP for
E == min {
ARE no² + 2Td,
vna + VVd]
Ae
Accuracy. We now formally prove the accuracy of our Distributed Matrix Mechanism (DMM). First, we explain an additional parameter: is the bit-width of the finite field F used in OMM. We prove the following in Section B. Theorem 4.2. Let n, m, d, T E N, and s $ 0 satisfy:
Results. For performance evaluation of DMM, we use n 40 clients per iteration. Figures 2 and 4 show that across e privacy levels, our DMM significantly outperforms DDG in terms of classification accuracy. This is precisely be- cause DMM uses correlated noise across iterations, whereas DDG uses fresh noise in each iteration. Our DMM also gets accuracy close to that of the otate-of-the-art central DP solutions for SO-NWP. This gap comes from the er- ror introduced in discretizing values and modular clipping that both arise from DMM representing numbers as finite field elements, well some error arising from summing Discrete Gaussians (see Section B). These errors are also present in DDG (Kairouz et al., 2021a). We also see that using the Honaker factorization only slightly degrades the accuracy compared to the mechanism based on the optimal amin-sep-participatie matrix factorization. Therefore, the
VdA
m 2 Ō max AAATIIlVTTT + max TETT
| BBTT)lla
TETT-1
Ler 'lMм be instantiated with parameters
7 δ max [|Agr.allzew 1l2eww
maxrelr"
myd
2m
< θ (H), and Ô
cA EVD
+
'Note that, as with prior work in the distributed DP setting, e.g., (Kairouz et al., 2021a), must use discrete noise. This is because cryptographic techniques work over finite, discrete algehraic structures (like finite fieldstingv/groups.
8

---

DMM: Distributed Matrix Mechanism for Differentially-Prise Priiitt Federated Learning
LRP Comp.
SecAgg Comp.
LRP
Naive SR
SecAgg
Accuracy Epsilon Federated EMNIST
Comm.
Comm.
Comm.
IMH Opt mel Factortocion
Opt.
3,34 s
58.5 ms
828 MB
379 GB
4.07 MB
Local UP DDG
Hon.
94.2 ms
58.5 ms
5.73 MB
2.61 GB
4.07 MB
Average Accurscy
Table 2. Client computation and communication of our LRP re- sharing protocol, naive secret resharing, and SecAgg per iteration on Federated EMNIST for committee size n = 64. We give re- sults for both the optimal and more efficient Honaker online matrix mechanisms. (ms == milliseconds; s = seconds).
0.5
0.0
*paikon Melces
Figure 4. Test. accuracies on FEMNIST actoss different privacy levels for the distributed DP DDG mechanism and our distributed DP DMM instantiated with the optimal matrix factorization and the Honaker online matrix factorization. DMM performs = 4 percentage points better than the prior distributed DP approach. We use 6 I/N for (z, 8)-DP, where N is the total number of clients across training.
In terms of communication, we see an increase of < 10 MB with the Honaker online factorization from LRP in DMM compared to that of SecAgg in DDG. We believe that this added overhead is worth it given the increased accuracy.
6. Conclusion
We present in this paper the Distributed Matrix Mechanism (DMM) for FL, which achieves both distributed DP and privacy-utility trade-off of the matrix mechanism for central DP in FL. Along the way, we introduce a constant-overhead linear secret resharing protocol LRP. We validate experi- mentally the utility and efficiency of DMM. Future work includes designing better low- memory matrix factorizations to get efficiency with better accuracy, as well adding ma- licious security to the encryption approach of (Ball et al., 2024).
tree mechanism might be best in practice due to much better efficiency, seen below.
Efficiency. Tables 1 and show client computation and communication costs of DMM for SO-NWP and FEMNIST, respectively, using both the optimal matrix factorization and the Honaker matrix factorization. We show the costs of SecAgg (the bottleneck of DDG) using the Flamingo construction (Ma et al., 2023) (recall: any SecAgg protocol can be used; Flamingo is the state-of-the-un and the costs of the resharing protocol LRP in IDDMM. We also give the communication costs of the naive secret resharing protocol of Section 3. For [DMM. we assume μ 1/6; i.e., the num- ber of corrupted and dropout parties per iteration satisfies to + ta < n²/3. We use 32 bits to represent field values. For computational experiments, we use n = 64, as the Flamingo code requires powers of two. For the optimal matrix fac- torization results, we report the worst-case complexity per iteration, which is the penultimate iteration, since clients reshare the noise from all previous iterations.
A Acknovledgements
We thank Keith Rush for providing valuable assistance with the code used to factorize matrices optimally.
Disclaimer
Disclaimer: This paper was prepared for informational pur- poses by the Artificial Intelligence Research group of JP- Morgan Chase & Co. and its affiliates ("JP Morgan") and is not product of the Research Department of JP Morgan. JP Morgan makes representation and warranty whatsoever and disclaims all liability, for the completeness, accuracy or reliability of the information contained herein. This docu- ment is not intended as investment research or investment advice, or a recommendation, offer or solicitation for the purchase or sale of any security, financial instrument, fi- nancial product or service, or to be used in any way for evaluating the merits of participating in any transaction, and shall not constitute a solicitation under any jurisdiction or to any person, if such solicitation under such jurisdiction or to such person would be unlawful.
We see that the naive n² overhead secret resharing protocol has infeasible communication of up to 2.13 TB per client, which is substantially more than the communication of LRP, with communication as low as 5.73 MB per client. We also see that the optimal matrix factorization substantially increases both the computation and communication com- pared to Honaker online factorization. This suggests that the small increase in accuracy from using the optimal matrix factorization may not be worth it in terms of the added effi ciency costs. Compared to SecAgg used by DDG, we see a modest increase in computation with the Honaker online factorization from L LRP in IMMM: less than 10 seconds (and sometimes less than 100 ms) per iteration is very reasonable.
2025 JPMorgan Chase & Co. All rights reserved.

---

DMM: Distributed Matrix Mechanism for Differeettilly-PPriatt Federated Learning
Impact Statement
pp. 293-302, New York, NY, USA, 2014. Associa- tion for Computing Machinery. ISBN 9781450329446. doi: 10. 10.114522114422226114744, URL ht sttps:///oi.. /doi. /0/ 111..1.1//61114422222222 2611474,
Our work provides privacy for FL using formal (e, 6)- guarantees. One should ensure when using DP that the used (e, 0) privacy levels are adequate for protecting sensitive data in their setting.
Ben-Or, M., Goldwasser, S., and Wigderson, A. Com- pleteness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the Twenti- eth Annual ACM Symposium on Theory of Computing, STOC 88, pp. 1-10, New York, NY. USA, 1988. Associ- ation for Computing Machinery. ISBN 0897912640, doi: 10. 10.1145/62212.62223.. URL https: http:///oo.ooo...///// 1145 62212.62211
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learn- ing with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Com- munications Security, CCS '16, pp. 308-318, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341394. doi: 10.1145/ 2978749.
Bienstock, A., Escudero, D., and Polychroniadou, A. On linear communication complexity for (maximally) fluid mpc. In Advances in Cryptology CRYPTO 2023: 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part I, pp. 263-294, Berlin, Heidelberg, 2023. Springer- ISBN 978-3-031-38556- doi: 10. 10.1007/976-33001--8855-------- 9. URL https: /doii. 10 org/10. 101.-11007778---1-888-----5
URL pettps:/doi..oo 1145/2976749 2T9127777779...781...
Agarwal, N., Kairouz, P., and Liu, Z. The skellam mech- anism for differentially private federated learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393.
Bienstock, A., Escudero, D., and Polychroniadou, A. Per- fectly secure fluid MPC with abort and linear communi- cation complexity. IACR Communications in Cryptology, 1(4), 2025. ISSN 3006-5496. doi: 10.62056/aesg89n4e.
Asoodeh, S., Liao, J.. Calmon, P., Kosut, O., and Sankar, I.. A better bound gives hundred rounds: En- hanced privacy guarantees via f-divergences. In 2020 IEEE International Symposium Information Theory (ISIT), pp. 920-925. IEEE Press, 2020. doi: 10.1 10.1109/ 109/ 1S1744444.0020.1144015. URL https: /ww.ioooorrr./o .rg/ 10. 10.1109/18I744488 2020. 9174015.
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 Com- munications Security, CCS '17, pp. 1175-1191, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450349468, doi: 10.1145/ 3133956.3133982. URL http:://doi..gg//// 1 1tt.:/3333556333333333
Authors, T. Tensorflow federated stack overflow dataset, 2019.
Ball, M., Bell-Clark, J., Gascon, A., Kairouz, P., Oh, S., and Xie, Z. Secure stateful aggregation: A practical protocol with applications in iffferentialll-privaal federated learn- ing. Cryptology ePrint Archive Paper 2024/1655, 2024. URL https: /eprint..../t/// iacr. /rgg///4//22/000
Bun, M. and Steinke, T. Concentrated differential pri- vacy: Simplifications, extensions, and lower bounds. In Proceedings, Part I, of the 14th International Con- ference on Theory of Cryptography Volume 9985, pp. 635-658, Berlin, Heidelberg, 2016. Springer- Verlag. ISBN 9783662536407. 978-3-662-53641-4 24. URL httt::://doooorggg 10.1007/978 3- 53641-44 44_
Balle, B., Barthe, G., Gaboardi. M., Hsu, J., and Sato, T. Hy- pothesis testing interpretations and renyi differential pri- vacy. In Chiappa, S. and Calandra, R. (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statisties, volume 108 of Proceedings of Machine Learning Research, pp. 2596. PMLR, 26- 28 Aug 2020. URL https: /tt:://prrooo http///ooceeeng..c//o/ ml.r. press/v10s 1w1100//aaaeeaaa..m html.
doi: 10.1007/
Caldas, S., Wu, P., Li, T. Konecný. J., McMahan, H. B., Smith, V., and Talwalkar, A. Leaf: A bench- mark for federated settings. ArXiv, abs/1812.01097, 2018. URL https: //api. semanticscholar. Lts//oorpuID::5300110
Baron, J., El Defrawy, K., Lampkins, J., and Ostro- vsky, R. How to withstand mobile virus attacks, re- visited. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14,
Canonne, C. L., Kamath, G., and Steinke, T. The discrete gaussian for differential privacy. Proceedings of the
10

---

DMM: Distributed Matrix Mechanism for Differentially-Privtt Federated Learning
34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. Differential privacy under continual observation. In Proceedings of the Forty-Second ACM Symposium Theory of Computing, STOC '10, pp. 715-724, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 9781450300566. doi: 10.1145/ 180668.
Chen, W.-N., Ozgur, A., and Kairouz, P. The poisson bi- nomial mechanism for unbiased federated learning with secure aggregation. In Chaudhuri, K., Jegelka, S., Song. L.. Szepesvari, C., Niu, G., and Sabato, S. (eds.), Pro- ceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 3490-3506. PMLR, 17-23 Jul 2022. URL https: pptpp/eeeceeeess.ceee/pepe mwr. press// v1 v162/chen224 html.
URL https://doi. org/10. 1145/1806689.0 1806787.
Frlingsson, Ú. Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., and Thakurta, A. Amplification by shuffling: From local to central differential privacy via anonymity. In Chan, T. M. (ed.), Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 2468-2479, SIAM, 2019. doi: 10.113771.978111119754422, 151. URL https: /doi. 151.
Choquette-Chox C. A., Ganesh, A., McKenna, R., McMa- han, H. B., Rush, K., Thakurta, A., and Xu, Z.. (amplified) banded matrix factorization: A unified approach to pri- vate training. In 37th Conference on Neural Information Processing Systems (NeurlPs 2023), 2023a.
Fallah, A., Mokhtari, A., and Ozdaglar, A. Personalized federated learning with theoretical guarantees:
Choquette-Choo, C. A., McMahan, H. B., Rush, K., and Thakurta, A. Multi-epoch matrix factorization mecha- nisms for private machine leanring. In 40th International Conference on Machine Learning, 2023b.
model-agnostic meta-learning approach. In Neural Information Processing Systems, 2020. URL https: //api. semanticscholee. wwwpllarrrrr//oopossttt 227276412.
Choudhuri, A. R., Goel, A., Green, M., Jain, A., and Kaptchuk, G. Fluid mpe: Secure multiparty computation with dynamic participants. pp. 94-123, Berlin, Heidel- berg. 2021. Springer- Verlag. ISBN 10--3--000024---- doi: 10. 10.1007/978----000-88888 doi. 11..0.100/99999 0000:/99788--00-8------
Fang. M., Cao, X., Jia, J., and Gong, N. Z. Local model poi- soning attacks to byzantine- robusst federated learning. In Proceedings of the 29th USENIX Conference on Security Symposium, SEC' USA, 2020. USENIX Association. ISBN 978-1-939133-1755
URL https: //
Denisov, S., McMahan, B., Rush, K., Smith, A., and Thakurta, A. G. Improved differential privacy for sgd via optimal private linear operators on adaptive streams. In 36th Conference on Neural Information Processing Systems (NeurIPS 2022), 2023.
Feldman, V., McMillan, A., and Talwar, K. Hiding among the clones: A simple and nearly optimal analysis of pri- vacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 954 964, 2022. doi: 10. 10.1109FFCCS52999
Dvijotham, K. D., McMahan, H. B., Pillutla, K., Steinke, T., and Thakurta, A. Efficient and Optrmml Noise Generation for Streaming Differential Privacy In 2024 IEFF 65th Annual Symposium on Foundations of Computer Science (FOCS), pp. 2306-2317, Los Alamitos, CA, USA, October 2024. IEEE Computer Society. doi: 10.1109/FOCS61266 202...006...2240.33.3. URL https: http://bb...eeccoomprrrrrooeeeee orgg 10. 10.1109/F0cs612e6 2024.
Franklin, M. and Yung, M. Communication complexity of secure computation (extended abstract). In Proceedings of the Ewvnty-Fourrds Annual ACM Symposium on The- ory of Computing, STOC '92, pp. 199-710, New York, NY, USA. 1992. Association for Computing Machinery. ISBN 0897915119. doi: 10. 10.1145/1297122112998. URL https: / /oii
Genkin, D., Ishai, Y., Prabhakaran, M. M., Sahai, A., and Tromer, E. Circuits resilient to additive attacks with applications
Dwork, C. and Rothblum, G. N. Concentrated differential privacy. CoRR, abs//6603.0188) 2016. URL http: weaaxiv.org/ae abs 603 01887.
secure computation. In Proceed- ings of the Forty-Sixth Annual ACM Symposium Theory of Computing, STOC '14, pp. 495-504, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450327107. 2591796.2591861. URL attps://dat /ttp:://dooooo//0/// 1145/2591796. 2591861..
Dwork, C., McSherry F., Nissim, K., and Smith, A. Cal- ibrating noise to sensitivity in private data analysis. In Halevi, S. and Rabin, T. (eds.), Theory of Cryptography, pp. 265 284, Berlin, Heidelberg, 2006. Springer Berlin Heidelherg. ISBN 978-3-540-32732-55
doi: 10.1145/

---

DMM: Distributed Matrix Mechanism for DifferrentialyyPriiaal Federated Learning
Gentry, C.,, Halevi, S., Krawezyk, H., Magri, B., Nielsen, J. B., Rabin, Tr, and Yakoubov, S. Yoso: You only speak once. In Malkin, T. and Peikert, C. (eds.), Ad- vances in Cryptology- - CRYPTO 2021, pp. 64 64-93, Cham, 2021. Springer International Publishing. ISBN 978-3- 030-84245-1.
of Machine Learning Research, pp. 1243-1252. PMLR, 2022.
ml r. ppress/
v180 v180/1iu22c.
Ma, Y., Woods, J., Angel. S., Polychroniadou, A.,, and Rabin,
T. Flamingo: Multi-round single-server secure aggrega- tion with applications to private federated learning. In 2023 IEEE Symposüum on Security and Privacy (SP), pp. 477-496, Los Alamitos, CA, USA, may 2023, IEEE Com- puter Society. doi: 10.1 00.11000PP6611..22331119999 URL. https: / /dwi. ieeecoompttrrsocceeyy org/10. (00..119/SPP4500 2111442221.2.22...1..12 10179434.
Goldreich, O. Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press, USA, 2004. ISBN 0521830842.
Honaker, J. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2, 2015.
Maram, S. K. D., Zhang, F., Wang, L., Low. A., Zhang, Y., Juels, A., and Song, D. Churp: Dynamic-commitee proactive secret sharing. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Commu- nications Security, CCS '19, pp. 2369-2386, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367479. doi: 10.1145/ 3319535.3363200 URL ptttps://di..rgg// 1145/331990 9535. 3363203.
Hubert Chan, T.-H., Shi, E., and Song, D. Private and continual release of statistics. In Abramsky. S., Gavoille, C.,, Kirchner, C.,, Meyer auf der Heide, F,, and Spirakis, P. G. (eds.), Automata, Languages and Programming, pp. 417, Berlin, Heidelberg. 2010. Springer Berlin Heidelberg. ISBN 978-3-642-14162.11
Kairouz, P., Liu, Z., and Steinke, T. The distributed dis- crete gaussian mechanism for federated learning with secure aggregation. In 38th International Conference on Machine Learning (ICML 2021), ), 202
Marchand, T., Muzellec, B., Beguier, C., Terrail, J. O. d., and Andreux, M. Securefedyj: a safe feature gaussian- ization protocol for federated learning. 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.
Kairouz, P.. McMahan, B., Song, S., Thakkar, O., Thakurta, A., and Xu, Z. Practical and private (deep) learning without sampling or shuffling. In 38th International Con- ference on Machine Learning (ICML 2021), 2021b. URL 00039.
https: / /aaxiviiivv.....//aaaa/aaaavv.aa http://aaii...oga//////////a
McMahan, H. B., Moore, E., Ramage, D.. Hampson, S., and y Arcas, B. A. Communication-effiiien learning of deep networks from decentralized data. In Interna- tional Conference on Artificial Intelligence and Statistics, 2016. URL https: / /api. semanticschooieeccooeii Arg//ooppsID:1111 :1mrPuuID:19953444 14955348.
Karthikeyan, H. and Polychroniadou, A. OPA: One- shot private aggregation with single client interaction and its applications to federated learning. In Interna- tional Workshop on Federated Foundation Models in Conjunction with NewrlPS 2024, 2024. URL https: i dddiddddappuuuu su
// www.eenrvveee.neeeeeee
McMahan, H. B., Xu, 7., and Zhang, Y. A hassle-free algo- rithm for strong differential privacy in federated learning systems. In Dernoncourt, F., Preotiuc-Pietro, D., and Shimorina, A. (eds.), Proceedings of the 2024 Confer- ence on Empirical Methods Natural Language Pro- cessing: Industry Track, pp. 842-865, Miami, Florida, US, November 2024. Association for Computational Linguistics. doi: 10.8665/w//2224.mmm/pimmd 64. URL halp--nnuutrr... 64/.
Li, H., Lin, H., Polychroniadou, A., and Tessaro, S. Lerna: Secure single-server aggregation via key-homomorphic masking. In Advances in Cryptology ASIACRYPT 2023: 29th International Conference on the Theory and Application of Cryptology and Information Secu- rity, Guangzhou, China, December 4-8, 2023, Proceed- ings, Part 1, pp- 302-334, Berlin, Heidelberg, 2023. doi: 10.
Springer-Verlle ISBN 1188981-99-87200 1007/978- 992--881-999991--111 10. URL https://doi. org/10.
8721-4_10 981--98879999-----111-----------
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263 225-275,77 2017. doi: 10.1109//SFF2017.111
Liu, Z., Chen, S., Ye, J., Fan, J., Li, H., and Li, X. SASH: efficient secure aggregation based on SHPRG for fed- erated learning. In Cussens, J. and Zhang, K. (eds.), Uncertainty in Artificial Intelligence, Proceedings of the Tiigth-Eighth Conference on Uncertainty in Arti- ficial Intelligence, UAI 2022, 1-5 August 2022, Eind- hoven, The Netherlands, volume 180 of Proceedings
Mironov, I., Pandey, O., Reingold, O., and Vadhan, S. Com- putational differential privacy. In Halevi, S. (cd.), Ad- vances in Cryptology CRYPTO 2009, pp. 142, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. ISBN 978-3-642-03356--.
12

---

DMM: Distributed Matrix Mechanism for Differentially-Privte Federated Learning
Ostrovsky, R. and Yung, M. How withstand mobile virus attacks (extended abstract). In Proceedings of the Tenth Annual ACM Symposium on Principles of Dis- tributed Computing, PODC '91, pp. 51-59, New York, NY, USA, 1991. Association for Computing Machinery. ISBN 0897914392. doi: 10.1 10.1145/1126000 12605. URL 112605. Rachuri, R. and Scholl, P. Le mans: Dynamic and fluid mpe for dishonest majority. In Advances in Cryptology CRYPTO 2022: 42nd Annual Interna- tional Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part I, pp- 719-749, Berlin, Heidelberg, 2022. Springer- Verlag. ISBN 978-3-031-15801 978- 778---031--15802-5555 URL https:/ /rri 10. 20.1007/9788 110-007777778---31-------------0
URL wtt.tttts///rroceeiiiig mll. wal...press/ve wangl 3b.html.
Zhu, Y. and Wang, Y.-X. Poission subsampled rényi dif- ferential privacy. In Chaudhuri, K. and Salakhutdinov, (eds.), Proceedings of the 36th International Confer- ence Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 7634-7642. PMLR, 09- mmlr.
https: / /dii.ii..//// org/ 10. 111511111111
15 Jun 2019. URL press/v9t / zhul 1 19..lmml.
doi: 10.1007/
Reddi, S., Charles, Z. B., Zaheer, M. Garrett, Z., Rush, K. Konečný, J., Kumar, S., and McMahan, B. (eds.).
Adaptive Federated Optimization, 2021. URL https:
//openreview.o net.ieeweee/eeee..... heteet/foommmiddddodeeee BB
Sahu, A. K., Li, T., Sanjabi, M., Zaheer, M., Talwalkar, A., and Smith, V. Federated optimization in heterogeneous networks. arXiv: Learning, 2018. URL htwps: //ppi. semanticschole org/ Corpps 99316566.
Shamir, A. How to share secret. Commun. ACM, 22 (11):612-613, November 1979. ISSN 0001-0782. doi: 01145/359916.3599778 URL https: /toi//oiiooooooooooo org/ 10. 10.1145/33 91 359176.
Shao, J., Sun, Y., Li, S., and Zhang, J. Dres-fl: dropout- resilient secure federated learning for non-iid clients via secret data sharing. In Proceedings of the 36th Inter- national Conference Neural Information Processing Systems, NIPS '2, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871082
Tolpegin, V., Truex, S., Gursoy, M. E., and Liu, L. Data poisoning attacks against federated learning systems. In Computer Security ESORICS 2020: 25th Euro- pean Symposium on Research in Computer Security, ES- ORICS 2020, Guildford, UK, September 14-18, 2020, Proceedings, Part pp. 480-501, Berlin, Heidelberg, 2020. Springer-Verlag, ISBN 778-3-000-58950-9 doi: 10.1007/978--3-000-5899--------9 24. URL https:://dae org/10..007/990 3-00007999977-00--88-8-0000 3-0---8931---------- 6_24.
Wang, Y.-X., Balle, B., and Kasiviswanathan, S. P. Sub- sampled renyi differential privacy and analytical mo- ments accountant. In Chaudhuri, K. and Sugiyama, M. (eds.), Proceedings of the Twenty-ecoon Interna- tional Conference on Artificial Intelligence and Statis- tics, volume 89 Proceedings of Machine Learning Research, pp. 1226-1233 1235. PMLR, 16-18 Apr 2019.
13

---

DMM: Distributed Matrix Mechanism for Differentially-Prinn Prrivate Federated Learning
Protocol Client Gradient Processing
Input: Gradient D, E Rd.
Parameters: model dimension d, clipping threshold c >> 0, granularity y, modulus m, noise scale >> 0 and bias 3 E [0, 1).
1. Clip and scale gradient: g min(1, T gi RR
2. Flatten vector: g g E 124.
3. Repeat:
(a) Let 9. E zd be randomized rounding of g i.e., D: is a product distribution with Blg.] 9 and |9: 9 llc <
1.
until ||اا| I minlcm/nnttt///e Vd, /2h2² l (2log(1/B) (c/r + [Vd)).
4. Output: ğ:-
Protocol 3 Server Aggregate Noisy Release Value Processing
Input: Vector AXT-
Parameters: model dimension d, clipping threshold e > 0, granularity y, modulus noise scale > 0 and bias , [0. 1).
1. Map Zm to 1111m/222mm/2 1,, ..r.,,,,,, m/2 1, 1,m that AX is mapped AX E (-m/2, zd (and we have AX, mod AXv.
Output: 7. UUAX E Rd..
Supplementary Material
A. Discretization Details of (Kairouz et al., 2021a)
We use the randomized rounding strategy from (Kairouz al., 2021a) for discretization in πmMм-- At a high-level, each client first clips and scales their imput gradient. Then, the clients flatten their gradient vectors using some unitary matrix U (intuitively, this minimizes the risk of modulo overlap in vector elements that are particularly large). Finally, the clients use a randomized process to round their gradient vectors in Rd to zd. On the sever side, after receiving the aggregated, noise outputs AXT T in each round, the server unflattens the vector by applying U and then descales. Protocols and give more detai, but we refer the readers to (Kairouz et al., 2021a) for full details on possible flattening matrices U and the randomized rounding procedure used.
To help with the analysis, (Kairouz et al., 2021a) uses the following definitions to represent the conditional randomized rounding. We present them verabtim.
Definition A.1 (Randomized Rounding). Let > 0 and d E N. Define R2 Rd + 7gd (where 7dd = ?2................ : 21..... 2d E 2} C Rd)) as follows. For x E [0. yld Rx(x) is product distribution on {0, 2d with mean x; that is, independently for each E [d], we have (x): = 0] = mny and Pr(R (x); = 7 = 2//7. In
general, for E IRd. we have (x) > x / + (1 7(x//]/ here 7 / 7dd is the point x rounded down coordinate-wise to the grid.
Definition A.2 (Conditional Randomized Rounding). Let 0 and d N and G Rd Define R. Rd + -2 G to R. conditioned on the hte output being in G. That is, Pr(RG (x) = y) Pr(R>(x) = v) Pr(R (a) E G] for all
14

---

DMM: Distributed Matrix Mechanism for Differentially-Prinn Federated Learning
y E 72 G, where R, is in Definition A.I.
B. Proofs for Section 4
B.1. Proof of Theorem 4.1
First we recall the notion of Rényi Divergences and Concentrated Differential Privacy (Bun & Steinke, 2016; Dwork & Rothblum, 2016), as well as some other standard DP notions. We also define the Discrete Gaussian and provide its DP guarantees. See (Kairouz et al., 2021a) for more details. Then we prove Thoerem 4.1
Definition B.1 (Rényi Divergences). Let P and Q be probability distributions on some common domain Ω. Assume that P is absolutely continuous with respect to Q so that the Radon-Nikodym derivative P(z)/Q(z) is well-defined for E Ω
For a E (1, 20), we define the Rényi Divergence of order a of P with respect to Q as:
(P(X)
(a(())Q) = a --1 log Ex+p
Q(x)
We also define
(.(II)) = sup D.(II)) aE(1,20)
Definition B.2 (Concentrated Differential Privacy (Bun & Steinke, 2016; Dwork & Rothblum, 2016)). A randomized algorithm M X + y' satisfies fs-concentrated differential privacy iff, for all x, E X differing by the addition or removal of a single user's 's records, we have (.(M (x))) S ==²
Definition B.3 (Rényi Differential Privacy (Mironov, 2017)). A randomized algorithm M X y satisfies (a, s)- Rényi differential privacy iff, for all x. x X' differing by the addition removal of single user's records, have (M) < }
Definition B.4 (Differential Privacy (Dwork et al., 2006)), A randomized algorithm M : X - y satisfies (s, dddiferrnntl privacy iff, for x, af E X' differing by the addition or removal of single user's records, we have
(r( e E ef Pr(M(x') +
for all events E Y. We refer (EPD) pure DP and (s, 6D for 8 0 as approximate DP.
We remark that ] conccenendre DP is equivalent to satisfying (a, _ Rényi DP simultaneously for all a E (1, oo). We also have the following conversion lemma from concentrated to approximate DP (Balle et al., 2020; Canonne et al., 2020; Asoodeh et al., 2020).
Lemma B.5. If M satisfies (s, 0)-DP, then it satisfies - concentraate DP. If M satisfies 2DP then, for any 5 > 0, M satisfies (E.)P(6),0)) 6D-P, where
=²a log(1/a0) + log(1 - 1/a) s a (/)/))))e////l(1111/ (V2)og(1/))+ e/22.
(aD inf a>l
a
Discrete Gaussian Here we define the Discrete Gaussiasn (Canonne al., 2020) and give its DP guarantees.
Definition B.6 (Discrete Gaussian). The discrete Gaussian with scale parameter a > O and location parameter μ E 2 is probability distribution supported on the integers & denoted by NZ o²) and defined by
(a (a=j))2
exp
2
Vx E Z
Pr X=N
(X x) Eyez exp
(y-u)) 2
Proposition B.7 ((Kairouz al., 2021a), Proposition 14). Let 2 2.2 Let X13 t 10, o²) independently for each and
15

---

DMM: Distributed Matrix Mechanism for Sutterentially-Privatt Federated Learning
Let X; (N
Xi,) E zd. Let Zn Ei=1 X zd.
Then, for all A 2 and all (1, 00).
0|/1|2
DaiZill A) S minn
+ rd,
2no²
|
||هاا 1
.T r2d)
+
no²
Vno
(|Alll
2 + +vva)
Vna
where == 10. 10- -2=²d 2t., An algorithm M that adds Zn to a query with &p sensitivity D, satisfies 2o2 ccnceennnere
DP for
A
min
2rd,
n1
A2
A
+2
+
T
no
Vno
42
+TV
Vno
Proof of Theorem 4.1
Proof. First, it is sufficient show that the computation CG Z satisfies - -cnccennntra DP, due to the post processing property of DP. Now consider two datasets G and H differing in one data record according to participation schema t. By assumption in the theorem statement, we have
sens (C) (C)= =, and thus sense (C) C
where d' is the bound the & norm of individual gradient vectors that aggregated. Since rounding techniques from Section A, gradients that are clipped to & norm can actually end up having & norm c' č after rounding, where è is as in the theorem statement. With the bound on the total sensitivity above, we know from Kairouz f -ccccnnentrete DP, with the e from the theorem
the randomized
et al. (2021a, Proposition 14) (reproduced above) that the computation is statement.
B.2. Proof of Theorem 4.2
We first prove the following exact result for the error:
Theorem B.8. Let B E [0, 1), o² 2 7/2 > O, and > O. Let n., d E N and 2 1. Let gr, E Rd with /lgT,ill S e for each i [n]. Let idddd be a random unitary matrix such that
Vo E Rdd e [d]
e Elexp(((Ux)))] exp(t? (110ppp)11//))))
Let
A s (C)
n-1
2n
T = 10
kml
2 + 1 2 + / 2log(1/8) 7 (c+ 1 (dd) (c (c+ (c+
8 min
2 + 2rd, no?
Ač
+ rvd ).
min
Vno
" and really consist of entries that are sums records.
16

---

DMM: Distributed Matrix Mechanism for Differentially-Privee Federated Learning
Then MMм satisftes 2e²² - conccenntte differential privacy.
Let
(x)
p.
T.
1 +
(22.11Apr to²
B 11
4
nnT (2² 11A
+ || o²)
d
o S 2 then
22 |1
2/2. r. e.ee-///a (10
E
(x)
-Arral
Σ 2/
- dn
B
Vn(1 - -B)
1=1
( ( 82.
8².
1/2)
(1A
|B o² o²)
+
-
We start with a modified version of Proposition 26 in (Kairouz et al., 2021a).
Proposition B.9. Let RG be in Definition A.2 and G {y E Rd 1lull2 S A Let IoMM (X) be ΠMм up the point of modular clipping. Consider the parameters from Theorem B.8. Then IIDM'' (X) satisfies }=²² conceenttee differential privacy. Also the following holds.
d. 4(1 - B)
+ (1-3>Van) ))) + 11 n d o².
E
L[MMM' (X) Arr.]
X
((.
Aprial Σ x 1)
exp( 2 11
|| n)
vt E Rd
E exp
(1 - B)nZ
First, the differential privacy claim follows from Kairouz et al. (2021a, Proposition 14). Now, for the utility analysis, have
Proof.
n
E
Πoмм (x) A
Σ
X
E
Ar.
Σ (R (gr.i) gr.i)
+ Br.
? Zr,
1=1
1=1
T
$
A? f.r
E
Σ 1=1
R (gT,s) - gr.i
+ BT, n.
-=1
d2.d.n
(1-g7vv )) + B nn.o?
3
$ A Amal
+ 4(1 4(1 - B)
where the last inequality is due directly to Proposition 26 of (Kairouz et al., 2021
Now, for each i [m), [T], we have that (g.:)) E 1/gra/>] + {0, 7d and a product distribution with mean g
Thus, (g.a) 97,x 7 and product distribution with mean Therefore, by Hoeffding's lemma, have:
T
(g..))) - -r.a))] exp( 2- n -11 -
Vt T Elexp (t. Σ Ar.r
17

---

DMM: Distributed Matrix Mechanism for Differentially-Priin Privvate Federated Learning
Thus,
T
Elexp (t. Σ Ar. Ei=1 Rg(g.. gr.)))
E Rd
Elexp( (t. Σ Ar.
R gr.,)
gr,1))]
Pr(R((gri) E G VT
i=1
exp( 72 n 11 [.,) 12 112113)
(1 3) n' g
Moreover, we have that (Canonne et al., 2020):
Σ Br. Σ 7 2,,i)) expl 8²
n
Vt E Rd
E Exe (t,
n. 2 nn. | 1|012).
Finally, able to prove modified version of Theorem 36 from (Kairouz et al., 2021a).
Proof of Theorem B.8. First, the differential privacy follows from Proposition B.9 and the post-processing property of DP. Now, for the utility, by assumption, we have that
Va E R Vj E B[exp(((Uxx))) S exp((? 1/=/1/)
Therefore,
T
E[exp(!
Σ
AT. (U _
gr. gr.)a)]
II
E Elexp(t: AT, (Ugr.)i)
r=1
(=1
r=1 1=1
exp(t? A7,r 1gr,11//22
i=1
n gr.. (...11//d))
exp(1
||A (r. 12 p.
Combining with the result of Proposition B.9, we have
12 -1-1A1rr [r,a
VI WERVi VERVjE Elexp(1 (A(Ux))))) S exp(
2d
exp((" 12 |A 112
a Bm
. n))
(1 - B)nT
Recall (2(x) = P.IAA m Σ Σn
119 (2 Amall
+ + | |B
By Proposition 35 of (Kairouz et al., 2021a), for all j E [d].
(HMMMM' (Ux)), 'oMM (U < (b - a)²
(1 BYrT e -00-0))7/80(00)
(e
2-3 1207
nod
+e n0 }
where -- and b here. Summing over j E [d] gives
M[I]M( (ToоM'' (U=)) IOMM'' (Um) S 4r2
(1 - B) e 22200
d
18

---

DMM: Distributed Matrix Mechanism for Differentially-Privaa Federated Learning
Continuing with the proof from (Kairouz al., 2021a), get:
B BM] (x) A[T
x x11
i=1
d
e (200110 + (IAuualB:
+ (22---m
(1-3 )²}
< (8r2.
(4(1 - B] (111-3)
(1 - 3)nT
1/2 2
B Brrall n d o²)
dn
22/2. r. e - (2/40((a)
+ (1AAmaa1B (2" 8. g9.n"
1/2
+ B o²
( 1-
1-8 B
Vn(1 3)
With this error bound, assuming that / s 1/ and (2(x)= s <///4lg((r////" we get
E|| [[[)A()) - A [r.)
x11121 S O(dn(()AArraal
72 ++ - o²)).
Proof of Theorem 4.2. Note that r r= mm. We verify that setting the parameters as specified yields _ concentrtte DP and the desired accuracy. First, we have that
2 e² S no² + 2rd
(V no²
+ 20nde 20nde-sP(0/99
2A202
2d12
20nde (0//)3
2 no²
n(a/7)2
Thus the privacy requirement is satisfied as long 2cA/E and (0/7)² > AdA2/e"n, and 20nde 70 S So we can set
a = max
2cA
7dv8d
8d
7
log(
80nd
)} θ
cA
d
7
+
y
log( nt
n n
evn n2
EV 72
n
e
We set B == min min ((2).
Next,
1311
0²
2 +
B +
n
d
4
p|| ||
In
(....
mn 8 m.a 11
d
p| Al
d²
7dds
nd o
0
FnT
+
m
+ B
[r.3 |
+
+
log
d
82
62
p|| (1AArall
c² A²
+ n log 2 nd
50(
InT
B
1/2
))
-
O
A
T.y
En + +|
d
22
19

---

DMM: Distributed Matrix Mechanism for Differentially-Priiee Federated Learning
Now work the asymptoties of the accuracy guarantee:
H| (X) Apr.)
X
dn
2V2 r. (20
+ (14 ( (2+
1/2
< 1 1-
+ +11 o²)
Vn(1 3)aT-1
1
1102
O(dil
re
+ ([. 11812 + B(T..) (1
Vn
/262
O(nd(
|| 11222 + +|IBrr.)) ((20))
T
S O(ni(
exp(
m2m
+ ||A 11272 + | rr:
c²
+
dy
+ + 2og= (
(nd)
nd
g2 1)))
n
862
2
sZn
e Add
m
-
ds
nd c2
S 0
nd
exp(
+ ||A r: 11 +
B T.
+ log"
8²
862
22n
Similarly to the analysis of Theorem 2 in (Kairouz al., 2021a), if
dA
nd
m² 2 O([1 (T..) 11 + pr.
log"
_e ))) loggll11111 + m² m²/nn) n))
dA
0(11 (r: [1 |||+++11rr000 ||
pr.
+ n));
then we can set
72 7²= = 00 pl| 10 1
|| B [
1222 A
log(1 (1 + m² m²/n)
g2
m2
S0 that m² exp(
S 1.
86
This gives us.
[(]) - Apr
X; 1
c² A 2d 82
dA2
nd
< <0I|B ||r
7 + || (1.)).1 1
+++|B ([ 11
+
log²
62 1))
22n
c² Add
A | ||
B(IlBrT.)) [T.)
d
e2
log(1 + m² /n)
dA2
nd
n1(11 + ||
12:1111 112 +
|
+ log²
m²
82n
Ad
log(1 + m2 /n)
< 500|
B B1::111
82
62
m²
dA
( nd
(0l14m..)111
+1 ||4 112 || (1:(
log²
E2 ))))
E2n
s [(I|B
112
2dd
(1
log(1 + m² /n)
n ( (ol +1+ ||4
dA I12
+ log
2 nd
(1)) ())))))
22
m²
22n
So,
m² 2 O(log( + m²/n)n (pll A (r: 11 +1+ ||T 12 B11,
ds
+ log"
(
(1d))
nd
222 )))
22n
2
Appl 1T + B pr:
1 g2
then the mean squared error is 0 B T. over each round from T to T T*
113 A ), as required. The final bound is obtained by simply summing the above
20

---

DMM: Distributed Matrix Mechanism for SutfereettilllyPriiaat Federated Learning
C. DMM Security Model and Proof
C.1. Security proofs
We first provide an intuition on the current analysis for proving the security of cryptographic protocols. In the security proof, we compare between an n-party function f (a1....., (T.) = (y1......W, Mn) and a protocol P( .... that allegedly privately computes the function f. Intuitively, a protocol P correctly and privately computes f if the following hold: (a) Correctness: For every input / = (.1,.-.. , Fn) the output of the parties at the end of the protocol interaction P is the same as [ā)); (b) Privacy: There exists simulator S that receives the input and output of the corrupted parties, and can efficiently generate the messages that the corrupted parties received during the protocol execution. The simulator does not know the input/outputs of the honest parties. Intuitively, the fact that the messages sent by the honest parties can be generated from the input/output of the corrupted parties implies that these messages do not contain any additional information about the inputs of the honest parties besides what is revealed from the output of the computation.
C.2. Security Model
We now introduce the formal security model. We first note that we consider robustness checks on inputs out of the scope of our security model; i.e., we do not cover poisoning attacks, have been extensively studied in the literature, e.g., (Tolpegin et al., 2020; Fang et al., 2020). Indeed, it is the case that malicious parties can imput to the protocol whatever they want as their gradients and noise g, z, which can lead to meaningless model.
We follow the standard real/ideal world security paradigm of (Goldreich, 2004). Consider some multi-party protocol II that is executed by some parties Pı..... PN that are grouped into committees C1...., Cr- from iteration 1 to iteration T" and a server S. Note: the committees can be arbitrarily chosen, but our protocol only provides security if the assumption that the number of parties A corrupts is at most te holds; in other words, we abstract out the committee selection process," 10 Each of these parties has inputs .i...., &N. and they want to evaluate some given functionality F. In our case, the functionality FPPFL is resharing the inputs from all previous committees to the next committee. in each iteration, and then outputting the AX y value to the sever in each iteration T. given some factorization A = BC. The security of protocol II defined by comparing the real-world execution of the protocol with an ideal-world evaluation of by trusted party (ideal functionality), who receives the inputs Bi...., NN from the parties in the clear and simply sends the relevant parties their outputs F(z1,..... ......... 2N) periodically. There is adversary A that chooses corrupt most of the parties in each iteration, along with the server. This adversary A sees all of the messages and inputs and outputs of the corrupted parties and is allowed to act arbitrarily on their behalf. Informally, it is required that for every adversary that corrupts some parties during the protocol execution, there is an adversary S, also referred to as the simulator, which can achieve the same effect and learn the same information in the ideal-world. This simulator only sees what the corrupted parties send to the honest parties and the outputs, not the inputs x of the honest parties. We now formally describe the security definition.
Real Execution. In the real execution, is executed in the presence of the adversary A. The view of party P during an execution of IT, denoted by ViewI consists of the messages receives from the other parties during the execution and P's input. The execution of II in the presence of A on inputs (ai,....; ) denoted R zxx is defined as [View)) The output of II to the honest parties in the presence of A on inputs (xI...., II,)...,)))))) is noted as Output.
Ideal Execution. In the ideal execution, the parties and an ideal world adversary S interact with a trusted party (ideal functionality). The ideal execution proceeds as follows: As a committee Cr comes online, the parties Pr.1. Pr., in that committee send their inputs æT.1..... Ty to the trusted party, who computes the output F( aT,)) to the server for that iteration. S is also allowed to release a vector X, which will be added to the output, to simulate additive attacks.
Definition C.1. Protocol II securely computes F if for every adversary A there exists simulator S such that
Output), (S (S(TT- F(LI,,, RT (T= F() ............ xT .n) + x)) S neg!(A),
where SD is the statistical distance between the two distributions, C(T) the set of corrupted parties in iteration T, and À is the security parameter.
In practice, the committee selection is done by the server.
(e) any function (1)
21

---

DMM: Distributed Matrix Mechanism for Cunferentialll-Prrival Federated Learning
C.3. Security Proof
We now give the formal security proof.
Theorem C.2 (Security). Прмм securely computes FPpel for to + ta < (1/2- 0 =
Proof. We first build the simulator S. The simulator runs A internally. We describe the simulator for the first iteration T = and then inductively for the rest. Throughout, we will (inductively) show that the simulator knows all of the corrupted parties' shares. We start with the case of a corrupted server S.
Corrupted Server In iteration 1, S simulates the shares sent by honest parties of iteration 1 to corrupted parties of iteration and by sampling random values from the field F., S receives on behalf of the honest parties in committee C1 the shares sent by corrupted parties from the same committee. Note that the honest shares completely (and exactly) define these sharings since the number of honest parties is exactly t. + k, and thus S can compute the corrupted parties' shares and the underlying secret yı- With the corrupted parties' shares, along with the output for iteration T = 1 (which S receives since the server is corrupted), S has te + k points on the (fc + k - degrre polynomial underlying each output [Yi,c], and thus can reconstruct the whole sharing. Based on this, the simulator can send the honest parties' shares to the server.
In subsequent iterations T > S first simulates the shares of honest parties' new gradients and noise as above, along with the reshares to the next committee. It also receives the corrupted parties' input shares from iteration T, and can reconstruct the whole sharing [t.].. in the same way as above. S also receives on behalf of the honest parties in committee Cr the reshared shares sent by corrupted parties from iteration I' - 1. Note that again the honest shares completely (and exactly) define these sharings since the number of honest parties is exactly te + k, and thus S can compute the corrupted parties' shares as well as the actual underlying reshared shares Zi...., Z of each corrupted party P. in Cr. Note that these might be different from the actual underlying shares Zi..... Z of the corrupted parties which, S knows from above. Thus, S can compute ein < Dr Zin for each m [k]] Since reconstruction used within Recover of LRP is just a constant X multiplied by a party's 's share, the error introduced here is X!- ein, for each E (T)). Thus S sets Xr + Σiee()) X eim.
This error will be incorporated in honest parties' shares of AX for all iterations including and after T. Indeed, in iteration T, S uses the computed corrupted parties' shares, along with the output for iteration T with the error X+ for all previous iterations T added in, to obtain le k values with which it can reconstruct the whole sharing as above, and thus the shares that honest parties send to the server.
Now we show that this is a good simulation. By the properties of Shamir Secret Sharing, we know that the at most te shares that the adversary receives in the real world for every sharing will be distributed randomly. Thus the shares that S sends are distributed the same way. We also showed that the errors Xr and the shares of the corrupted parties are computed exactly as in the real world. Therefore S perfectly simulates the real world. 12
Honest Server In the case of an honest server, we can use all of the same simulation above, except instead of simulating the output shares to the server, we can use this same simulation to compute the eиror values Xr added to the honest output. We also need to show that, even in the presence of honest dropout parties, if the corrupted parties do not deviate from the protocol deseription, then the correct values are output to the server. This is true since the number of honest parties that do not dropout is at least n tu > (1/2 + p)n and k S 2pn. Indeed, ta + k S (1/2 + p)n n -ta, so the shares of the parties that do not dropout can still be used to reconstruct the secrets, both during Recover of LRP and the actual output reconstruction to the server in each iteration.
This completes the security proof.
D. Additional Experimental Results
FEMNIST details. Federated EMNIST is an image classification dataset containing 671,58; training handwritten digit/letter images over 64 classes grouped into N 3400 clients by their writer. We use the standard dataset split provided by TensorFlow. As in (Kairouz et al., 2021a), we train small convolutional net with two 3 x 3 conv layers with 32/64 /4 channels followed by two fully connected layers with 128 /62 output units; a 2 x 2 max pooling layer and two dropout layers with
Note that both in the real and ideal world, if an honest party ever hears from less than t. + k parties from the previous iteration, they will abort since then more parties have dropped out (or have heen dropped by the server) than can tolerated.
22

---

DMM: Distributed Matrix Mechanism for Differentially-Prise Prrvvtt Federated Learning
SO-NWP Accuracy Vs Rounds
0.25
0.20
0.15
Accuracy
0.10
DMM Honaker Online 4.5)
DMM Honaker Online 3.9)
0.05
DMM Honaker Online = 8)
DMM Optimal Factorization (E = 3.5)
DMM Optimal Factorization (E 8)
DMM Optimal Factorization (E 2.5)
0.00
1000
1500
2000
Rounds
Figure 5. Accuracies during training for SO-NWP across different for both the optimal factorization and Honaker Online facorization
drop 0.25/0.5 are added after the first 3 trainable layers, respectively. The total number of parameters is d 1018174 We namely momentum 0.9, 1 client training epoch per iteration, client learning rate M/ 0.02, server learning rate 77 1, and client batch size to 16.
SO-NWP details. Stack Overflow is a large-scale text dataset based on the question answering site Stack Overflow. It contains over 108 training sentences extracted from the site grouped by the N = 342477 users, and each sentence has associated metadata such as tags. The task SO-NWP involves predicting the next words given the preceding words in a sentence We use the standard dataset split provided by TensorFlow. As in (Kairouz al., 2021a; Choquette- 2023b), the LSTM architecture defined in (Reddi al., 2021) directly, which has model size of d 4050748 parameters (slightly under 222). We namely momentum 0.9, 1 client training epoch per iteration, client learning rate Te 0.02, server learning rate 1)s 1, and client batch size to 16.
et al.,
Accuracy Across Training iterations. In Figures 5 and 6, we show how the accuracies of our different models vary across training iterations. We show the results for the different matrix factorizations (Honaker Online and optimal) and different privacy values
Privacy Guarantees with Dropouts and Corrupted Parties. We note that, just as in (Kairouz al., 2021a), our privacy guarantees degrade with corrupt parties and honest dropouts the amount of combined noise in each iteration is proportional to (1 u')n yn instead of n, where y' is the fraction of parties that are corrupted or dropped out (recall that we assume y' < (1/2- - 4). for 0 < p < 1/2). Indeed, the actual obtained e' value for DP scales the originally derived value by ~ 1/(1 - p²) factor. See Kairouz et al. 12021a, Figure 9) for a graphical representation.
23

---

DMM: Distributed Matrix Mechanism for Differentiilll-Prrn PPrivate Federated Learning
FEMNIST Accuracy vs Rounds
0.8
0.6
Accuracy
0.4
0.2
DMM Honaker Online 2)
DMM Honaker Online 1.4)
DMM Optimal Factorization (E = 5)
DMM Optimal Factorization (E = 2.7)
0.0
1000
1400
Rounds
Figure 6. Accuracies during training for FEMNIST across different e for both the optimal factorization and Honaker Online facorization
24


Reviews:
[{"review_id": "c0EvA6ZBQH", "reviewer": "Reviewer_QYjM", "summary": "This paper presents a protocol for long running secure aggregation with matrix mechanism DP. The protocol consists of a sequence of committees/data-providers passing theinternal secrets of the algorithm along in secret shared form. The main theoretical innoviation is the novel secret resharing scheme used to pass large amounts of secret shared data along in a linear and communication efficient manner.", "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": "1) Dropout Resistance:\n\nWe thank the reviewer for pointing this out. We did not include the details for dropout resistance in the main body to make the (already complex) protocol easier to understand, but we should have included it in the appendix.\n\nHowever, the reviewer is correct; there is a simple way to fix this: The clients in cohort T+1 must agree on a subset of clients from cohort T whose shares they use in the Recover algorithm. As the reviewer suggests, the server (through which all communication is routed) can simply send to cohort T+1 this subset directly, defined as those clients of cohort T who sent shares to *all* cohort T+1 clients. (For reference, it is quite common for communication to be routed through the server, see, e.g., (Bonawitz et al, 2017)).\n\nThen, the Recover algorithm of protocol LRP in Section 3 will additionally take as input such a set of NONDROPOUTS (received from the server), and the existing summation in the Recover algorithm will now be for i \\in NONDROPOUTS (and similarly for the Recons algorithm).\n\nWe will make this change for dropout resistance in the final version.\n\n2) Description of Ball et al:\n\nNote that in Ball et al, the server receives ciphertexts from the clients, then maintains and aggregates the ciphertexts which are to be eventually decrypted (also by the server). For example, in Section 4.1 of that paper, it is written that from an encryption of x1 received from Alice and x2 received from Bob, “the server can sum the result to get an encryption of x1+x2”. Then “imagine the server is holding a ciphertext” encrypting x, “Alice and Bob can simply compute and send” their (noisy) secret keys which “enables the server to recover x”.\n\nAlso, in Section 4.2, it is written that “writing to the secret state” means “the server then simply sums the resulting correlated ciphertext with all ciphertexts received from cohort Ci”.\n\nThus, the server maintains the ciphertexts itself and even performs the decryption itself, so it can certainly submit the wrong ciphertext for decryption. Furthermore, even if the server did not perform the decryption itself, the clients would still need to receive the maintained (aggregated) ciphertexts from the server.\n\n3) Comparison to matrix mechanism in the clear (without discretization):\n\nNote that we indeed compare to the matrix mechanism in the clear (without discretization) for the StackOverflow NWP task in FIgure 2. We achieve very similar accuracy for given privacy values \\eps.", "claims_and_evidence": "The support for the claims is presented though I have a couple of concerns which I address in the next boxes.", "methods_and_evaluation_criteria": "The assessment in the experiments section does make sense. It would have been nice to see a comparison to the optimal matrix mechanism in the clear i.e. without discretization but this would merely be a nice to have.", "theoretical_claims": "I verified the correctness and security of the secret sharing scheme. The paper claimed that Recon is a function of i and z_i and adding any t_c+k of the Recons would give the result. This is close tot he truth but not right because the \\lambda_i depend on exactly which subset of clients are involved in the reconstruction. This led me to doubt whether the Recover function worked. It can be made to work but only if the client in cohort T+1 agree on a subset of the clients from cohort T to use information from in the reconstruction (whom they have all received shares from). This would mean they need to know information about which messages get through to everyone, this is probably achieveable without too much expense (maybe if the communication all goes via the server it could play a co-ordinating role) but it should be specified how this is going to be achieved. I suspect the authors missed this was necessary because they oversimplified the description of how Recon works. Alternatively maybe they mean for their protocol to not be resistant to any lost messages or dropouts and thus the set being used should always be all n=t_c+k clients.", "experimental_designs_or_analyses": "I didn't check the details of the experiments", "relation_to_broader_scientific_literature": "The Matrix mechanism work in the central model is a big new thing. Putting that in a secure distributed setting is an obvious and potentially impactful expansion combination that makes a lot of sense. The only other paper attempting to do this I am aware of is the Ball et al pre-print. Ball et al uses very different methods (in a similar threat model) so this is a good additional angle of attack and the ideas might well be combinable.", "essential_references_not_discussed": "None I am aware of.", "other_strengths_and_weaknesses": "One mistake I think should be pointed out is in the description of Ball et al. This paper states that paper suffers from the server being able to submit the wrong ciphertexts for decryption. That is a misconception, in that paper the information the clients use for decryption is the secret key they have shared amongst them and the public parameters used for encryption neither of which come from the server (except in the sense that the initial seed for generating the public parameters may come from the server). Having said that this paper can be justified alongside Ball et al by the novelty of its approach so the valitiy of this paper shouldn't depend on them having that privacy advantage over Ball et al.\n\nIf their protocol is not resistant to any dropouts (which it isn't as written) that seems a major weakness for any hope of a practical implementation. Fixing this is the main substantive thing stopping my review from being more enthusiastic.", "other_comments_or_suggestions": "None.", "questions_for_authors": "Is your protocol supposed to be dropout resistant? If so how would you deal with the problem I highlighted about co-ordination for Recover?\n\nHave I misinterpreted Ball et al? If not can you fix that description for the camera ready?", "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": "ykcGHAdQ3Z", "reviewer": "Reviewer_p54v", "summary": "The paper focuses on differentially private (DP) federated learning (FL), with the main contribution of formulating a distributed version of the well-known matrix mechanism. As the continuous Gaussian mechanism typically used with the centralized matrix mechanism does not work well with cryptographic primitives, the proposed method is based on the discrete Gaussian mechanism.\n\nThe paper proposes a method with constant-overhead (in communication, compared to squared scaling of a naive approach) based on a suitable linear secret sharing protocol, and includes a formal proof that the construction  is secure. The proposed method is also shown to be robust against a fraction of malicious or failing parties.\n\nThe paper includes empirical experiments on some data sets and models (Stack Overflow with LSTM model, FEMNIST with small CNN) demonstrating that the proposed method outperforms a local variant of discrete Gaussian DP mechanism.\n\n### Update after the rebuttal and discussions\n\nI raise my score to weak accept reflecting the discussions. I am still not perfectly happy with the paper, e.g., the authors should use more recent noise mechanism to be able to claim being SOTA (while this was discussed, I do not accept this as a made change without seeing some evidence of the change actually being implemented), I am somewhat hesitant about the contribution (as discussed, as the main contribution is a cryptography protocol, I think this would be a more suitable submission in a more cryptography oriented venue to get more relevant estimation of the novelty and importance of the said protocol; beyond this concern however, I do think the paper is within scope for ICML), and generally the paper could be written more clearly.", "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": "1) How baseline is run:\n\nWe use the exact experiment details specified in the respective papers: (Section 5; Kairouz et al., 2021) for Local DP DDG and (Section 6 and Appendix I; Choquette-Choo et al., 2023a) for the Central DP mechanisms. For local DP DDG, the FEMNIST norm clip is set to 0.03 and the SO-NWP norm clip is set to 0.3. Additionally, Generic RDP amplification via sampling (Zhu And Wang, 2019) is used. For central DP, the SO-NWP clip is set to 1. Amplification is calculated using the technique presented in their paper along with the dp_accounting python library (reference [18] in their paper). We will include these in our paper.\n\n2) Effect of number of rounds on complexity:\n\nLet T* be the total number of rounds and d the model dimension. In a given round T <= T*, the complexity of our algorithm for a general matrix factorization (including the Optimal Matrix Factorization) scales as O(d * T), while for the Honaker Online mechanism, the complexity scales as O(d log T). We will make this more explicit in the paper.\n\n3) Scaling in terms of k:\n\nWe use k = 2 * \\mu * n for 0 < \\mu < 1/2, as stated in Section 3, “Communication Complexity”. In round T, the concrete overhead is a 1/(4 \\mu^2) factor (times d * T in the case of general, including optimal, Matrix Factorization, and d log T in the case of Honaker Online mechanism). We will make this clearer in the paper.\n\n4) Noise methods and centralized MM papers:\n\nSince our techniques are independent of the noise distribution, we just chose one that we believe to be the most well-studied/understood: the discrete Gaussian. Indeed, we just need CX + Z to be differentially-private, where Z can be sampled from any (discrete) noise distribution; whichever distribution yields the best results can be used and these results will be at least as good as those in our paper. Ultimately, the message of our paper is the same: using the matrix mechanism for local (distributed) DP is better than using uncorrelated noise for local (distributed) DP.\n\nAlso, we believe that the Skellam Distribution is incomparable to the discrete Gaussian in terms of privacy-utility tradeoff: Theoretically, quoting from (Agarwal et al., 2021) the bound on \\eps DP they “provide is at most 1 + O(1/\\mu) worse than the bound for the Gaussian” (this also holds with respect to the discrete Gaussian). Experimentally, it can be seen from Figure 5 of (Agarwal et al., 2021) that performance from the discrete Gaussian and Skellam are quite similar; depending on \\eps, sometimes the discrete Gaussian is better.\n\nFor the Poisson binomial mechanism of (Chen et al. 2022), Table 1 of that paper indicates that the error from that mechanism and the discrete Gaussian is asymptotically the same. They do not experimentally compare to the discrete Gaussian or run FL experiments, so it is hard to tell which has better accuracy in practice. We will be sure to cite this paper.\n\nWe are happy to include the performance of the Skellam and Poisson binomial distributions in our paper (in the current version we do acknowledge and reference the Skellam Distribution in Footnote 6).\n\nAlso, note that we do reference and indeed compare to “Choquette-Choo: (Amplified) Banded Matrix Factorization: A unified approach…” as the SOTA, which is indeed a NeurIPS 2023 paper and thus cited as (Choquette-Choo et al., 2023) in e.g., caption of Figure 2, and elsewhere.\n\n5) Pseudo-gradients:\n\nOur system only requires clients to compute vectors that will be used to update the model parameters at the server (by somehow aggregating all of the vectors of the clients, i.e., averaging). So pseudo-gradients can be used in our system.\n\n6) Lines 269-270:\n\nYes, thank you for pointing it out.\n\n7) Lines 252-254:\n\nYes, each party i = 1,...,n in round T sends n shares, for a total of n^2 communication per round across all i=1,...,n.\n\n8) Client-to-client communication:\n\nNote: in practice the communication between clients will be (end-to-end encrypted and) routed through the server. Indeed, it is quite common for communication to be routed through the server, see, e.g., (Bonawitz et al, 2017) and most follow-ups. Moreover, such communication only occurs between clients of consecutive cohorts (i.e. rounds T and T+1), so we do not believe it's a heavy requirement.\n\n9) Suitability of ICML:\n\nWe believe that any paper that improves the SOTA for any topics of interest in the Call for Papers should be seen as suitable. Our paper is for “Trustworthy Machine Learning” topic listed in the call. Indeed, we directly improve an IMCL 2021 paper (Kairouz et al. 2021a).\n\n10) LDP -> DDP:\n\nThanks. We will fix it.\n\n11) LRP description:\n\nThe input to Reshare is indeed a vector of k shares: z_[1,k]^i = (z_1^i, …, z_k^i). The output is a packed secret sharing where the shared secret vector is the above, z_[1,k]^i. This output sharing is denoted by [z_[1,k]^i] = ( (z_[1,k]^i)^1 ,... , (z_[1,k]^i)^n) (i.e., a vector of n shares, 1 for each party in the next cohort).", "claims_and_evidence": "Some of the claims are not properly supported by the evidence (see Questions for authors for more details):\n* Claims about beating current SOTA, when the experiments only use discrete Gaussian mechanism also for the baselines.", "methods_and_evaluation_criteria": "The methods and evaluation mostly seem to be ok and can be used for the stated purpose. I find the complexity evaluation to be somewhat unclear (see Questions for authors for more details).", "theoretical_claims": "I did not have chance to check the correctness of proofs.", "experimental_designs_or_analyses": "I have checked all the reported empirical results, and have some doubts and questions on the implementation (see Questions for authors for details).", "relation_to_broader_scientific_literature": "There is some discussion relating the current paper to the more general field of distributed DP ML. I think this is good enough given the topic.", "essential_references_not_discussed": "The paper fails to mention several references, e.g., DP noise mechanisms improving on the discrete Gaussian (see Questions for authors for some concrete examples).", "other_strengths_and_weaknesses": "### Strengths\n* The problem of formulating a distributed matrix mechanism is an interesting and, I believe, an important one.\n* The proposed method has several nice properties (constant overhead, fault-tolerance).\n* The code is provided in the supplement.\n\n### Weaknesses\n* The empirical comparisons do not include state-of-the-art DDP baselines, even though such methods should be well-suited to the problem given the assumed trust model and the available secure primitives.\n* Considering a typical FL setting, requiring client-to-client communications in cross-device setting between clients for each step is a heavy requirement.\n* I find the writing to be somewhat confusing at times (although this might be partially due to not being an expert in cryptography).\n* The main contribution of the paper is a cryptography protocol. While I do not think this is exactly out of scope for ICML, I do think that there might be other venues better suited for this kind of work.", "other_comments_or_suggestions": "* Eg: lines 19-20, 1st col; 29-33, 2nd col etc.: please do not call your distributed matrix mechanism local DP (LDP), as LDP has a well-established meaning that does not correspond to the proposed setting (in LDP each client guarantees DP on their own data independently of others). Instead, distributed DP (DDP) is often used in settings where LDP-type noise is combined with cryptographic primitives such as SecAgg for enhanced privacy-utility trade-offs.\n* I find the description of the LRP in Sec.3 to be somewhat confusing, maybe partially because of notations; e.g., looking at the Reshare, is the idea that the input is a list of $k$ shares, and the output then length $k$ list of shares, where each element is again a list of $k$ shares?", "questions_for_authors": "### Critical\n\n1) Sec. 5.: Please clarify how exactly the baseline is run (e.g., how all the hypers such as clipping have been set, how is subsampling amplification calculated).\n\n2) Lines 407-409: how does the number of rounds affect the complexity of the algorithm?\n\n3) Lines 296-299: how is the scaling of the proposed method in terms of $k$?\n\n4) Cf. lines 99-101, 2nd col: there have been several improved noise methods proposed after the discrete Gaussian (see, e.g., Agarwal et al. 2021: The Skellam Mechanism for  DP FL, Chen et al. 2022: The Poisson binomial mechanism...). Is there some specific reason to instead use the discrete Gaussian as the noise mechanism in the current paper and claim that it is state of the art? Note that there are also improved centralized MM papers not referenced, e.g., Choquette-Choo 2024: (Amplified) Banded Matrix Factorization: A unified approach...\n\n5) Does the proposed method assume that each client always runs a single optimization step, or does it work with pseudo-gradients resulting from running multiple local steps?\n### Non-critical\n* Lines 269-270: should the number of non-faulting honest parties be $n-t_d-t_c$?\n* Lines 252-254: so does this mean that in the naive scheme each party $i=1,\\dots,n$ chosen at round $T$ needs to send $n$  shares to each of the $j=1,\\dots,n$ parties chosen for round $T+1$?", "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": "a3vtPVViYZ", "reviewer": "Reviewer_sHuj", "summary": "The paper proposes a Linear Secrete Sharing Protocol with a Constant-Overhead Linear Secret Resharing method to facilitate matrix mechanism to preserve DP in Federated Learning. In the case of Distributed FL, in which the clients do not trust the server, the clients will generate the noise and share to each other their gradients. The proposed method facilitates this process with marginal communication overhead.", "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": "1) Construction of matrix A:\n\nThe matrix A (and its factorization A=BC) is a public value that can be constructed before training begins by the central server (which does still exist in our framework, though importantly privacy holds even with respect to this server; see, e.g., right of Figure 1).\n\n2) Figure 6, performance of eps=5 and eps=2.7 at given round:\n\nNote that it is common for the accuracy at different privacy levels to be similar in early training rounds before the accuracy for weaker privacy levels (i.e., smaller noise scale) becomes higher in the final training rounds. See, e.g., Figure 7 in (Kairouz et al., 2021a).\n\n3) Practical Setting and Motivation:\n\nDifferentially Private Federated Learning has already been widely deployed in practice (see Section 1). In many cases, there could be regulations and/or other privacy concerns that prevent even a central server from obtaining sensitive client information, or that prevent clients from trusting that the central server will properly add noise. This is the setting in which our results fit—clients must add noise locally. We believe our experiments show the practicality of our solution.\n\nMoreover, our setting is the same as many other works, including an ICML 2021 paper (Kairouz et al., 2021a), and a concurrent work (Ball et al., 2024). (See our comparison to the latter paper, which has weaker privacy guarantees, in Section 1, Related Work and Section E.)\n\n4) “Theoretical analysis heavily depends on existing works”:\n\nWe believe that our proposed Constant-Overhead Linear Secret Resharing protocol and its correctness/security analyses are novel and significant contributions.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I did check the correctness of all the theoretical proofs.\n- Theorem 1.\n- Theorem 2.\n\nI don't see any issues with these theorems.", "experimental_designs_or_analyses": "I did check the validity of the experiments in the main body.\n- Figure 6, How can eps=5 and eps=2.7 be run at the same epoch and achieve the same accuracy? To achieve eps=2.7 with the same # of rounds, you need a larger noise scale leading to bigger degradation of performance", "relation_to_broader_scientific_literature": "Not Applicable", "essential_references_not_discussed": "Not Applicable", "other_strengths_and_weaknesses": "Strength:\n- Thorough theoretical and experimental analysis.\n- Adapt existing works with modification, which is easy to adopt.\n\nWeakness:\n- Lack of practical setting and motivation.\n- The theoretical analysis heavily depends on existing works.", "other_comments_or_suggestions": "- It would be better to discuss a practical setting before diving into the mathematical notation. \n- The notations are hard to follow.", "questions_for_authors": "- In the case of distributed FL, how can matrix A be constructed? Since the learning process does not include a hosting server to construct this matrix, how can each user can construct this?\n- Figure 6, How can eps=5 and eps=2.7 be run at the same epoch and achieve the same accuracy? To achieve eps=2.7 with the same # of rounds, you need a larger noise scale leading to bigger degradation of performance", "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": "QiCqXO5tVg", "reviewer": "Reviewer_M2TL", "summary": "This paper introduces a distributed matrix mechanism for federated learning. It is a local DP mechanism where each client of FL uses their own noises instead of the server adds the noise. To achieve this goal, the authors use cryptographic protocols for secrete sharing to achieve this. The proposed frame is robust, as it could handle corrupted clients and dropped out honest clients (as long as they are not too many for the problem to be not recoverable). Experiments are conducted to show that the proposed method has good tradeoff between $\\epsilon$ and the accuracy compared to prior local DP method for FL, and it dramatically saves the communication cost compared to implement the crypto protocol naively.\n\n## Update after rebuttal\nAuthors explained the reason for using discrete noise is due to the use of cryptography tools that work only for finite field. They are encouraged to incorporate this rationale into the revision. As my score was on the positive side, I'll keep it as is.", "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": "1) Why discrete Gaussians?:\n\nSince our novel techniques are independent of the noise distribution used, we just chose one distribution that we believe to be the most well-studied/understood: the discrete Gaussian distribution. Indeed, we just need CX + Z to be differentially-private, where Z can be sampled from any (discrete) noise distribution; whichever distribution yields the best results can be used and these results will be at least as good as those stated in our paper. We are not currently aware of any other (discrete) noise distribution that is always better than the discrete Gaussian. Ultimately, the main message of our paper is the same: using the matrix mechanism for local (distributed) DP is better than using uncorrelated noise for local (distributed) DP.", "claims_and_evidence": "Yes, the statements made in the paper are backed up by proofs, and extensive experiments are performed to show the good accuracy of proposed method against other local DP methods, and the communication cost saving.", "methods_and_evaluation_criteria": "Yes, datasets used are standard and comparisons are fair.", "theoretical_claims": "I read the DP proofs, I think they are correct. However I'm not familiar with cryptography.", "experimental_designs_or_analyses": "The experimental design and analyses are quite standard.", "relation_to_broader_scientific_literature": "I think the contributions of this paper are significant. Local DP for FL is an important subject of study as it does not require server to access noise and can just do simple average. This paper in particular studies matrix mechanism, a powerful DP tool that achieves good privacy and utility. To make it work, it introduces novel secret sharing into the picture to further reduce communication cost. This combination of secret sharing and matrix mechanism is interesting, and I believe publishing this paper would be beneficial to the FL community.", "essential_references_not_discussed": "The paper cites proper references.", "other_strengths_and_weaknesses": "Overall, I think the paper presents interesting results and experiments are performed to show the validity of their proposed method.", "other_comments_or_suggestions": "Some suggestions:\n\n1. The paper is very technically dense due to combining tools from different fields, therefore certain parts are hard to parse (for me, since I'm more familiar with DP and FL, the secret sharing part is quite hard to read). It might be helpful to start with an overview of the techniques so that each part is packaged in a more black-box fashion (e.g., abstract the secret sharing, or abstract the matrix mechanism) so that readers can get a better sense on the high level details before diving into heavily technical parts.\n\n2. The paper could benefit from providing a table comparing the error guarantees against other local DP method, and central matrix mechanism (maybe in appendix). It would give a better sense on various tradeoffs for local v.s. central, non-matrix mechanism v.s. matrix mechanism.", "questions_for_authors": "Why were discrete Gaussian noises used? Is it for the ease of practical implementations?", "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 submission proposes a distributed matrix mechanism (DMM) for federated learning (FL) with local differential privacy (DP), aiming to achieve a better privacy-utility tradeoff using a novel cryptographic protocol for secure value transfer with constant communication overhead.
While the idea of combining the matrix mechanism with cryptographic techniques in a distributed setting is interesting and potentially impactful, several concerns raised by the reviewers, particularly regarding the setting and assumptions, the experimental evaluation and the comparison to the prior work (in particular the state-of-the-art differentially private federated learning baselines), as well as the writing and clarity of exposition. It would be preferable if the paper addresses these concerns before getting published at a venue such as ICML.
Decision: Accept (poster)