Scaling Secure Multi-Party Computation

267 concepts247 papers4 proposals

Secure Multi-Party Computation (SMPC) and Homomorphic Encryption (HE) offer a compelling promise: allowing multiple independent parties to collaboratively compute functions or train machine learning models over their combined datasets without ever revealing their raw, private inputs.

However, deploying these cryptographic protocols in the real world introduces a massive "privacy tax." As Melissa Chase et al. observe in Private Collaborative Neural Network Learning, traditional cryptographic protocols suffer from severe communication and computational overheads. These bottlenecks scale poorly as the number of participants or the dimensionality of the data grows, frequently rendering generic secure computation frameworks impractical for high-performance or real-time applications.

To bridge this gap, a major research direction focuses on reducing the cryptographic overhead of secure computation. Rather than treating cryptography as a black box, researchers are redesigning protocols from the ground up by co-optimizing the underlying mathematics, data structures, and hardware.


The Root of the Overhead: Why Secure Computation is Slow

To understand why secure computation scales poorly, we must look at how cryptographic primitives handle basic operations.

In standard multi-party computation or homomorphic encryption, linear operations (like addition and scalar multiplication) are relatively cheap. They can often be performed locally by manipulating secret shares or encrypted ciphertexts without network interaction.

The bottleneck occurs with non-linear operations (such as the ReLU or Sigmoid activation functions in neural networks, or comparisons in sorting algorithms). In standard cryptographic frameworks, computing a non-linear function requires complex interactive protocols like garbled circuits or boolean secret sharing. As Peichen Xie et al. note in BAYHENN: Combining Bayesian Deep Learning and Homomorphic Encryption for Secure DNN Inference, these methods impose prohibitive communication overhead between clients and servers, requiring massive data transfers and multiple rounds of back-and-forth network synchronization.

Furthermore, when scaling to dynamic networks—such as mobile federated learning—the cost of transferring cryptographic secret shares among evolving groups of participants can scale quadratically with the number of users, as detailed by Alexander Bienstock et al. in DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning using Packed Secret Sharing.

To overcome these fundamental limitations, researchers employ several key strategies.


Strategy 1: Shifting the Burden Offline

One of the most effective ways to accelerate secure computation is to decouple the cryptography from the live data processing. If the heavy communication and computational work can be performed before the actual inputs are known, the live ("online") phase can run at near-native speeds.

A powerful mechanism for this is Function Secret Sharing (FSS). In Online Efficient Secure Logistic Regression based on Function Secret Sharing, Jing Liu et al. leverage FSS to optimize logistic regression. By generating independent, data-oblivious cryptographic keys during an offline phase, the parties can evaluate complex non-linear functions (like the sigmoid activation) during the online phase with minimal network interaction. This approach shifts the bulk of the communication volume offline, drastically reducing online latency.


Strategy 2: Algorithmic and Polynomial Approximations

Because exact non-linear operations are cryptographically expensive, another core strategy replaces them with mathematically friendlier alternatives. Since homomorphic encryption and secret sharing natively support addition and multiplication, any function that can be expressed as a low-degree polynomial can be computed efficiently.

In SAFENet: A Secure, Accurate and Fast Neural Network Inference, Qian Lou et al. demonstrate this by replacing standard activation functions with optimized, channel-wise polynomial approximations. By using a binary-tree search algorithm to find the lowest-degree polynomial that maintains model accuracy, they bypass the need for expensive garbled circuits entirely.

Similarly, for tree-based models, Lunchen Xie demonstrates in An Efficient Learning Framework for Federated XGBoost Using Secret Sharing and Distributed Optimization that replacing slow cryptographic comparisons with mathematical reshaping and distributed optimization allows vertical federated learning to match the accuracy of centralized training without the typical encryption overhead.


Strategy 3: Exploiting Data Sparsity

In conventional computing, multiplying by zero is a trivial operation that can be skipped. In secure computation, however, hiding which elements are zero is a core privacy requirement. Consequently, naive SMPC protocols treat zeros and non-zeros identically, wasting massive amounts of bandwidth and compute on empty data cells.

To resolve this, researchers design specialized protocols that respect data structures without leaking private information. Phillipp Schoppmann et al. introduce this paradigm with ROOM in Make Some ROOM for the Zeros: Data Sparsity in Secure Distributed Machine Learning. By developing cryptographic linear algebra protocols tailored specifically for sparse data structures, the authors allow distributed machine learning algorithms (like k-Nearest Neighbors and Logistic Regression) to scale efficiently to high-dimensional real-world datasets by securely skipping redundant zero-value computations.


Strategy 4: Asymmetric Architectures and Hybrid Privacy

Not all participants in a distributed network possess equal computing power. In mobile federated learning, for example, a central server has vast resources, while edge clients are highly constrained.

Recognizing this asymmetry, researchers design frameworks that offload the cryptographic burden away from weak nodes. In Efficient-FedRec: Efficient Federated Learning Framework for Privacy-Preserving News Recommendation, Fangzhao Wu proposes decomposing recommendation models so that heavy encoding tasks are handled by the server, leaving only a lightweight model on the client side. This architectural split minimizes the size of the parameters that must pass through secure aggregation pools.

Additionally, researchers frequently combine cryptographic primitives with Differential Privacy (DP) to achieve a hybrid balance. By strategically injecting statistical noise, frameworks can relax their reliance on heavy, multi-round cryptographic protocols while maintaining rigorous mathematical privacy guarantees, as explored by Yi Zhou et al. in HybridAlpha: An Efficient Approach for Privacy-Preserving Federated Learning.


Strategy 5: Hardware-Assisted Acceleration

When algorithmic and mathematical optimizations reach their limits, hardware acceleration offers a final, powerful layer of scalability. Rather than relying solely on software-based cryptography, protocols can be offloaded to specialized physical environments like Trusted Execution Environments (TEEs) or Field Programmable Gate Arrays (FPGAs).

In FLAIRS: FPGA-Accelerated Inference-Resistant & Secure Federated Learning, Huimin Li et al. demonstrate how offloading complex defense and aggregation algorithms to optimized FPGA logic can bypass software bottlenecks, delivering massive speedups over pure cryptographic software implementations. Similarly, Fumiyuki Kato et al. show in Secure and Efficient Trajectory-Based Contact Tracing using Trusted Hardware that leveraging hardware enclaves (such as Intel SGX) allows systems to privately process millions of sensitive data records with minimal latency, providing a highly scalable alternative to pure mathematical multi-party computation.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_secure_computation_scalability_1ac9406f,
  title = {secure computation scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/secure-computation-scalability/rdr_1ac9406f468c43d298634ae62abd7cb9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_secure_computation_scalability_1ac9406f_v1,
  title = {secure computation scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/secure-computation-scalability/rdr_1ac9406f468c43d298634ae62abd7cb9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake