PaperlayerView exact revision on arXiv

Source-linked AI summary

Byzantine-Resilient Secure Federated Learning

Jinhyun So, Basak Guler, A. Salman Avestimehr

arXiv:2007.11115v2cs.CRcs.DCcs.LGstat.ML

TL;DR

Secure federated learning must protect local updates while still detecting Byzantine manipulation. BREA combines stochastic quantization, verifiable outlier detection, and secure aggregation in a single-server framework; experiments show convergence with Byzantine users and accuracy comparable to federated averaging.

  • Problem

    Masked local updates prevent the server from comparing individual models, creating a challenge for simultaneously preserving privacy and resisting Byzantine adversaries.

  • Method

    BREA combines stochastic quantization, verifiable secret sharing, secure outlier detection, and secure aggregation in a single-server federated-learning framework.

  • Results

    BREA converges with Byzantine users and has convergence rate and test accuracy comparable to federated averaging, while incurring quantization loss for privacy.

  • Takeaways & Limitations

    The framework provides theoretical convergence, robustness, privacy, dropout tolerance, and performance trade-off guarantees for Byzantine-resilient secure aggregation.

Abstract

from arXiv · show

Secure federated learning is a privacy-preserving framework to improve machine learning models by training over large volumes of data collected by mobile users. This is achieved through an iterative process where, at each iteration, users update a global model using their local datasets. Each user then masks its local model via random keys, and the masked models are aggregated at a central server to compute the global model for the next iteration. As the local models are protected by random masks, the server cannot observe their true values. This presents a major challenge for the resilience of the model against adversarial (Byzantine) users, who can manipulate the global model by modifying their local models or datasets. Towards addressing this challenge, this paper presents the first single-server Byzantine-resilient secure aggregation framework (BREA) for secure federated learning. BREA is based on an integrated stochastic quantization, verifiable outlier detection, and secure model aggregation approach to guarantee Byzantine-resilience, privacy, and convergence simultaneously. We provide theoretical convergence and privacy guarantees and characterize the fundamental trade-offs in terms of the network size, user dropouts, and privacy protection. Our experiments demonstrate convergence in the presence of Byzantine users, and comparable accuracy to conventional federated learning benchmarks.

I. INTRODUCTION

Federated learning must reconcile Byzantine resilience, which requires comparing individual updates, with privacy-preserving secure aggregation, which masks them from the server. BREA addresses this conflict in a single-server framework using quantization, verifiable checks, secure outlier detection, and aggregation, with theoretical and experimental support.

  • Federated learning iteratively has mobile users update a server-maintained global model from local data, after which the server aggregates their updates.
  • Secure aggregation masks each local update with additive secret sharing and pairwise random keys, allowing the server to learn only the aggregate.
  • Byzantine resilience requires comparing individual updates and removing outliers, but masking prevents the server from observing the values needed for that comparison.
  • BREA is the first single-server Byzantine-resilient secure aggregation framework, using stochastic quantization, verifiable secret sharing, secure distance computations, and distance-based outlier removal.
  • BREA theoretically guarantees convergence, Byzantine robustness, dropout tolerance, and local-update privacy under N≥2A+1+max{m+2,D+2T}.
  • With N=40 users and up to A=12 Byzantine users, BREA converges at a rate comparable to federated averaging and achieves comparable test accuracy despite quantization loss.
  • The convergence analysis assumes i.i.d. data, while distance-based outlier removal makes non-i.i.d. variation difficult to distinguish from Byzantine attacks.
  • Secure aggregation traditionally uses additive masking and secret-shared keys to handle user dropouts, but Byzantine-resilient secure aggregation introduces substantial communication and computation overhead.

IV. PROBLEM FORMULATION

