Secure Multi-Party Computation (MPC) and Fully Homomorphic Encryption (FHE) promise a world where we can compute on data we cannot see. But historically, there has been a massive catch: performing mathematical operations on encrypted data is incredibly slow. Multiplying ciphertexts or evaluating non-linear functions requires heavy cryptographic machinery and constant network communication. If a user wants to run a real-time query—such as a private medical diagnosis or a fast Transformer inference—waiting minutes for a response is unacceptable.
To bypass this cryptographic bottleneck, researchers decouple the computation into two distinct phases based on input-independence:
- The Offline Phase (Preprocessing): Executed long before the user provides their private data. This phase handles the heavy cryptographic operations, generating raw "cryptographic fuel" based solely on the known structure of the function or network.
- The Online Phase: Executed the moment the private input arrives. This phase consumes the precomputed fuel to evaluate the function using ultra-fast plaintext arithmetic and minimal communication.
The Magic of Correlated Randomness
To understand why this works, let's look at the primary bottleneck of secure computation: multiplication. In secret-sharing-based MPC, adding two secret shares is "free"—parties simply add their local values without talking to each other. But multiplying two secret shares requires interactive, heavy cryptographic protocols.
The offline-online paradigm solves this using Beaver Triples (or correlated randomness), a technique leveraged by Bendlin et al..
During the offline phase, before the private inputs $x$ and $y$ are known, the system generates secret shares of three random values $(a, b, c)$ such that:
$$c = a \times b$$
When the online phase begins and the real inputs $x$ and $y$ arrive, the parties use the random values $a$ and $b$ as "blinding factors" to mask the real data:
- Each party locally computes and reveals their shares of $e = x - a$ and $f = y - b$.
- Because $a$ and $b$ are uniformly random, the broadcasted values $e$ and $f$ are completely random plaintexts that reveal absolutely nothing about the private inputs.
Now, the parties can mathematically reconstruct the product $x \times y$ using the public values $e, f$ and their local secret shares of $a, b,$ and $c$:
$$x \times y = (a + e)(b + f) = ab + af + eb + ef = c + af + eb + ef$$
Because $e$ and $f$ are now public plaintexts, computing $af$ and $eb$ only requires multiplying a local secret share by a known constant. The expensive ciphertext-ciphertext multiplication is entirely avoided during live execution. As shown by Burra et al. and Zhou et al., this preprocessing model restricts the online phase to lightweight arithmetic operations and minimal communication.
Scaling to Complex Functions
The same intuition applies to more complex, non-linear functions like the activations in deep learning. Instead of evaluating functions on the fly, modern frameworks use Function Secret Sharing (FSS).
In FSS, as explored by Gupta et al. and Chen et al., a non-linear function is broken down into secret-shared evaluation keys during the offline phase. During the online phase, the parties merely evaluate these keys on masked inputs locally. This eliminates the constant back-and-forth communication rounds that typically plague secure protocols, reducing the online phase to a single round of reconstruction (Liu et al.).
For private neural network inference, frameworks like MiniONN (Liu et al.) and Primer (Zheng et al.) precompute random masks and matrix products. When a user query arrives, the online phase combines these precomputed components with the encrypted input, achieving latencies that approach plaintext execution speeds.
Managing the Preprocessing Burden
While the online phase becomes incredibly fast, the offline phase still bears a heavy computational cost. To manage this, researchers employ several structural strategies:
- Server-Aided Preprocessing: In frameworks like Chameleon (Riazi et al.), a semi-honest third party generates the correlated randomness (multiplication triples and oblivious transfer masks) during the offline phase. This completely frees the active online parties from heavy cryptography. Similar server-aided preprocessing models are used to optimize Oblivious RAM (Kolesnikov et al.) and Gaussian process regression (Luo et al.).
- Bypassing Ciphertext Multiplications: In secure machine learning training, Xue et al. demonstrate that precomputing products of random masks offline allows the online training phase to use fast ciphertext-plaintext multiplications instead of slow ciphertext-ciphertext operations, avoiding expensive relinearization steps.
- Hardware Blinding: Boneh et al. show that by pre-generating random blinding factors offline, a Trusted Execution Environment (TEE) can safely outsource heavy linear layers to an untrusted, high-performance GPU online, verifying the results with minimal arithmetic overhead.
Broad Impact Across Privacy-Preserving Workloads
This decoupling paradigm has become the standard blueprint for making privacy-preserving systems practical across diverse domains:
- Federated Learning: In large-scale collaborative training, generating message-independent tokens and masking tables offline (Tang et al.) or pre-computing oblivious transfer components (Arora et al.) drastically reduces active training round latency.
- Database Queries and Sorting: For private set intersection or recommendation systems, pre-computing encryptions of constant bits or OLE tuples allows online sorting and comparisons to run at field-arithmetic speeds (Kerschbaum et al.). For example, Pranav Verma in Efficient privacy preserving top-k recommendation using homomorphic sorting pre-computes encryptions of constant zero and one bits during offline phases to eliminate the latency of on-the-fly encryption during sorting.
- Verifiable Computing: Early work by Gennaro et al. established that converting a function into a garbled circuit once offline enables a weak client to verify outsourced computations non-interactively and instantaneously online.
By separating preparation from execution, the cryptographic community has successfully shifted the question from "how do we make cryptography faster?" to "how do we do the cryptography ahead of time?"
Key Foundational Work
Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers (2009) — contributed 1 concept elements to this direction.
Generating Random Factored Numbers, Easily (2003) — contributed 1 concept elements to this direction.