SPDZ Protocol

SPDZ provides security against active adversaries who may arbitrarily deviate from the protocol. Each secret-shared value is accompanied by a message authentication code (MAC)—a random linear combination held jointly by the parties. Any attempt to cheat during computation corrupts the MAC relationship, causing the protocol to abort with overwhelming probability. This information-theoretic guarantee eliminates reliance on computational assumptions for integrity.

SPDZ separates computation into two phases:

• Preprocessing (offline): Parties generate correlated randomness—Beaver triples, random shared values, and MAC keys—independent of the function inputs
• Online phase: Parties consume preprocessed material to evaluate the circuit using only lightweight operations (addition, scalar multiplication)

This architecture shifts heavy cryptography to the input-independent offline phase, enabling sub-millisecond online multiplication in the arithmetic setting.

SPDZ operates natively over arithmetic circuits modulo a prime p, making it exceptionally efficient for machine learning workloads involving matrix multiplications and dot products. Unlike garbled circuits that require decomposing arithmetic into boolean gates, SPDZ performs additions with zero communication and multiplications with constant-round interaction. This makes it the protocol of choice for secure neural network inference and secure stochastic gradient descent.

The original SPDZ offline phase required somewhat homomorphic encryption (SHE) with high computational cost. The Overdrive protocol variant dramatically improves preprocessing throughput by:

• Using oblivious transfer extensions for triple generation
• Batching SHE operations across many triples simultaneously
• Reducing ciphertext expansion through clever packing techniques

These optimizations make maliciously secure MPC practical for production-scale workloads with hundreds of millions of gates.

Once preprocessing material is generated, the SPDZ online phase achieves information-theoretic security—security that holds against computationally unbounded adversaries. The only cryptographic assumption resides in the offline phase. This property means:

• Online operations are unconditionally secure given correct preprocessing
• No reliance on hardness assumptions during function evaluation
• Post-quantum security in the online phase
• Extremely low computational overhead per gate

Pre-computed, secret-shared multiplication triples that are the primary cryptographic fuel for SPDZ's online phase. Each triple consists of random shares [a], [b], [c] where c = a * b.

• Preprocessing Model: Triples are generated offline, independent of the function or inputs
• Online Efficiency: A single multiplication requires only opening two masked values and local operations
• MACed Triples: In SPDZ, triples are authenticated with information-theoretic MACs to detect cheating
• Consumption Rate: One triple is consumed per multiplication gate in the arithmetic circuit

SPDZ uses information-theoretic MACs on secret-shared values to achieve malicious security. Every shared value [x] is accompanied by a MAC share [m_x] where m_x = α * x for a global secret key α.

• Global Key α: A secret-shared random value unknown to any single party
• MAC Check: After computation, parties open a random linear combination of all opened values and verify the corresponding MACs
• Cheating Detection: Any inconsistency between a value and its MAC reveals tampering with overwhelming probability
• Overhead: Adds one extra secret-shared value per wire in the circuit

Multi-party Arithmetic with Secure Oblivious Transfer — a protocol for generating authenticated Beaver triples using only oblivious transfer as the base primitive, avoiding expensive somewhat homomorphic encryption.

• OT-Based: Uses correlated oblivious transfer extensions for efficient triple generation
• Malicious Security: Achieves active security through MAC authentication on all shares
• Communication Complexity: O(n²) per multiplication gate in the preprocessing phase
• Practical Threshold: Efficient for up to ~100 parties before communication overhead dominates

A family of SPDZ protocols (LowGear, HighGear, TopGear) that use somewhat homomorphic encryption (SHE) for efficient triple generation, dramatically reducing communication at scale.

• LowGear: Optimized for low-latency LAN settings with SHE-based triple production
• HighGear: Balances computation and communication for WAN deployments
• TopGear: Pushes triple generation to a dedicated preprocessing phase for maximum online speed
• SIMD Packing: Encrypts multiple plaintexts in a single ciphertext for amortized efficiency

A variant of SPDZ operating over a mod-2^k ring (typically k=64) rather than a prime field, mapping directly to native CPU integer arithmetic for dramatic speed improvements.

• Native Arithmetic: Eliminates modular reduction overhead of prime fields
• Probabilistic MACs: Uses slightly weaker statistical security (e.g., 2^-40 forgery probability) for practical efficiency
• Truncation: Supports efficient fixed-point arithmetic via probabilistic truncation protocols
• Machine Learning: Particularly well-suited for quantized neural network inference