12e-spdz-protocol.ipynb

Kernel: SageMath 10.5

Notebook 12e: The SPDZ Protocol

Module 12: Multi-Party Computation

---

Motivating Question. Additive secret sharing lets parties compute on shared values, and Beaver triples handle multiplication. But what if a party cheats, sending a wrong share to bias the output? Can we detect (and abort) when any party deviates from the protocol?

---

Prerequisites. You should be comfortable with:

• Additive secret sharing and Beaver triples (Notebook 12b)

• Oblivious transfer (Notebook 12d)

• Message authentication codes (basic concept)

Learning objectives. By the end of this notebook you will be able to:

1. Explain the offline/online paradigm of SPDZ.

2. Implement SPDZ shares: a value share paired with a MAC share.

3. Perform addition and multiplication on SPDZ shares.

4. Open a shared value with a MAC check that detects cheating.

5. Demonstrate that a malicious party cannot cheat undetected.

1. From Semi-Honest to Malicious Security

Bridge from Notebooks 12a–12d. So far, our secret sharing protocols assumed all parties follow the protocol honestly ("semi-honest" model). In the real world, a party might send incorrect shares to learn extra information or corrupt the output. SPDZ (Damgård, Pastro, Smart, Zakarias, 2012) upgrades to malicious security: any cheating is detected.

The Offline/Online Paradigm

SPDZ splits computation into two phases:

Phase	What happens	Uses
Offline (preprocessing)	Generate Beaver triples + MAC material	Heavy crypto (OT, HE)
Online (computation)	Compute on shares using preprocessed material	Only field operations

The offline phase is expensive but input-independent, it can run before parties even know what they want to compute.

2. SPDZ Shares: Values + MACs

The key idea in SPDZ: every shared value carries a Message Authentication Code (MAC).

Setup: All $n$ parties share a global MAC key $\alpha \in \mathbb{F}_p$. Party $i$ holds $\alpha_i$ with $\alpha = \sum_i \alpha_i$. No party knows $\alpha$ itself.

SPDZ share of $x$: Party $i$ holds a pair $(x_i, m_i)$ where:

• $\sum_i x_i = x$ (additive shares of the value)

• $\sum_i m_i = \alpha \cdot x$ (additive shares of the MAC)

We write $\langle x \rangle$ for a SPDZ-shared value (brackets denote "authenticated sharing").

# Setup: same field as our other Module 12 notebooks
F = GF(1009)
n = 3  # number of parties

# Global MAC key α, shared additively
alpha_shares = [F.random_element() for _ in range(n)]
alpha = sum(alpha_shares)  # no single party knows this!

print(f"Field: GF({F.order()})")
print(f"Parties: {n}")
print(f"MAC key shares: α_0 = {alpha_shares[0]}, α_1 = {alpha_shares[1]}, α_2 = {alpha_shares[2]}")
print(f"Global MAC key: α = {alpha}  (no single party knows this!)")

def spdz_share(secret, alpha_shares, field):
    """Create a SPDZ sharing of a secret.
    
    Returns: list of (value_share, mac_share) tuples, one per party.
    """
    n = len(alpha_shares)
    alpha = sum(alpha_shares)
    mac = alpha * secret  # the MAC on the whole value
    
    # Random additive shares of the value
    x_shares = [field.random_element() for _ in range(n - 1)]
    x_shares.append(secret - sum(x_shares))
    
    # Random additive shares of the MAC
    m_shares = [field.random_element() for _ in range(n - 1)]
    m_shares.append(mac - sum(m_shares))
    
    return list(zip(x_shares, m_shares))

# Share the secret value 42
secret = F(42)
shares = spdz_share(secret, alpha_shares, F)

print(f"Secret: x = {secret}")
print(f"MAC: α·x = {alpha * secret}")
print()
for i, (x_i, m_i) in enumerate(shares):
    print(f"Party {i} holds: (x_{i} = {x_i}, m_{i} = {m_i})")

# Verify
x_reconstructed = sum(x_i for x_i, _ in shares)
mac_reconstructed = sum(m_i for _, m_i in shares)
print(f"\nCheck: Σx_i = {x_reconstructed} (should be {secret}) {'✓' if x_reconstructed == secret else '✗'}")
print(f"Check: Σm_i = {mac_reconstructed} = α·x = {alpha * secret} {'✓' if mac_reconstructed == alpha * secret else '✗'}")

Checkpoint 1. Each SPDZ share is a pair: a value share and a MAC share. The MAC shares sum to $\alpha \cdot x$, where $\alpha$ is a key that no single party knows. This is what makes cheating detectable.

