RFLPA: A Robust Federated Learning Framework against Poisoning Attacks with Secure Aggregation
Authors: Peihua Mai
Ran Yan
Yan Pang
Venue: NeurIPS 2024 poster (2024)
Keywords: federated learning
poisoning attack
privacy protection
Primary area: privacy

Abstract: Federated learning (FL) allows multiple devices to train a model collaboratively without sharing their data. Despite its benefits, FL is vulnerable to privacy leakage and poisoning attacks. To address the privacy concern, secure aggregation (SecAgg) is often used to obtain the aggregation of gradients on sever without inspecting individual user updates. Unfortunately, existing defense strategies against poisoning attacks rely on the analysis of local updates in plaintext, making them incompatible with SecAgg. To reconcile the conflicts, we propose a robust federated learning framework against poisoning attacks (RFLPA) based on SecAgg protocol. Our framework computes the cosine similarity between local updates and server updates to conduct robust aggregation. Furthermore, we leverage verifiable packed Shamir secret sharing to achieve reduced communication cost of $O(M+N)$ per user, and design a novel dot product aggregation algorithm to resolve the issue of increased information leakage. Our experimental results show that RFLPA significantly reduces communication and computation overhead by over $75\%$ compared to the state-of-the-art secret sharing method, BREA, while maintaining competitive accuracy.

