Federated learning was introduced to enable machine learning over large decentralized datasets while promising privacy by eliminating the need for data sharing. Despite this, prior work has shown that shared gradients often contain private information and attackers can gain knowledge either through malicious modification of the architecture and parameters or by using optimization to approximate user data from the shared gradients.However, prior data reconstruction attacks have been limited in setting and scale, as most works target FedSGD and limit the attack to single-client gradients. Many of these attacks fail in the more practical setting of FedAVG or if updates are aggregated together using secure aggregation. Data reconstruction becomes significantly more difficult, resulting in limited attack scale and/or decreased reconstruction quality. When both FedAVG and secure aggregation are used, there is no current method that is able to attack multiple clients concurrently in a federated learning setting.In this work we introduce Loki, an attack that overcomes previous limitations and also breaks the anonymity of aggregation as the leaked data is identifiable and directly tied back to the clients they come from. Our design sends clients customized convolutional parameters, and the weight gradients of data points between clients remain separate even through aggregation. With FedAVG and aggregation across 100 clients, prior work can leak less than 1% of images on MNIST, CIFAR-100, and Tiny ImageNet. Using only a single training round, Loki is able to leak 76-86% of all data samples.

Secure aggregation promises a heightened level of privacy in federated learning, maintaining that a server only has access to a decrypted aggregate update. Within this setting, linear layer leakage methods are the only data reconstruction attacks able to scale and achieve a high leakage rate regardless of the number of clients or batch size. This is done through increasing the size of an injected fully-connected (FC) layer. However, this results in a resource overhead which grows larger with an increasing number of clients. We show that this resource overhead is caused by an incorrect perspective in all prior work that treats an attack on an aggregate update in the same way as an individual update with a larger batch size. Instead, by attacking the update from the perspective that aggregation is combining multiple individual updates, this allows the application of sparsity to alleviate resource overhead. We show that the use of sparsity can decrease the model size overhead by over 327x and the computation time by 3.34x compared to SOTA while maintaining equivalent total leakage rate, 77% even with 1000 clients in aggregation.

Federated learning (FL) has attracted growing interest for enabling privacy-preserving machine learning on data stored at multiple users while avoiding moving the data off-device. However, while data never leaves users’ devices, privacy still cannot be guaranteed since significant computations on users’ training data are shared in the form of trained local models. These local models have recently been shown to pose a substantial privacy threat through different privacy attacks such as model inversion attacks. As a remedy, Secure Aggregation (SA) has been developed as a framework to preserve privacy in FL, by guaranteeing the server can only learn the global aggregated model update but not the individual model updates.While SA ensures no additional information is leaked about the individual model update beyond the aggregated model update, there are no formal guarantees on how much privacy FL with SA can actually offer; as information about the individual dataset can still potentially leak through the aggregated model computed at the server. In this work, we perform a first analysis of the formal privacy guarantees for FL with SA. Specifically, we use Mutual Information (MI) as a quantification metric and derive upper bounds on how much information about each user's dataset can leak through the aggregated model update. When using the FedSGD aggregation algorithm, our theoretical bounds show that the amount of privacy leakage reduces linearly with the number of users participating in FL with SA. To validate our theoretical bounds, we use an MI Neural Estimator to empirically evaluate the privacy leakage under different FL setups on both the MNIST and CIFAR10 datasets. Our experiments verify our theoretical bounds for FedSGD, which show a reduction in privacy leakage as the number of users and local batch size grow, and an increase in privacy leakage as the number of training rounds increases. We also observe similar dependencies for the FedAvg and FedProx protocol.

