corrupt-party-additive.ipynb

Kernel: SageMath 10.0

Break: Corrupt Party in Additive Secret Sharing

Module 12 | Breaking Weak Parameters

Show how a single malicious party can bias the output in additive sharing --- and how SPDZ MACs catch them.

Why This Matters

Additive secret sharing (Notebook 12b) splits a secret $s$ into shares $s_1 + s_2 + \cdots + s_n = s$. It has perfect secrecy: any $n - 1$ shares reveal nothing about $s$.

But it has no redundancy. In Shamir sharing with threshold $t < n$, corrupting one share can be detected by checking consistency across subsets. In additive sharing, there is only one "subset" --- all $n$ parties. If any single party modifies their share before the reconstruction step, the corrupted value is silently accepted.

Worse, the malicious party can choose their corruption adaptively: they can shift the output to any value they want, even without knowing the secret.

The Scenario

Three parties hold additive shares of a secret $s$ over $\mathbb{F}_p$. Party 2 is malicious: before the summation step, they add a bias $\delta$ to their share. The reconstructed value becomes $s + \delta$, and the other parties have no way to detect the tampering.

# === Setup: additive sharing helpers (from Notebook 12b) ===

p = 1009
F = GF(p)

def additive_share(secret, n, field):
    """Split secret into n additive shares."""
    p_val = field.order()
    shares = [field(randint(0, p_val - 1)) for _ in range(n - 1)]
    shares.append(field(secret) - sum(shares))
    return shares

def additive_reconstruct(shares):
    """Reconstruct by summing all shares."""
    return sum(shares)

# The secret and sharing parameters
secret = F(42)
n = 3

print(f"Additive ({n},{n}) sharing over F_{p}")
print(f"Secret: s = {secret}")

Step 1: Honest Protocol

All three parties honestly reveal their shares. The sum equals the secret.

# === Step 1: Honest additive reconstruction ===

shares = additive_share(secret, n, F)

print("Shares distributed:")
for i, s in enumerate(shares):
    print(f"  Party {i+1}: s_{i+1} = {s}")

reconstructed = additive_reconstruct(shares)
print(f"\nReconstruction: {' + '.join(str(s) for s in shares)} = {reconstructed} (mod {p})")
print(f"Correct? {reconstructed == secret}")

Step 2: Malicious Party Adds a Bias

Party 2 adds $\delta = 100$ to their share before broadcasting it. The reconstructed value silently shifts from $s$ to $s + \delta$.

# === Step 2: Party 2 cheats by adding delta ===

delta = F(100)
cheating_shares = list(shares)  # copy
cheating_shares[1] = shares[1] + delta  # Party 2 adds bias

print(f"Party 2 adds delta = {delta} to their share")
print(f"  Honest share:   s_2 = {shares[1]}")
print(f"  Cheating share: s_2' = {cheating_shares[1]}")
print()

# Reconstruction with the cheating share
corrupted_result = additive_reconstruct(cheating_shares)

print(f"Reconstruction: {' + '.join(str(s) for s in cheating_shares)} = {corrupted_result} (mod {p})")
print(f"Expected honest result: {secret}")
print(f"Actual result:          {corrupted_result} = {secret} + {delta}")
print(f"\nThe output is silently shifted by delta = {delta}.")

Step 3: The Malicious Party Controls the Output

The attack is even more powerful than it looks. Party 2 can shift the output to any value they want --- even without knowing the secret $s$.

Want the output to be 999? Set $\delta = 999 - s$. But wait, Party 2 doesn't know $s$. That's fine --- they can still shift the output by any relative amount $\delta$, which is devastating in practice (e.g., adding funds to a balance, flipping a vote).

# === Step 3: The cheater can apply ANY bias ===

print("Party 2 tries different biases (secret s = 42):")
print()
for delta_val in [1, -1, 100, -42, 500]:
    d = F(delta_val)
    cheated = list(shares)
    cheated[1] = shares[1] + d
    result = additive_reconstruct(cheated)
    print(f"  delta = {delta_val}: output = {result}  (= {secret} + {d})")

print(f"\nThe cheater has FULL additive control over the output.")
print(f"The other parties see only the final sum, they cannot tell it was tampered.")

Step 4: No Detection Is Possible (Without MACs)

The fundamental problem: in additive sharing, every set of $n$ field elements that sum to some value is a valid sharing of that value. There is no "invalid" share.

