Secure Multi-Party Computation (MPC) and threshold cryptography allow a group of distrusting parties to jointly compute a function over their private inputs without revealing anything beyond the output. To make these protocols fast enough for practical use—such as deep learning inference or distributed cryptographic wallets—modern systems rely on an offline/online paradigm.
In the online phase, parties compute the actual function quickly using pre-distributed, structured random data known as correlated randomness (such as Beaver multiplication triples, random masks, or oblivious transfers). The core bottleneck of this paradigm is the offline phase (or preprocessing phase): traditionally, generating millions of these correlated pairs requires massive network communication, which scales poorly and chokes high-throughput applications.
A rapidly growing research direction solves this bottleneck through silent preprocessing. Instead of transmitting massive volumes of random data over the network, parties interact just once to exchange tiny, correlated cryptographic keys or seeds. They then expand these seeds locally into an unbounded stream of high-quality correlated randomness without any further communication.
The Core Mechanism: From PRFs to Correlated Expansion
To understand why silent preprocessing works, consider a standard Pseudorandom Function (PRF). A single party with a short cryptographic seed can locally evaluate a PRF to generate an arbitrarily long stream of pseudorandom numbers.
In a multi-party setting, we want something similar, but with a twist: we need the expanded streams held by different parties to be individually random, yet jointly correlated according to a specific algebraic relationship. This is achieved via Pseudorandom Correlation Generators (PCGs) and Pseudorandom Correlation Functions (PCFs).
Traditional Preprocessing:
[Party A] <==== (Massive Interactive Communication) ====> [Party B]
Result: Gigabytes of Triples/Oblivious Transfers sent over the network.
Silent Preprocessing:
[Party A] <--- (One-time Setup: Tiny Seeds) ---> [Party B]
|| ||
\/ (Local Expansion) \/ (Local Expansion)
[Unbounded Correlated Randomness] [Unbounded Correlated Randomness]
Early iterations of this concept relied on a trusted setup or a central authority to distribute seeds. For instance, in Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications, M. Sadegh Riazi et al. demonstrated that distributing short cryptographic seeds rather than full sets of random values dramatically lowers the communication burden during the preprocessing stage of secure protocols, reducing data transfer for arithmetic triples by several orders of magnitude. Similarly, in the context of privacy-preserving machine learning, GuardHFL: Privacy Guardian for Heterogeneous Federated Learning by Hanxiao Chen et al. uses shared secret seeds to let parties locally generate identical pseudo-random number streams, minimizing network overhead during initialization.
To eliminate the need for a trusted third party, modern PCFs use advanced public-key primitives to let parties generate these correlated seeds interactively. In The Rise of Paillier: Homomorphic Secret Sharing and Public-Key Silent OT, Claudio Orlandi et al. established a powerful connection between Homomorphic Secret Sharing (HSS) and PCFs. By evaluating secret shares of a PRF homomorphically under cryptographic assumptions like Decisional Composite Residuosity (DCR), the authors constructed efficient PCFs for Oblivious Transfer (OT) and Vector Oblivious Linear Evaluation (VOLE). This template was expanded by Amik Raj Behera et al. in Privately Constrained PRFs from DCR: Puncturing and Bounded Waring Rank to build privately constrained PRFs, allowing parties to evaluate secret shares of PRF outputs under specific input restrictions without revealing the constraints themselves.
Non-Interactive Generation of Complex Correlations
While generating simple random masks or identical streams is straightforward, generating complex algebraic structures—like multiplication triples ($a, b, c$ where $c = a \cdot b$)—completely non-interactively across multiple parties requires combining local secret sharing with structured mathematical embeddings.
In honest-majority scenarios, Anders P. K. Dalskov et al. showed in Fast Fully Secure Multi-Party Computation over Any Ring with Two-Thirds Honest Majority that non-interactive random secret generation can produce correlated random masks without direct communication, significantly boosting protocol efficiency.
To achieve higher-degree correlations over rings without network overhead, Cheng Hong et al. introduced a novel approach in Degree-D Reverse Multiplication-Friendly Embeddings: Constructions and Applications. By pairing Pseudo-Random Secret Sharing (PRSS) with Reverse Multiplication-Friendly Embeddings (RMFEs), the authors allowed parties to perform multiple multiplications on "packed" data locally. This framework transforms the communication complexity of preprocessing from a logarithmic growth relative to the number of parties into a constant factor, allowing high-degree correlated randomness to be generated entirely through local computation from shared seeds.
Application: Low-Bandwidth, Stateless Threshold Signatures
One of the most impactful applications of silent correlation expansion is in threshold cryptography, where a private signing key is split among multiple parties (e.g., in decentralized blockchain wallets). Traditional threshold signature schemes require parties to interactively generate random nonces for every single signature, which introduces high latency and forces nodes to maintain a synchronized state to prevent catastrophic nonce-reuse vulnerabilities.
PCGs and PCFs fundamentally alter this paradigm by acting as a multi-party analogue of a PRF. In Low-Bandwidth Threshold ECDSA via Pseudorandom Correlation Generators, Damiano Abram et al. demonstrated that exchanging tiny cryptographic seeds that expand locally into massive volumes of signature material reduces the preprocessing bandwidth per signature by up to 400x compared to transmitting full multiplication triples.
Furthermore, this local expansion enables stateless operation. Instead of storing and tracking thousands of pre-generated triples, parties can compute the exact correlated randomness they need on-the-fly using a public counter or input index.
The authors of Two-Round Stateless Deterministic Two-Party Schnorr Signatures From Pseudorandom Correlation Functions (Yashvanth Kondi et al.) utilized PCFs to translate single-party stateless deterministic signing techniques directly into the two-party setting, bypassing the need for expensive zero-knowledge proofs. This concept was scaled to multi-party settings by Kang Yang 0002 et al. in Stateless Deterministic Multi-Party EdDSA Signatures with Low Communication. By using PCFs to generate correlated randomness locally from pre-shared keys, the protocol eliminates the need for participants to synchronize or track state between signing sessions. This removes state-tracking vulnerabilities entirely, making distributed hardware security modules and cryptocurrency wallets significantly more resilient and practical.
Key Foundational Work
Low-Bandwidth Threshold ECDSA via Pseudorandom Correlation Generators (2021) — contributed 2 concept elements to this direction.
The Rise of Paillier: Homomorphic Secret Sharing and Public-Key Silent OT (2021) — contributed 2 concept elements to this direction.
Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications (2018) — contributed 2 concept elements to this direction.