RFLPA: A Robust Federated Learning Framework against Poisoning Attacks with Secure Aggregation

Dear Reviewer VWie,

Thanks for your time and valuable comments. Hope our response below could address your concern.

W1-a&W4-b: Additional communication cost of cosine similarity computation

The 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.

We 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.

[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).]

W1-b: Advantages over other solutions

Thanks for your suggestion. We summarize the advantages of our method with in Table R2, with explanation as followed:

• 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.
• 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.
• 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.
• 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.

[Table R2. Comparison of various solutions. More * implies higher level of computation overhead.]

W2: Assumption on clean public samples

Thanks 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.

W3: The server have all shares of the secret gi and can recover it

Thanks 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.

W4: Experiments on subtle attacks

Thanks 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.

W5: Thanks for pointing out. We will address these issues.

[1]Rathee, Mayank, et al. "Elsa: Secure aggregation for federated learning with malicious actors." 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023.

[2]Lycklama, Hidde, et al. "Rofl: Robustness of secure federated learning." 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023.

[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.

[4]Hao, Meng, et al. "Efficient, private and robust federated learning." Proceedings of the 37th Annual Computer Security Applications Conference. 2021.

Dear Reviewer,

We are grateful for your constructive feedback. We are happy for your recongnition in the comprehensive and detailed explanation, effectiveness, and systematic theoretical analysis of our paper. Below we summarize the main concerns we addressed in the rebuttal:

Additional communication cost of cosine similarity computation: We provide detailed analysis for the communication cost in each stage. We show that the additional communication cost introduced by cosine similarity computation is small compared to the communication overhead reduced by our approach.

Advantages over other solutions: We summarize the advantage of our solution over the provided baseline in terms of three dimensions: collusion threshold, robust aggregation rule, and computation overhead.

Assumption on clean public samples: We clarify that the required clean root dataset could be of small size and slightly diversed from the from the overall training data distribution. We also propose several remedies suppose we cannot get any clean root dataset even if the required size is small.

The server have all shares of the secret and can recover it: We clarify that the secret shares are encrypted sending to the server and explain the encryption process.

Experiments on subtle attacks: We conduct additional experiments against KRUM attack, BadNets, and scaling attacks and will include the results in our paper.

Once more, we thank the Reviewer for the constructive feedback. We sincerely hope that the provided answers address the Reviewer's concerns and that the score can be reconsidered.

Best Regards,

Authors of Submission 11258

Considering the higher scores given by other reviewers, I reread the paper and the rebuttal, and still have serval big questions.

1. The algorithm part is hard to follow because the symbolic representation is confusing. Maybe you can clarify some cases of them here.

$\langle \mathbf{g_i} \rangle$ denotes the secret sharing of $\mathbf{g_i}$. So $\mathbf{V}^i=\{v_{jk}^i\}$ is also the secret sharing of $\mathbf{g_i}$? In the Algorithm 3 RobustSecAgg, $\{s_{ij} \}$ is the packed secrets of $\mathbf{g_i}$, and $\{v_{ij} \}$ is the witness.

And again,$cs_k^j$ denotes the $j^{th}$ share of the cosine similarity between $\mathbf{g_k}$ with $\mathbf{g_0}$? Here $k$ denotes the index of clients, and then in the next part “Step 1: Secret resharing of partial dot product”, $s_{jk}^i$ denotes the share sent to user $j$ for the $k^{th}$ group of elements. Here ,$k$ denote the index of group of elements. Maybe fixing the notations can help the readers.

And another, $\ell$ is the number of elements packed into one polynomial, also in the “Step 1: Secret resharing of partial dot product”, $p$ is used for the number of secrets packed.

It's very hard to follow your algorithm for me.

2. Efficiency of RFLPA .

The design goals include efficiency that mainly is achieved by packed secret sharing. But As we can see, the clients are burdened with a large number of computational tasks. That includes secret sharing, encryption and decryption of shares, addition, scale multiply and multiply on packed secret sharing. IMPORTANT: The multiply on packed secret sharing will generate a degree-$(d_1+d_2) or (2d)$ results and more operations need to be done to keep a degree-$d$ style. That is the main source of communication cost for MPC operation and this paper didn't discuss it.

You mentioned “ELSA and PBFL and SecureFL rely on the unrealistic assumption of two non-colluding parties”, RFLPA just put those computation tasks on the clients, maybe that is more unfriendly for the clients (mobile or other edge devices). Existed works can be extended to multi-parties using shamir secret sharing.

And this paper didn’t conduct experimental comparison under WAN/LAN setting. 4 round communications per iteration (that did not include the communication incurred by multiply on packed secret sharing also), that would a huge burden for WAN.

About Q2-c: Adaption to heterogeneous computation power of each client is a good idea. But I must point out that selecting clients with more computation power by the server will increase the risk of collusion attack among the server and the clients. If we consider that the server could collude with some clients, the privacy goal of RFLPA will be failed.

About Q2-d: Communication round is a very important factor under WAN setting that you shouldn't ignore. For example, if you have 1000 rounds communication, and the latency will increase 1000*100ms(assume the latency will be 100ms for WAN and ignored for LAN) = 100s, that is also the main cost for the secret sharing-based solutions compare with those based on HE(heavy computation) or Garbled Circuit (heavy communication bytes).

You mentioned that "many existing SecAgg algorithms (focusing only on privacy protection) also rely on multiple communication rounds"[1][2]. Those works use Diffie-Hellman for key negotiation, and their multiple rounds of communication occured in offline phase.

Dear Reviewer VWie,

Thank you for your reply and time. Hope our response below could address your additional concern.

Reply to Q2-a:

Firstly, the encryption and decryption is based on symmetric encryption, much more efficient than the assymetric encryption in HE-based protocol. During our experiment, we found that the encryption & decryption time on the secret is much smaller than the time for other operations on the secret shares, including secret sharing and reconstruction.

Furthermore, even if in the BREA's p2p channel, the symmetric encryption on the secret shares is neccessary to avoid the ear dropper's inference attack. However, their solution omit this encryption & decryption process, posing the user's private value in great risk. The encryption is indispensable for secure communication.

Reply Q2-b:

The dot product aggregation protocol shares some relation to the degree reduction protocol in terms of secret resharing. The degree reduction is included in (3) sending and receiving secret shares of partial gradient norm square and cosine similarity (O(N) messages).

We are pleased that the reviewer recognize the value and contribution of our packed secret sharing with dot product aggregation protocol. The major purpose of dot product aggregation is to address the issue of increased privacy leakage, and we believe that this benefit (in terms of privacy) has been clearly understood and recognized by the readers and reviewers. The degree reduction can be treated as the side benefit (though not the major purpose), and we will highlight this point in our paper.

Reply to Q2-c:

We understand that the inherent tradeoff between the number of participating clients and collusion threshold. At the same time, we would like to make it clear that:

• Even if we select a proportion of clients, the privacy risk is much lower than the case in HE's 2 non-colluding parties.

• Even if we use the whole set of clients, each client's computation cost is significantly lower than the protocol proposed by BREA with $O(n)$ threshold.

• In cross-silo setting, the clients typically host stronger computing power (such as server), and thus there's few need to consider the client selection. In cross-device setting, the heterogeneous issue arises, but typically this setting consists of a large number of clients, and thus select a proportion of them could maintain a certain level of protection.

Reply to Q2-d

We would like to highlight that:

• The reduced message size from RFLPA compared with BREA is much larger than the extra latency in WAN setting, as is deomstrated in our previous reply.

• The extra latency in more communication rounds is negligible compared with the reduced computation time from RFLPA compared with HE-based methods. As is shown by Appendix L.7.1 and our initial rebuttal, the computation time for RFLPA is hours fewer than the HE-based methods for even a single iteration. Therefore, the total communication latency (100s) is much smaller.

Furthermore, the communication rounds in SecAgg [1][2] is 4 for each iteration. The reviewer can refer to their algorithm for further description.

About Q2-a: Secret sharing-based operations cost the network resources, the encryption and decryption of shares consume the computation resource, that cannot be treated as same. So RFLPA replaces the p2p channel between clients assumed in BERA by using the sever as a repeater(or forwarder) with encryption of the shares. So the encryption/decryption cost will be introduced to the clients.

About Q2-b: I guess that you use a method like the degree-reduction technology in shamir secret sharing? Every $p$ elements in $cs^i$ is reshared as a degree-d polynomial. So the communication cost is genereated by the resharing operation. Maybe that has been included in " (3) sending and receiving secret shares of partial gradient norm square and cosine similarity (O(N) messages)"?

So using a packed secret sharing with the partial dot product is the core contribution of this paper, and I encourage the authors to improve the representation of the key part. It's not very clear for me, and it's important to understand your work for the researchers in MPC/PPML.

Dear Reviewer WU56,

Thank you for your recognition and valuable comments. Hope our response below could address your concern.

W1: Applicability to other federated learning models, such as those involving more dynamic and heterogeneous client populations

Thanks 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.

• 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.

• 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.

[Table R1. Accuracy under dynamic client data distribution against gradient manipulation attack.]

W2: The effectiveness of RFLPA in more diverse and complex datasets remains to be tested.

Thanks 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.

[Table R2. Accuracies on NLP dataset against gradient manipulation attack.]

To 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.

[Table R3. Accuracy on Cifar-100 dataset under gradient manipulation attack.]

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.

Thanks 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.

Q1: Should the gradients with norm smaller than $\|g_0\|$ also be normalized? If so, how to verify that they are normalized?

That'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:

• 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.

• 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\|$.

[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.

[2] Bentivogli, L., Clark, P., Dagan, I., & Giampiccolo, D. (2009). The Fifth PASCAL Recognizing Textual Entailment Challenge. TAC, 7(8), 1.

[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.

Dear Reviewer WU56,

Thank you for your recognition and valuable comments. Hope our response below could address your concern.

W1 & Q2: Assumption on clean public samples

Thanks 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.

W2: Distinguish between new and existing concept

Thanks for your suggestion. We clarify the distinctions as followed.

The 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.

The 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.

Q1: Experiment when server conducts an active inference attack

Thanks 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.

We 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.

We will include the explicit analysis for both inference attacks in our paper.

[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.

[2] Zhu, L., Liu, Z., & Han, S. (2019). Deep leakage from gradients. Advances in neural information processing systems, 32.

Dear Reviewer WU56,

Thank you for your recognition and valuable comments. Hope our response below could address your concern.

W1 & Q4: Assumption that the server has a clean root dataset and that secure communication can be maintained without significant overheads

Thanks for your comment.

For 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.

For 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.

W2: The code was not revealed

Thanks for your comment. We have sent the code in anonymized link to AC.

W3: Evaluation of backdoor attacks

Thanks 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.

Q1: Insights into the practical implementation challenges of integrating verifiable packed Shamir secret sharing into existing FL systems?

Thanks 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.

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?

Thanks 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.

[Table R1. Complexity summary of RFLPA for N clients and M dimensional model.]

The 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.

[Table R2. Per client overhead of RFLPA using a MNIST classifier (1.6M).]

In 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.

For 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.

Q3: Could the authors elaborate on the potential vulnerabilities in the cryptographic mechanisms used and how they are mitigated?

Diffie-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.

Symmetric 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.