The problem formulation requires secure aggregation to protect individual updates while remaining robust to Byzantine users, dropouts, and privacy threats. BREA frames these requirements around robustness, privacy, and dropout tolerance.

  • BREA considers a single-server network where Byzantine users may modify local datasets or share false information during protocol execution.
  • Robustness against Byzantine users: The protocol must remain robust against up to A Byzantine users who manipulate local data or exchanged protocol information.
  • Privacy of local updates: Individual local updates should remain private from the server and collusions among up to T users.
  • Tolerance to user dropouts: Privacy and convergence guarantees should hold even when up to D users drop out or are delayed during execution.
  • BREA is presented as a single-server Byzantine-resilient secure aggregation framework with stochastic quantization and verifiable secret sharing of user models.

V. THE BREA FRAMEWORK

BREA combines finite-field stochastic quantization with verifiable secret sharing to keep user models private and shares consistent. The framework uses these mechanisms to support secure Byzantine-resilient aggregation.

  • A. Stochastic Quantization: BREA quantizes real-valued local updates into a finite field so verifiable secret sharing and secure computations can be performed.The field size is assumed large enough to avoid wrap-around during secure distance computation and model aggregation.
  • A. Stochastic Quantization: Stochastic quantization uses unbiased rounding, with variance decreasing as the number q of quantization levels increases.The rounding function satisfies E_Q[Q_q(x)] = x.
  • A. Stochastic Quantization: A mapping function represents negative integers in the finite field using two’s complement representation.
  • B. Verifiable Secret Sharing: Verifiable secret sharing keeps individual user models private while helping prevent invalid secret shares from Byzantine users.The framework leverages Feldman’s verifiable secret sharing, combining Shamir’s secret sharing with homomorphic encryption.
  • B. Verifiable Secret Sharing: Users create secret shares and broadcast commitments that allow other users to verify whether the shares were constructed correctly.Under the stated discrete-logarithm intractability assumption, the server and users cannot recover the quantized model from the commitments.

C. Secure Distance Computation

BREA computes pairwise distances over secret shares rather than exposing model parameters. These distances support outlier removal while preserving the privacy of the underlying updates.

  • Distance-based outlier removal addresses malicious users who submit correctly formed shares corresponding to false local updates.
  • Users locally compute pairwise distances between other users’ secret-shared model parameters and send the scalar results to the server.Because the computations use secret shares, the computing user learns no information about the true model parameters.

D. User Selection at the Server

The server reconstructs pairwise distances despite dropped or malicious computations, then selects users through distance-based outlier removal for final aggregation. Reed–Solomon decoding handles erasures and errors in the reported computations.

  • C. Secure Distance Computation: Reed–Solomon decoding reconstructs pairwise distances from computation results containing up to D erasures and up to A errors.Dropped users correspond to erasures, while manipulated computations from Byzantine users correspond to errors.
  • C. Secure Distance Computation: The server obtains true pairwise distances from the decoded polynomial and converts them from the finite field to the real domain.The field size is assumed large enough to ensure correct distance recovery.
  • D. User Selection at the Server: BREA uses a distance-based outlier removal procedure following the multi-Krum algorithm to select models for aggregation.The procedure operates on quantized stochastic gradients rather than true gradients.
  • D. User Selection at the Server: The server iteratively selects m users using scores based on distances to users whose models are closest to each candidate.After m iterations, the selected set is S = S(m).

E. Secure Model Aggregation

BREA securely aggregates selected local models without revealing individual updates to the server. Reed-Solomon decoding recovers aggregates despite dropouts and Byzantine errors, after which the server updates the global model.

  • Secure aggregation: BREA aggregates secret shares from selected users so the server learns only the aggregate, not individual local models.The server broadcasts the selected set, users locally aggregate the corresponding shares, and the resulting computation is sent for decoding.
  • Robust decoding: Reed-Solomon decoding treats dropped-user computations as erasures and Byzantine manipulations as errors.The server decodes an [N,T+1,N−T] Reed-Solomon code with at most D erasures and A errors.
  • Robust decoding: The server recovers the true aggregate of selected user models from the decoded polynomial using h(0).The selected set must contain sufficiently many users; if it is too small, honest users may decline to send computation results.
  • Global update: After obtaining the aggregate, the server updates the global model for the next iteration.
  • Representation: The finite-field computation uses a demapping function, integer parameter q, and stochastic rounding function Q_q.The field size p is assumed large enough to avoid wrap-around.