Party 1 sees share $s_1$, Party 3 sees share $s_3$. When Party 2 broadcasts $s_2' = s_2 + \delta$, the other parties have no way to know that $s_2'$ was modified --- because $(s_1, s_2', s_3)$ is a perfectly valid sharing of $s + \delta$.

# === Step 4: Demonstrate that corrupted shares look valid ===

# From Party 1 and Party 3's perspective:
# They know their own shares, and they see Party 2's broadcast.
# Is there any statistical test they can run?

print("Can Parties 1 and 3 detect the cheating?")
print()
print(f"Party 1 knows: s_1 = {shares[0]}")
print(f"Party 3 knows: s_3 = {shares[2]}")
print(f"Party 2 broadcasts: s_2' = {cheating_shares[1]}")
print()

# For ANY value v, there exists a valid sharing where s_2 = v
# Specifically: (s_1, v, s - s_1 - v) is a sharing of s
# So Party 2's broadcast of any value is consistent with SOME secret
print("For any value v that Party 2 could broadcast:")
for v in [shares[1], cheating_shares[1], F(0), F(999)]:
    implied_secret = shares[0] + v + shares[2]
    print(f"  s_2 = {v}: implies secret = {implied_secret}")

print(f"\nEvery broadcast value is consistent with some secret.")
print(f"Without additional information, detection is IMPOSSIBLE.")

The Fix: SPDZ-Style MAC Verification

The SPDZ protocol (Notebook 12e) adds a Message Authentication Code to every share. A global MAC key $\alpha$ is shared among all parties. Each share $s_i$ is paired with a MAC share $m_i$ such that $\sum m_i = \alpha \cdot s$.

When a value is opened, parties check: $$\sum_i (m_i - \alpha_i \cdot x) = 0$$

If any party tampered with their share, this check fails with probability $1 - 1/p$. The cheater would need to know $\alpha$ to forge a valid MAC, but no single party knows it.

# === The Fix: SPDZ MAC check ===

def spdz_share(secret, alpha_shares, field):
    """Create a SPDZ sharing: value shares + MAC shares."""
    n_parties = len(alpha_shares)
    alpha = sum(alpha_shares)
    mac = alpha * secret
    x_shares = [field.random_element() for _ in range(n_parties - 1)]
    x_shares.append(secret - sum(x_shares))
    m_shares = [field.random_element() for _ in range(n_parties - 1)]
    m_shares.append(mac - sum(m_shares))
    return list(zip(x_shares, m_shares))

def spdz_open(shares, alpha_shares):
    """Open a SPDZ-shared value with MAC verification."""
    F_local = shares[0][0].parent()
    x = sum(x_i for x_i, _ in shares)
    sigma = sum(m_i - a_i * x for (_, m_i), a_i in zip(shares, alpha_shares))
    if sigma != F_local(0):
        raise ValueError(f"MAC check FAILED (sigma = {sigma})! Cheating detected.")
    return x

# Setup: global MAC key shared among 3 parties
alpha_shares = [F.random_element() for _ in range(n)]
alpha = sum(alpha_shares)
print(f"MAC key shares: {[str(a) for a in alpha_shares]}")
print(f"Global MAC key alpha = {alpha} (no single party knows this!)")
print()

# SPDZ sharing of s = 42
spdz_shares = spdz_share(secret, alpha_shares, F)
print("SPDZ shares (value, MAC):")
for i, (xi, mi) in enumerate(spdz_shares):
    print(f"  Party {i+1}: (x_{i+1} = {xi}, m_{i+1} = {mi})")

# Honest opening works
result = spdz_open(spdz_shares, alpha_shares)
print(f"\nHonest opening: s = {result}")

# === Now Party 2 tries to cheat ===

delta = F(100)
cheating_spdz = list(spdz_shares)
x2_honest, m2_honest = cheating_spdz[1]
cheating_spdz[1] = (x2_honest + delta, m2_honest)  # modify value, keep MAC

print(f"Party 2 adds delta = {delta} to their value share")
print(f"  Honest:  (x_2 = {x2_honest}, m_2 = {m2_honest})")
print(f"  Cheating: (x_2 = {x2_honest + delta}, m_2 = {m2_honest})")
print()

try:
    result = spdz_open(cheating_spdz, alpha_shares)
    print(f"Opening returned: {result} --- THIS SHOULD NOT HAPPEN")
except ValueError as e:
    print(f"CAUGHT: {e}")
    print(f"\nThe MAC check detected the tampering!")
    print(f"Party 2 would need to adjust m_2 by alpha * delta = {alpha * delta},")
    print(f"but they only know alpha_2 = {alpha_shares[1]}, not the full key alpha = {alpha}.")

# === Exercise: Detection rate over many trials ===

detected = 0
trials = 500

for _ in range(trials):
    # Fresh keys and shares each trial
    test_alpha = [F.random_element() for _ in range(n)]
    test_shares = spdz_share(F(42), test_alpha, F)
    
    # Party 2 cheats with a random nonzero bias
    d = F.random_element()
    while d == F(0):
        d = F.random_element()
    cheated = list(test_shares)
    cheated[1] = (test_shares[1][0] + d, test_shares[1][1])
    
    try:
        spdz_open(cheated, test_alpha)
    except ValueError:
        detected += 1

print(f"Cheating detected: {detected}/{trials} ({100*detected/trials:.1f}%)")
print(f"Theoretical: {100*(1 - 1/p):.1f}% (= 1 - 1/{p})")
print(f"\nWith a 256-bit prime, detection probability is essentially 100%.")
print(f"\nWithout MACs (plain additive): 0% detection.")
print(f"With SPDZ MACs: ~100% detection.")
print(f"That is the entire point of SPDZ.")

Summary

Aspect	Detail
Attack	Malicious party adds bias $\delta$ to their additive share before reconstruction
Impact	Output silently shifts from $s$ to $s + \delta$; cheater has full additive control
Detection (plain)	Impossible --- every set of shares summing to some value is a valid sharing
Root cause	Additive sharing has no redundancy and no authentication
Fix	SPDZ MAC: pair each share with a MAC tag; tampering is detected with probability $1 - 1/p$
Real world	SPDZ, MASCOT, Overdrive all use MACs for malicious security

Key takeaway: secret sharing provides privacy (no party learns the secret), but not integrity (no party can be caught cheating). For integrity, you need authentication. SPDZ's MAC-based approach adds minimal overhead to the online phase while providing overwhelming cheating detection.

---

Back to Module 12: Multi-Party Computation