Secure Multi-Party Computation (SMPC)

The foundational guarantee of SMPC. No party learns anything about another party's private input, except what can be logically inferred from the final, agreed-upon output. This is achieved through secret sharing, where private data is split into mathematically random shares that reveal nothing in isolation. For example, in a private auction, the losing bids remain cryptographically hidden from all participants, including the auctioneer.

The protocol ensures that the computed output is mathematically correct, as if a trusted third party had performed the calculation on the original private inputs. This holds even if a minority of participants are malicious adversaries attempting to deviate from the protocol. Robust schemes like SPDZ and BMR use Message Authentication Codes (MACs) on secret shares to detect and abort any fraudulent computation, preventing a corrupt party from forcing a false result.

A protocol is fair if it is impossible for a malicious adversary to learn the output while preventing honest parties from doing the same. In standard SMPC, fairness is often guaranteed only when a majority of parties are honest. If a corrupt majority exists, they could theoretically abort the protocol after receiving the output. Techniques like gradual release or blockchain-based commitments can enforce fairness by ensuring output delivery is an all-or-nothing event.

SMPC protocols are designed to withstand active (Byzantine) adversaries who can arbitrarily deviate from the protocol specification—sending malformed messages, aborting early, or colluding. This is a stronger model than passive (honest-but-curious) security. Active security is achieved through zero-knowledge proofs and cut-and-choose techniques, which force participants to prove they executed the computation correctly without revealing their secrets.

A critical building block that extends standard secret sharing. VSS allows a dealer to distribute shares of a secret to multiple parties and then prove that the shares are consistent and reconstruct a valid secret, without revealing the secret itself. This prevents a corrupt dealer from distributing invalid shares that would prevent reconstruction. The Feldman VSS scheme uses homomorphic commitments to achieve this verification non-interactively.

A foundational technique for two-party SMPC where a function is represented as a Boolean circuit. One party (the garbler) encrypts the circuit's truth tables, and the other (the evaluator) computes the output using Oblivious Transfer to retrieve only the encrypted keys corresponding to their input. The evaluator learns the final output but sees no intermediate values, and the garbler learns nothing about the evaluator's input. Optimizations like Half-Gates drastically reduce ciphertext size.

A cryptographic scheme enabling computation directly on ciphertexts, generating an encrypted result that matches the output of operations performed on the plaintext. Fully Homomorphic Encryption (FHE) supports arbitrary computation but incurs high computational overhead, while Partially Homomorphic Encryption (PHE) supports only specific operations like addition or multiplication. SMPC often uses homomorphic encryption as a building block for secure linear algebra operations.

A mathematical framework providing a provable guarantee that the output of a computation reveals no information about any single individual's data. It operates by injecting calibrated statistical noise—typically from a Laplace or Gaussian distribution—into query results or model gradients. The privacy budget (epsilon) quantifies the cumulative privacy loss, with lower values offering stronger guarantees. SMPC and differential privacy are complementary: SMPC protects data during computation, while differential privacy protects the output from inference attacks.

The property of a distributed system to reach correct consensus even when an arbitrary subset of nodes behaves adversarially. In the context of SMPC, Byzantine resilience ensures the protocol completes correctly despite malicious parties sending falsified shares or aborting prematurely. Key techniques include:

• Verifiable Secret Sharing (VSS): Ensures dealers distribute consistent shares
• Byzantine Agreement: Guarantees honest nodes agree on a common value
• Robust Aggregation: Filters out malicious gradient updates in federated SMPC settings

A fundamental cryptographic primitive where a sender transmits one of potentially many pieces of information to a receiver, but remains oblivious to which piece was transferred. The receiver learns only their selected message and nothing about the others. 1-out-of-2 Oblivious Transfer is a core building block for SMPC protocols like Garbled Circuits, enabling secure evaluation of AND gates without revealing input values.

A cryptographic protocol introduced by Andrew Yao that enables two parties to jointly evaluate a Boolean circuit over their private inputs. One party (the garbler) encrypts the circuit by assigning random keys to each wire value, while the other party (the evaluator) uses Oblivious Transfer to obtain keys corresponding to their inputs. The evaluator decrypts the circuit gate-by-gate, learning only the final output. This forms the foundation of constant-round two-party SMPC.

A method for distributing a secret among a group of participants, where each receives a share of the secret. The secret can only be reconstructed when a sufficient number of shares—defined by a threshold—are combined. Shamir's Secret Sharing uses polynomial interpolation, where a secret encoded as the constant term of a polynomial of degree t-1 requires t shares for reconstruction. SMPC protocols leverage this to split private inputs across computing parties, ensuring no single party can access the raw data.