3. Operations on SPDZ Shares

Addition (Local, No Communication)

To compute $\langle x + y \rangle$ from $\langle x \rangle$ and $\langle y \rangle$: each party $i$ locally adds their pairs.

$$\text{Party } i: \quad (x_i + y_i, \; m_i(x) + m_i(y))$$

This works because $\sum(x_i + y_i) = x + y$ and $\sum(m_i(x) + m_i(y)) = \alpha x + \alpha y = \alpha(x + y)$.

def spdz_add(shares_x, shares_y):
    """Add two SPDZ-shared values (local, no communication)."""
    return [(x_i + y_i, mx_i + my_i)
            for (x_i, mx_i), (y_i, my_i) in zip(shares_x, shares_y)]

def spdz_add_const(shares_x, c, alpha_shares):
    """Add a public constant c to a SPDZ-shared value."""
    # Party 0 adds c to their value share
    # Every party adds α_i · c to their MAC share
    result = []
    for i, ((x_i, m_i), a_i) in enumerate(zip(shares_x, alpha_shares)):
        if i == 0:
            result.append((x_i + c, m_i + a_i * c))
        else:
            result.append((x_i, m_i + a_i * c))
    return result

def spdz_mul_const(shares_x, c):
    """Multiply a SPDZ-shared value by a public constant c."""
    return [(c * x_i, c * m_i) for (x_i, m_i) in shares_x]

# Test: ⟨42⟩ + ⟨17⟩ = ⟨59⟩
shares_x = spdz_share(F(42), alpha_shares, F)
shares_y = spdz_share(F(17), alpha_shares, F)
shares_sum = spdz_add(shares_x, shares_y)

result = sum(s for s, _ in shares_sum)
mac_result = sum(m for _, m in shares_sum)
print(f"⟨42⟩ + ⟨17⟩ = ⟨{result}⟩")
print(f"MAC check: Σm_i = {mac_result}, α·59 = {alpha * F(59)} {'✓' if mac_result == alpha * F(59) else '✗'}")

# Test: ⟨42⟩ + 10 = ⟨52⟩
shares_plus_c = spdz_add_const(shares_x, F(10), alpha_shares)
result_c = sum(s for s, _ in shares_plus_c)
mac_c = sum(m for _, m in shares_plus_c)
print(f"\n⟨42⟩ + 10 = ⟨{result_c}⟩")
print(f"MAC check: Σm_i = {mac_c}, α·52 = {alpha * F(52)} {'✓' if mac_c == alpha * F(52) else '✗'}")

Checkpoint 2. Notice that addition and scalar operations are free, no communication needed, and the MAC stays valid. This is just like plain additive sharing from Notebook 12b, but now with authentication.

Multiplication via Beaver Triples

Bridge from Notebook 12b. We saw that multiplying shared values requires Beaver triples $(a, b, c)$ with $c = ab$. In SPDZ, the triple is also authenticated: $\langle a \rangle, \langle b \rangle, \langle c \rangle$ all carry MACs.

To compute $\langle x \cdot y \rangle$:

1. Open $\varepsilon = x - a$ and $\delta = y - b$ (these are random-looking, so they leak nothing)

2. Compute $\langle xy \rangle = \langle c \rangle + \varepsilon \cdot \langle b \rangle + \delta \cdot \langle a \rangle + \varepsilon \delta$

def spdz_beaver_triple(alpha_shares, field):
    """Generate a random Beaver triple in SPDZ format.
    
    In practice, this is the expensive offline phase.
    Here we simulate it with a trusted dealer.
    """
    a = field.random_element()
    b = field.random_element()
    c = a * b
    return (spdz_share(a, alpha_shares, field),
            spdz_share(b, alpha_shares, field),
            spdz_share(c, alpha_shares, field))

# Generate a triple
triple = spdz_beaver_triple(alpha_shares, F)
shares_a, shares_b, shares_c = triple

a_val = sum(s for s, _ in shares_a)
b_val = sum(s for s, _ in shares_b)
c_val = sum(s for s, _ in shares_c)
print(f"Beaver triple: a = {a_val}, b = {b_val}, c = a·b = {c_val}")
print(f"Verify: a·b = {a_val * b_val} = c? {a_val * b_val == c_val}")

def spdz_open(shares_x, alpha_shares):
    """Open a SPDZ-shared value with MAC verification.
    
    All parties reveal their value shares and check the MAC.
    Raises ValueError if a cheating party is detected.
    """
    # Reconstruct the value
    x = sum(x_i for x_i, _ in shares_x)
    
    # MAC check: each party computes σ_i = m_i - α_i · x
    # If honest: Σσ_i = Σm_i - (Σα_i)·x = α·x - α·x = 0
    sigma = sum(m_i - a_i * x
               for (_, m_i), a_i in zip(shares_x, alpha_shares))
    
    if sigma != F(0):
        raise ValueError(f"MAC check FAILED (σ = {sigma})! Cheating detected.")
    
    return x

def spdz_mul(shares_x, shares_y, triple, alpha_shares):
    """Multiply two SPDZ-shared values using a Beaver triple."""
    shares_a, shares_b, shares_c = triple
    
    # Compute [ε] = [x] - [a]  and  [δ] = [y] - [b]
    shares_eps = spdz_add(shares_x, spdz_mul_const(shares_a, F(-1)))
    shares_delta = spdz_add(shares_y, spdz_mul_const(shares_b, F(-1)))
    
    # Open ε and δ (with MAC check!)
    eps = spdz_open(shares_eps, alpha_shares)
    delta = spdz_open(shares_delta, alpha_shares)
    
    # [xy] = [c] + ε·[b] + δ·[a] + ε·δ
    result = shares_c
    result = spdz_add(result, spdz_mul_const(shares_b, eps))
    result = spdz_add(result, spdz_mul_const(shares_a, delta))
    result = spdz_add_const(result, eps * delta, alpha_shares)
    
    return result

# Test: ⟨7⟩ · ⟨6⟩ = ⟨42⟩
shares_x = spdz_share(F(7), alpha_shares, F)
shares_y = spdz_share(F(6), alpha_shares, F)
triple = spdz_beaver_triple(alpha_shares, F)

shares_product = spdz_mul(shares_x, shares_y, triple, alpha_shares)
result = spdz_open(shares_product, alpha_shares)
print(f"⟨7⟩ · ⟨6⟩ = ⟨{result}⟩  (expected 42) {'✓' if result == F(42) else '✗'}")

# Exhaustive test: 20 random multiplications
all_correct = True
for trial in range(20):
    x_val = F.random_element()
    y_val = F.random_element()
    expected = x_val * y_val
    
    sx = spdz_share(x_val, alpha_shares, F)
    sy = spdz_share(y_val, alpha_shares, F)
    t = spdz_beaver_triple(alpha_shares, F)
    
    sp = spdz_mul(sx, sy, t, alpha_shares)
    result = spdz_open(sp, alpha_shares)
    
    if result != expected:
        print(f"FAIL: {x_val} · {y_val} = {result}, expected {expected}")
        all_correct = False

print(f"20 random multiplications: {'all correct ✓' if all_correct else 'FAILURES'}")

4. Detecting Cheating

Here's the key question: what happens if a party lies during the opening phase?

Suppose Party 0 sends $x_0' = x_0 + \Delta$ instead of their real share $x_0$. The reconstructed value becomes $x' = x + \Delta$. But the MAC check computes:

$$\sigma = \sum_i m_i - \sum_i \alpha_i \cdot x' = \alpha x - \alpha(x + \Delta) = -\alpha \Delta$$

Since Party 0 doesn't know $\alpha$, they can't adjust their MAC share to compensate. The check catches the cheat!

# Honest opening: everything works
honest_shares = spdz_share(F(42), alpha_shares, F)
result = spdz_open(honest_shares, alpha_shares)
print(f"Honest opening: x = {result} ✓")

# Cheating: Party 0 modifies their value share
cheating_shares = list(honest_shares)  # copy
x0_honest, m0_honest = cheating_shares[0]
delta = F(5)  # Party 0 adds 5 to their share
cheating_shares[0] = (x0_honest + delta, m0_honest)  # MAC not updated!

print(f"Party 0 changes their share from {x0_honest} to {x0_honest + delta}")
print(f"Party 0 hopes to make the output x + {delta} = {F(42) + delta}")
print()

try:
    result = spdz_open(cheating_shares, alpha_shares)
    print(f"Opening returned: {result}  ← THIS SHOULD NOT HAPPEN")
except ValueError as e:
    print(f"CAUGHT: {e}")
    print(f"\nThe cheater can't fix the MAC without knowing α = {alpha}.")
    print(f"They only know their share α_0 = {alpha_shares[0]}.")

# How likely is it that cheating goes undetected?
# The cheater needs -α·Δ = 0, which means α·Δ = 0.
# Since Δ ≠ 0 and we're in a field, α·Δ = 0 iff α = 0.
# Probability: 1/p = 1/1009 ≈ 0.1%

