Secure Multi-Party Computation: Privacy-Preserving Collaborative Computation

Secure Multi-Party Computation (MPC) is a cryptographic protocol that allows multiple parties to jointly compute a function over their private inputs while revealing only the output. Each party learns nothing about other parties' inputs beyond what can be inferred from the output.

Secure Multi-Party Computation: Privacy-Preserving Collaborative Computation

Secure Multi-Party Computation (MPC) is a cryptographic protocol that enables multiple parties to jointly compute a function over their private inputs without revealing those inputs to each other. Each party learns only the final output of the computation, and nothing about other parties' inputs beyond what can be inferred from that output. MPC solves the fundamental problem of how to collaborate on data analysis, fraud detection, or auctions without requiring participants to share sensitive information.

To understand MPC properly, it helps to be familiar with secret sharing, public key cryptography, and zero-knowledge proofs.

Secure MPC overview:

┌─────────────────────────────────────────────────────────────────────────┐
│                   Secure Multi-Party Computation (MPC)                    │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│   Party A (input x) ──┐                                                 │
│   Party B (input y) ──┼───── MPC Protocol ─────► Output f(x, y, ...)   │
│   Party C (input z) ──┘            │                                     │
│                                    │                                     │
│                                    ▼                                     │
│                         Each party learns ONLY the output               │
│                         Nothing about other inputs                       │
│                                                                          │
│   Example: Two millionaires want to know who is richer without          │
│            revealing their actual net worth.                            │
│                                                                          │
│   Traditional Approach:     MPC Approach:                               │
│   ┌───────────────────┐     ┌───────────────────────────────────────┐   │
│   │ A tells B wealth  │     │ A and B run MPC protocol              │   │
│   │ B reveals their   │     │ Each learns only comparison result    │   │
│   │ wealth inequality │     │ Neither learns exact values           │   │
│   └───────────────────┘     └───────────────────────────────────────┘   │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

What Is Secure Multi-Party Computation?

Secure Multi-Party Computation is a subfield of cryptography that enables multiple parties to jointly compute a function over their private inputs without revealing those inputs. The protocol ensures correctness (the output is correct) and privacy (no party learns more than the output). MPC can be used for any function that can be expressed as a circuit: addition, comparison, machine learning models, database queries, and more.

Privacy: Each party's input remains confidential. Only the final output is revealed. Nothing about intermediate values is disclosed.
Correctness: The output is guaranteed to be correct, assuming honest majority (or malicious security). Parties cannot deviate from protocol to produce incorrect output.
Fairness: All parties receive output, or none do. (Not always required, depends on protocol).
Independence: Parties' inputs are independent. No party can influence another's input.
Adversary Models: Honest-but-curious (semi-honest): parties follow protocol but try to learn extra info. Malicious (active): parties may deviate arbitrarily from protocol (harder).

Why Secure MPC Matters

Organizations have valuable data but cannot share it due to privacy regulations, competitive concerns, or confidentiality requirements. MPC enables collaboration without data sharing.

Privacy Regulations (GDPR, HIPAA, CCPA): Healthcare data cannot be shared across institutions (HIPAA restricts patient data sharing). Financial data subject to confidentiality agreements. MPC allows analysis without violating regulations.
Fraud Detection Across Banks: Individual banks cannot see each other's transactions (competitive sensitivity). MPC detects fraudulent patterns across institutions without sharing transaction details. Reduces false positives using combined data.
Private Set Intersection (PSI): Two companies find common customers without revealing non-overlapping customers. Used for ad targeting, fraud detection, contact discovery.
Secret Auctions / Bidding: Bids remain secret until auction closes. MPC computes winner and price without revealing individual bids. No trusted auctioneer needed.
Machine Learning on Encrypted Data: Multiple hospitals train a model on combined patient data without sharing raw records. Privacy-preserving medical research. Model training and inference on encrypted inputs.
Threshold Cryptography (Key Generation): DKG is a special case of MPC (generating random secret). Threshold signatures use MPC to sign without reconstructing key.

MPC applications examples:

Application                    Inputs                      Output
─────────────────────────────────────────────────────────────────────────────
Private Set Intersection       Party A: set S_A            Intersection S_A ∩ S_B
                               Party B: set S_B
