Scaling Cryptographic Protocols Beyond Two Parties

142 concepts134 papers1 proposal

Secure multi-party computation (MPC), private set intersection (PSI), and privacy-preserving machine learning (PPML) have undergone a dramatic performance revolution. Today, two parties can securely evaluate complex neural networks or find intersections across millions of records in seconds.

However, this efficiency is often an illusion of scale. Many of the most powerful cryptographic optimizations are hardcoded to the geometric and algebraic simplicity of exactly two or three participants. When we attempt to scale these protocols to an arbitrary number of parties ($N$-party) or massive distributed ecosystems, we hit a structural wall.

To understand why scaling beyond two parties is so difficult, we must look at how the underlying mechanics of communication, trust, and coordination break down as a network expands.


The Comfort Zone of Few-Party Cryptography

To appreciate why multi-party scaling fails, we first need to understand why two-party (2PC) and three-party (3PC) systems work so beautifully.

In a 2PC setting, the roles are perfectly complementary. For instance, in Garbled Circuits, one party acts as the "garbler" (generator) and the other as the "evaluator." High-performance frameworks like ObliVM by Liu et al., SIRNN by Rathee et al., and PASNet by Peng et al. exploit this bilateral symmetry to design highly specialized math libraries and hardware-aware neural architectures. Because there are only two entities, communication is a direct, point-to-point pipe.

When we move to 3PC, we gain a unique algebraic superpower: the honest majority assumption. If we assume that at most one out of three parties is corrupt, we can use replicated secret sharing over rings. As demonstrated by frameworks like ASTRA by Chaudhari et al. and EVA-S3PC by Peng et al., three parties can shift the heavy cryptographic lifting (like generating multiplication triplets) to an offline preprocessing phase. During the online phase, they can evaluate gates with minimal communication because any cheating can be immediately detected by the other two non-colluding parties.

2PC (Bilateral Symmetry)       3PC (Honest Majority Ring)
     [Party A]                      [Party A]
        ▲                             ▲   ▲
        │ (Direct Pipe)              /     \  (Replicated Shares)
        ▼                           ▼       ▼
     [Party B]               [Party B] ◄──► [Party C]

Why the Few-Party Mechanics Break Down

When we transition from 2PC or 3PC to an arbitrary $N$-party scenario, two fundamental bottlenecks emerge: communication topology and trust disintegration.

1. The Communication Mesh Explosion

In 2PC, evaluating a gate requires sending data across a single channel. In a general $N$-party MPC protocol, computing a multiplication gate typically requires an all-to-all broadcast or a round-robin exchange among all participants. This transforms a linear communication overhead into a quadratic ($O(N^2)$) or exponential complexity curve.

2. The Loss of Simple Honest Majorities

In an $N$-party setting, we can no longer rely on the simple replicated secret sharing that makes 3PC so fast. If $N=100$, assuming a simple honest majority means up to 49 parties could collude maliciously. To protect against this, protocols must abandon fast ring operations and adopt threshold secret sharing schemes (such as Shamir's secret sharing).

Threshold schemes require polynomial interpolation over finite fields to reconstruct secrets or evaluate multiplication gates. This introduces heavy computational overhead and forces multiple rounds of all-to-all communication, shattering the low-latency guarantees of few-party frameworks.


The Scalability Wall in Set Analytics

This breakdown is highly visible in Private Set Intersection (PSI)—the process of finding common elements across private databases without revealing non-intersecting data.

For two parties, De Cristofaro et al. demonstrated in Practical Private Set Intersection Protocols with Linear Computational and Bandwidth Complexity that PSI can achieve linear complexity relative to the dataset size. But as Liang et al. show in A Framework of Private Set Intersection Protocols, these linear-time methods do not naturally scale to multi-party environments (MPSI).

If $N$ independent databases want to find their mutual intersection, they face a difficult trade-off:

This multi-party bottleneck extends across all forms of distributed data alignment, including estimating intersection sizes via Bloom filters (Kikuchi et al.), evaluating sample similarity (Blundo et al.), and linking records across multiple financial or administrative jurisdictions (Han et al.).


The Coordination Overhead in Machine Learning

In Privacy-Preserving Machine Learning (PPML), scaling limitations manifest as a coordination and leakage problem.

In two-party vertical federated learning or split learning, one party holds the features and the other holds the labels. Frameworks like Squirrel (Zhang et al.) can securely train models because protecting against label leakage only requires securing a single boundary.

When data is split across many participants, coordinating this protection becomes significantly more complex. As Li et al. demonstrate in Label Leakage and Protection in Two-party Split Learning, noise-injection defenses (like differential privacy) that work perfectly for two parties fail to scale easily to multi-party environments. Coordinating noise injection across an arbitrary number of data-sharing parties while maintaining model utility requires complex global tracking (Yuan et al.).

Two-Party Split Learning (Simple Coordination)
[Data Owner] ◄─────────────── (Single Boundary) ──────────────► [Label Owner]

Multi-Party Federated Learning (Complex Coordination)
[Data Owner 1] ──┐
[Data Owner 2] ──┼─► [Secure Aggregator / Noise Coordinator] ──► [Global Model]
[Data Owner N] ──┘

Furthermore, many algorithmic optimizations are structurally anchored to fixed-server counts. For example, Xu highlights in Harnessing Sparsification in Federated Learning: A Secure, Efficient, and Differentially Private Realization that secure aggregation protocols for sparse updates often rely on a rigid, fixed three-server architecture with a single-honest-majority assumption.

When forced to scale to large-scale ecosystems with millions of concurrent participants (Ünal et al.) or decentralized shuffling networks (Cheu et al.), these architectures struggle under the weight of synchronization delays, client churn, and metadata management.


Bridging the Gap to True Multi-Party Scalability

To break through the multi-party scalability wall, researchers are developing techniques that decouple the number of data owners from the cryptographic complexity of the computing network.

One promising direction is Verifiable Function Secret Sharing (VFSS). As explored by de Castro et al. in Lightweight, Verifiable Function Secret Sharing and its Applications, VFSS allows users to outsource computations to a fixed set of servers using symmetric-key operations, enabling efficient batch verification where verifying thousands of secret shares costs the same in communication as verifying just one.

Another approach is the hybrid integration of cryptographic primitives. By combining homomorphic encryption with secret sharing—as seen in the CAESAR framework by Chen et al.—protocols can handle high-dimensional sparse data across multiple entities without incurring the full performance penalties of general-purpose MPC.

Ultimately, achieving true multi-party scalability requires moving away from tailored 2PC/3PC shortcuts. The next generation of privacy-preserving protocols must be designed from the ground up to ensure that communication, trust verification, and coordination overhead scale sublinearly as the participant network expands.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_multi_party_scalability_8165f4c1,
  title = {multi-party scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-party-scalability/rdr_8165f4c16e4a4e48b92204732fcb81cc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_multi_party_scalability_8165f4c1_v1,
  title = {multi-party scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-party-scalability/rdr_8165f4c16e4a4e48b92204732fcb81cc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake