NOMAI: Scalable Federated Learning with Private Weights

Detailed Research Summary of NOMAI: Scalable Federated Learning with Private Weights

NOMAI (Scalable MPC-based FL system) is a novel framework designed to simultaneously achieve model privacy, data privacy, and data integrity within a single coordinating server environment. It is presented as the first scalable Multi-Party Computation (MPC)-based Federated Learning (FL) system capable of providing all three security guarantees concurrently. NOMAI operates under an honest-majority assumption in the semi-honest model, with an extension to the malicious-with-abort setting.

Core Architectural Innovations and Scalability

NOMAI addresses the scalability limitations of monolithic MPC protocols by employing a New Architecture that retains a single coordinating server while distributing computational load across small, disjoint committees of participating users who act as MPC helpers.

• Committee-Based MPC: Each user's data is assigned to one specific committee, and this data is secret-shared among the members of that committee. This structure allows committees to operate in parallel on their respective data shards, enabling massive scalability beyond traditional n-party protocols.

• SIMD-Style Parallelism via Packed Shamir Secret Sharing (PSS): Within each committee, NOMAI utilizes Packed Shamir Secret Sharing (PSS). This cryptographic primitive enables SIMD-style parallelism, significantly reducing the computational cost associated with operations within the committee.

• Efficiency through ML-Aware Optimizations: The system incorporates several New Cryptographic Primitives specifically tailored for machine learning workloads to drastically reduce per-user overhead:

• Efficient Linear Layers: Targeted optimizations for linear layers using ML-inspired transformations and novel packing strategies under PSS.

• Efficient Secure Exponentiation: A new protocol that minimizes the required rounds for secure exponentiation by converting PSS sharing into additive shares and applying the multinomial theorem.

• Efficient Degree Reduction: A protocol that integrates repacking directly into degree reduction, eliminating the overhead associated with explicit unpacking and repacking steps.

• Efficient Truncation: A new truncation protocol compatible with PSS, leveraging Mersenne prime fields for highly efficient bit operations.

Security Guarantees

NOMAI is engineered to satisfy three critical security objectives:

1. Data Privacy: For every honest user, no other user can learn any information about their raw private data. The coordinating server only learns the final aggregate gradient (G) and nothing beyond what is revealed by this aggregate.

2. Weight Privacy: The model parameters held by the central server remain hidden from all participating users.

3. Data Integrity: The server guarantees that individual user gradients are syntactically well-formed by enforcing a validation predicate, Valid(times), which defines necessary constraints (e.g., norm bounds). Crucially, NOMAI achieves this efficiently by executing the computationally expensive gradient computation under the cheaper semi-honest model and reserving malicious security checks only for the final validation and aggregation steps.

Performance and Empirical Results

The system demonstrates exceptional practical deployability at unprecedented scales:

• Speed: NOMAI reduces per-user computation to less than 350 ms (semi-honest) for MNIST training iterations and less than 700 ms (malicious) for the same, representing three orders of magnitude improvement over prior work.

• Scale: It successfully supports user populations exceeding 106 users.

• Comparative Gains: The system achieves gains of 10 cubed to 10 5 times over baselines, including a 2 times 10 cubed to 1.7 times 10 5 times improvement against POSEIDON, even when considering the per-machine cost independence of NOMAI from the total number of users (N) in the semi-honest setting.

Detailed Operational Analysis and Trade-offs

The paper provides a deep dive into how NOMAI balances performance against security parameters:

• Overhead vs. Corruption Threshold (t): The configuration of NOMAI is determined by selecting the optimal committee size (c), packing factor (l), and corruption threshold (t). The system selects the smallest t such that the probability of any committee containing more than t corrupted members is 10-12.

• Trade-offs in Packing Factor (l): Increasing the packing factor l allows for more values to be packed into a share, reducing the number of processed objects. However, this simultaneously increases the sharing degree (d = t + l - 1) and consequently raises the committee size n = 2d + 1, making interactive operations like degree reduction and truncation more expensive. The optimal l is workload-dependent (e.g., l=20 for FC arches, l=50 for CNN arches).

• Workload Distribution: A key finding is that the dominant cost in NOMAI is the semi-honest secure training computation, whose per-committee-member workload is largely independent of the total user population N. Increasing N primarily impacts the number of committees that need coordination and checking for malicious security, leading to a relatively weak dependence on N for fixed costs.

• Communication Efficiency: For CNN architectures, NOMAI shows significant communication advantages due to packing; it requires only one degree reduction per packed output regardless of spatial dimension, yielding bandwidth reductions up to 29,258 times for MNIST-CNN and SVHN-CNN compared to HMMPC's O(n) communication.

• Competitive Edge: NOMAI maintains competitiveness with baseline systems even when performing the significantly stronger task of executing the full forward and backward pass under MPC, unlike baselines where helpers only support secure aggregation of pre-computed updates.

In summary, NOMAI is a highly optimized, architecture-specific MPC framework that leverages advanced cryptographic packing and ML-aware transformations to deliver state-of-the-art performance in scalable federated learning while rigorously enforcing simultaneous data privacy and integrity guarantees.

1. Bold architecture for scalability in FL: NOMAI provides the first scalable MPC-based FL system to provide all three guarantees simultaneously by combining a multi-committee MPC architecture with packed Shamir secret sharing, enabling SIMD-style secure computation that scales far beyond what monolithic n-party protocols can support. This allows training on populations of over 106 users while maintaining privacy and integrity.

2. Bold computational efficiency for user hardware: The system reduces "per-user computation to just <350 ms (semi-honest) and <700 ms (malicious) for per iteration of training MNIST, achieving three orders-of-magnitude improvements over prior work." This makes the FL system practically deployable on resource-constrained edge devices.

3. Bold optimization for linear layers: NOMAI introduces ML-aware optimizations such as Winograd convolution and novel packing strategies to reduce multiplication costs in linear layers, which are the dominant source of multiplications in ML training. This results in reduced overhead for operations like convolutional and fully connected layers.

4. Bold protocol efficiency for non-linearities: The system utilizes polynomial approximations for nonlinearities rather than exact protocols, which are more amenable to efficient packed computation and avoid the high cost of costly degree-reduction steps. This allows the system to maintain accuracy while minimizing interaction rounds in secure computation.

5. Bold integrity mechanism for malicious users: NOMAI ensures data integrity by enforcing a validation predicate, as it enforces a validation predicate Valid(·) that defines a syntax for the gradients, and NOMAI turns this observation into an efficiency gain by executing the expensive gradient computation in the cheaper semi-honest model.

6. Bold robustness against adversarial behavior: The system implements checks to detect protocol deviations, such as weight-consistency check and per-gradient well-formedness checks. This allows the server to abort if validation fails or if consistency is violated, ensuring that only gradients satisfying Valid(g) = 1 are accepted.

7. Bold enhanced security for malicious settings: In the malicious setting, NOMAI uses a novel maliciously secure aggregation protocol that combines only well-formed gradients into the final aggregate, and performs a final degree-2t consistency check on the received vector before reconstructing the aggregate, ensuring that an adversary cannot accumulate more than 2t shares.

8. Bold improved dropout tolerance: The system incorporates mechanisms to handle unavailable members, requiring a committee size of n+2D members in the malicious-with-abort setting, which ensures that even with up to D erasures, the protocol maintains its security bound by ensuring a source gradient contribution is either rejected or accepted as the correct aggregate.

The twin goals of privacy-preserving federated learning (FL) -- harnessing distributed data while protecting the parties who contribute it -- demands three properties: model privacy, data privacy, and integrity. Achieving all three in a realistic deployment -- with a single coordinator and millions of users -- remains an open challenge that prior work has yet to fully resolve. We present NOMAI, the first scalable MPC-based FL system to provide all three guarantees simultaneously. NOMAI operates under an honest-majority assumption in the semi-honest model, with an extension to the malicious-with-abort setting. At its core, NOMAI combines a multi-committee MPC architecture with packed Shamir secret sharing, enabling SIMD-style secure computation that scales far beyond what monolithic n-party protocols can support. We further introduce ML-aware optimizations and new cryptographic primitives that substantially reduce per-user overhead. Our evaluation shows NOMAI is practically deployable at unprecedented scale: it reduces per-user computation to just <350 ms (semi-honest) and <700 ms (malicious) for per iteration of training MNIST, achieving three orders-of-magnitude improvements over prior work while seamlessly supporting populations of over 106 users. This demonstrates, for the first time, that MPC-based FL can meet the scale demands of real-world systems without compromising on privacy or integrity.