Multi-Party Computation (MPC)

The foundational guarantee of MPC: no party learns anything about another party's private input beyond what can be logically inferred from the output of the computation itself. This is formally proven using the real-ideal world paradigm, where the security of the real protocol is shown to be indistinguishable from an ideal world where a trusted third party performs the computation. Input privacy holds even against active adversaries who deviate arbitrarily from the protocol, not just passive eavesdroppers.

The protocol ensures that the output is mathematically correct according to the agreed-upon function, even if a subset of parties are malicious. This is achieved through verifiable secret sharing and consensus on broadcast channels. In SPDZ-family protocols, correctness is enforced via Message Authentication Codes (MACs) on secret-shared values, allowing parties to detect tampering before output reconstruction. The guarantee is probabilistic in some designs but can be made overwhelming with sufficient security parameters.

A stronger property than correctness alone. Guaranteed output delivery ensures that all honest parties receive the result regardless of adversarial behavior. This is achievable only with an honest majority (e.g., 3 out of 4 parties). In the dishonest majority setting, fairness is impossible in general; the best achievable property is security with abort, where the protocol halts upon detecting cheating but prevents the adversary from learning the output while honest parties do not.

MPC protocols are parameterized by the number of corrupt parties they tolerate. Common models include:

• t < n/2: Honest majority, enabling fairness and guaranteed output delivery
• t < n/3: Required for protocols with information-theoretic security and asynchronous networks
• t < n: Dishonest majority, achievable only with computational assumptions and typically providing security with abort The choice of threshold directly impacts the protocol's efficiency and the cryptographic primitives required.

Modern MPC protocols are Turing-complete, capable of evaluating any function representable as an arithmetic or Boolean circuit. The gold standard for security is Universal Composability (UC), which guarantees that a protocol remains secure even when composed arbitrarily with other protocol instances. UC-secure MPC protocols, such as those based on the Global Random Oracle model, provide modular security proofs essential for complex decentralized applications.

A critical practical property: the total data exchanged between parties during protocol execution. In information-theoretic protocols like BGW, communication scales linearly with circuit size and quadratically with the number of parties. Constant-round protocols (e.g., Yao's garbled circuits) minimize latency but incur high bandwidth. Preprocessing models (SPDZ, MASCOT) shift heavy cryptographic work to an offline phase, enabling extremely efficient online phases measured in milliseconds for linear operations.

The foundational building block of most MPC protocols. A secret is split into shares distributed among participants, where the secret can only be reconstructed when a threshold of shares is combined.

• Shamir's Secret Sharing: Uses polynomial interpolation; any k of n shares reconstruct the secret
• Additive Sharing: Secret is split such that shares sum to the original value
• Individual shares reveal zero information about the underlying secret

A two-party MPC protocol where one party encrypts a Boolean circuit representing the function and the other evaluates it obliviously.

• The garbler encrypts each gate's truth table with random keys
• The evaluator uses oblivious transfer to obtain input keys without revealing their inputs
• Constant-round protocol ideal for low-latency settings
• Forms the basis of Yao's protocol, the first general-purpose MPC construction

A cryptographic primitive where a sender transmits one of many pieces of information to a receiver, but remains oblivious to which piece was transferred.

• 1-out-of-2 OT: Sender has two messages; receiver chooses one without sender learning which
• Receiver learns nothing about the unchosen message
• OT is a complete primitive for secure computation
• OT extension techniques dramatically reduce the cost of many OTs using only a few base OTs

Distributes cryptographic operations across multiple parties so that no single party holds the complete key. A threshold t-of-n scheme requires t parties to collaborate.

• Threshold Signing: Used in institutional crypto custody to eliminate single points of compromise
• Threshold Decryption: Enables distributed key management for encrypted data at rest
• Combines MPC with standard cryptographic primitives like ECDSA and BLS signatures
• Widely deployed in crypto wallets and HSM alternatives

Allows computation directly on encrypted data without decryption. While MPC requires interaction between parties, homomorphic encryption is non-interactive.

• Partially Homomorphic Encryption (PHE): Supports only addition or multiplication
• Somewhat Homomorphic Encryption (SHE): Supports limited operations before noise overwhelms ciphertext
• Fully Homomorphic Encryption (FHE): Supports arbitrary computation on ciphertexts
• Often combined with MPC in hybrid protocols for optimal performance

A mathematical framework that quantifies the privacy leakage from algorithm outputs by adding calibrated noise to results.

• Provides a formal ε (epsilon) privacy budget that bounds information leakage
• Ensures that an adversary cannot determine whether any individual's data was included in the computation
• Complementary to MPC: MPC protects data during computation; differential privacy protects the output
• Used by the US Census Bureau and Apple for privacy-preserving analytics