RFLPA: A Robust Federated Learning Framework against Poisoning Attacks with Secure A Aggregation
Peihua Mai
Ran Yan National University of Singapore
Yan Pang
Abstract
Federated learning (FL) allows multiple devices to train a model collaboratively without sharing their data. Despite its benefits. FL is vulnerable to privacy leakage and poisoning attacks. address the privacy concern, secure aggregation (SecAgg) is often used to obtain the aggregation of gradients
sever without inspecting individual user updates. Unfortunately, existing defense strategies against poisoning attacks rely the analysis of local updates in plaintext, making them incompatible with SecAgg. To reconcile the conflicts, we propose robust federated learning framework against poisoning attacks (RFLPA) based SecAgg protocol. Our framework computes the cosine similarity between local updates and server updates conduct robust aggregation. Furthermore, we leverage verifiable packed Shamir secret sharing to achieve reduced communication cost of O(M + _N) per user, and design a novel dot product aggregation algorithm resolve the issue of increased information leakage. Our experimental results show that RFLPA significantly reduces communication and computation overhead by over 75% compared the state-of fate--of-thearr secret sharing method, BREA, while maintaining competitive accuracy.
Introduction
Federated learning (FL.) (15) is promising machine learning technique that has been gaining attention in recent years. It enables numerous devices to collaborate on building machine learning model without sharing their data with each other. Compared with traditional centralized machine learning, FL preserves the data privacy by ensuring that sensitive data remain on local devices.
Despite its benefits, FL still has two key concerns be addressed. Firstly, there is threat of privacy leakage from local update. Recent works have demonstrated that the individual updates could reveal sensitive information, such properties of the training data 66] 77. even allows the server to reconstruct the training data 8 91. The second issue is that FL. is vulnerable to poisoning attacks. Indeed, malicious users could send manipulated updates corrupt the global model their will [10). The poisoning attacks may degrade the performance of the model, in the case of untargeted attacks, or bias the model's 's prediction towards a specific target labels, in the case of targeted attacks
Secure aggregation (SecAgg) has become potential solution to address the privacy concern. Under SecAgg protocol, the server could obtain the sum of gradients without inspecting individual user updates 12 [3]. However, this protocol poses significant challenge in resisting poisoning attacks in [14] [5] require the server to access local updates detect the attackers, which increases the risk of privacy leakage. The contradiction makes difficult to develop a FL framework that simultaneously resolves the privacy and robustness concerns.
FL. Most defense strategies
To our best knowledge, BREA is the state-of-the-ar FL framework that defends against poisoning attacks using secret sharing-based SecAgg protocol [16.. Based on verifiable secret sharing, their
"Correspondence to bizpyj @nus. edu.ssedd.gpg.. sg
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

framework leverages pairwise distances to remove outliers. However, their work is limited by the scaling concerns arising from computation and communication complexity. For model with dimen- sion M and N selected clients, the framework incurs O(MN + N) communication per user, and O((N2+ + MN) log² N log log N) computation for the server due to the costly aggregation rule. Fur- thermore, BREA makes unrealistic assumptions that the users could establish direct communication channels with other mobile devices.
To address the above challenge, we propose robust federated learning framework against poisoning attacks (RFLPA) based on SecAgg protocol. We leverage verifiable packed Shamir secret sharing to compute the cosine similarity and aggregate gradients in a secure manner with reduced communication cost of (MM + .N per user. To resolve the increased information leakage from packed secret sharing, we design dot product aggregation protocol that only reveals single value of the dot product to the server. Our framework requires the server to store a small and clean root dataset as the benchmark. Each user relies on the server to communicate the secret with each other, and utilizes encryption and signature techniques to ensure the secrecy and integrity of messages. The implementation is available at http:/giwww..oooouuoooaaaaaaaeee
Our main contributions involves the following:
(1) We propose a federated learning framework that overcomes privacy and robustness issues with reduced communication cost, especially for high-dimensional models. The convergence analysis and empirical results show that our framework maintains competitive accuracy while reducing communication cost significantly.
(2) To protect the privacy of local gradients, we propose novel dot product aggregation protocol. Directly using packed Shamir secret sharing for dot product calculation can result in information leakage. Our dot product aggregation algorithm addresses this issue by ensuring that the server only learns the single value of the dot product and not other information about the local updates. Furthermore, the proposed protocol enables degree reduction by converting the degree-2d partial dot product shares into degree-d final product shares.
(3) Our framework guarantees the secrecy and integrity of secret shares for a server-mediated network model using encryption and signature techniques.
Literature Review
2.1 Defense against Poisoning Attacks.
Various robust aggregation rules have been proposed to defend against poisoning attacks. KRUM selects the benign updates based on the pairwise Euclidean distances between the gradients [14). Yin et al. (17) proposes two robust coordinate-wist aggregation rules that computes the median and trimmed mean at each dimension, respectively. Bulyan [18) selects a set of gradients using syzannine-resiliee algorithm such as KRUM, and then aggregates the updates with trimmed mean. RSA [19] adds regularization term to the objective function such that the local models are encouraged to be similar to the global model. In FLTrust [15), the server maintains a model its clean root dataset and computes the cosine similarity to detect the malicious users. The aforementioned defense strategies analyze the individual gradients in plaintext, and thus are susceptible to privacy leakage.
2.2 Robust Privacy-Preserving FI..
To enhance privacy and resist poisoning attacks, several frameworks have integrated homomorphic eneryption (HE) with existing defense techniques. Based on Paillier cryptosystem, PEFL [20] calculates the Pearson correlation coefficient between coordinate-wise medians and local gradients to detect malicious users. PBFL (2T) uses cosine similarity identify poisonous gradients and adopted fully homomorphic encryption (FHE) to ensure security. ShieldFL (22) computes cosine similarity between encrypted gradients with poisonous baseline for Syzantine-toleran
aggregation. The above approaches inherit the costly computation overhead of HE. Furthermore, they rely two non-colluding parties to perform secure computation and thus might be vulnerable to privacy leakage. Secure Multi-party Computation (SMC) is an alternative to address the privacy concern. To the best of our knowledge, BREA (16) is the first work that developed Byzantine robust FL framework using verifiable Shamir secret sharing. However, their method suffers high communication complexity of

---

SMC and high computation complexity of KRUM aggregation protocol. Refer to Appendix K.4 for comprehensive comparison among existing protocols.
This paper explores the integration of SMC with defense strategy against poisoning attacks. We develop framework that reduces communication cost, employs efficient aggregation rule and guarantees the security for server-mediated model.
3 Problem Formulation and Background
3.1 Problem Statement
assume that the server trains model with N mobile clients in a federated learning setting. All parties are assumed to be computationally bounded. Each client holds local dataset (eN) and the server owns a small, clean root dataset Do. The objective to optimize the expected risk function:
F F(w)= min L w),
where L(D, w) a empirical loss function given dataset D.
In federated learning, the server aggregates local gradients g to obtain global gradient g' for model update:
g' s'= ==Ennsh w' w'=w -'''
(2)
where ?/ the weight of client i, 7 is the learning rate, and S is the set of selected clients.
Adversary Model
We consider two types of users, i.e., honest users and malicious users. The definitions of honest and malicious users are given as follows.
Definition 3.1 (Honest Users). A user u is honest if and only u honestly submits local gradient Ju. where 9u is the true gradients trained its local dataset D..
Definition 3.2 (Malicious Users). A user is malicious if and only if u is manipulated by an adversary who launches model poisoning attack by submitting poisonous gradients g..
Server aims to infer users' information with two types of attacks, i.e., passive inference and active inference attack. In passive inference attack, the server tries to infer users' sensitive information by the intermediate result receives from the user or cardrops during communication. In active inference attack, the server would manipulate certain users' messages to obtain the private values of targeted users.
3.3 Design Goals
We aim design federated learning system with three goals.
Privacy. Under federated learning, users might still be concerned about the information leakage from individual gradients. To protect privacy, the server shouldn' 't have access to local update of any user. Instead, the server learns only the aggregation weights and global gradients, ensuring that individual user data remains protected.
Robustness. We aim design a method resilient to model poisonous attack. meaning that the model accuracy should be within reasonable range under malicious clients.
Efficiency. Our framework should maintain computation and communication efficiency even if it is operated on high dimensional vectors.
3.4 Cryptographic Primitives
In this section we briefly describe cryptographic primitives for our framework. For more details refer to Appendix B

---

Packed Shamir Secret Sharing. This study uses generalization of Shamir secret sharing scheme known "packed secret-sharing" that allows represent multiple secrets by single polynomial A degree-d (d 2 - 1) packed Shamir sharing of = (#1. -2,.... 81) stores the / secrets shares for
23
24
.... polynomial f(+) of degree at most d. The secret sharing scheme requires reconstruction, and any d - + shares reveals no information of the secret.
Key Exchange. The framework relies on Diffic-Hellmah key exchange protocol parties to establish a secret key securely.
25 that allows two
Symmetric Encryption. Symmetric encryption guarantees the secrecy for communication between two parties [26). The encryption and decryption are conducted with the same key shared by both communication partners.
Signature Scheme. To ensure the integrity and authenticity of message, we adopt UF-CMA secure
signature scheme 27
28
4 Framework
4.1
Overview
User Device
Server
Normalize and quantize local update
St
Compute update Col act and transmit secret shares local update
Round
Generate and serd secret shares of local update
Shares of
s Compute local shares of partial cosine similanty cs and gradient norm nyz
Shares of mi;
Collect transmit secret caj my;
Round
@ Obtain final shares coeine similarit and
Final af, and ni;
verify gradient
Round
Recover similanty compule trust
gradiant norm
Trust score
aggregation
Locally eggregsted
Reconetruct global gredient and update model
Round 4
shures
Figure 1: Overall framework
Figure T depicts the overall framework of our robust federated learning algorithm. The algorithm consists of four rounds:
Round 1: each client receives the server update go. computes their updates normalized by Po. and distributes the secret shares of their updates other clients.
Round 2: each client computes the local shares of partial dot product for gradient norm and cosine similarity, and conducts secret re-sharing on the local shares.
Round each client obtains final shares of partial dot product for gradient norm and cosine similarity, and transmits the shares to server. Then the server would verify the gradient norm, recover cosine similarity, and compute the trust score for each client.
Round 4: receiving the trust score from the server, each client conducts robust aggregation on the secret shares locally, and transmits the secret shares of aggregated gradient the server. The server finally reconstructs the aggregation on the secret shares.

---

To address increased information leakage caused by packed secret sharing, we design a dot product aggregation protocol sum up the dot product over sub-groups elements. Refer Appendix D for the algorithm to perform robust federated learning.
4.2 Normalization and Quantization
To limit the impact of attackers, we follow model update:
15
to normalize each local gradient based the server
|
gi:
gi
where gi is the local gradient of the ith client, and go is the server gradient obtained from clean root data.
Each client performs local gradient normalization, and the server validates if the updates truly normalized. The secret sharing scheme operates over finite field F, for some large prime number and thus the user should quantize their normalized update g. The quantization poses challenge on normalization verification, as g might not be exactly equal to || after being converted into finite field.
To address this issue, we define the following rounding function:
gg /g/l// [z + 1)/9,
r 2 0
Q(x)
r < 0
where [qa] is the largest integer less than or equal qa.
Therefore, the server could verify that ||g:|| S ||go||. which ensured by the quantization method.
4.3 Robust Aggregation Rule
Consistent with FLTrust 15 our framework conducts robust aggregation using the cosine similarity between users' and server's updates. The trust score of user is:
TS: max (0.
(gi gu)
1 ga)
max
0,
(5)
|g
go
go 1
where we clip the negative cosine similarity to zero avoid the impact of malicious clients. The global gradient then aggregated by:
N
g
Σ
T
(6)
Σ
Dis
TS
Finally, we use the gradient to update the global model:
W W 78.
(7)
Our framework leverages the robust aggregation rule consistent with FLTrust due to its advantages including low computation cost, the absence of requirement for prior knowledge about number of poisoners, defend against majority number of poisoners, and compatibility with Shamir Secret Sharing. Appendix details the comparison between FLTrust and existing robust aggregation rules.
4.4 Verifiable Packed Secret Sharing
The core idea of packed secret sharing is to encode / secrets within a single polynomial. Consequently, the secret shares local updates generated by each user would reduce from NM to NM/I. By selecting O(N), the per-user communication cost at secret sharing stage be decreased to OM+NN.. We assume that the prime number is large enough such that P max(N]les ll. l avoid overflow.
One issue with secret sharing is that malicious client may send invalid secret shares, i.e., shares that are not evaluated at the same polynomial function, break the training process. To address this
5

---

issue, the framework utilizes the verifiable secret sharing scheme from (29, which generates constant size commitment to improve communication efficiency. We construct the verifiable secret shares for both local gradients and partial dot products described in Section 4.5 During verifiable packed secret sharing, the user would send the secret shares s, commitment C, and witness wy to other users. A commitment is a value binding to polynomial function Φ(z),, i.e., the underlying generator of the secret shares, without revealing it. A witness allows others to verify that the secret share st is generated at of the polynomial (see Appendix B for more details).
4.5 Dot Product Aggregation
Directly applying packed secret sharing may increase the risk of information Ieakage when calculating cosine similarity and gradient norm. In the example provided by Figure 2 the gradient vectors are created as secret shares by packing 1 secret into a polynomial function. Following the local similarity computations by each client, the server can reconstruct the element-wise product between the two gradients, which makes it easy to recover the user's gradient J from the reconstructed metric. On the other hand, our proposed protocol ensures that only the single value of dot product is released to the server. Based on this, we introduce term partial dot product, or partial cosine similarity (norm square) depending on the input vectors, defined as follows:
Partial dot product represents the multiple dot products of several subgroups of elements from input vectors rather than single dot product value.
Another related concept is final dot product, referring to the single value of dot products between
two vectors. For example, given two vectors D1 = (2. 1, 4, 5, 3) and vi2 = (1, 0, 3, 2, 1), the reconstructed partial dot product could be (0, 15, 9) if we pack 2 elements into secret share, while the final dot product is 6. If each client directly uploads the shares from local dot product computation, the server would reconstruct a vector of partial cosine similarity (norm square) and thus learn more gradient information. To ensure that the server only has access to final cosine similarity
Sever sodde au (12-244
Uber upddte A MAM
d 100 if 197 d 156
12 59
53 d ta
4 121 of HLL d 174
d- &
51
4 4
4 43
Loee sertertt
120
eieeec Dotersket
Seoee moces paraal ol pnddc 9 (3.00)
Saaver recass ans Seaderooa sicket
A
Figure 2: Cosine similarity computation on packed secret sharing
(norm square), we design dot product aggregation algorithm based on secret re-sharing that allows the users to sum up the dot products over subgroups.
Suppose that the user i creates packed secret sharing V Lufe beNe of g (gi, Sh. Shr), by packing each elements into a secret. On receiving the secret shares, each nryy:
user can compute the vectors cs' = (cs), cs2, csty) and nr (mrf.. .r.....rr'
cs = Σ oh vu nr² Σ u R
where es) and nr denotes the 5th share of partial cosine similarity and partial gradient norm square for user j's gradient.
The partial cosine similarity (or gradient norm square) could be further aggregated by the procedure below in four steps.
Step 1: Secret resharing of partial dot product. Each user i could construct the verifiable packed secret shares of es (or nrr) by representing p secrets polynomial:
si
///p/l
S
NTN/ol

---

where $j denotes the share sent to user j for the kt group of elements in vector cs' (or nr'). By choosing (N), each user will generate (N) secret shares.
Step Disaggregation on re-combination vector. After distributing the secret shares, each user receives a re-combination vector Sit = (s)g. S .... xN for & E [[N/p]]. Since we pack elements for the secret shares of partial dot product, this step aims transform the Sy into vectors, with each vector representing one element. For each j E [7]. user i locally computes:
(10) where Bey is an n by n matrix whose (i, k) entry is (as - -2y)-1, and Chopa is an n by n matrix whose ki entry is if S =i=k & I d and 0 otherwise. After this operation, the degree-2d partial dot product shares are transformed into degree-d shares.
hij - Su, Chopa,
Step 3: Aggregation along packed index. The new secrets are summed up along j E [1] at client side:
h
Σ N
(11)
Step 4: Decoding for final secret shares. User i can derive the final secret shares st by recovering from hj, (h) h42.... ..,, hix) using Reed-Solomon decoding. Noted that (=]]k=][N/pp] becomes a packed secret share of dot products degree (see Appendix F).. Therefore, the server could recover the cosine similarity (or gradient norm square) for all users receiving the final shares from sufficient users.
4.6 Secret Sharing over Insecure Channel
This framework relies on a server-mediated communication channel for the following reasons: (1) it's challenging for mobile clients to establish direct communication with each other and authenticate other devices; (2) a server could act as central coordinator to ensure that all clients have access to the latest model. On the other hand, the secret sharing stage requires to maintain the privacy and integrity of secret shares.
To protect the secrecy of message. utilize key agreement and symmetric encryption protocol. The clients establish the secret keys with each other through During secret sharing, each client uses the common key knv to encrypt the message sent client and client v could decrypt the cyphertext with the same key.
key exchange protocol.
Another concern is that the server may falsify the messages transmitted between clients. Signature scheme is adopted to prevent the active attack from server. We assume that clients receive their private signing key and public signing keys of all other clients from a trusted third party. Each client i generates a signature o, along with the message m, and other clients verify the message using client i's public key d."K.
5 Theoretical Analysis
5.1 Complexity Analysis
In this section, we analyze the per iteration complexity for selected clients, and model dimension of M, and summarize the complexity in Table Further details of the complexity analysis available in Appendix G One important observation is that the communication complexity of our protocol reduces from O(MN N N) to O(M + N). Furthermore, the server-side computation overhead is reduced O((M + N) log" N log log N), benefiting from the efficient aggregation rule and packed secret sharing. It should be noted that while the BERA protocol has similar server communication complexity, it makes an unrealistic assumption that users can share secrets directly with each other, thereby saving the server's 's overhead.
5.2 Security Analysis
The security analysis is conducted for Algorithm 3 Given security parameter server S, and any subsets of users U, let REAL//.. 14,. be random variable representing the joint view of parties
7

---

Table 1: Complexity summary of RELPA and BERA
RFI
BERA
Computation
Communication
Computation
Communication
Server User
O((M N) log? N log log N) O((M + N2) log" N)
O((M N)N) O([M + N))
O((N2 + log" N log log N) O(MN N + MN²)
OIMN + N²) O + N)
in C C UUUS S where the threshold is set and U, be the subset of respondents round i such that U 2 Ui 2 U2 2 U4 2 U4. We show that the joint view of any group of parties from C with users less than É can be simulated given the inputs of clients in that group, trust score (TS})jeu, and global gradient g. In other words, the server learns no information about clients' inpul except the global gradient and trust score.
Theorem 5.1 (Security against active server and clients). There exists a PPT simulator SIM such that for all S K L. C((S) the output of SIM computationally indistinguishable from the output of REAL U.
REAL H. (xxx) = SIM (xu)
(12)
where represents computationalyy indistinguishable.
5.3 Correctness against Malicious Users
In this section, we show that our protocol executes correctly under the following attacks of malicious
users: (1) sending invalid secret shares; (2) sending shares from incorrect computation of 10 or
11
Note that adversaries may also create shares from arbitrary gradients, and we left the discussion
of such attack Section 5.4
The first attack arises when the user doesn't 't generate shares from the same polynomial. Such attempt prevented by verifiable secret sharing that allows for the verification of share validity by testing [8]
The second attack could addressed by Seed-Solomon codes. For a degree-d packed Shamir secret sharing with n shares, the feed-Solomon decoding algorithm could recover the correct result with E errors and crasures as long as S + 2E d + & n.
5.4 Convergence Analysis
Theorem 5.2. Suppose Assumption J.1 J.2 J.3 in Appendix D hold. For arbitrary number of malicioius clients, the difference between the global model w learnt by our algorithum and the optimal w is bounded. Formally, we have the following inequality with probability at least 1 5:
l|w - w S (1 p)) will+ 12 + r
(13)
where (V1 /2/(411)) 2474 + 27b). A = V1V Do
d log + log (3/5), A2 =
v
Dol
dlog
1842 2s
t log
Dol d
log
Guğr/DD 02211
L2 max m L1}.
Remark 5.3. r/d/g is the noise caused by the quantization process in our algorithm.
Experiments
6.1 Experimental Setup
We use three standard datasets to evaluation the performance of RFLPA: MNIST [30]. FaShionMNIST (F-MNIST) (31), and CIFAR-10 (32). MNIST and F-MNIST are trained on the neural network classification model composed of two convolutional layers and two fully connected layers, while CIFAR-10 10 is trained and evaluated with ResNet-9 333 model.
Dataset.
s Attacks. We simulate two types of poisoning attacks: gradient manipulation attack (untargeted) and label flipping attack (targeted). Under gradient manipulation attack, the malicious users generate

---

arbitrary gradients from normal distribution of mean 0 and standard deviation 200. For label flipping attack, the adversaries flip the label from P where the number of classes. We consider the proportion of attackers from 0% to 30%.
6.2 Experiment Results
6.2.1 Accuracy Evaluation
We compare our proposed method with several FL frameworks: FedAvg [4 Bulyan (18), Trim- mean [17). local differential privacy (LDP) [35. central differential privacy (CDP) 35 and BREA [16. Refer to T for the corse-grained comparison between RFLPA and the baselines. Noted
that several baselines are not included in the accuracy comparison because: (i) The security of the some schemes relics on the assumption of two non-colluding parties, which is vulnerable in real life. (ii) Some frameworks entail significant computation costs, rendering their implementation in real-life scenarios impractical (see Appendix K.8.I). Table summarizes the accuracies for different methods under the two attacks.
When defense strategy is not implemented, the accuracies of FedAvg decrease as the proportion of attackers increases, with a more significant performance drop observed under gradient manipulation attacks. Benefited from the trust benchmark, our proposed framework, RFLPA, demonstrates more stable performance for up to 30% adversaries compared to other baselines. In the absence of attackers, our method achieves slightly lower accuracies than FedAvg, with an average decrease of 2.84%, 4.38%and 3.46%, respectively, for MNIST, F-MNIST, and CIFAR- 10 dataset.
6.2.2 Overhead Analysis
To verify the effectiveness of our framework on reducing overhead, we compare the per-iteration communication and computation cost for BREA and RFLPA in Figure 3 the degree as 0.4N and encode 0.1 elements within a polynomial.
For each experiment
The left-most graph presents the overhead with different participating client size using the 1.6M parameter model described in Section 6.1 For M > N,, the per-client communication complexity for RFLPA remains stable at around 82.5MB, regardless of user size. Conversely, BREA exhibits linear scalability with the number of participating clients. Our framework reduces the communication cost by over 75% compared with BREA.
The second left graph examines the communication overhead for varying model dimensions with 2,000 participating clients. RFL.PA achieves much lower per-client cost than BREA by leveraging packed secret sharing, leading to a 99.3% reduction in overhead.
The right two figures presents the computation cost under varying client size using MNIST classifier with 1.6M parameters. Benefiting from the packed VSS, RFLPA reduces both the user and server computation overhead by over 80% compared with BREA.
Table 2: Accuracy under different proportions of attackers. The values denote the mean + standard deviation of the performance.
Mazipulatio
Flipping
Proportion Anackers
MNIST
0.98 10:00
0.06 20.1
0:30 2001
0.32 2:0.0
0.98 1:0.0
0.96 10.0
0.92 20.0
0.88 2:0.0
FedAug
F.MNIST
0.88 4-0.0
0.56 =0.0
0.51 =0.00
0.45 :.0.1
0.88 0.0.0
0.82 +0.0
0.78 0..0
0.69 =00.0
CIFAR-10
0.76 2..6-20.3
0.14 20.2
0.13 0.13-20.8 20.8
0.13 20.2
0.76 20.3
0.72 21.1
0.88 22.7
0.59 0.59.20- 20.8
MSSIS
0.98 20.0
0.32 20.0
0.89 20.0
0.37 20.00
0.98 20.0
0.31 20.0
0.90 =0.0
0.37
Bulym
F-MNIST
0.86 20.0
20.0
0.71 2001
0.69 2:0.0
0.86 20.0
0.76 2.00
0.70-200 0.70-20011
0.68 2:0.0
CIFAR-10
0.77 41.0
0. 1.73 20.8
0.45 21.5-1122
0.27 2:066
0.77 21
0.72 2:0
0.62 0..2
0.40 2:0.0
MSIITT
0.71
0.78
0.74
0.73
CIFAR-10
0.76 +1.0
0.67 #2.1
0.51
0.47 2-222
0.76
0.71
0.68 0.0.7
0.56
MNIST
0.57 1.0.1
0.13 20.00
0.10 1.000
0.10 0.10 0.0.
0.87 10.11
0.87 3.0.3
0.89 1:222
0.77 2.1
LDP
FANNIST
0.74 =0.1
0.50 =0.4
0.53 1..2
0.12
0.74 #0.1
0.63 20.5
0.62 =0.22
0.59 1.2
CIFAR-10
0.14 20.2
0.14 20.2
0.12 20.3
0.12 0.12.220.1
0.14 +0.2
0.14 20022
0.14
0.13 m0
MNNIST
0.96 =-0.0
0.96 =0000
0.35 +-0.0
0.00
0.96 +.0.0
0.96 =.0.0
0.95 +-0.3
0.91 +0.2
CDP
FANNIT
0.83:2011
0.51 20.1
0.41 20.00
0.34
0.83 20.1
0.81 20.55
0.79 20000
0.78 2:077
11.2
0..3
0.93
0.93
100.0
0.69
0.68
0.68 1.0.7
0.70 3222
0.67 0...9
0.65 2.7
MNNSTT
0.96 10.0
0.96 10.0
0.95 10.0
0.95 10.0
0.96 10.0
0.96 1..00
1.0000000
0.95 10.0
RELPA
F-NNIST
0.54 +0.0
0.84 +0.0
0.63 +0.0
0.62 +0.0
0.84 +0.0
0.88 +0.0
0.63
0.82 +0.0
CIFAR-10
0.74 22.3
0.70 21.8
0.70 2.702199
0.89 2
0.74 12.3
0.71 21.77
0.70.11..6
0.89 0.89.20.8

---

BREA
Con (000000
301
1,00
Number officee Droantions
Mumber ofthars
Sinner
Figure 3: Per-iteration communication (left two) and computation cost (right two).
6.2.3 Other studies
For other studies, analyze the impact of iterations accuracy (see Appendix|K. (..5) evaluate protocol against additional attacks (see Appendix K.6). conduct further overhead analysis (see K.8).
and examine the performance under non-iid setting (see Appendix K.9
7
Conclusion
This paper proposes RFLPA, a robust leverages verifiable packed Shamir secret sharing compute the cosine similarity between user and server update and conduct robust aggregation. We design secret re-sharing algorithm to address the increased information leakage concern, and utilize encryption and signature techniques to ensure the security over server-mediated channel. Our approach achieves the reduced per-user communication overhead O(M + N). The empirical study demonstrates that: (1) RFLPA achieves competitive accuracies for up 30% poisoning adversaries compared with nate-of-theeart defense methods. (2) The communication cost and computation cost for RFLPA is significantly lower than BERA by over 75% under the same FL settings.
FL framework with SecAgg. Our framework
8 Discussion and Future Work
Collection of server data. One important assumption is that the server is required to collect a small, clean root dataset. Such collection affordable for most organizations as the required dataset is of small size, e.g., 200 samples. According to theoretical analysis, the convergence is guaranteed when the root dataset is representative of the overall training data. Empirical evidence presented in (15) suggests that the performance of the global model is robust even when the root dataset diverges slightly from the overall training data distribution. Furthermore, Appendix 10 several alternative robust aggregation modules, such as KRUM and comparison with global model, to circumvent the assumption.
Compatibility with other defense strategies. RFLPA adopts a robust aggregation rule that computes the cosine similarity with server update. The framework be easily generalized distance-basee based method such as KRUM or multi-KRUM by substituting the robust aggregation module. However, extending the framework rank-based defense methods may be more challenging. Existing SMC techniques for rank-based statistics requires log M rounds of communication, where M is the range of input values (36). We leave the problem of communication-efficcee rank-based robust FL to future work.
Differential privacy guarantee. Differential privacy (DP) 37 38 provides formal privacy guaran- tees to prevent information leakage. The combination of SMC and DP, also known as Distributed DP [39]. reduces the magnitude of noise added by each user compared with pure local DP. However, adopting DP the
robust FL framework non-trivial, especially when bounding the privacy leakage of robustness metrics such cosine similarity may sacrifice utility. We leave the problem of incorporating DP into the privacy-rreservig robust FL framework to future work.
10

---

References
[1] H Brendan McMahan et al. "Federated learning of deep networks using model averaging". In: arXiv preprint PrXivv1602.056222 2 (2016).
[2] Rui Ye et al. "Feddisco: Federated learning with discrepancy-awarc collaboration". In: Inter- national Conference on Machine Learning. PMLR. 2023, pp. 39879-39902.
[3] Rui Ye et al. "Openfedllm: Training large language models on decentralized private data via federated learning" In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024, pp. 6137-6147.
[4] Jianyu Wang al. "Tackling the objective inconsistency problem in heterogeneous federated optimization". In: Advances in neural information processing systems 33 (2020), pp. 7611- 7623.
[5] Rui Ye et al. "Fake It Till Make It: Federated Learning with Consensus-Oriented Generation". In: The Twelfth International Conference on Learning Representations.
[6] Luca Melis et al. "Exploiting unintended feature leakage in collaborative learning". In: 2019
IEEE symposium on security and privacy (SP). IEEE. 2019, pp. 691-706.
[7] Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. "Model inversion attacks that exploit confidence information and basic countermeasures"" In: Proceedings of the 22nd ACM SIGSAC conference on computer and communications security. 2015, pp. 1322-1333.
[8] Ligeng Zhu, Zhijian Liu, and Song Han. "Deep leakage from gradients". In: Advances in neural information processing systems 32 (2019).
[9] Di Chai et al. "Secure federated matrix factorization". In: IEEE Intelligent Systems 36.5 (2020), pp. 11-20.
[10] Eugene Bagdasaryan al. "How backdoor federated learning". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2020, pp. 2938-2948.
[11] Ling Huang et al. "Adversarial machine learning". In: Proceedings of the 4th ACM workshop on Security and artificial intelligence. 2011, 1, pp. 43-58.
[12] Keith Bonawitz et "Practical secure aggregation for criacc-preserring machine learning". In: proceedings of the 2017 ACM SIGSAC Conference Computer and Communications
Security. 2017, pp. 1175-1191.
[13] James Henry Bell et al. "Secure single-server aggregation with (poly) logarithmic overhead".
In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. 2020, pp. 1253-1269.
[14] Peva Blanchard et al. "Machine learning with adversaries: Byzantine tolerant gradient descent".
In: Advances in neural information processing systems 30 (2017).
[15] Xiaoyu Cao et al. "FLTrust: Byzantine-robie Federated Learning via Trust Bootstrapping".
In: ISOC Network and Distributed System Security Symposium (NDSS). 2021.
[16] Jinhyun So, Başak Güler, and A Salman Avestimehr. "Byzantine-resilien secure federated
learning". In: IEEE Journal on Selected Areas in Communications 39.7 (2020), pp. 2168-2181.
[17] Dong Yin et al. "Byzantine-robust distributed learning: Towards optimal statistical rates". In: International Conference on Machine Learning. PMLR. 2018, pp. 5650-5659.
[18] Rachid Guerraoui, Sébastien Rouault, et al. "The hidden vulnerability of distributed learning in byzantium" In: International Conference on Machine Learning. PMLR. 2018, pp. 3521-3533
[19] Junyu Shi al. "Challenges and approaches for mitigating byzantine attacks in federated leam- ing". In: 2022 IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom). IEEE, 2022, pp. 139-146.
[20] Xiaoyuan Liu et al. "Privacy-enhanee federated learning against poisoning adversaries". In: IEEE Transactions on Information Forensics and Security 16 (2021). pp. 4574-4588
[21] Yinbin Miao et al. Errivacy-preservvee Byzantine-robust federated learning via blockchain systems". In: IEEE Transactions on Information Forensics and Security 17 (2022), pp. 2848- 2861.
[22] Zhuoran Ma et al. "ShieldFL: Mitigating model poisoning attacks in privacy-preserving federated learning". In: IEEE Transactions on Information Forensics and Security 17 (2022),
pp. 1639-1654.
[23] Adi Shamir. "How to share secret". In: Communications of the ACM 22.11 (1979), pp. 612-
613.

---

[24] Matthew Franklin and Moti Yung. "Communication complexity of secure computation". In: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing. 1992.
pp. 699-710.
[25] Whitfield Diffie and Martin E Hellman. "New directions in cryptography". In: Democratizing Cryptography: The Work of Whitfield Diffie and Martin Hellman. 2022, pp. 365-390.
[26] Hans Delfs et al. "Symmetric--ke eneryption". In: Introduction to cryptography: principles and applications (2007), pp. 11-31.
[27] Ravneet Kaur and Amandeep Kaur. "Digital signature". In: 2012 International Conference on Computing Sciences. IEEE. 2012, pp. 295-301.
[28]
Jonathan katz. Digital signatures. Vol. 1. Springer, 2010.
[29] Aniket Kate, Gregory M Zaverucha, and Ian Goldberg. "Constant-size commitments to poly- nomials and their applications". In: Advances in CryptologyAASAARTI
2010: 16th Inter- national Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16. Springer. 2010, pp. 177-194.
[30] Yann LeCun et al. "Gradient-basee based learning applied to document recognition". In: Proceedings of the IEEE 86.11 (1998), pp. 2278-2338 2324.
Han Xiao. Kashif Rasul, and Roland Vollgraf. "Fashion-mnis a novel image dataset for benchmarking machine learning algorithms", In: arXiv preprint arXiv: 1708. 07747 (2017). [32] Alex Krizhevsky et al. "Learning multiple layers of features from tiny images". . In: (2009).
[3]]
[33]
Kaiming He et al. "Deep residual learning for image recognition". In: Proceedings of the IEEE conference computer vision and pattern recognition. 2016, pp- 770-778.
[34]
Jakub Konečný et al. "Federated learning: Strategies for improving communication efficiency". In: arXiv preprint arXiv:1610. 0042200055422.. (2016).
[35]
Mohammad Naseri, Jamie Hayes, and Emiliano De Cristofaro. "Local and central differential privacy for robustness and privacy in federated learning". In: arXiv preprint arXiv:2009.0355 200903361 (2020).
[36] Gagan Aggarwal, Nina Mishra, and Benny Pinkas. "Secure computation of the k th-ranked element". In: Advances in Eyspooloy-EUROCRYYSS 2004: International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004. Proceedings 23. Springer. 2004, pp. 40-55.
[37] Thông T Nguyên et al. "Collecting and analyzing data from smart device users with local differential privacy". In: arXiv preprint arXiv: 05053 (2016).
[38] Arnaud Berlioz et al. "Applying differential privacy to matrix factorization". In: Proceedings of the 9th ACM Conference on Recommender Systems. 2015, pp. 107-114.
[39] Peter Kairouz, Ziyu Liu, and Thomas Steinke. "The distributed discrete gaussian mechanism for federated learning with secure aggregation".. In: International Conference on Machine Learning. PMLR. 2021, pp. 5201-5212.
[40] Mihir Bellare and Chanathip Namprempre. "Authenticated encryption: Relations among notions and analysis of the generic composition paradigm". In: Advances in Cryptol- ogy-ASIACRYPI 2000: 6th International Conference on the Theory and Application of Cryptology and Information Security Kyoto, Japan, December 3-7, 2000 Proceedings 6. Springer. 2000, pp. 531-545.
[41] Menezes Alfred, Vanstone Scott, et al. Handbook of applied cryptography. 1997.
[42] Dan Boneh and Xavier Boyen. "Short signatures without random oracles". In: Advances in Crypolog-EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004. Proceedings 23. Springer. 2004. pp. 56-73.
[43] Hsiang- Tsung Kung. Fast evaluation and interpolation. Carnegic-Mellon University. Depart- ment of Computer Science, 1973.
[44] Shuhong Gao. "A new algorithm for decoding Reed-Solomon codes". In: Communications, information and network security (2003), pp. 55-68.
[45] Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. "Robust aggregation for federated
learning". In: IEEE Transactions on Signal Processing 70 (2022), pp. 1142-1154.
[46] Meng Hao et al. "Efficient, private and robust federated learning". In: Proceedings of the 37th Annual Computer Security Applications Conference. 2021, pp. 45-60.
12

---

[47] Hidde Lycklama et al. "Rofl: Robustness of secure federated learning". In: 2023 IEEE Sympo-
sium on Security and Privacy (SP). IEEE. 2023, pp. 453-476.
[48]
Mayank Rathee et al. "Elsa: Secure aggregation for federated learning with malicious actors". In: 2023 IEEE Symposium Security and Privacy (SP). IEEE. 2023, pp. 1961-1979. federated
[49] Minghong Fang et al. "Local model poisoning attacks (Byzantine-Rohunt
learning". In: 29th USENIX security symposium (USENIX Security 20). 2020, pp. 1605-1622.
[50] Tianyu Gu et al. "Badnets: Evaluating backdooring attacks on deep neural networks", In: IEEE
Access (2019), pp. 47230-47244.
[51] Luisa Bentivogli et al. "The Fifth PASCAL Recognizing Textual Entailment Challenge." In: TAC 7.8 (2009), 1.
[52] Hector Levesque, Emesst Davis, and Leora Morgenstem. "The winograd schema challenge". In: Thirteenth international conference on the principles of knowledge representation and reasoning. 2012.
[53] V Sanh. "DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter." In: Proceedings of Thirty-thire Conference Neural Information Processing Systems (NIPS2019). 2019.
[54] Brendan McMahan et al. "Communication--fficcee learning of deep networks from decentral- ized data". In: Artificial intelligence and statistics. PMLR. 2017, pp. 1273-1282.
[55] Mi Luo al. "No fear of heterogeneity: Classifier calibration for federated learning with non-iid data". In: Advances in Neural Information Processing Systems 34 (2021), pp. 5972- 5984.
[56] Duygu Nur Yaldiz, Tuo Zhang, and Salman Avestimehr. "Secure Federated Learning against Model Poisoning Attacks via Client Filtering". In: ICLR 2023 Workshop Backdoor Atlacks and Defenses in Machine Learning.
13

---

A
Notation Table
Table 3: Notation table.
NOTATION
DESCRIPTION
NOTATION
DESCRIPTION
Model parameter
Gradients
D. Do.
Datasct
Aggrogation weight
Learning rate
S
Sct of participation clients
N
Participating client size
M
Model dimension
V M/A
Packed secret shares for gradients # of socrets packed at a polynomial for gradient
TS:
Trust score
of secrets packed at polynomial for shares of partial product
cs' cs)
Shares of partial cosine similarity
nr'. .n3
Shares of partial gradient norm square
S' S',
Packed secret shares of es' nr Packed secret share of dot product Pre-determined secret point by matrix whose (i, k) entry is (or, ey)(-1
h2
Secret shares disaggregated along packed index Secret shares aggregated along packed index Pre-selected elements for secret sharing
hi
matrix whose (f, k) entry
B.,
Chops
if 1 S i= k I d and O otherwise
B Details of Cryptographic Primitives
B.1 Packed Shamir Secret Sharing
The operations Packed Shamir Secret Sharing performed on a finite field Fp for some prime number P. Denote heihe as the pre-determined secret point, and {aile as the pre-selected elements for secret sharing. To share the secrets = (9), .......tt). 9t), the user can generate degree-d polynomial function:
((x) = q(=)((( e,) + (1)
(14)
I1 (x-e))
where g(x) random degree-d polynomial, and Li(x) the Lagrange polynomial
The shares sent to player j generated by:
8j ((a))
(15)
We use ag)a to denote the degree-d packed secret shares of vector The following properties holds for the packed sharing scheme:
(ox + By)a = =x(xx + B(y)a
(x y)di+dz = (xx), * (y)d2
B.2 Key Exchange
-ellman key exchange protocol consists of the following algorithms:
Generate parameters: pp = GenParam(s)) set up the parameters, including prime number and primitive root, according to the security parameter.
Key generation: (sSK, PK) KEGen(pp) generates the private-public key pairs for user i.
Key derivation: 8ij KEAgree(s$* , ) outputs the shared secret key between user i
and j.
B.3 Symmetric Encryption
The smmetric encryption scheme consists of the following algorithms:
Encryption: c Enc(m, k) encrypts message m eyphertext using key
Decryption: Dec(c, k) reverses cyphertext message using key kt
14

---

To ensure correctness, we require that m = Dec( (occ(Emmmm, k). For security, the encryption scheme should be indistiguushaabiity under a chosen plaintext attack (IND-DPA) and integrity under ciphertext-only attack (INT-CTXT) [40]
B.4
Signature Scheme
The UF-CMA secure signature scheme that consists tuple of algorithms (Gen, Sign, Verify):
Key generation: Based on the security parameter sp, (dSk, ddP)) SigGen(sp) returns the private-public key pairs.
Signing algorithm: = Sign(d .m generates signature a with secret key and message as input.
Signature verification: Verify(d m, o) takes as input the public key, a message and a signature, and returns if the signature is valid and otherwise.
To proof the security of the signature scheme, show that no adversary can forge a valid signature on an arbitrary message. Denote a UF-CMA secure signature scheme as DS - (k, Sign, Verify). where k is the security parameter. The UF-CMA advantage of adversary A is defined as uf-cua/aAa Advps(A, (A, k) P(Expps cmi (A, k) 1). where Expps uf cm- ( (A, k) represents the experiments produce signature, and Expñs Exprt--ma uf-cma (A, k) means that A produced conducted by adversary
a valid signature. In a UF-CMA secure signature scheme, no probabilistic polynomial time (PPT) adversary is able to produce valid signature on an arbitrary message with more than negligible probability. In other words, for all PPT adversaries A, there exists negligible function such that Adv A, k) < e(k).
C Comparison between Byzantine-robust aggregation rules
To provide justification for our algorithm's utilization of FLTrust the aggregation rule, we sum- marize the existing Byzantine-robust aggregation rules along four dimensions: (i) computation complexity, (ii) whether the algorithm needs prior knowledge about the number of poisoners, (iii) maximum number of poisoners, (iv) whether the algorithm is compatible with Shamir Secret Sharing (SSS).
Table 4: Comparison between Byzantine-robust aggregation rules.
Need prior knowledge about # of poisoners
Compatible with SSS
Computation complexity
# of poisoners
KRUM Bulyan
O(N-(M log N))
Yes
< 50%
Yes
O(N2M O( log N) ((N))
Yes
< 25%
No
Trim-mean
Yes
<< 50%
No
FLTrust
No
100%
Yes
Among these dimensions, FLTrust demonstrates clear advantages over other robust aggregation rules:
Low computation cost: for system with N and M model size, the computation cost of FLTrust is O(MN), lower than existing methods that grow quadratically with N.
No need of prior knowledge about number of poisoners: the server does not need know the number of malicious clients in advance to conduct robust aggregation.
Defend against majority number of poisoners: benefiting from the trusted root of clean dataset at the server, the aggregation rule we adopted can return robust result even when the number of poisoners is above 50%.
Compatible with Shamir Secret Sharing (SSS): the method we adopted is compatible with the SSS algorithm. While for Bulyan and Trim-mean, there are some non-linear operations not supported by SSS.
15

---

D Algorithm of RELPA
This section presents the our algorithm to conduct robust federated learning with secure aggregation.
Algorithm 1 RFLPA
Input:
Local dataset D; of clients E [N], root dataset Dn at server, number of iterations T,
security parameter
Output: Global model w
Clients set up encryption and signature key pairs (c.²K, ee (df" dgk) SetupKeys(N, x)
for i E [N]
Server initialize global model w
for t E [1 do
Server conduct local update with root data, compute update norm |gol| and create packed secret
shares Vo-
Each clients from Ui download global model w'-1, corresponding shares of Vo. and ||
Server obtain gradients <- RobustSecAgg(H, w Vo. [|gol])
Server update global model w w 7/g
end for
Algorithm SetupKeys
Input: number of clients N, security parameter k.
Output: key pairs {(dfk dd [E]]];
secret keys {kir [.j][
Each user [N] receive their signing key dik from the trusted third party, as well the verification keys dl dteK of all users j E [N].
Each user E [N] generate key pairs (s , _.") = KEGen(sp), and create signature o, Sign(d,". ss"K),
Users E [N] send (..K( public key along with signature, the server.
Server distribute {(s helr) to all users.
Each user i asserts that Verify(d PK 0,)) 1, and compute kij K KEAgree(s$K, PK)
for j [N]
Suppose that user create a packed secret shares s of g with polynomial ((z). Providing x security, the user sets up generator si and secret key and also outputs the public key (#), 16 ..... ya for degree polynomial. To make the secret shares verifiable, the user broadcasts commitment to the function:
C vpb())
(16)
E
Verifiable Packed Secret Sharing
For each secret 81, user computes a witness sent to the corresponding client in a private channel:
Wi = ((a)(()))
(17)
After receiving the commitment and witness, user | can verify the secret by checking:
e(C, v/) = e(w,, /0
////////// /us )e((, 16)
(18)
where e(.) denotes symmetric bilinear pairing.
The correctness and secrecy of the protocol are guarantee by the discrete logarithm (DL) 4T)
polynomial Diffie-Hellman (f-polyDH) [29]. and f-Strong Diffie-Hellman (t-SDH) 42 assumptions.
Explanation of Secret Re-sharing
For m [[N/p]], the shares of secret cs mm for some & E [p] can be represented as:
(sfm
(cs 01 ... Oa .... 0) Bei:
(19)
16

---

Algorithm 3 RobustSecAgg
Input:
Set of active clients in current iteration U6 global parameters downloaded from server, packed secret shares of server update Vo, norm of server update ||go||-
Output: Global aggregated gradient Round 1:
Client
Generate local gradient
Generate packed secrets (vi) jetto commitments C and witness (wir) Je for Bs from 15
16
and
17 encrypt Cij Enc Vig We]j kij), and create signature dij (dg cijl(C) for
E
[N]]]
Send
the server
Server:
Collect messages from least K clients (denote U4 the set of all respondents). Send (CIl hem bel to client j for j E U11
Round 2:
Client i:
Receive (Cll(c))euu willay)) from server, and assert that Verify ccillC,
1.
Recover ((yiiheuu (witheu Deo(c, kyj), and verify the secret shares {Viiljeur
by testing 18
Compute local shares partial norm (ur])eeu and partial cosine similarity {cs))jez, from 8
Construct packed secret shares | commitments C, and witness (w/R heu for
(fnr))jeu, {cs} bezn ). encrypt c/K
anccss//l// kak), and create signature dek
Sign(d dx (CC) for E [
Send (Cicclllo (lly for [M] to the server
Server:
Collect messages from least K clients (denote U2 the of all respondents). Send (CIl vill heury) to client j for j E U2.
Round 3:
Client i:
Receive
from server, and assert that Verify(d,%* C,ill,,
1.
Recover se (a/x)euw))) = Dec(c' kjj), and verify the secret shares (5/
by testing [8
Obtain the final share of norm (TFF) beju and cosine similarity (T8)) from 10
and Reed-Solomon decoding.
Send (1r4))s {c5) heru/ul to the server.
Server:
Collect messages from at least K clients (denote 14g the set all respondents).
Recover (Ilg, 112) Iyeu, using Reed-Solomon decoding, and assert that [gg 1|2 S |lgul 11 Vj E Un.
Recover (g. hel,, using Reed-Solomoo decoding, and compute the trust score (TS) } heu
from[5]
Broadeast the trust score (TS) to all users i E U3-
Round 4:
Client
Compute local aggregation (g) from and send to the server.
Server:
Collect messages from least K clients.
Recover g using Reed-Solomon decoding.
where (0)bet4 random integers.
17

---

Hence, the user side computation of I0 is the same as:
im
1m
Bed ChopaBey = =Ber
8 Nm ... Nm
(20)
Cs
X
(m--1)+t::
(m-1)pth
Bes -hhopa
The aggregation of new secret and reconstruction of { } is equivalent to taking the first column of:
BT
C$ (m-11)p
Cs (m=1))+k
(21)
x B
BB, Chopa-
Since es' is packed secret share of the partial cosine similarity, it follows that:
(cs), css)) Bey Chopa =
....
(22)
meaning that the first elements gives the partial cosine similarity. Therefore, the final shares sent to server ( can be formulated as:
(
(En 0m(p-1)+h. 0 0₂ 0 O...) Bes:
(23)
for h (m(p- 1), mp]. Therefore, the server could retrieve the dot product by Reed-Solomon decoding, which equivalent to multiplying (Br, Jae(m(p-1).mp and obtaining the first element.
G Details of Complexity Analysis
User computation: User's 's computation cost can be broken as: (1) generating packed secret shares of update (O(M + log" N) complexity (43)); (2) computing shares of partial gradient norm square and cosine similarity (O(M + N)) complexity); (3) creating packed secret shares of partial gradient norm square and cosine similarity (O(N log .) complexity):
(4) deriving final secret shares of gradient norm square and cosine similarity (O(N2 log* N) complexity). Therefore, each user's computation cost O(M N2) log² N).
User's communication cost can be broken as: (1) downloading parameters from server (O(M) messages); (2) sending and receiving secret shares of gradient (O(MM, N)) messages); (3) sending and receiving secret shares of partial gradient norm square and cosine similarity (O(N) messages); (4) sending final shares of gradient norm square and cosine similarity (0(1) messages); (5) receiving trust scores from the server (O(N) messages); (6) sending shares of aggregated update the server (O(M/N + messages). Hence, each user's communication cost is O(M + N).
User communication:
The server's 's computation cost be broken as: (1) recovering gradient norm square and cosine similarity by Reed-Solomon decoding (O(N log" N log log N) complexity (44]); (2) computing the trust score of each user (O(N) complexity); (3) decoding the aggregated global gradient (O(M) + .N) log² N log log N) complexity). Therefore, the server's computation cost is O(MM + N) log? N log log N).
Server computation:
The server's communication cost can be broken as: (1) distributing pa- rameters to clients (O(MN) messages); (2) sending and receiving secret shares of user update (O((M + N)) messages); (3) sending and receiving secret shares of partial gradient norm square and cosine similarity (O(N2) messages); (4) receiving final shares of gradient norm square and cosine similarity (O(N) messages); (5) broadcasting trust scores to clients (O(N2) messages); (6) receiving shares of aggregated update from clients (O(M + N) messages). Overall, the server's communication cost is O(M N)N).
Server communication:
18

---

H Proof of Theorem 5.1
Proof. We utilize the standard hybrid argument prove the theorem. define PPT simulator SIM through series of (polynomially many) subsequent to REAL M.A.i that the view of C in SIM is computationally indistinguishable from that in REAL u.....
Hyb;: In the hybrid, each honest user from U1 AC encrypts shares of a uniformly random vector, instead of the raw gradients. The properties of Shamir's secret sharing ensure that the distribution of any [C < shares of raw gradients is identical to that of any equivalent length vector, and IND-CPA security guarantees that the view of server indistinguishable both cases. Hence, this hybrid is identical from the previous one.
Hyb2: In the hybrid, the simulator aborts if provides any of the honest user with a signature j's message, Czz. but the user couldn't 't produce the same signature given the public key (in round 2). The security of the signature scheme guarantees that this hybrid is indistinguishable from the previous one.
Hyb3: In this hybrid, SIM aborts if any of the honest user fails to verify the secret shares 8ji from user j by checking 18] The the DL. E-polyDH, and t-SDH assumptions guarantee that this hybrid is identical from the previous one.
Hyb4: In the hybrid, each honest user from U2 Ç encrypts shares of uniformly random vector rather than partial norm and cosine similarity. The properties of Shamir's secret and IND-CPA security ensure that this hybrid is indistinguishable from the previous one.
Hyb5: In the hybrid, the simulator aborts if C' provides any of the honest user i with a signature on j's message, Cj but the user couldn't 't produce the same signature given the j's key (in round 3). Because of the security of the signature scheme, this hybrid is indistinguishable from the previous one.
Hyb:: This hybrid is defined as Hybg, with the only difference that SIM verify the secret shares s' in round 3. This hybrid is indistinguishable from the previous one under DL, L-polyDH, and (-SDH assumptions.
The above changes do not modify the views seen by the colluding parties, and the hybrid doesn't make use of the honest users' input. Therefore, the output of SIM is computationally indistinguishable from the output of REAL 4. and this concludes the proof.
I Proof of Theorem 5.2
Denote g' E; m/g, be the aggregated gradients iteration t.
Lemma L.. For arbitrary number of adversarial clients, the distance between g' and V V((w') is bounded by:
! - VF(w") S 33g +2 Vd
(24)
19

---

Proof. It follows that:
g
VL)(w)]
=
Σ mg VF'(w)]
Σ
go go FF (w)l
go
g0
Σ
go
BD
8ol
go VF ||
(25)
|B:1 + B
Bo
goll
+ go (w)(
(a)
Vd + go (F'(w))
$ 2
goll
+
vd
$ 3 go
V F" w
V (w)l +
where (a) is because Σ; 1/1 = 1, g goll. Bool S || go |l-
Lemma 1.2. Under Assumption J.1
we have the following bound at iteration t:
l|w w" VF((")] S /1- 122 (AL2())))) w'll
(26)
Proof. Refer lemma in 15 for the proof.
Lemma L.3 Suppose Assumption J.1 J.2 J.3 holds. For any (0,1), AI S v2//1, D S
12. /22, we have:
P (llgo VF(w)] & 882/|ww - w 44, 21-5,
(27)
for any E OC {w w: |w | w |ww =
given some positive number
Proof. Refer lemma 4 in 15 for the proof.
Proof of Theorem 5.2 Given the lemmas above, proceed to prove Theorem 5.2
We have:
lw w"ll S - -VF(W w yllg VF(w")l
S ww VVF - w + 3 - VF(w")l
+2> + vv
(28)
((11- (V1- 11111/1(433) + 24/42 + 27L ||w"-1 -wll
w'll
+127A1 yvd
q
Therefore, with probability least 5, follows that:
Iw w S (1 - w) - w/ +127+ + IVd
(29)
J Assumptions for convergence analysis 5.4
Assumption J.1. The expected risk function F(w) is ju-stroglly convex and L-smooth for any w,
w:
F(w) 2 F(w) + (VF(w). w - w) + - w|| [VF(w) VF(W) S L| - w/l.
(30)
20

---

Moreover, the empirical loss function L(D, w) is L1-smooth probabilistically. For any å E (0, 1), there exists an L1 such that:
VL(D, VL(D.W)
8
P
sup
W S 41
(31)
3
Assumption J.2.
The root dataset Du and clients' local dataset Dj 1, 2,., n) are sampled independently from distribution X.
Assumption J.3. The gradients of the empirical loss function VL(D, w") at the optimal model w bounded. Furthermore, h D, w) = VL(D, w) VL(D, w*) is also bounded. Specifically,
LVL(D, w*), ). v) and (h(D, w) E[ D, w)] v)) /| w l are -xtenexpoeetial for any unit vector v. Formally, for Aala S 1/a1, M/ - 1/a2, = (v ||=|| = 1}. it holds that:
sup E(exp(A
w w*), v))l S e
VEB
(h(D. w) - w)) v) ]
(32)
S c02x212
sup vEB,W
E
exp
- w
K
Experiments
The experiments are conducted on a 16-core Ubuntu Linux 20.04 server with 64GB RAM and A6000 driver, where the programming language is Python.
K.1
Datasets
MNIST is a collection of handwritten digits. including 60,000 training and 10,000 testing images of 28 28 pixels. F-MNIST consists of 70,000 fashion images of size x 28 and split into 60,000 training and 10,000 testing samples. CIFAR-10 10 is natural dataset that includes 60,000 32 32 colour images 10 classes, splitting into 50,000 training and 10,000 testing images.
K.2 FL configuration
both datasets split among 10,000 users and select 100 users in each iteration. The server stores 200 clean samples as benchmark. We allow up to 20% clients to drop out in each round, and maximum of 30% participating clients to collaborate with each other reveal the secret. Therefore, we construct a secret sharing of degree 40, considering the doubling of degree during dot product computation, and pack each 10 elements into secret.
K.3 Hyper-Parameters
The parameters are updated using Adaptive Moment Estimation (Adam) method with a learning rate of 0.01. Each accuracy reported in the tables an average of experiments, and each round of experiments runs for 200 iterations. Both LDP and CDP adopt privacy parameter 3 and 0.0001.
K.4
Comparison among Aggregation Frameworks
In Table 5 we summarize the comparison among aggregation frameworks along four dimensions:
Robustness against malicious users: most algorithms provide certain level of robustness against malicious users. Local DP is not that effective in defending malicious users according to our experiment results. Though Robust Federated Aggregation (RFA) (45) provides robust aggregation protocol based on geometric median, the malicious users could freely manipulate the uploaded gradients for poisoning attacks.
Privacy Protection against server: whether the framework protect user's plaintext gradient against server. Only PEFL., PBFL., ShieldFI., SecureFL. [46), RoFL. (47), ELSA [48), BREA, and RFLPA achieves the goals of robustness and privacy simultancously.
21

---

Collusion threshold during model training: the server could obtain users' plaintext gradients it colludes with more than the given level parties. PEFL, PBFL, ShieldFL. SecureFL. and ELSA all rely on two non-colluding parties during model training to protect users' message. The collaboration between the two non-colluding parties could compromise user's privacy.
MPC techniques: the main multiparty computation techniques leveraged by the framework. PEFL, PBFL, ShieldFL, SecureFL, and ELSA are based on multi-party computation (MPC) homomorphic encryption (HE), RoFL is based zero-knowledge proof (ZKP), and BREA and RFLPA are based on secret sharing.
Furthermore, although RoFL and ELSA could defend against malicious users, they are designed specifically for naive robust aggragation method, norm bounding. It's completely impractical to generalize these frameworks more advance defense method such as Krum.
Table 5: Corse-grained comparison among Aggregation Frameworks. "f" denotes non-applicable.
ELSA improves RoFL regarding the the efficiency.
Robustness against
Privacy Protection
Collusion threshold during model training
MPC techniques
malicious users
against server
FedAvg
Yes
No
Bulyan
No
Trim-mean
Yes
No
KRUM
Yes
No
Central DP
Yes
No
Local DP
Not effective
Yes
RFA
No
Yes
PEFL
Yes
Yes
HE (Paillier)
PBFL
Yes
Yes
HE (CKKS)
ShieldFL
Yes
Yes
HE (Paillier)
SecureFL
Yes
Yes
MPC HE (BFV)
RoFL.
Yes
Yes
O(N)
ZKP
ELSA
Yes
Yes
1
MPC
BREA
Yes
O(N)
Secret sharing
RFLPA
Yes
Yes
O(N)
Secret sharing
K.5
Accuracies over Iterations
Figure demonstrates the impact of different iterations test accuracies for RFLPA, BREA and FedAvg using the MNIST dataset. The results reveal that the RFLPA algorithm displays comparable convergence regardless of the existence of attackers, while FedAvg exhibits significantly inferior convergence when 30% attackers are present.
K.6 Performance on Additional Attacks
K.6.1 Poisoning Attacks
We evaluate our protocol against several stealthier attacks: (1) KRUM attack 49 (2) BadNets (50] and (3) Scaling attack [10]. KRUM attack is untarget attack, and BadNets as well as Scaling attack backdoor attacks that specifically degrade the performance triggered samples. We follow the same approach as in (50) and [10] to embed triggers in the targeted images.
Table 6 compares the performance of RFLPA and FedAvg against the above attacks. For KRUM attack, RFLPA improves the accuracy on the general dataset over FedAvg by more than 1.6x. For the two backdoor attacks, RFLPA show trivial performance loss on the general and triggered dataset, as opposed to the significant degradation in accuracy for FedAvg.
K.6.2 Inference Attacks
We assess our RFLPA against passive inference attack using the Deep Leakage from Gradients (DLG) It is important note that experiments were not conducted for active inference attacks, where
22

---

FodAvg-No Attackers
FodAvg-30% Attackers
RFLRA-No Attackers
RFLRA-30% Attackers
BREA-No Attackers
BREA-30% Attackers
MreiilantMnnipuaation
Fiippingg
1.0
0.8
Male you M Mann
0.7
Tead Recurayy
0.6
05
641
63
0.3
62
0.
0.1
30
Ro Meratoons
Figure Test accuracy of RFLPA and FedAvg for different proportions of malicious users on MNIST dataset.
Table 6: Accuracies CIFAR-10 under varying proportions of attackers. For backdoor attacks, the values are presented as overall accuracy (backdoor accuracy).
FedAvg
RFLPA
attackers
10%
20%
30%
10%
20%
30%
KRUM attack
0.27
0.12
0.11
0.71
0.70
0.70
BadNets
0.68 (0.54)
0.67 (0.54)
0.55 (0.28)
0.71 (0.68)
0.70 (0.68)
0.69 (0.66)
Scaling attack
0.70 (0.22)
0.68 (0.21)
0.54 (0.19)
0.70 (0.69)
0.70 (0.69)
0.69 (0.69)
the server might alter users' messages, such as secret shares, to access private data. This omission due the protection provided by the signature scheme, which safeguards message integrity and prevents the server from forging any user's messages.
DL.G attempts reconstruct the original image from the aggregated gradients. We conducted attack on the CIFAR-10 dataset, using the specifications in Appendix K.2 The average peak signal- to-noise ratio (PSNR) of generated image with respect to original image 11.77. much lower than the value of 36.5 when no secure aggregation is involved. Figure 5 shows that the inferred images are far from the raw images under DLG attack.
Original images
Generated images
Figure 5: Original and inferred image under RFLPA.
23

---

K.7 Performance on Diverse Dataset
K.7.1 Performance on Natural Language Processing (NLP) Dataset
We evaluate the accuracy our framework on two NLP datasets, Recognizing Textual Entailment (RTE) [51] and Winograd NLI (WNLI) [52], by finetuning distilIBERT model (53]. We present the performance for gradient manipulation attack in Table The result demonstrates that for the two NLP datasets, RFLPA has robust accuracies in the presence of up 30% attackers.
Table 7: Accuracies on NLP dataset under different proportions of attackers.
RTE
WNLI
Proportion of Attackers
No
10%
20%
30%
No
10%
20%
30%
FedAvg
0.599
0.509
0.487
0.462
0.619
0.563
0.437
0.437
BREA
0.584
0.592
0.570
0.567
0.592
0.592
0.577
0.563
RFLPA
0.596
0.582
0.582
0.577
0.619
0.592
0.592
0.563
K.7.2
Performance on CIFAR-100 Dataset
To test more complex CV dataset, we evaluate our frameworks on CIFAR-100 [32 dataset using a ResNet-9 classifier. It can be observed in Figure that RFLPA significantly enhances the accuracy over FedAvg from 10% attackers, by an average of 3.94x. Furthermore, RFLPPA experiences little performance degradation in the presence of up 30% attackers.
Table Accuracy on CIFAR- 100 dataset under gradient manipulation attack.
FedAvg
RFLPA
% of attackers
No
10%
20%
30%
No
10%
20%
30%
Accuracy
0.55
0.11
0.10 200
0.10
0.55
202
0.54
0.50 201 0.49
K.8
Overhead Analysis
K.8.1
Computation Time between RFLPA and HE-based methods
To verify the practicability of RFLPA, we benchmark our framework with three HE-based methods,
PEFL 220]. PBFL [2I]. and ShieldFL [22]. presenss the per-iteration computation time using
MNIST classifier (I.6M parameters) for the three algorithms and RFLPA. It can be observed that
takes 1.5 to 6,5 day to run the three HE-based algorithms for only single iteration, which renders
them impractical for real-life deployment.
Table 9: Computation cost (in minutes) with varying client size.
Per-user Cost
Server Cost
Client size
100
200
300
400
100
200
300
400
RFLPA
3.41
11.44
24.51
42.60
6.68
8.46
15.00
26.47
PEFL
111.51
109.27
109.44
110.13
2156.20
6056.98
6785.71
9365.46
PBFL
12.65
12.58
12.73
12.63
1806.05
3598.54
5386.97
7193.64
ShieldFL
111.73
109.43
109.25
109.84
2192.48
6093.05
6809.60
9384.11
K.8.2 Ablation Study
Considering that RFLPA and BREA leverage different robust aggregation rule, we conducted ablation study to demonstrate that the reduction in overhead is attributed to the scheme design of RFLPA rather than the inherent advantages of the underlying aggregation rule. In particular, we replace the aggrega- tion module in RFLPAA with KRUM, and presents the per-iteration communication and computation cost, respectively. in Table TO and II It can be observed that even with substituting the aggregation module with KRUM in our framework, there's still notable reduction the communication cost benefiting from the design of our secret sharing algorithm.

---

Table 10: Communication cost (in MB) per client with varying client size with MNIST classifier
(1.6M parameters). RFLPA (KRUM) replaces the aggregation rule with KRUM in RFLPA.
Client size
300
400
500
600
RFLPA
82.51
82.52
82.53
82.54
BREA
1909.92
2544.45
3178.98
3813.51
RFLPA (KRUM)
79.58
82.25
85.68
89.87
Table 11: Computation cost (in minutes) with varying client size with MNIST classifier (1.6M
parameters). RFLPA (KRUM) replaces the aggregation rule with KRUM in RFLPA.
Per-user Cost
Server Cost
Client size
100
200
300
400
100
200
300
400
RFLPA
3.41
11.44
24.51
42.60
6.68
8.46
15.00
26.47
BREA
44.73
101.30
182.27
294.27
75.85
145.30
216.96
287.2 22
RFLPA (KRUM)
13.60
35.56
46.48
75.78
31.77
34.04
39.76
62.81
K.9
Non-IID Setting
K.9.1
Heterogenous Clients
The previous experiments were conducted under the assumption that the local data of clients are independent and identically distributed (IID). To simulate the non-IID dataset, adopted the setting in (54) by sorting the data based on their labels and dividing them into 10,000 subsets. Consequently, the local data owned by most clients consist of only one label.
BRSALF
Poportoon of Advencotes
Proprtion
Figure 6: Test accuracy on non-IID dataset. GM stands for gradient manipulation attack, and L. stands for label flipping attack.
We compare the accuracy of RFLPA, BREA and FedAvg on non-lII dataset in Figure The RFLPA demonstrates resilient performance against poisoning attacks, even when the dataset distributed non-identically among clients.
K.9.2 Dynamic Data
For dynamic settings, consider the case where the data of the clients change during the federated training with the arrival of new data. To simulate the setting, we leverage Dirichlet Distribution Allocation (DDA) (55) to sample non-iid dataset, and change the distribution for each client every 20 epochs. The parameter of the Dirichlet distribution is set to a = 0.1.
Table 12 presents the accuracy against gradient manipulation attack. Our RFLPA demonstrates robust performance under the dynamic setting for up to 30% attackers. The improvement of RFLPA over FedAvg is more than 2x when there are at least 20% attackers.
25

---

Table 12: Accuracy under dynamic client data distribution against gradient manipulation attack.
MNIST
F-MNIST
% of attackers
No
10%
20%
30%
No
10%
20%
30%
FedAvg RFLPA
0.98 20.0
0.27 20.
0.29 20
0.29 1
0.86 =0.0
a.
0.21 20
0.18 20.2
0.96 20.0
0.94 =0.0
0.92.0.0
0.90
0.831o.0
0.79
0. 0.79
0.77
K.10
Integration with Other Aggregation Protocols
The robust aggregation rule of RFLPA is based FL.Trust, requiring a clean root data set side. Suppose we cannot get any clean root dataset even if the required size is small, is feasible replace the aggregation protocol with other robust aggregation algorithms to circumvent the assumption.
First, algorithm be integrated with KRUM-based method by substituting the aggregation module with KRUM. Though KRUM incurs greater cost than the original method, Appendix K.8.2 shows that there is notable reduction in communication and computation cost compared with BREA, benefiting from the design of our secret sharing algorithm. The accuracy of RFLPA (KRUM) is expected to be the same BREA, as both utilize the aggregation rule.
Another alternative is to compute the cosine similarity with global weights. Specifically, we can compute the cosine similarity between each local update and the global weights as follows (56):
(w
cos( (w), w 1)
(33)
and filter out the clients with similarity smaller than a pre-specified threshold, which is set to in our evaluation.
observe that compared with FedAvg, RELPA-GW effectively improves the accuracy in the presence of attackers. Noted that the communication and computation cost of RFLPA-GW is at the same scale RFLPA's original level, as both compute the cosine similarity with single baseline.
From Table 13
Table 13: Accuracy for defense based on global weight under different proportions of attackers. RFLPA-GW replaces the robust aggregation rule in RFLPA with the method based on cosine similarity with global weight.
MNIST
F-MNIST
of attackers
No
10%
20%
30%
No
10%
20%
30%
FedAvg
0.98 20.0
0.46 20.1
0.40 20.1
0.32 20.0
0.88 :0.0
0.55 =0.0
0.51
0.45
RELPA-GW
0.98 10.0
0.95
10.1
0.92
0.91
0.90.a.0
0.80.o.1
0.77.0.0
0.75.0.0
L Impact Statement
Our work in developing a robust federated learning framework (RFLPA) addresses significant challenges in privacy and security in federated learning (FL), presenting substantial benefits in data protection and carrying broader societal implications. The advancements in safeguarding data privacy bolster ethical standards in data handling, yet they may raise concerns in scenarios requiring data transparency. Our efforts contribute to the technical evolution of FL but also underscore the need for ongoing ethical considerations in the face of rapidly advancing machine learning technologies.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See Section g Discussion and Future Work.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttpp//..aarrrpp.ccppppp//lhcct
27

---

Answer: [Yes]
Justification:
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See Appendix D
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: NA]
Justification:
28


Reviews:
[{"review_id": "tFnkIFDIRj", "reviewer": "Reviewer_WU56", "summary": "This paper presents a framework to address the dual challenges of privacy leakage and poisoning attacks in federated learning. The authors propose RFLPA, which integrates cosine similarity for robust aggregation with verifiable packed Shamir secret sharing to ensure secure aggregation without compromising on robustness. The framework also introduces a new dot-product aggregation algorithm to prevent information leakage. The proposed method is evaluated on 3 benchmark datasets.", "questions": "1. Could the authors provide more insights into the practical implementation challenges of integrating verifiable packed Shamir secret sharing into existing FL systems?\n2. How does the framework scale with the number of clients and the dimensionality of models, and are there potential bottlenecks for large-scale deployments? \n3. Could the authors elaborate on the potential vulnerabilities in the cryptographic mechanisms used and how they are mitigated?\n4. How realistic is the assumption of the server having a clean root dataset in different FL application domains, and can the framework be adapted for scenarios without such a dataset?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and well-structured. The paper addresses a very important problem in the security of federated learning systems. Thorough experimentation and analysis are undertaken to evaluate the proposed method.", "weaknesses": "The paper’s reliance on the assumption that the server has a clean root dataset and that secure communication can be maintained without significant overheads may not always be realistic. Additionally, the code was not revealed and could not be evaluated at the time of this review. Finally, one of the main threats that challenge robust aggregators is backdoor attacks, which are tested on the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer WU56, \n\nThank you for your recognition and valuable comments. Hope our response below could address your concern.\n\n**W1 & Q4: Assumption that the server has a clean root dataset and that secure communication can be maintained without significant overheads**\n\nThanks for your comment. \n\nFor the first assumption, referring to our answer to Q1 in global rebuttal to program chair, the public samples can be of small size (e.g., 200 samples), and the gobal model is robust even when the root dataset diverges slightly from the overall training data distribution. Moreover, we have proposed two remedies in the absence of such dataset, including comparison with global weights and KRUM. \n\nFor the second point, we may clarify that we haven't explicitly assumed that secure communication can be maintained without significant overheads. Instead, our paper aims to minimize the communication cost during secure communication by reducing the message size. It should be noted that secure communication is neccessary to protect the secrecy and integrity of the messages transmitted during federated learning. We are pleased to provide further clarification if there's any misunderstanding in your concern.\n\n**W2: The code was not revealed**\n\nThanks for your comment. We have sent the code in anonymized link to AC.\n\n**W3: Evaluation of backdoor attacks**\n\nThanks for your suggestion. As discussed in our response to Q2 in the global rebuttal, we tested RFLPA's robustness on two backdoor attacks, BadNets, and scaling attacks. We will include the empirical analysis in appendix.\n\n**Q1: Insights into the practical implementation challenges of integrating verifiable packed Shamir secret sharing into existing FL systems?**\n\nThanks for your question. The verifiable packed Shamir secret sharing could be vulnerable to the following implementation errors: (a) the client conducts incorrect computation, such as aggregation and dot product, on the secret shares, and (b) the client might collaborate to recover the secret. In our paper, we propose the following mitigations to such challenges: (a) The Reed-Solomon decoding algorithm allows the server to recover the correct computation results in case of certain computation errors.  For a degree-d packed Shamir secret sharing with n shares, the Reed-Solomon decoding algorithm could recover the correct result with E errors and S erasures as long as $S + 2E + d + 1 \\leq n$. (b) Formal security guarantee on the packed secret shares suggests that any O(N) shares reveal no information of the secret values.\n\n**Q2: How does the framework scale with the number of clients and the dimensionality of models, and are there potential bottlenecks for large-scale deployments?**\n\nThanks for your question. We explain the scalability in terms of communication and computation cost. The theoretical overhead is listed in Section 5.1 Complexity Analysis, and we summarize the cost in Table R1. \n\n[**Table R1.** Complexity summary of RFLPA for N clients and M dimensional model.]\n\n| |Computation|Communication|\n|-|-|-|\n|Server|$O((M+N)log^2NloglogN)$|$O((M + N)N)$|\n|User|$O((M + N^2)log^2N)$|$O(M + N)$|\n\nThe empirical overhead can be found in Section 6.2.2 and Appendix L.7. We also highlight the per client communication and computation cost under varies client size in Table R2.\n\n[**Table R2.** Per client overhead of RFLPA using a MNIST classifier (1.6M).]\n\n|client size|100|200|300|400|\n| ---- | ----- | ---- |---- |---- |\n|Communication cost (MB)|82.50|82.50|82.51|82.52|\n|Computation cost (minute)|3.41|11.44|24.51|42.60|\n\nIn our study, we observed that communication costs remain relatively stable as N increases significantly, with message size staying nearly constant with N but linearly scaling with M (when $M\\gg N$). For computation cost, training time shows an approximate second-order polynomial increase with N and a linear increase with M.\n\nFor large-scale deployments, the bottlenecks are as followed: (1) Server communication: the server could suffer heavier communication overhead, which mainly comes from the stage of distributing the user's secret shares. To mitigate this issue, we can allocate the secret distribution task to multiple nodes to relief the server's workload. The signature and encryption schemes prevent the nodes from conducting man-in-the-middle attacks on the secret shares. (2) Synchronization: each training iteration consists of four rounds, raising dropout problem. The server should wait for the result of participating clients to continue. Noted that the secret sharing scheme could inherently mitigate the problem. For a degree-d packed Shamir sharing, the reconstruction can be done on receiving responses from d+1 users.\n\n**Q3: Could the authors elaborate on the potential vulnerabilities in the cryptographic mechanisms used and how they are mitigated?**\n\nDiffie-Hellman (DH) key exchange protocol: The major vulnerability of DH key exchange protocol is the Man-in-the-Middle attack. The attacker could alter the key exchange messages between the communicating parties. Such vulnerability could be addressed by the signature scheme. In particular, each client could receive their own signing key, as well as the verification keys for all other users from a trusted third party. The third party could be a government agency or certificate authorities that provide digital certificates for secure communication. The signiture scheme prevents the attacker from modifying the messages.\n\nSymmetric Encryption & Signature Scheme: (1) Side-channel attacks. The attacker could infer the sensitive information exploiting side-channel signals, such as timing information. It's important to utilize mature encryption and signature packages robust to side-channel attacks. (2) Key management. Weak key management practices could lead to key leakage or theft. It's crucial to store private keys in secure environments, such as Hardware Security Modules.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cd5U7JhWmX", "reviewer": "Reviewer_4mMR", "summary": "This paper aims to enhance the vulnerability of FL when dealing with poisoning attacks. A common strategy used in FL to avoid directly sharing local updates is called secure aggregation(SecAgg), which works with ciphertexts and is incompatible with defense techniques against poisoning attacks. To address this issue, the paper proposes using verifiable packed Shamir's secret sharing to compute the cosine similarity between local and global models for aggregation. Additionally, a novel dot product aggregation method is introduced to reduce the communication overhead caused by Shamir's secret sharing.", "questions": "1. It seems that only the experiments of malicious users are examined. I could not find that case when server conducts an active inference attack, is it included?\n\n2. If the clean dataset at the server is not available, is it still possible to adjust the proposed protocol to deal with this situation?", "limitations": "Limitations are adequately addressed", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "+ The problem of addressing poisoning attacks in FL is timely and challenging, especially with provable security guarantee \n\n+ The attempt to reduce the communication overhead caused by secret sharing is valuable \n\n+ Extensive experimental validations and very detailed comparison with existing frameworks, especially for various aggregation methods", "weaknesses": "- The assumption that the server has trusted root of clean datasets seems a fundamental limitation \n\n- The presentation could be improved; there are too many concepts introduced, making it hard to distinguish between what is new and what is from existing literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer WU56, \n\nThank you for your recognition and valuable comments. Hope our response below could address your concern.\n\n**W1 & Q2: Assumption on clean public samples**\n\nThanks for your comment. As discussed in our response to Q1 in global rebuttal to program chair, we proposed some remedies in the absence of such dataset, including comparison with global weights and KRUM. Furthermore, the public samples can be of small size (e.g., 200 samples), and the gobal model is robust even when the root dataset diverges slightly from the overall training data distribution.\n\n**W2: Distinguish between new and existing concept**\n\nThanks for your suggestion.  We clarify the distinctions as followed.\n\nThe cryptographic techniques introduced in Section 3.4 Cryptographic Primitives are from existing literature, including packed Shamir secret sharing, Diffie-Hellman (DH) key exchange protocol,symmetric encryption and UF-CMA secure signature scheme.\n\nThe Verifiable Packed Secret Sharing (V-PSS) is our proposed concept, as previous verifiable secret sharing scheme are mainly associated with the vanilla Shamir secret sharing. We leverage the commitment technique in [1] to design the V-PSS algorithm. Furthermore, the Dot Product Aggregation and the related concept *partial dot product* is proposed by our paper. The secure communication scheme for secret sharing is proposed by our work, building on the aforementioned DH key exchange protocol, symmetric encryption and signature scheme. We will emphasize the new concepts in our paper.\n\n**Q1: Experiment when server conducts an active inference attack**\n\nThanks for your question. In activate inference attack, the server would manipulate certain users' messages to obtain the private values of targeted users. In particular, the server may alter the secret shares user sents to others to infer their private value. We didn't include the experiment in our paper since **the integrity of the message is protected by the signiture scheme, and thus the server is prevented from forging the message of any user**. If the server changes the value of the encrypted message, then the signiture verification would indicate the other user that it's an invalid message. In Appendix C.4, we provide a security analysis for the signature scheme. For a UF-CMA secure signature scheme, no probabilistic polynomial time (PPT) adversary is able to produce a valid signature on an arbitrary message with more than negligible probability. \n\nWe added experiments for passive inference attack using the Deep Leakage from Gradients (DLG)[2]. DLG attempts to reconstruct the original image from the aggregated gradients. We conducted an attack on the CIFAR-10 dataset, using the specifications in Appendix L.2. The average PSNR of generated image with respect to original image is 11.27, much lower than the value of 36.5 when no secure aggregation is involved. We also upload an PDF in the global rebuttal section, presenting the original and inferred image under RFLPA. It can be observed that the inferred images are far from the raw images under DLG attack.\n\nWe will include the explicit analysis for both inference attacks in our paper.\n\n[1] Kate, A., Zaverucha, G. M., & Goldberg, I. (2010). Constant-size commitments to polynomials and their applications. In Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16 (pp. 177-194). Springer Berlin Heidelberg.\n\n[2] Zhu, L., Liu, Z., & Han, S. (2019). Deep leakage from gradients. Advances in neural information processing systems, 32.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CRg3xoM1f1", "reviewer": "Reviewer_aBFW", "summary": "The paper proposes a defense mechanism against poisoning attacks on federated learning while maintaining privacy guarantee. The solution is based on secure aggregation and evaluates the trustworthiness of client updates with cosine similarity. Information leakage during the computation of cosine similarity is mitigated by a novel aggregation method for dot products. Theoretical and empirical analysis show that the defense successfully reduces the communication and computation overhead and keeps a competitive accuracy compared to previous work.", "questions": "In section 4.2 normalization, should the gradients with norm smaller than $||g_0||$ also be normalized? If so, how to verify that they are normalized?", "limitations": "The paper has adequately addressed its limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The use of packed Shamir secret sharing with the proposed dot-product aggregation sounds novel and reliable.\n2. The security and efficiency of the framework is well supported by theoretical analysis and experiments.\n3. The framework largely reduces the overhead of previous works and maintains good accuracy even when no poisoning attack is considered, making deployment more practical.", "weaknesses": "1. The paper focuses on a specific type of federated learning setup. Its applicability to other federated learning models, such as those involving more dynamic and heterogeneous client populations, is not explored.\n2. The experiments conducted use standard datasets like MNIST, F-MNIST, and CIFAR-10. These datasets, while commonly used, do not fully represent the complexity and diversity of real-world data. The effectiveness of RFLPA in more diverse and complex datasets remains to be tested.\n3. The performance comparison against other state-of-the-art methods might not be exhaustive. There might be other emerging methods or variations of existing ones that were not considered in the evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer WU56, \n\nThank you for your recognition and valuable comments. Hope our response below could address your concern.\n\n**W1: Applicability to other federated learning models, such as those involving more dynamic and heterogeneous client populations**\n\nThanks for your comment. Our approach is also applicable in the federated learning setup involving dynamic and heterogeneous client populations. We would address the concern from two perspectives: the heterogeneous clients and dynamic change.\n\n- **Heterogenous clients**. The experiment result is already presented in Appendix L.8 Non-IID Setting, where each client holds a dataset biased towards a certain class. Compared with BREA and FedAvg, **RFLPA demonstrates resilient performance against poisoning attacks under the setting where clients hold heterogeneous dataset**. For 30% adversaries, the accuracy of RFLPA is over 0.89 and 0.79 on MNIST and F-MNIST dataset, respectively.\n\n- **Dynamic change**. For dynamic settings, we consider the case where the data of the clients change during the federated training with the arrival of new data. We added experiments for this case and will include the analysis in the appendix. To simulate such setting, we leverage Dirichlet Distribution Allocation (DDA)[1] to sample non-iid dataset, and change the distribution for each client every 20 epochs. Table R1 presents the accuracy under the gradient manipulation attack, demonstrating **RFLPA's robustness under the dynamic setting**. \n\n[**Table R1.** Accuracy under dynamic client data distribution against gradient manipulation attack.]\n| Proportions | of attackers |No|10%|20%|30%|\n| ---- | ----- | ---- |---- |---- |---- |\n|FedAvg|MNIST|0.98|0.26|0.29|0.30|\n||F-MNIST|0.86|0.52|0.21|0.18|\n|RFLPA|MNIST|0.96|0.94|0.92|0.90|\n||F-MNIST|0.83|0.79|0.79|0.77|\n\n**W2: The effectiveness of RFLPA in more diverse and complex datasets remains to be tested.**\n\nThanks for your comment. In Appendix L.6 Performance on Natural Language Processing (NLP) Dataset, we present the result under two NLP datasets, Recognizing Textual Entailment (RTE)[2] and Winograd NLI (WNLI)[3]. Table R2 highlights a portion of the results, and the full results can be found in Appendix L.6.\n\n[**Table R2.** Accuracies on NLP dataset against gradient manipulation attack.]\n|  |RTE| | | |WNLI| | | |\n| ---- | ----- |--|--|--|--|--|--|--|\n| Proportions of attackers|No|10%|20%|30%|No|10%|20%|30%|\n|FedAvg|0.599|0.509|0.487|0.462|0.619|0.563|0.437|0.437|\n|RFLPA|0.596|0.582|0.582|0.577|0.619|0.592|0.592|0.563|\n\nTo test a more complex CV dataset, we further added the experiments on Cifar-100 dataset using ResNet-9. The analysis of these experiments will be included in the appendix. Table R3 presents the accuracy under varying proportions of attackers performing gradient manipulation attacks.\n\n[**Table R3.** Accuracy on Cifar-100 dataset under gradient manipulation attack.]\n| Proportions of attackers |No|10%|20%|30%|\n| - | ----- | ---- |---- |---- |\n|FedAvg|0.55 | 0.11 |0.10|0.10|\n|RFLPA|0.55|0.54|0.50|0.49|\n\n**W3: The performance comparison against other state-of-the-art methods might not be exhaustive. There might be other emerging methods or variations of existing ones that were not considered in the evaluation.**\n\nThanks for your comment. We attempt to review the SoTA methods that achieve the goals of privacy protection as well as robustness against poisonous attacks as much as possible. We also discuss the advantages of RFLPA against additional frameworks in the response to reviewer VWie's W1-b. We would be pleased to make further comparisons if you provide additional baselines for us.\n\n**Q1: Should the gradients with norm smaller than $\\|g_0\\|$ also be normalized? If so, how to verify that they are normalized?**\n\nThat's an interesting question. In principle, the gradients with norm smaller than $\\|g_0\\|$ should also be normalized. However, the server could simply verify that $\\|\\bar{g}_i\\|\\leq \\|g_0\\|$ for the following reasons:\n\n- **A malicious user has no motivation to skip the normalization if $\\|g_i\\|<\\|g_0\\|$.** For benign users, they would honestly execute the protocol. For malicious user, skipping the normalization would reduce their trust score, and thus the weight on the aggregated gradients. Specifically, the trust score is a ReLU function of the dot product between the normalized local gradient and server model update. Therefore, a smaller scale of $\\|\\bar{g}_i\\|$ leads to lower level of trust score, thus reducing the malicious user's impact on the global model.\n\n- **The convergence bound in Theorem 5.2 is derived in the case where all gradients are smaller than $\\|g_0\\|$.** Even if it's un-normalized, we can still obtain the convergence bound in Theorem 5.2 because the derivation only requires that $\\|\\bar{g}_i\\|\\leq \\|g_0\\|$ for each $i$, rather than $\\|\\bar{g}_i\\|$ being close to $\\|g_0\\|$.\n\n[1] Luo, M., Chen, F., Hu, D., Zhang, Y., Liang, J., & Feng, J. (2021). No fear of heterogeneity: Classifier calibration for federated learning with non-iid data. Advances in Neural Information Processing Systems, 34, 5972-5984.\n\n[2] Bentivogli, L., Clark, P., Dagan, I., & Giampiccolo, D. (2009). The Fifth PASCAL Recognizing Textual Entailment Challenge. TAC, 7(8), 1.\n\n[3] Levesque, H., Davis, E., & Morgenstern, L. (2012, May). The winograd schema challenge. In Thirteenth international conference on the principles of knowledge representation and reasoning.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u0eswBD5q7", "reviewer": "Reviewer_VWie", "summary": "The paper proposes RFLPA, which deploys a robustness algorithm based on cosine similarity detection on SecAgg, defending against privacy attacks from the server and poisoning attacks from clients. Furthermore, the paper reduces communication and computation costs through packed Shamir secret sharing and dot-product aggregation.", "questions": "see the above", "limitations": "no", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.The structure of the paper is clear, providing a comprehensive and detailed explanation of how RFLPA deploys FLTrust's cosine similarity detection scheme on SecAgg and reduces SecAgg's overhead through packed Shamir secret sharing and dot-product aggregation.\n\n2.Experiments show that, compared to the previous work BREA, RFLPA reduces communication and computation costs by 75% while maintaining the same accuracy.\n\n3.The paper also provides a systematic theoretical analysis and proof of RFLPA's convergence and the cryptographic protocols used.", "weaknesses": "1. The paper seems to achieve practical improvements over BREA mainly by reducing communication costs, but the phase of computing cosine similarity among clients introduces additional communication costs. The advantages over other state-of-the-art MPC-based solution ELSA[1], HE & ZKP-based solution RoFL[2], and Blockchain-based solution PBFL[3] are not explained in detail in the paper.\n\n2. Regarding Byzantine robustness, the paper adopts the FLTrust approach, assuming the server holds clean root dataset. However, this requires a substantial number of clean public samples of all labels, making this assumption impractical in real-world scenarios, which is conflicted to  the goal of practical PPFL solution.\n\n3. The RFLPA framework seems like questionable.As descripted in section 3.2, the security goal is to defend passive inference and active inference attacks both. But the packed secret shares of $g_i$ generted by client i are sent to the server and the server transmit them to the other clients using a broadcast channel. Which means that the server have all shares of the secret $g_i$ and can recover it. So, what kind of role is played by the server?\n\n4. In the experimental section, a) the robustness testing of BREA only includes two types of Byzantine attacks. The paper lacks strong experiments to demonstrate how BREA performs under more subtle attacks like Krum-attack and Badnet. b) The communication overhead of RFLPA could not be small, because all clients are involved all computation of consin similarity $s^j_k$ of any user pair (i,j), the author should give out the detail results. \n\n6. The notations and formulations should be more clear.\n\na) Line95, $D$ is not predefined.\n\nb) Line210, $\\tilde{\\mathbf{g}}_i$ should be $\\bar{\\mathbf{g}_i}$. \n\n\n[1] Rathee, Mayank, et al. \"Elsa: Secure aggregation for federated learning with malicious actors.\" 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023.\n[2] Lycklama, Hidde, et al. \"Rofl: Robustness of secure federated learning.\" 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023.\n[3] Miao, Yinbin, et al. \"Privacy-preserving Byzantine-robust federated learning via blockchain systems.\" IEEE Transactions on Information Forensics and Security 17 (2022): 2848-2861.\n[4] Hao, Meng, et al. \"Efficient, private and robust federated learning.\" Proceedings of the 37th Annual Computer Security Applications Conference. 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer VWie, \n\nThanks for your time and valuable comments. Hope our response below could address your concern.\n\n**W1-a&W4-b: Additional communication cost of cosine similarity computation**\n\nThe additional communication cost introduced by cosine similarity computation is small compared to the communication overhead reduced by our approach. We utilize secret sharing (SS) instead of homomorphic encryption (HE) to compute the cosine similarity since: (1) Existing HE-based frameworks rely on the unrealistic assumption of 2 non-colluding parties. (2) According to Appendix L.7.1, the HE-based methods take massive computation time, which far outweights the communication time introduced by SS-based frameworks.\n\nWe leverage packed secret sharing to reduce the communication overhead. Appendix H presents the analysis of the overhead, and here we explain in more details: (1) For N users and M-dimensional gradients, we packed O(N) elements within a single polynomial. Then each user transmits O(max(M/N,1)\\*N)=O(M+N) (instead of O(MN)) elements. (2) By computing cosine similarity of other users, each user obtains O(N) partial dot products in total. (3) During dot product aggregation, each user secret shares the partial dot products. To reduce overhead, they pack O(N) elements within a single polynomial. Then each user communicates O(N\\*N/N)=O(N) elements. (4) The user locally computes final secret shares of the consine similarity and uploads them to the server. Since the final shares are secret shares of dot products by packing O(N) secret shares, each user only requires to send O(N/N)=O(1) elements to the server. **Benefiting from the packed secret share algorithm, the total per-user communication cost is reduced to O(M+N), a siginificant improvement over the O(MN + N) cost in BREA.**\n\n[**Table R1.** Break down of per-user communication cost. Cosine similarity computation incurred O(N) additional communication cost, lower than the original scale O(M+N).]\n|Stage|Communication cost|Incurred by cosine similarity computation|\n|-|-|-|\n|Download parameters|O(M)|No|\n|Secret share local gradient|O(M+N)|No|\n|Upload aggregated update|O(M/N+1)|No|\n|Sum (original)|O(M+N)|\n|Secret share partial dot product|O(N)|Yes|\n|Upload final share of dot product|O(1)|Yes|\n|Receive trust score|O(N)|Yes|\n|Sum (cosine similarity)|O(N)|\n\n**W1-b: Advantages over other solutions**\n\nThanks for your suggestion. We summarize the advantages of our method with in Table R2, with explanation as followed:\n- ELSA[1]: Firstly, ELSA relies on the vulnerable assumption of 2 non-colluding servers. Secondly, ELSA utilizes a naive and limited method to filter poisonous gradients, i.e., bounding the $l_2$ norm of each gradient. It's completely impractical to generalize their framework to more advance defense method such as Krum. In contrast, our framework is compatible with defense method such as FLTrust and Krum.\n- RoFL[2]: Similar to ELSA, RoFL is designed specifically for a naive robust aggragation method, norm bounding. Furthermore, RoFL relies on expensive zero-knowledge proofs. It's estimated to take 3.6 hours per round to train a 1.6M MNIST classifier, while for RFLPA it's within 10 minutes in the same setting.\n- PBFL[3]: We have explained the limitations of PBFL in appendix L.4 and L.7.1, in terms of the assumption of 2 non-colluding parties, and expensive computation cost.\n- SecureFL[4]: SecureFL also relies on the unrealistic assumption of two non-colluding parties. Additionally, it utilizes expensive MPC and HE methods. The computation time for training a 1.6M MNIST classifier is estimated to be 2.5 hours per round, much higher than that for RFLPA.\n\n[**Table R2.** Comparison of various solutions. More \\* implies higher level of computation overhead.]\n| |Collusion threshold|Robust Aggregation Rule|Computation Overhead|\n|-|-|-|-|\n|ELSA|1|Norm bound|\\*\\*|\n|RoFL|O(N)|Norm bound|\\*\\*\\*|\n|PBFL|1|FLTrust|\\*\\*\\*\\*|\n|SecureFL|1|FLTrust|\\*\\*\\*|\n|RFLPA|O(N)|FLTrust|\\*\\*|\n\n**W2: Assumption on clean public samples**\n\nThanks for your comment. Firstly, the required sample data is of small size, e.g., 200 samples. The gobal model is robust even when the root dataset diverges slightly from the overall training data distribution. Secondly, we have proposed some remedies in the absence of such dataset (see response to Q1 in global rebuttal), including comparison with global weights and KRUM. \n\n**W3: The server have all shares of the secret gi and can recover it**\n\nThanks for your comments. We have explained in Section 4.6 that **the secret shares are encrypted by the clients' secret key before sending to the server, and thus the server is ignorance of the values for secret shares given the IND-CPA of the encryption system**. Specifically, the clients establish the secret keys with each other through Diffie-Hellman key exchange protocol. During secret sharing, each client u uses the common key $k_{uv}$ to encrypt the message sent to client v, and client v could decrypt the cyphertext with the same key.\n\n**W4: Experiments on subtle attacks**\n\nThanks for your suggestion. In our response to Q2 in global rebuttal, we added experiments on the subtle attacks. The empirical results validate RFLPA's robustness against KRUM attack, BadNets, and scaling attacks.\n\n**W5**: Thanks for pointing out. We will address these issues.\n\n[1]Rathee, Mayank, et al. \"Elsa: Secure aggregation for federated learning with malicious actors.\" 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023. \n\n[2]Lycklama, Hidde, et al. \"Rofl: Robustness of secure federated learning.\" 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023. \n\n[3]Miao, Yinbin, et al. \"Privacy-preserving Byzantine-robust federated learning via blockchain systems.\" IEEE Transactions on Information Forensics and Security 17 (2022): 2848-2861. \n\n[4]Hao, Meng, et al. \"Efficient, private and robust federated learning.\" Proceedings of the 37th Annual Computer Security Applications Conference. 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers,

We want to express our profound gratitude for your insightful comments and valuable suggestions. We address some common questions in this global rebuttal section. 

**Q1: The paper relies on the assumption that the server has trusted root of clean datasets.**

Please note that the required clean root dataset in our approach is of small size, e.g., 200 samples. Suppose we cannot get any clean root dataset even if the required size is small, we propose several remedies:
- **Cosine similarity with global weights.** Existing studies show that global weights could be useful in detecting malicious updates[1]. We can compute the cosine similarity between each local update and the global weights as follows:
$$cos(W_i^t, W_G^{t-1})=\frac{<W_i^t, W_G^{t-1}>}{\|W_i^t\|_2\|W_G^{t-1}\|_2}$$
, and filter out the clients with similarity smaller than a pre-specified threshold. To validate the effectiveness of such approach, we conduct experiments against the Byzantine attack under various proportions of attacks. It can be observed in Table R1 that **compared with FedAvg, RFLPA-GW effectively improves the accuracy in the presence of attackers**. **The communication and computation cost of such an approach is at the same scale of RFLPA’s original level** as both compute the cosine similarity with a single baseline.

[**Table R1.** Accuracy for defense based on global weight under different proportions of attackers. RFLPA-GW replaces the robust aggregation rule in RFLPA with the method based on cosine similarity with global weight.]
| Proportions | of attackers |No|10%|20%|30%|
| ---- | ----- | ---- |---- |---- |---- |
|FedAvg|MNIST|0.98|0.46|0.40|0.32|
||F-MNIST|0.88|0.55|0.51|0.45|
|RFLPA-GW|MNIST|0.98|0.95|0.92|0.91|
||F-MNIST|0.90|0.80|0.77|0.75|

- **KRUM-based method.** We can substitute the aggregation module with KRUM when a trusted baseline is missing. Though KRUM incurs greater cost than the original method, we show in Appendix L.7.2 Ablation Study that **there’s a notable reduction in communication and computation cost compared with BREA**, benefiting from the design of our secret sharing algorithm (see Table 2 for a summary). **The accuracy of RFLPA (KRUM) is expected to be the same as BREA**, as both utilize the same aggregation rule.

[**Table R2.** Communication (in MB) and computation cost (in Minutes) with MNIST classifier (1.6 parameters).]
| | RFLPA | |BREA | |RFLPA-KRUM||
| ---| ----| ---- |---- |---- |---- |---- |
|client size|300|400|300|400|300|400|
|Communication cost|82.51|82.52|1909.02|2544.45|79.58|82.25|
|Computation: per-user cost|24.51|42.46|182.27|294.27|46.48|75.78|
|Computation: server cost|15.00|26.47|216.96|287.22|39.76|62.81|

- **Collection of slightly biased root data.** [2] has conducted experiments where the root data is biased towards a certain class. Empirical evidence presented in suggests that **the performance of the global model is robust even when the root dataset diverges slightly from the overall training data distribution**. Specifically, the accuracy of MNIST-0.5 is at least 0.92 when the bias probability is within 0.4. Note that for MNIST dataset, the bias probability ranges from 0.1 to 1, and a larger bias probability suggests a more imbalanced distribution of the root dataset.

We summarize the pros and cons of three robust aggregation modules in Table R3. We will add a discussion in the appendix.

[**Table R3.** Pros and cons of different aggregation modules.]
| Approach | Pros | Cons |
|-|-|-|
| RFLPA-FLTrust | Lower overhead | Collection of validation data |
|  | No need for prior knowledge about # of poisoners |  |
|  | Robust under slightly biased validation data |  |
| RFLPA-GW | Lower overhead | Lack of theoretical convergence guarantee |
|  | No need for prior knowledge about # of poisoners |  |
|  | No need for validation data |  |
| RFLPA-KRUM | No need for validation data | Higher overhead |
|  |  | Need prior knowledge about # of poisoners |

**Q2: Experiments on more stealthy attacks.**

We added experiments for more stealthy attacks: (1) KRUM attack (untargeted attack)[3], (2) BadNets (backdoor attack)[4], and (3) Scaling attack (backdoor attack)[5]. We will include the experiment results in the appendix.

Table R4 shows the results for the additional attacks on CIFAR-10. For backdoor attacks, the classification accuracy on the triggered dataset is shown in parentheses. Compared with FedAvg, RFLPA  not only improves the accuracy on the general dataset, but also the accuracy on the triggered dataset. 

[**Table R4.** Accuracies on CIFAR-10 under varying proportions of attackers. For backdoor attacks, the values are presented as *overall accuracy (backdoor accuracy)*.]
| Proportions | of attackers |10%|20%|30%|
|-|-|-|-|-|
|FedAvg|KRUM attack|0.27|0.12|0.11|
||BadNets|0.68 (0.54)|0.67 (0.54)|0.55 (0.28)|
||Scaling|0.70 (0.22)|0.68 (0.21)|0.54 (0.19)|
|RFLPA|KRUM attack|0.71|0.70|0.70|
||BadNets|0.71 (0.68)|0.70 (0.68)|0.69 (0.66)|
||Scaling|0.70 (0.69)|0.70 (0.69)|0.69 (0.69)|

[1] Yaldiz, D. N., Zhang, T., & Avestimehr, S. Secure Federated Learning against Model Poisoning Attacks via Client Filtering. In ICLR 2023 Workshop on Backdoor Attacks and Defenses in Machine Learning.

[2] Cao, X., Fang, M., Liu, J., & Gong, N. Z. (2021, January). FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping. In ISOC Network and Distributed System Security Symposium (NDSS).

[3] Fang, M., Cao, X., Jia, J., & Gong, N. (2020). Local model poisoning attacks to {Byzantine-Robust} federated learning. In 29th USENIX security symposium (USENIX Security 20) (pp. 1605-1622).

[4] Gu, T., Liu, K., Dolan-Gavitt, B., & Garg, S. (2019). Badnets: Evaluating backdooring attacks on deep neural networks. IEEE Access, 7, 47230-47244.

[5] Bagdasaryan, E., Veit, A., Hua, Y., Estrin, D., & Shmatikov, V. (2020, June). How to backdoor federated learning. In International conference on artificial intelligence and statistics (pp. 2938-2948). PMLR.

Meta-review: Existing defenses against poisoning attacks rely on analysis of local updates in plaintext, and thus are incompatible with the well-established security protocol SecAgg, which allows no knowledge of user updates by the server. To reconcile, FLTrust's cosine-similarity-based aggregation is employed on SecAgg. Verifiable packed Shamir secret sharing is used to reduce SecAgg's communication overhead, and the increased risk of privacy leakage with VPSSS is managed with a new dot-product aggregation algorithm. The idea of dot product aggregation is interesting and novel, but the primary advantage comes from the use of existing packed Shamir Secret Sharing. In this sense, the level of contribution is somewhat limited. More comprehensive analysis (provable security, computation overhead), realistic evaluation setups (non-IID settings using Dirichlet distribution, larger datasets like CIFAR-100, larger models, other common attacks like LIE, Min-Max and Min-Sum attacks) and comparison with existing work (like geometric median-based RFA [Pillutla 2022, IEEE Transactions on Signal Processing] which also does not require access to individual updates for defending against adversarial attacks while preserving privacy) would be desirable.
Decision: Accept (poster)