VI. THEORETICAL ANALYSIS

The theoretical analysis establishes conditions under which BREA remains Byzantine-resilient, converges, and preserves local-update privacy. These guarantees depend on quantization error, adversary and dropout counts, network size, and assumptions on the objective and learning rates.

  • Quantized estimation: BREA’s quantized gradient estimator is unbiased and has bounded variance under stochastic rounding.Its variance includes both the local gradient-estimation variance and a quantization term.
  • Robustness: BREA is Byzantine-resilient when quantization and sampling deviation is sufficiently smaller than the true gradient norm and 2A+2 < N−m.The resilience angle depends on the ratio between standard deviation and gradient norm.
  • Robustness: The protocol executes correctly against up to A Byzantine users, and the trained model is (α,A)-Byzantine resilient.
  • Convergence: Under the stated smoothness, learning-rate, moment, noise, and gradient conditions, BREA’s gradients converge almost surely to zero.The proof derives convergence from the Byzantine resilience of the quantized multi-Krum aggregation function.
  • Privacy: The server or any group of up to T users cannot compute an unknown local update.The privacy guarantee is stated for views received by any user set of size at most T.
  • Performance limits: A sufficient network-size condition is N ≥ 2A+1+max{m+2,D+2T}, where m is the number of selected models.Separate decoding conditions include N ≥ D+2A+2T+1 and N ≥ D+2A+T+1.
  • Scope: The convergence result concerns gradients approaching a flat region, which may be a local minimum, saddle point, or extremal point.The objective may be non-convex, so the analysis does not establish convergence of the model itself to a minimum.

A. Complexity Analysis

BREA’s baseline protocol incurs cubic server communication and computation costs because it recovers all pairwise distances. This overhead motivates a generalized framework that reduces both costs for larger networks.

  • User complexity: Each user’s computation costs O(dNlog2 N), O(dN^2), and O(dN) for sharing, pairwise distances, and selected-model aggregation, respectively.The pairwise-distance calculation is the dominant user-side term when selected users scale as O(N).
  • User complexity: Each user communicates O(dN + N^2), combining secret-share transmission, distance-share transmission, and aggregate-model transmission.The three components contribute O(dN), O(N^2), and O(d), respectively.
  • Server complexity: Recovering all pairwise distances gives the server computation cost O(N^3 log2 N log log N).There are O(N^2) Reed-Solomon decoding operations, each costing O(N log2 N log log N).
  • Server complexity: The server’s communication cost is O(dN + N^3), dominated by receiving secret shares of O(N^2) pairwise distances.The aggregate model contributes O(dN), while distance-related communication contributes O(N^3).
  • Scaling limitation: For very large networks, the server’s O(N^3) communication and computation overhead can become a limitation.The paper proposes a generalized framework to reduce these costs to quadratic order.

B. The Generalized BREA Framework

The generalized BREA framework batches pairwise distances into polynomials before secure transmission and decoding. Setting K = O(N) reduces communication and computation from cubic to quadratic order.

  • Distance batching: The framework partitions the N(N−1)/2 pairwise distances into groups of size K and embeds each group in one polynomial.This reduces the number of polynomials from O(N^2) to O(N^2/K).
  • Verifiable sharing: Users secret-share quantized models using modified random polynomials whose degree increases from T to K + T − 1.Each user sends the resulting secret share to every other user.
  • Secure distance computation: Users compute pairwise distances over secret shares, embed K distances per partition into a polynomial, and send one evaluation point per polynomial to the server.The server reconstructs the distance values after collecting enough evaluations.
  • Protocol continuation: The server decodes all grouped distances and then applies the original BREA model-selection and aggregation steps.The generalized protocol otherwise follows the procedures of the earlier BREA framework.
  • Complexity improvement: Setting K = O(N) yields O(N^2) communication and O(N^2 log2 N log log N) computation.The quadratic bounds follow from O(N) grouped polynomials and the decoding cost per polynomial.

