Byzantine-robust Federated Learning (FL) aims to counter malicious clients and train an accurate global model while maintaining an extremely low attack success rate. Most existing systems, however, are only robust when most of the clients are honest. FLTrust (NDSS '21) and Zeno++ (ICML '20) do not make such an honest majority assumption but can only be applied to scenarios where the server is provided with an auxiliary dataset used to filter malicious updates. FLAME (USENIX '22) and EIFFeL (CCS '22) maintain the semi-honest majority assumption to guarantee robustness and the confidentiality of updates. It is therefore currently impossible to ensure Byzantine robustness and confidentiality of updates without assuming a semi-honest majority. To tackle this problem, we propose a novel Byzantine-robust and privacy-preserving FL system, called MUDGUARD, to capture malicious minority and majority for server and client sides, respectively. Our experimental results demonstrate that the accuracy of MUDGUARD is practically close to the FL baseline using FedAvg without attacks (approximate 0.8% gap on average). Meanwhile, the attack success rate is around 0%-5% even under an adaptive attack tailored to MUDGUARD. We further optimize our design by using binary secret sharing and polynomial transformation leading to communication overhead and runtime decreases of 67%-89.17% and 66.05%-68.75%, respectively.

Gordon et al. (TCC 2015) systematically studied the security of Multi-client Verifiable Computation (MVC), in which a set of computationally-weak clients outsource the computation of a general function f over their private inputs to an untrusted server. They introduced the universally composable (UC) security of MVC and proposed a scheme achieving UC-security, where the protocol remains secure after arbitrarily composed with other UC-secure instances. However, the clients in their scheme have to undertake the heavy computation overhead caused by fully homomorphic encryption (FHE) and further, the plaintext size is linear to the function input size. In this work, we propose a more efficient UC-secure multi-client privacy-preserving verifiable computation protocol, called MVOC, that sharply reduces amortized overheads for clients, in both semi-honest and malicious settings. In particular, our protocol achieves stronger outsourcability by outsourcing more computation to the server, so that it may be more friendly to those lightweight clients. More specifically, we revisit the definition of garbling scheme, and propose a novel garbled circuit protocol whose circuit randomness is non-interactively provided by multiple parties. We also realize the idea of hybrid homomorphic encryption, which makes the FHE plaintext size independent of the input size. We present the detailed proof and analyze the theoretical complexity of MVOC. We further implement our protocol and evaluate the performance, and the results show that, after adopting our new techniques, the computation and communication overheads during input phase can be decreased by 55.15%–68.05% and 62.55%–75% respectively.