Secure Auction                 Parties: bids               Winner and price
Private average                Party i: salary             Average salary
Fraud detection                Party i: transactions       Fraud probability
Private genome analysis        Party i: genetic data       Disease risk
Joint machine learning         Party i: training data      Model parameters

MPC Protocol Families

Semi-honest

Protocol Method Round Complexity Communication Adversary Model

Garbled Circuits (GC) Boolean circuits + encryption 2 rounds High (per gate) Semi-honest (malicious extensions)

Secret Sharing (SS) Additive or Shamir sharing 1 round (linear) / multiple (non-linear) Moderate Semi-honest

Oblivious Transfer (OT)

Cryptographic primitive (building block) 2-3 roundsSemi-honest / malicious

Moderate	Semi-honest / malicious
GMW (Goldreich-Micali-Wigderson)	GC + OT combining	Per gate (linear)	High (circuit size)
SPDZ (Damgård-Pastor)	Secret sharing + MACs ограничењимаOffline/online phases	Moderate to high	Malicious (actively secure)

Protocol comparison:

Protocol        Best For                      Complexity      Active Security
─────────────────────────────────────────────────────────────────────────────
Garbled Circuits   Boolean circuits (2-party)   High (gates)    Extensions exist
Secret Sharing     Arithmetic (n-party)          Low (linear ops) No (without MAC)
SPDZ               Malicious n-party             High (offline)  Yes (MACs)
GMW                General purpose (2-party)     High (OTs)      Extensions exist
BGW (BGW)          n-party, honest majority      Moderate        No (honest majority)

Secret Sharing Based MPC

In secret sharing MPC, inputs are split into shares and distributed among parties. Computation proceeds locally on shares, and final shares are reconstructed to reveal output.

Additive secret sharing (2 parties, honest-but-curious):

Setup: Party A has x, Party B has y, want to compute x + y

Protocol:
  1. A chooses random r, sends r to B
  2. A keeps (x - r)
  3. Shares: A: [x] = x - r, B: [x] = r
  4. Each party shares their input similarly
  5. Locally compute [x + y] = [x] + [y]
  6. Parties reveal shares to reconstruct sum

Properties:
  • No single party learns x or y (only shares)
  • XOR for boolean circuits (instead of addition)
  • Multiplication requires interaction (Beaver triples)

Multiplication with Beaver triples (precomputed):

Precomputation (offline):
  Generate random a, b, c such that c = a × b
  Distribute shares [a], [b], [c] to parties

Online multiplication (x × y):
  Each party computes:
    [d] = [x] - [a]
    [e] = [y] - [b]

  Reveal d, e (shares reconstructed)
  Each party computes:
    [z] = [c] + d·[b] + e·[a] + d·e

  Result: z = x × y (with privacy)

Why it works: (d = x - a, e = y - b)
  x·y = (a + d)·(b + e) = a·b + d·b + e·a + d·e

Garbled Circuits (Two-Party Computation)

Garbled circuits are the most efficient method for two-party computation where one party (garbler) encrypts a boolean circuit, and the other (evaluator) evaluates it without learning intermediate values.

Yao's Garbled Circuit (2-party):

Phase 1: Garbling (Party A):
  For each wire in circuit:
    • Choose two random keys (k_0 for 0, k_1 for 1)
  For each gate (AND, OR, XOR):
    • Encrypt truth table: Enc_k_a0( Enc_k_b0( k_c0 ) ), etc.
    • Permute rows (free XOR optimization makes XOR gates free)
  Send garbled circuit to Party B