VII. EXPERIMENTS

Experiments compare BREA with FedAvg across i.i.d. and non-i.i.d. MNIST and CIFAR-10 settings. BREA converges and maintains comparable accuracy despite Byzantine users, while quantization introduces a tunable trade-off.

  • Evaluation: Experiments evaluate BREA against FedAvg using cross-entropy loss and test accuracy across training iterations.The study examines convergence and resilience under Byzantine users.
  • Evaluation setup: The evaluation uses a six-layer convolutional network for ten-class MNIST image classification.The architecture includes convolutional, pooling, fully connected, and softmax layers.
  • i.i.d. MNIST: The protocol runs with N = 40 users, T = 7 potentially colluding users, and either 0% or 30% Byzantine users.The i.i.d. MNIST setup partitions 60,000 training samples evenly across users.
  • i.i.d. MNIST: With i.i.d. MNIST, BREA at 0% and 30% Byzantine users is as efficient as FedAvg with 0% Byzantine users, whereas FedAvg does not tolerate Byzantine users.FedAvg with 30% Byzantine users diverges in the convergence comparison.
  • Quantization: Larger quantization parameters improve BREA performance by reducing quantization variance, but q must remain below a field-size-dependent threshold.The comparison uses q = 1024 for the reported BREA cases.
  • CIFAR-10: On CIFAR-10, BREA with 30% Byzantine users has comparable test accuracy to FedAvg with no Byzantine users.The experiment uses a model with about 10^6 parameters.

VIII. CONCLUSION

The paper presents BREA as a single-server framework combining secure outlier detection with privacy protection and Byzantine robustness. Its theory and experiments support convergence and resilience across several data-partitioning settings.

  • Contribution: BREA is presented as the first single-server solution for Byzantine-resilient secure federated learning.The framework uses verifiable secure outlier detection while protecting individual-user privacy.
  • Theory: The paper provides theoretical convergence guarantees and characterizes trade-offs involving Byzantine adversaries and user dropouts.The analysis also addresses the number of adversaries and dropouts the system can tolerate.
  • Empirical validation: Experiments on i.i.d. and non-i.i.d. MNIST over up to N = 100 users demonstrate convergence, Byzantine robustness, and privacy preservation.Both data-partitioning settings are evaluated numerically.
  • Future directions: Future work targets heterogeneous computation and communication resources, more efficient communication architectures, and improved quantization techniques.These directions address deployment and efficiency concerns identified by the paper.

APPENDIX

BREA supports local updating schemes in which users perform multiple stochastic-gradient-descent steps before transmitting updated models. The framework adapts its update, outlier-detection, and aggregation procedures while retaining multi-Krum-based user selection.

  • APPENDIX: Users can perform multiple local stochastic-gradient-descent steps on their data before sending updated models to the server.This extends BREA to local updating schemes beyond a single gradient estimate.
  • APPENDIX: The local-update version follows BREA’s existing procedure from Sections V-A through V-E, replacing each user’s gradient estimate with a multi-step SGD model update.The modification concerns the local update while preserving the framework’s other steps.
  • APPENDIX: A malicious user may transmit any random vector b^(t+1)_i, while benign users follow the specified local-update equation.The formulation explicitly distinguishes benign updates from arbitrary malicious vectors.
  • APPENDIX: Global synchronization occurs at steps J_E = {nE | n = 1, 2, · · ·}, where E denotes the number of local iterations.The selected-user set S^(t+1) is obtained using the multi-Krum algorithm described in Section V-D.
  • APPENDIX: An additional vector v^(t+1)_i represents the immediate result of one SGD step from w^(t)_i.This vector is introduced within the local-update formulation.
  • APPENDIX: Distance-based outlier detection remains effective on local models because model distances equal the learning rate γ multiplied by corresponding gradient distances.The server-side aggregation step is then represented using the adapted local-model formulation.
Loading 2007.11115v2…