Private set intersection (PSI) is a popular protocol that allows multiple parties to evaluate the intersection of their sets without revealing them to each other. PSI has numerous practical applications, including privacy preserving data mining and location-based services. In this work, we develop a new approach for the PSI problem within the federated analytics framework. In particular, we consider a setting where a server wants to determine (query) which among its local set of data identifiers appears coupled with the same value in at least K of the N parties. Applications for this framework include but are not limited to: double-filing insurance verification, credit scoring and password checkup on an institutional level. To address the proposed setting, we propose a new protocol Fed-K-PSI that allows the server to answer this query while being oblivious to the data of identifiers that do not satisfy the distributed query at the parties. In addition, Fed-K-PSI also maintains the anonymity of the parties by hiding which K parties satisfied the query, or which value associated with the identifier which caused the query to be successful. Our proposed setting does not lend itself directly to state-of-the-art approaches in PSI based on Oblivious Transfer, since the server does not have a complete representation of a datapoint (only the identifier, but no value). Our proposed approach tackles this problem by constructing a distributed function at the parties, which encodes the datapoints and returns a deterministic known property if and only if the value for a given identifier is the same in at least K of the N parties. We show that Fed-K-PSI achieves a strong information-theoretic privacy guarantee and is resilient to collusion scenarios among honest-but-curious parties. We also evaluate Fed-K-PSI via extensive experiments to study the effect of the different system parameters.

Decentralized (i.e., serverless) training across edge nodes can suffer substantially from potential Byzantine nodes that can degrade the training performance. However, detection and mitigation of Byzantine behaviors in a decentralized learning setting is a daunting task, especially when the data distribution at the users is heterogeneous. As our main contribution, we proposeBasil, a fast and computationally efficient Byzantine-robust algorithm for decentralized training systems, which leverages a novel sequential, memory-assisted and performance-based criteria for training over a logical ring while filtering the Byzantine users. In the IID dataset setting, we provide the theoretical convergence guarantees ofBasil, demonstrating its linear convergence rate. Furthermore, for the IID setting, we experimentally demonstrate thatBasilis robust to various Byzantine attacks, including the strong Hidden attack, while providing up to absolute ~16% higher test accuracy over the state-of-the-art Byzantine-resilient decentralized learning approach. Additionally, we generalizeBasilto the non-IID setting by proposing Anonymous Cyclic Data Sharing (ACDS), a technique that allows each node to anonymously share a random fraction of its local non-sensitive dataset (e.g., landmarks images) with all other nodes. Finally, to reduce the overall latency ofBasilresulting from its sequential implementation over the logical ring, we proposeBasil+that enables Byzantine-robust parallel training across groups of logical rings, and at the same time, it retains the performance gains ofBasildue to sequential training within each group. Furthermore, we experimentally demonstrate the scalability gains ofBasil+through different sets of experiments.

Secure model aggregation across many users is a key component of federated learning systems. The state-of-the-art protocols for secure model aggregation, which are based on additive masking, require all users to quantize their model updates to the same level of quantization. This severely degrades their performance due to lack of adaptation to available communication resources, e.g., bandwidth, at different users. As the main contribution of our paper, we proposeHeteroSAg, a scheme that allows secure model aggregation while using heterogeneous quantization. HeteroSAg enables the edge users to adjust their quantization proportional to their available communication resources, which can provide a substantially better trade-off between the accuracy of training and the communication time. Our proposed scheme is based on a grouping strategy by partitioning the network into groups, and partitioning the local model updates of users into segments. Instead of applying aggregation protocol to the entire local model update vector, it is applied on segments with specific coordination between users. We further demonstrate how HeteroSAg can enable Byzantine robustness while achieving secure aggregation simultaneously. Finally, we prove the convergence guarantees of HeteroSAg under heterogeneous quantization in the non-Byzantine scenario.