detected = 0
trials = 1000
for _ in range(trials):
    # Fresh MAC key each time
    test_alpha = [F.random_element() for _ in range(n)]
    sh = spdz_share(F(42), test_alpha, F)
    
    # Party 0 cheats with random Δ
    cheat = list(sh)
    d = F.random_element()
    while d == F(0):
        d = F.random_element()
    cheat[0] = (sh[0][0] + d, sh[0][1])
    
    try:
        spdz_open(cheat, test_alpha)
    except ValueError:
        detected += 1

print(f"Cheating detected in {detected}/{trials} trials ({100*detected/trials:.1f}%)")
print(f"Expected detection rate: {100*(1 - 1/1009):.1f}% (= 1 - 1/p)")
print(f"\nWith a 256-bit prime, detection probability ≈ 1 - 2^(-256) ≈ 100%")

Misconception alert. "Can't the cheater just also adjust their MAC share?" They could try, but they'd need to subtract $\alpha \cdot \Delta$ from their MAC share. Computing $\alpha \cdot \Delta$ requires knowing $\alpha$, but the cheater only knows their own share $\alpha_i$, not the full MAC key.

5. Complete Computation: $f(x, y) = x \cdot y + x$

Let's put it all together. Three parties compute $f(x, y) = x \cdot y + x$ where:

• Party 0 inputs $x = 7$

• Party 1 inputs $y = 6$

• Expected result: $7 \cdot 6 + 7 = 49$

# Fresh MAC key for this computation
alpha_shares = [F.random_element() for _ in range(n)]

# Offline phase: generate one Beaver triple (for the multiplication)
print("=== Offline Phase ===")
triple = spdz_beaver_triple(alpha_shares, F)
print("Beaver triple generated ✓")
print()

# Online phase: parties provide inputs
print("=== Online Phase ===")
x_val, y_val = F(7), F(6)
shares_x = spdz_share(x_val, alpha_shares, F)
shares_y = spdz_share(y_val, alpha_shares, F)
print(f"Party 0 inputs x = {x_val}")
print(f"Party 1 inputs y = {y_val}")
print()

# Step 1: Multiply x * y
print("Step 1: Compute ⟨x·y⟩ via Beaver triple...")
shares_xy = spdz_mul(shares_x, shares_y, triple, alpha_shares)
print("  Multiplication done (opened ε and δ, MAC checks passed) ✓")

# Step 2: Add x
print("Step 2: Compute ⟨x·y + x⟩ = ⟨x·y⟩ + ⟨x⟩...")
shares_result = spdz_add(shares_xy, shares_x)
print("  Addition done (local, no communication) ✓")

# Step 3: Open the result
print("Step 3: Open the result with MAC check...")
result = spdz_open(shares_result, alpha_shares)
print(f"  MAC check passed ✓")
print()
print(f"Result: f({x_val}, {y_val}) = {x_val}·{y_val} + {x_val} = {result}")
print(f"Expected: {x_val * y_val + x_val}")
print(f"Correct? {result == x_val * y_val + x_val}")

Checkpoint 3. Count the communication rounds in the computation above: opening $\varepsilon$ and $\delta$ (one round), then opening the final result (one round). That's two rounds for the online phase, regardless of how complex the additions are.

6. The Offline Phase

We've been using a trusted dealer to generate Beaver triples. In real SPDZ, the offline phase uses cryptographic protocols to generate authenticated triples without any trusted party:

Method	Idea	Performance
Somewhat HE (original SPDZ)	Encrypt shares with homomorphic encryption; multiply under encryption	Moderate
OT-based (MASCOT, 2016)	Use oblivious transfer to create correlated randomness	Faster
Overdrive (2018)	Optimized HE-based preprocessing	Fastest for large batches

Bridge from Notebook 12d. OT extension (millions of OTs from 128 base OTs) makes the OT-based approach practical. The MASCOT protocol generates one authenticated triple using roughly $O(\kappa)$ OTs per party, where $\kappa$ is the security parameter.

The beauty of the offline/online split: all the expensive crypto happens before the inputs are known. The online phase is blazingly fast, just field arithmetic.

7. Semi-Honest vs. Malicious Security

Property	Plain Additive Sharing (12b)	SPDZ
Shares	Value only: $x_i$	Value + MAC: $(x_i, m_i)$
Addition	Local (free)	Local (free)
Multiplication	Beaver triple	Beaver triple + MAC
Opening	Just sum shares	Sum shares + MAC check
Security model	Semi-honest	Malicious (with abort)
Cheating detection	None	MAC fails with prob $1 - 1/p$
Offline cost	Trusted dealer	OT / HE protocols

"Malicious with abort" means: if any party cheats, honest parties detect it and abort. The cheater doesn't learn the output either. This is the strongest practical security notion for MPC.

