Secure Multi-Party Computation (MPC) allows a group of participants to collaboratively compute a function over their private inputs without revealing the inputs themselves. Historically, evaluating functions interactively meant that every multiplication gate required real-time network round-trips and heavy public-key cryptographic operations, making the protocol incredibly slow.
To make MPC practical for real-world applications like private machine learning and database queries, modern cryptography relies on a powerful architectural split: the offline-online paradigm.
The Intuition of Preprocessing
The core idea behind the offline-online split is to decouple the cryptographic heavy lifting from the actual data processing.
- The Offline Phase (Preprocessing): Before any private inputs are known, the parties interact to generate "correlated randomness." These are raw cryptographic materials—such as Beaver multiplication triples, authenticated bits, or Oblivious Linear Evaluation (OLE) tuples—that are completely independent of the inputs but structurally bound to the function being computed.
- The Online Phase: Once the actual inputs are provided, the parties use this precomputed material to evaluate the function. Because the cryptographic complexity was handled beforehand, the online phase requires only cheap, linear local operations and minimal communication.
This paradigm allows the online phase to be lightning-fast and round-optimal, as demonstrated by Zhelei Zhou et al. in Single-Input Functionality against a Dishonest Majority: Practical and Round-Optimal and Daniel Escudero et al. in Honest Majority MPC with Abort with Minimal Online Communication.
However, this speedup is not free. The cryptographic complexity has not been eliminated; it has merely been rescheduled. Shifting these tasks creates a massive preprocessing bottleneck defined by severe communication and storage overhead. As Zhelei Zhou et al. observe in Practical Constructions for Single Input Functionality against a Dishonest Majority, the offline generation of correlated randomness frequently dominates the total execution time and data volume, often making the overall system impractical despite a highly optimized online phase.
The Communication Explosion
Why does generating correlated randomness require so much data transfer? To protect against malicious adversaries who might actively cheat, the precomputed data must be cryptographically bound to the parties' identities using Message Authentication Codes (MACs) or Oblivious Transfer (OT) extensions.
Sai Sheshank Burra et al. noted in High Performance Multi-Party Computation for Binary Circuits Based on Oblivious Transfer that even when using symmetric primitives to minimize computation, the offline phase still requires substantial data transfer to generate authenticated triples. Similarly, M. Sadegh Riazi et al. show in Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications that standard OT protocols incur massive communication overhead when scaling to large-scale neural networks.
This creates a strict trade-off: online computational speedups are purchased at the cost of massive offline data exchange, as highlighted by Jiaqi Xue et al. in CryptoTrain: Fast Secure Training on Encrypted Dataset and Kui Ren et al. in A New PPML Paradigm for Quantized Models. If generating this randomness places a high communication load on any single participant, the scalability benefits of the online phase are entirely negated, a challenge explored by Claudio Orlandi et al. in On the Bottleneck Complexity of MPC with Correlated Randomness.
[ Traditional MPC ]
Online Phase: High Cryptographic Computation + Multiple Network Round-Trips (Slow)
[ Preprocessing MPC ]
Offline Phase: Massive Data Exchange (OT/MACs) ──> Generates Gigabytes of Triples
│
▼
Online Phase: Lightweight Local Linear Operations + 1 Round of Communication (Fast)
The Hidden Storage and I/O Tax
Even if network bandwidth is plentiful, storing gigabytes of precomputed correlations introduces a secondary, physical bottleneck.
In their foundational work, Jesper Buus Nielsen et al. demonstrated in A New Approach to Practical Active-Secure Two-Party Computation that high-throughput secure computation shifts the performance bottleneck away from cryptographic computation and directly onto disk I/O and memory bandwidth.
When scaling to massive circuits or large datasets, the memory or disk space required to hold authenticated bits and precomputed auxiliary data becomes a severe operational constraint. As highlighted by Samuel Ranellucci et al. in Authenticated Garbling and Communication-Efficient, Constant-Round, Secure Two-Party Computation, the physical storage needed for these precomputed values limits the feasibility of executing massive circuits. This storage-speed trade-off is a recurring issue across applications, from Private Set Intersection (Florian Kerschbaum et al. in Faster Secure Comparisons with Offline Phase for Efficient Private Set Intersection) to federated learning deployments (Yang Liu et al. in A Secure Federated Transfer Learning Framework).
A Pervasive Cryptographic Pattern
This setup bottleneck is not unique to general-purpose MPC; it is a structural characteristic of many modern privacy-preserving protocols:
- Private Set Intersection (PSI): In unbalanced Circuit-PSI, encoding large databases and exchanging cryptographic keys introduces a heavy initial preprocessing phase that restricts one-time or infrequent interactions (Meng Hao 0001 et al. in Unbalanced Circuit-PSI from Oblivious Key-Value Retrieval).
- Zero-Knowledge Proofs: In multi-verifier zero-knowledge proofs, the latency of generating offline cryptographic correlations limits responsiveness in time-sensitive applications (Daniel Escudero et al. in Dishonest Majority Multi-Verifier Zero-Knowledge Proofs for Any Constant Fraction of Corrupted Verifiers).
- Lattice-Based Cryptanalysis: Outside of secure protocols, machine learning attacks on lattice-based cryptography require extensive preprocessing of data using classical lattice reduction algorithms, demanding weeks of computation before the learning phase can begin (Emily Wenger et al. in Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors).
Breaking the Bottleneck
To overcome these communication and storage constraints, researchers are pursuing two primary strategies: compressing the randomness or changing the underlying computational representation.
Silent Preprocessing
Instead of transmitting massive volumes of raw correlated randomness over the network, parties can use Pseudorandom Correlation Generators (PCGs). As shown by Damiano Abram et al. in Low-Bandwidth Threshold ECDSA via Pseudorandom Correlation Generators, parties only need to exchange tiny cryptographic seeds. These seeds expand locally into massive amounts of signature or multiplication material, reducing communication costs by up to 400x and bypassing the network bottleneck entirely.
Private Lookup Tables
Another approach avoids arithmetic circuits entirely for non-linear operations. By treating quantized model operators or activation functions as private lookup tables rather than complex arithmetic circuits, protocols like Tabula (Max Lam et al. in Tabula: Efficiently Computing Nonlinear Activation Functions for Secure Neural Network Inference) and the work of Kui Ren et al. in A New PPML Paradigm for Quantized Models drastically reduce the reliance on standard Beaver Triples, achieving massive end-to-end speedups and significant reductions in preprocessing communication.
Key Foundational Work
High Performance Multi-Party Computation for Binary Circuits Based on Oblivious Transfer (2015) — contributed 1 concept elements to this direction.
A New Approach to Practical Active-Secure Two-Party Computation (2012) — contributed 1 concept elements to this direction.