Phase 2: Oblivious Transfer (Party B gets input keys):
  • Party A has keys for its inputs (knows which values)
  • Party B gets keys for its inputs via OT (doesn't reveal bits)
  • B learns only the keys corresponding to its bits

Phase 3: Evaluation (Party B):
  • Decrypt gates sequentially (only one row decrypts correctly)
  • Obtain output keys
  • Map output keys to output bits (via output decoding table)

Result: B learns output, not A's inputs (except derived from output)

Oblivious Transfer (OT)

Oblivious Transfer is a fundamental MPC primitive where a sender has two messages, and a receiver chooses one without revealing choice. The sender doesn't know which message was selected.

**1-out-of-2 OT:** Receiver gets m_choice but learns nothing about the other message. Sender learns nothing about which message was chosen.

**Uses in MPC:** Garbled circuits (receiver obtains input wire keys). Multiplication protocols. Building block for higher-level MPC.

OT role in Garbled Circuits:

Party A (Garbler)                Party B (Evaluator)
      │                                    │
      │  Knows: k_0, k_1 for each wire    │  Knows: input bits
      │  Creates garbled circuit          │
      │                                    │
      │──── Garbled Circuit ──────────────→│
      │                                    │
      │  For each wire of B's input:       │
      │    (k_0, k_1)                      │
      │                                    │
      │←──── OT Protocol ─────────────────→│
      │                                    │
      │                                    │  Gets k_bit for bit
      │                                    │  (learns only that key)
      │                                    │
      │                                    │  Evaluates circuit
      │                                    │
      │←──── Output ───────────────────────│

SPDZ (Malicious Security)

SPDZ is the state-of-the-art protocol for actively secure MPC for any number of parties. It uses secret sharing with information-theoretic Message Authentication Codes (MACs) to detect cheating.

Offline Phase (precomputation): Generate Beaver triples and MAC keys (independent of inputs).

Online Phase: Compute function using precomputed triples (very fast). MAC verification ensures correctness, even if parties are malicious. Active security: parties cannot deviate from protocol undetected.

SPDZ architecture:

Offline Phase (one-time preprocessing):
  ┌─────────────────────────────────────────────────────────────────────┐
  │  Generate Beaver triples ([a], [b], [c]) with MACs                  │
  │  Distribute shares and MAC keys to all parties                     │
  │  (Independent of inputs, can be reused for many computations)      │
  └─────────────────────────────────────────────────────────────────────┘

Online Phase (per function):
  ┌─────────────────────────────────────────────────────────────────────┐
  │  1. Parties input shares of their data (with MACs)                  │
  │  2. Compute linear operations locally (addition)                   │
  │  3. Compute multiplications using Beaver triples (interactive)     │
  │  4. MAC verification on outputs (detects cheating)                 │
  │  5. Reveal outputs (if MACs valid)                                 │
  └─────────────────────────────────────────────────────────────────────┘

Security: Malicious parties detected with high probability.

Private Set Intersection (PSI)

PSI is a special case of MPC where two parties find the intersection of their sets without revealing non-overlapping elements. Applications: contact discovery (find friends without exposing all contacts). Fraud detection (common customers across banks). Adtech (common audiences).

DH-based PSI (2-party):

Setup: Party A has set S_A, Party B has set S_B

Protocol:
  1. A sends {H(x)^a for all x in S_A} to B
  2. B computes { (H(x)^a)^b } = H(x)^(ab) for all x in S_A
  3. B computes { H(y)^b for all y in S_B }
  4. B sends both lists to A
  5. A computes { (H(y)^b)^a } = H(y)^(ab) for all y in S_B
  6. A compares and finds matches (same H(·)^(ab))

Result: A learns intersection size and elements
        B learns nothing

Properties:
  • Efficient: O(|S_A| + |S_B|) exponentiations
  • Only works for two parties
  • DH assumption

MPC Anti-Patterns

Rolling Your Own MPC Protocol: Extremely difficult to get correct (vulnerable to subtle privacy leaks). Even academic protocols often have hidden assumptions. Use established libraries (MP-SPDZ, libOTe, MOTION).
Assuming Honest Majority with Malicious Parties: Honest majority is not enough for malicious security (parties can deviate). Use active security (SPDZ) for adversarial environments. Honest-but-curious is unrealistic for competitive settings.
Large Communication Overhead Ignored: Garbled circuits for large functions have huge overhead (gates). Secret sharing with non-linear ops requires interaction (multiplication rounds). Estimate communication before deployment.
No Input Validation: Malicious parties can provide out-of-range inputs (invalid shares). Always verify inputs before computation. Use zero-knowledge proofs for range checks.
Ignoring Output Privacy: Output may reveal more than intended (e.g., average reveals sum, which reveals individual if n small). Consider differential privacy on outputs. Anonymize aggregate results.

MPC pitfalls checklist:

[X] Custom implementation of MPC (use libraries)
[X] Assuming honest-but-curious in adversarial settings
[X] Ignoring communication costs (size of circuit)
[X] No input validation (out-of-range values)
[X] No output privacy (aggregates revealing individuals)

[✓] Use established MPC framework (MP-SPDZ, MOTION)
[✓] Malicious security for untrusted participants
[✓] Precompute offline phase (Beaver triples)
[✓] Validate input ranges with ZK proofs
[✓] Apply differential privacy to outputs

MPC Best Practices

Use Established Frameworks: MP-SPDZ (C++, Python APIs), MOTION (C++, OT-based), libOTe (OT primitives), OpenMined (Python, PySyft). These implement state-of-the-art protocols, manage communication and optimize performance.
Choose Appropriate Security Model: Honest-but-curious for internal audits (parties follow protocol). Malicious security for competitive environments (banks, auctions). Covert security (if cheating is detected, but no penalty).
Precompute Offline Phase (Beaver Triples): Precomputation independent of inputs (can be done ahead of time). Online phase is fast (only linear work). Suitable for repeated computations (e.g., model training).
Optimize Circuit Representation: Use arithmetic circuits for arithmetic operations (cheaper). Use boolean circuits for comparisons, bitwise ops. Minimize non-linear gates (multiplication, comparisons).
Test with Small Scale First: Test 2-party, small input size, small circuit. Measure communication, runtime, memory usage. Validate correctness and privacy (inputs not revealed).

MPC framework selection guide:

Requirement                          Recommended Framework
─────────────────────────────────────────────────────────────────────────────
2-party, semi-honest                 libOTe + custom circuit
2-party, malicious                   libOTe + OT extension
n-party, semi-honest                  MP-SPDZ (semi-honest mode)
n-party, malicious                    MP-SPDZ (SPDZ)
High-level language (Python)          MP-SPDZ (Python interface)
Research / prototyping                MP-SPDZ, MOTION
Machine learning (encrypted)          CrypTen (PyTorch), PySyft

Popular MPC Libraries and Frameworks

Framework	Language	Protocols	Security
MP-SPDZ	C++ / Python	SPDZ, MASCOT, Overdrive	Malicious (actively secure)
MOTION	C++	Garbled circuits, OT, secret sharing	Semi-honest / malicious
libOTe	C++	OT extensions, base OTs	Semi-honest / malicious

CrypTen Python (PyTorch) Secret sharing Semi-honest

PySyft (OpenMined) Python Secret sharing, PSI

Frequently Asked Questions

What is the difference between MPC and FHE (Fully Homomorphic Encryption)?
MPC involves multiple parties interacting during computation. FHE is a single party computing on encrypted data (no interaction). MPC supports arbitrary parties, lower overhead. FHE supports arbitrary functions (theoretically), but impractical. MPC is more mature and efficient for many-party settings.
How many parties can MPC support?
SPDZ supports up to 20-50 parties in practice (communication overhead grows quadratically). Garbled circuits are primarily 2-party. Secret sharing MPC scales to thousands with honest majority. Scalable MPC (e.g., BRISTOL) is an active research area for 100+ parties.
Is MPC quantum-safe?
Many MPC protocols rely on OT and public-key crypto (RSA, ECC) not quantum-safe. Post-quantum MPC uses lattice-based OT or code-based crypto. Active research ongoing; not yet production-ready for most use cases.
Can MPC handle machine learning models?
Yes, but training large models requires optimization (linear operations are cheap, non-linear like ReLU require interaction). Inference is more feasible. CrypTen (PyTorch) supports MPC for ML models.
What is the communication overhead for MPC?
Proportional to circuit size (gates). Garbled circuits: O(|circuit|) encryption. Secret sharing: O(|circuit|) communication per multiplication. Large circuits (e.g., AES) can require gigabytes network.
What should I learn next after MPC?
After mastering MPC, explore secret sharing (Shamir, additive), oblivious transfer (OT), garbled circuits (Yao), SPDZ protocol internals, Distributed Key Generation (DKG), and Private Set Intersection (PSI).

Secure Multi-Party Computation: Privacy-Preserving Collaborative Computation