Secure Multi-Party Computation (SMPC)

A foundational cryptographic method that distributes a secret among multiple parties, where each receives a unique share. The original secret can only be reconstructed when a qualified subset of shares is combined. In SMPC, additive secret sharing is commonly used, where the secret is split into random values that sum to the original. No single share reveals any information about the secret, providing information-theoretic security.

• Shamir's Secret Sharing: Uses polynomial interpolation; any t of n shares reconstruct the secret
• Additive Sharing: Splits a value x into random shares x₁, x₂, ..., xₙ where x = Σxᵢ
• Enables parties to compute on data without ever reconstructing the original inputs locally

A two-party secure computation protocol introduced by Andrew Yao in 1986. One party (the garbler) encrypts a boolean circuit gate-by-gate, creating a garbled circuit and corresponding input labels. The second party (the evaluator) obliviously evaluates the circuit using oblivious transfer to obtain their input labels, learning only the final output. The evaluator sees encrypted truth tables and cannot determine the function's intermediate values.

• Constant-round protocol: Communication rounds are independent of circuit depth
• XOR gates can be evaluated for free using the Free-XOR optimization
• Forms the basis for many modern two-party computation frameworks

A fundamental cryptographic protocol where a sender transmits one of potentially many pieces of information to a receiver, but remains oblivious to which piece was selected. The receiver, in turn, learns only the piece they chose and nothing about the others. OT serves as a core building block for garbled circuits and general SMPC protocols.

• 1-out-of-2 OT: Sender has two messages; receiver chooses one without the sender learning which
• OT Extension: Efficiently extends a small number of base OTs into millions of OTs using only symmetric-key operations
• Essential for securely evaluating conditional branches in MPC protocols

A cryptographic method enabling computation directly on ciphertext, producing an encrypted result that, when decrypted, matches the output of operations performed on the plaintext. In SMPC contexts, HE allows one party to encrypt their input and send it to another, who performs computations without ever seeing the raw data. Partially homomorphic encryption supports only addition or multiplication, while fully homomorphic encryption supports arbitrary circuits.

• Additive HE (e.g., Paillier): Enables secure aggregation of encrypted values
• Leveled FHE: Supports circuits of predetermined multiplicative depth
• Often combined with secret sharing in hybrid MPC protocols for efficiency

A protocol where a prover convinces a verifier that a statement is true without revealing any information beyond the validity of the statement itself. In SMPC systems, ZKPs ensure correctness by allowing parties to prove they executed the protocol honestly without exposing their private inputs. This prevents malicious adversaries from poisoning the computation with falsified intermediate results.

• zk-SNARKs: Succinct, non-interactive proofs with fast verification
• Bulletproofs: Short proofs for range statements without trusted setup
• Critical for enforcing malicious security in MPC protocols where parties may deviate arbitrarily

A mathematical framework that injects calibrated statistical noise into computation outputs to prevent the re-identification of individual records. When combined with SMPC, differential privacy provides a dual layer of protection: SMPC hides inputs during computation, while differential privacy ensures the output itself does not leak individual contributions. The privacy budget ε (epsilon) quantifies the maximum information leakage.

• Local DP: Noise added by each party before sharing data
• Global DP: Noise added to the final aggregated result
• Enables privacy-preserving analytics where even the output reveals no single user's data