SPDZ & Arithmetic MPC over Secret Shares

Boolean MPC works on bits (XOR/AND). Arithmetic MPC works on integers or field elements, supporting addition and multiplication directly. Better for ML and statistics applications.

A value x ∈ Z_p is shared as x = x_1 + x_2 + ... + x_n mod p. Addition of shared values is free: each party adds their shares locally. No communication needed.

To multiply shares [a] and [b], parties pre-distribute a Beaver triple ([a_t], [b_t], [c_t]) where c_t = a_t·b_t. Online multiplication uses one round of communication.

SPDZ (Damgård et al. 2012) = "Somewhat Homomorphic Encryption-based Distributed Zero-Knowledge". Offline phase generates authenticated triples via SHE. Online phase is fast additive-share evaluation.

Each share is accompanied by a MAC: MAC(x_i) = α·x mod p where α is a global secret key. This prevents malicious parties from corrupting their shares undetected.

SPDZ offline uses Somewhat Homomorphic Encryption (BGV/BFV). Parties homomorphically multiply their shares to produce authenticated Beaver triples. This phase is compute-intensive but parallelisable.

Given triple ([a],[b],[c]) and inputs [x],[y]: reveal d=x-a and e=y-b (masked, so no info leak). Then [x·y] = [c] + d·[b] + e·[a] + d·e. One round of communication.

MASCOT replaces the SHE offline with OT extension, producing triples faster for small fields. It is the preferred offline for 2-party SPDZ.

Multiple hospitals compute average patient age without sharing records. Each encodes its data as arithmetic shares. SPDZ evaluates sum and count; parties learn only the ratio.

SPDZ-2k (Cramer et al. 2018) extends to Z_{2^k} for machine-learning-friendly fixed-point arithmetic. The MP-SPDZ library benchmarks at 1M multiplications/second over LAN for 2 parties.

Arithmetic MPC uses additive shares over Z_p. Addition is free; multiplication uses Beaver triples in one round. SPDZ adds MACs for malicious security. MASCOT uses OT for fast triple generation. MP-SPDZ brings these to practice.