Privacy-Preserving and Verifiable Approximate Distributed Coded Computing

Technical Summary: Privacy-Preserving and Verifiable Approximate Distributed Coded Computing

Problem Statement
Distributed machine learning paradigms, specifically Federated Learning (FL) and Decentralized Learning (DL), enable collaborative model training without centralizing raw data. However, these systems remain vulnerable to two distinct threat classes: privacy leakage (where adversaries infer sensitive data from model updates) and malicious manipulation (Byzantine attacks where participants inject poisoned updates). Existing defenses typically address these threats in isolation. Privacy-enhancing technologies (PETs) like homomorphic encryption or differential privacy often incur prohibitive computational overheads or degrade model utility. Conversely, robust aggregation techniques mitigate malicious behavior but rarely address privacy leakage and are often tailored to specific architectures. Furthermore, most prior work focuses on FL with a central aggregator, leaving decentralized settings—where data is exchanged rather than model updates—underexplored regarding unified adversary resilience.

Methodology
The authors propose a unified, model-agnostic framework that jointly addresses privacy and integrity across both FL and DL settings. The core technical foundation is Generalized Privacy-aware Berrut Approximated Coded Computing (GPBACC), a privacy-enhancing coded computing technique applicable to arbitrary machine learning models.

1. Core Mechanism (GPBACC):

   • Built upon Berrut Approximated Coded Computing (BACC), which uses rational interpolation (Berrut barycentric formulation) to distribute the computation of arbitrary functions while tolerating stragglers.
   • Privacy Extension: GPBACC introduces Gaussian random noise into the encoding process. The master node encodes data tensors using a rational interpolation function augmented with random noise terms. This creates an Additive White Gaussian Noise (AWGN) channel effect, limiting the mutual information accessible to colluding semi-honest nodes.
   • Generalization: Unlike previous schemes, GPBACC supports multi-source configurations and arbitrary-rank tensor inputs, making it suitable for deep learning workloads.

2. Federated Learning (FL) Integration:

   • In FL, where a central aggregator exists, the framework integrates GPBACC with robust aggregation strategies (e.g., Coordinate-wise Median, Trimmed Mean, Krum, Multi-Krum).
   • The aggregation rule is embedded as the target function $f$ evaluated by the workers. The system sets the coding compression dimension $K=1$ to enable per-coordinate decoding, allowing the aggregator to reconstruct the robustly aggregated update with high numerical precision despite the approximate nature of the coding.

3. Decentralized Learning (DL) Integration:

   • In DL, where no central aggregator exists, the framework employs a verification pipeline combining Approximate Decode-and-Compare (ADC) and Group Testing (GT).
   • ADC: Since GPBACC introduces controlled perturbations for privacy, exact equality checks are insufficient. ADC establishes a dynamic threshold ($\tau$) based on a bootstrap strategy to determine if reconstructed results from different worker subsets are consistent within an acceptable error envelope.
   • Group Testing: To efficiently isolate malicious workers without full decoding, the system uses non-adaptive pooling matrices. Workers are grouped, and their pooled results are tested against the ADC threshold. A noisy Group Testing decoder (e.g., COMP, DD) identifies the set of adversarial workers, which are then pruned before the final reconstruction.

Key Contributions

• Unified Framework: Definition of a single framework that simultaneously addresses privacy leakage and malicious behavior in both FL and DL paradigms without restricting applicability to specific model architectures.
• FL Adaptation: Proposal to combine GPBACC with robust aggregation strategies, preserving the model-agnostic nature of the coding scheme.
• DL Adaptation: Proposal to complement GPBACC with approximate decode-and-compare and group testing techniques, enabling lightweight verification and adversary isolation without a trusted aggregator.
• Attack-Driven Evaluation: A practical evaluation methodology that explicitly implements representative privacy attacks (Membership Inference Attacks) and malicious behaviors (Label Flipping, Noise Addition, Gaussian Noise) to empirically validate the framework's efficacy, rather than relying solely on theoretical guarantees.

Experimental Results
The framework was evaluated on Convolutional Neural Networks (CNNs) using MNIST and CIFAR10 datasets.

• Federated Learning:

  • Privacy: Under Membership Inference Attacks (RMIA), GPBACC significantly reduced the Area Under the Curve (AUC) to near-random levels (~0.50), comparable to Multi-Key Homomorphic Encryption (MKHE) and Differential Privacy (DP-SVT), but without the severe utility degradation seen in DP.
  • Robustness: Under Label Flipping and Noise Addition attacks, GPBACC combined with robust aggregators (Median, Multi-Krum) maintained high accuracy, closely matching unprotected robust baselines. While Krum aggregation showed sensitivity to the approximate decoding noise, the system still converged.
  • Utility: GPBACC preserved clean-model utility almost perfectly, with accuracy deviations below $4 \times 10^{-4}$ compared to unprotected baselines.

• Decentralized Learning:

  • Robustness: Under noise addition attacks, unprotected DL collapsed (accuracy ~0.63), whereas GPBACC with ADC+GT maintained high accuracy (>0.96), demonstrating resilience comparable to exact coded computing (ALCC) but with greater flexibility.
  • Privacy: Mutual information between plain and encoded datasets was estimated using the KSG estimator, yielding ~1.012 bits, which aligns closely with the theoretical privacy bounds derived from information-theoretic analysis.

Significance and Claims
The paper claims that the combination of privacy-enhancing coded computing (GPBACC) with paradigm-specific adversary-resistance strategies provides a practical and deployable foundation for secure distributed machine learning. Unlike prior works that treat privacy and robustness in isolation or rely on heavy cryptographic primitives, this approach offers a unified, attack-validated solution that balances privacy guarantees, robustness against active adversaries, and model utility. The authors emphasize that their contribution lies in bridging these gaps across learning paradigms, offering an architecture-independent defense mechanism suitable for real-world deployment. The work does not claim to solve all threat models but demonstrates that explicit, attack-driven integration of these techniques significantly reduces privacy leakage and improves resilience compared to existing isolated defenses.