Crypto foreshadowing. SPDZ and its variants (SPDZ2k, Overdrive, MP-SPDZ) are the backbone of real-world MPC deployments: private machine learning (training on combined datasets without sharing data), secure auctions (computing the winning bid without revealing losing bids), and threshold cryptography (distributed key generation for blockchain wallets).

8. Exercises

Exercise 1 (Worked): Cheating During Multiplication

Problem. Show that if a party cheats when opening $\varepsilon = x - a$ during a multiplication, the MAC check catches it.

Solution:

# Exercise 1: Cheating during the epsilon opening in multiplication

alpha_shares_ex = [F.random_element() for _ in range(n)]
shares_x = spdz_share(F(7), alpha_shares_ex, F)
shares_y = spdz_share(F(6), alpha_shares_ex, F)
triple = spdz_beaver_triple(alpha_shares_ex, F)
shares_a, shares_b, shares_c = triple

# Compute [ε] = [x] - [a] honestly
shares_eps = spdz_add(shares_x, spdz_mul_const(shares_a, F(-1)))

# Party 0 tampers with their epsilon share before opening
tampered_eps = list(shares_eps)
tampered_eps[0] = (shares_eps[0][0] + F(3), shares_eps[0][1])  # add 3

print("Party 0 tampers with ε share (adds 3)...")
try:
    eps = spdz_open(tampered_eps, alpha_shares_ex)
    print(f"Opened ε = {eps}  ← should not reach here")
except ValueError as e:
    print(f"CAUGHT: {e}")
    print(f"\nThe MAC on ε = (x - a) was computed honestly.")
    print(f"Tampering with the value share breaks the MAC relationship.")
    print(f"Multiplication aborted safely, no incorrect output produced.")

Exercise 2 (Guided): Compute $f(x, y, z) = x \cdot y + z$

Problem. Three parties each provide one input. Compute $f(x, y, z) = x \cdot y + z$ using SPDZ.

Hint: you need one Beaver triple (for $x \cdot y$) and one addition (adding $z$).

# Exercise 2: fill in the TODOs
alpha_shares_ex2 = [F.random_element() for _ in range(n)]
x_val, y_val, z_val = F(5), F(8), F(13)
expected = x_val * y_val + z_val

# TODO: Create SPDZ shares of x, y, z
# shares_x = spdz_share(x_val, alpha_shares_ex2, F)
# shares_y = spdz_share(y_val, alpha_shares_ex2, F)
# shares_z = spdz_share(z_val, alpha_shares_ex2, F)

# TODO: Generate a Beaver triple for the multiplication
# triple = spdz_beaver_triple(alpha_shares_ex2, F)

# TODO: Compute ⟨x·y⟩ using spdz_mul
# shares_xy = spdz_mul(shares_x, shares_y, triple, alpha_shares_ex2)

# TODO: Add z to get ⟨x·y + z⟩
# shares_result = spdz_add(shares_xy, shares_z)

# TODO: Open and verify
# result = spdz_open(shares_result, alpha_shares_ex2)
# print(f"f({x_val}, {y_val}, {z_val}) = {result} (expected {expected})")

Exercise 3 (Independent): How Many Triples?

Problem.

1. How many Beaver triples are needed to compute $f(x, y) = x^2 + 2xy + y^2$ using SPDZ? Can you reduce this by rewriting the expression?

2. Implement the computation using SPDZ and verify your answer.

3. In general, if a function has $d$ multiplications, how many Beaver triples and communication rounds does the online phase need?

# Exercise 3: write your solution here

Summary

Concept	Key Fact
SPDZ shares	Each value has paired MAC shares: $(x_i, m_i)$ with $\sum m_i = \alpha \cdot x$
MAC key	Global $\alpha$ shared additively, no single party knows it
Addition	Local, free, MAC stays valid automatically
Multiplication	Beaver triple + open $\varepsilon, \delta$ (all MAC-checked)
Opening	Reveal shares, verify $\sum(m_i - \alpha_i \cdot x) = 0$
Cheating detection	Tampering breaks MAC with probability $1 - 1/p \approx 1$
Offline/online split	Expensive triple generation before inputs; cheap online phase

SPDZ achieves malicious security with abort: any cheating party is caught, and the protocol halts before producing an incorrect output. Combined with secret sharing (12a–12b), garbled circuits (12c), and oblivious transfer (12d), this completes our tour of the fundamental building blocks of secure multi-party computation.

---

This is the final notebook in the series. Congratulations on completing all 12 modules, from modular arithmetic to multi-party computation!