Communication overhead is one of the major performance bottlenecks in large-scale distributed computing systems, in particular for machine learning applications. Conventionally, compression techniques are used to reduce the load of communication by combining intermediate results of the same computation task as much as possible. Recently, via the development of coded distributed computing (CDC), it has been shown that it is possible to enable coding opportunities across intermediate results of different computation tasks to further reduce the communication load. We propose a new scheme, named compressed coded distributed computing (in short, compressed CDC), which jointly exploits the above two techniques (i.e., combining the intermediate results of the same computation and coding across the intermediate results of different computations) to significantly reduce the communication load for computations with linear aggregation (reduction) of intermediate results in the final stage that are prevalent in machine learning (e.g., distributed training algorithms where partial gradients are computed distributedly and then averaged in the final stage). In particular, compressed CDC first compresses/combines several intermediate results for a single computation, and then utilizes multiple such combined packets to create a coded multicast packet that is simultaneously useful for multiple computations. We characterize the achievable communication load of compressed CDC and show that it substantially outperforms both combining methods and CDC scheme. Based on the compressed CDC technique, we then study a distributed training problem as one of its application. We characterize the communication load for this distributed training problem and show that it is asymptotically optimal.

Centralized coded caching and delivery is studied for a radio access combination network (RACN), whereby a set of H edge nodes (ENs), connected to a cloud server via orthogonal fronthaul links with limited capacity, serve a total of K user equipments (TIEs) over wireless links. The cloud server is assumed to hold a library of N files, each of size F bits; and each user, equipped with a cache of size μRN F bits, is connected to a distinct set of r ENs each of which equipped with a cache of size μTN F bits, where μT, μR∈ [0, 1] are the fractional cache capacities of the TIEs and the ENs, respectively. The objective is to minimize the normalized delivery time (NDT), which refers to the worst case delivery latency when each user requests a single distinct file from the library. Three coded caching and transmission schemes are considered, namely the MDSIA, soft-transfer and zero-forcing (ZF) schemes. MDS-IA utilizes maximum distance separable (MDS) codes in the placement phase and real interference alignment (IA) in the delivery phase. The achievable NDT for this scheme is presented for r = 2 and arbitrary fractional cache sizes μTand μR, and also for arbitrary value of r and fractional cache size μTwhen the cache capacity of the TIE is above a certain threshold. The soft-transfer scheme utilizes soft-transfer of coded symbols to ENs that implement ZF over the edge links. The achievable NDT for this scheme is presented for arbitrary r and arbitrary fractional cache sizes μTand μR. The last scheme utilizes ZF between the ENs and the TIEs without the participation of the cloud server in the delivery phase. The achievable NDT for this scheme is presented for an arbitrary value of r when the total cache size at a pair of TIE and EN is sufficient to store the whole library, i.e., μT+μR≥ 1. The results indicate that the fronthaul capacity determines which scheme achieves a better performance in terms of the NDT, and the soft-transfer scheme becomes favorable as the fronthaul capacity increases.

In this paper, we characterize the degrees of freedom (DoF) region of a MIMO device-relaying cellular network (DRCN) with three users and one base station (BS), where each user exchanges unicast messages with the BS. We assume that one of the users has no direct link to the BS, and hence, device-relaying is utilized to exchange data between this user and the BS, i.e., data is relayed via another user which has a direct link to the BS and a device to device (D2D) link to this user. We assume that each node operates in perfect full-duplex mode. Cut-set and genie-aided bounds are utilized to derive an outer bound on the DoF region. We provide achievability schemes that utilize signal space alignment for network coding, null-space beamforming and zero-forcing. The achievable schemes provide an inner bound on the DoF region that coincides with the outer bound.

Centralized coded caching and delivery is studied for a partially-connected fog radio access network (F-RAN), whereby a set of H edge nodes (ENs) (without caches), connected to a cloud server via orthogonal fronthaul links, serve K users over the wireless edge. The cloud server is assumed to hold a library of N files, each of size F bits; and each user, equipped with a cache of size MF bits, is connected to a distinct set of r ENs; or equivalently, the wireless edge from the ENs to the users is modeled as a partial interference channel. The objective is to minimize the normalized delivery time (NDT), which refers to the worst case delivery latency, when each user requests a single file from the library. An achievable coded caching and transmission scheme is proposed, which utilizes maximum distance separable (MDS) codes in the placement phase, and real interference alignment (IA) in the delivery phase, and its achievable NDT is presented for r = 2 and arbitrary cache size M, and also for arbitrary values of r when the cache capacity is sufficiently large.