Implementing Secure Multi-Party Computation

Overview

Secure Multi-Party Computation (SMPC) enables multiple parties to jointly compute a function over their combined inputs while keeping each party's individual input private. No party learns anything beyond the output of the computation and what can be inferred from their own input and the output.

SMPC supports GDPR Article 5(1)(c) data minimization by eliminating the need to centralize data, Article 25(1) data protection by design by building privacy into the computation architecture, and Article 26 joint controller arrangements by enabling collaborative analytics without data sharing.

Core SMPC Techniques

Shamir Secret Sharing

Shamir's Secret Sharing (1979) splits a secret value into n shares such that any t shares can reconstruct the secret (threshold t-out-of-n), but fewer than t shares reveal no information.

Properties:

• Information-theoretic security (unbreakable regardless of computational power)
• Supports addition of shared values without communication
• Multiplication requires an interactive protocol (Beaver triples or resharing)

Application: Splitting personal data across multiple servers such that no single server (or coalition below threshold) can reconstruct the data.

Garbled Circuits

Yao's Garbled Circuits (1986) enable two-party computation. One party (the garbler) encrypts a boolean circuit; the other party (the evaluator) evaluates the encrypted circuit without learning intermediate values.

Properties:

• Constant-round protocol (efficient for high-latency networks)
• Communication cost proportional to circuit size
• Best for two-party computation with complex boolean functions

Oblivious Transfer

Oblivious Transfer (OT) is a protocol where a sender has multiple messages and a receiver selects one message to receive, without the sender learning which message was selected and without the receiver learning the other messages.

Role in SMPC: OT is the foundational building block for garbled circuit evaluation and is used for input wire labels in Yao's protocol.

SMPC Frameworks

Framework	Protocol	Language	Security Model	Best For
MP-SPDZ	Multiple (SPDZ, MASCOT, semi-honest, malicious)	Python-like DSL	Semi-honest and malicious	Research and prototyping with multiple security models
CrypTen	Secret sharing (2-party and 3-party)	Python (PyTorch)	Semi-honest	ML inference and training on shared data
MOTION	GMW, BMR, arithmetic/boolean sharing	C++	Semi-honest	High-performance 2+ party computation
ABY/ABY3	Arithmetic, Boolean, Yao sharing	C++	Semi-honest (2-party ABY, 3-party ABY3)	Mixed-protocol computation (switching between share types)
Sharemind	Additive secret sharing (3-party)	SecreC (DSL)	Semi-honest (honest majority)	Enterprise deployment with managed infrastructure

MP-SPDZ Protocol Selection

Protocol	Security Model	Parties	Preprocessing	Online Performance
SPDZ/MASCOT	Malicious (dishonest majority)	2+	Heavy (OT-based)	Fast online phase
Semi2k	Semi-honest (dishonest majority)	2+	Moderate	Fast
Shamir	Semi-honest (honest majority)	3+	Light	Very fast
Rep3	Semi-honest (honest majority)	3	None	Very fast
MASCOT	Malicious (dishonest majority)	2+	OT-based	Moderate
Yao's GC	Semi-honest	2	Garbling	Fast evaluation

Architecture for GDPR-Compliant SMPC

┌─────────────────────────────────────────────────────────────┐
│                  SMPC Computation Coordinator                │
│              (orchestrates protocol execution)               │
└──────┬─────────────────┬─────────────────┬──────────────────┘
       │                 │                 │
┌──────▼──────┐  ┌───────▼──────┐  ┌──────▼──────┐
│  Party A    │  │  Party B     │  │  Party C    │
│  (Bank)     │  │  (Insurer)   │  │  (Retailer) │
│             │  │              │  │             │
│ Input: x_A  │  │ Input: x_B   │  │ Input: x_C  │
│ Share: [x_A]│  │ Share: [x_B] │  │ Share: [x_C]│
│             │  │              │  │             │
│ Compute on  │  │ Compute on   │  │ Compute on  │
│ local share │  │ local share  │  │ local share │
└──────┬──────┘  └───────┬──────┘  └──────┬──────┘
       │                 │                 │
       └────────────────►│◄────────────────┘
                         │
                  ┌──────▼──────┐
                  │  Output:    │
                  │  f(x_A,x_B, │
                  │    x_C)     │
                  │  (revealed  │
                  │   to all)   │
                  └─────────────┘

Each party learns ONLY the final output f(x_A, x_B, x_C),
NOT the individual inputs of other parties.

Practical Deployment Patterns

Pattern 1: Private Set Intersection (PSI)

Two parties determine which records they have in common without revealing records unique to either party.

Use case: A bank and an insurer identify shared customers for a joint risk assessment without revealing their full customer lists.

Step	Action	Privacy Guarantee
1	Each party hashes their customer identifiers with a shared key	Individual identifiers not revealed
2	Parties engage in PSI protocol (DH-based or OT-based)	Only intersection elements revealed
3	For matched records, proceed with joint computation on shared data	Non-matched records remain private

Pattern 2: Private Aggregation

Multiple parties compute aggregate statistics (sum, mean, count) over their combined data without revealing individual contributions.

Use case: Three regional offices of Prism Data Systems AG compute total headcount and average salary without revealing per-office figures.

Pattern 3: Private ML Training

Multiple parties jointly train a machine learning model using SMPC to protect training data during the process.

Use case: Using CrypTen, two hospitals jointly train a logistic regression model on encrypted patient features.

Performance Considerations

Factor	Impact	Mitigation
Network latency	SMPC is communication-intensive; high latency increases total time	Co-locate computation nodes; use constant-round protocols (Yao) for WAN
Data size	Communication scales with input size	Pre-aggregate locally where possible; use sketching
Circuit complexity	Deeper circuits require more communication rounds (for GMW)	Optimize circuit depth; use Yao for constant rounds
Number of parties	More parties = more communication pairs	Use 3-party protocols with honest majority for efficiency
Security model	Malicious security is 10-100x slower than semi-honest	Use semi-honest for trusted consortium members; reserve malicious for adversarial settings

Implementation Workflow

1. Define the computation — Express the joint function as arithmetic or boolean operations.
2. Select security model — Semi-honest if all parties are trusted (e.g., consortium members); malicious if adversarial behavior is possible.
3. Select framework — Choose MP-SPDZ for flexibility, CrypTen for ML workloads, Sharemind for managed enterprise.
4. Implement protocol — Write the computation in the framework's DSL, test on synthetic data.
5. Benchmark — Measure end-to-end latency, communication volume, and memory usage.
6. Deploy — Establish secure communication channels (mTLS), key distribution, and monitoring.
7. Govern — Execute joint controller agreement (Art. 26), update Article 30 records, document in DPIA.

Key Regulatory References

• GDPR Article 5(1)(c) — Data minimization (no data centralization needed)
• GDPR Article 25(1) — Data protection by design
• GDPR Article 26 — Joint controller arrangements for SMPC consortia
• GDPR Article 28 — Processor obligations (SMPC coordinator role)
• GDPR Article 32(1) — Security measures
• GDPR Recital 78 — Technical measures for data protection
• ENISA Report: Data Protection Engineering (2022)