12b-secret-sharing-additive.ipynb

Kernel: SageMath 10.5

Notebook 12b: Additive Secret Sharing

Module 12: Multi-Party Computation

---

Motivating Question. Shamir's scheme is powerful but complex, it uses polynomial interpolation and works with thresholds. Is there a simpler secret sharing scheme? Additive secret sharing is the simplest possible: split a secret into random pieces that sum to it. The trade-off: all parties must participate to reconstruct.

---

Prerequisites. You should be comfortable with:

• Shamir secret sharing and its threshold property (Notebook 12a)

• Modular arithmetic (Module 01)

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

1. Split a secret into $n$ additive shares.

2. Implement XOR-based sharing for binary data.

3. Perform addition and scalar multiplication on shared values.

4. Understand why multiplication requires communication.

5. Compare additive and Shamir sharing.

1. Additive Sharing: The Simplest Scheme

Bridge from Notebook 12a. Shamir uses degree-$(t-1)$ polynomials to achieve $(t, n)$ thresholds. Additive sharing is the special case $t = n$: all parties must collaborate. The upside: it's trivially simple and very efficient.

The idea:

• Secret $s \in \mathbb{F}_p$

• Pick $s_1, s_2, \ldots, s_{n-1} \xleftarrow{$} \mathbb{F}_p$ uniformly at random

• Set $s_n = s - (s_1 + s_2 + \ldots + s_{n-1})$

• Reconstruct: $s = s_1 + s_2 + \ldots + s_n$

This is an $(n, n)$ scheme, you need all $n$ shares to recover the secret.

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)

# Split secret 42 among 5 parties
secret = 42
n = 5
shares = additive_share(secret, n, F)

print(f"=== Additive Secret Sharing ===")
print(f"Secret: s = {secret}")
print(f"Shares:")
for i, s in enumerate(shares):
    print(f"  Party {i+1}: s_{i+1} = {s}")
print(f"\nSum: {' + '.join(str(s) for s in shares)} = {sum(shares)} (mod {p})")
print(f"Correct? {additive_reconstruct(shares) == F(secret)}")

# Security: any n-1 shares reveal nothing
print("=== Security of Additive Sharing ===")
print(f"\nSuppose parties 1-4 collude (miss party 5):")
print(f"They know: {[str(s) for s in shares[:4]]}")
print(f"They need: s_5 = {shares[4]}")
print()
print(f"But s_5 = s - (s_1 + s_2 + s_3 + s_4) mod {p}")
print(f"Without knowing s, s_5 could be anything in F_{p}.")
print()

# Show that different secrets are consistent with the same 4 shares
partial_sum = sum(shares[:4])
for guess in [0, 1, 42, 100, 500]:
    missing = F(guess) - partial_sum
    print(f"  If s = {guess}: s_5 would be {missing} (consistent with known shares)")

print(f"\nEvery secret is equally likely, information-theoretic security!")

Checkpoint 1. Additive sharing is an $(n, n)$ scheme: all shares are needed. Each individual share looks uniformly random, knowing $n-1$ shares gives zero information about the secret. The simplicity comes at a cost: no threshold flexibility.

2. XOR-Based Sharing (Binary)

For binary data (bits, byte strings), we can use XOR instead of addition mod $p$. XOR is just addition in $\mathbb{F}_2$.

def xor_share(secret_byte, n):
    """Split a byte into n XOR shares."""
    shares = [randint(0, 255) for _ in range(n-1)]
    last = secret_byte
    for s in shares:
        last ^^= s  # XOR
    shares.append(last)
    return shares

def xor_reconstruct(shares):
    """Reconstruct by XORing all shares."""
    result = 0
    for s in shares:
        result ^^= s
    return result

# Share a byte
secret_byte = 0b10101010  # 170
xor_shares = xor_share(secret_byte, 4)

print(f"=== XOR Secret Sharing ===")
print(f"Secret: {secret_byte} = {bin(secret_byte)}")
print(f"\nShares (binary):")
for i, s in enumerate(xor_shares):
    print(f"  Party {i+1}: {s} = {bin(s):>10s}")
print(f"\nXOR of all shares: {xor_reconstruct(xor_shares)} = {bin(xor_reconstruct(xor_shares))}")
print(f"Correct? {xor_reconstruct(xor_shares) == secret_byte}")

# Share a full string
message = "Hello!"
msg_bytes = [ord(c) for c in message]
n_parties = 3

# Share each byte
all_shares = [xor_share(b, n_parties) for b in msg_bytes]

print(f"Message: '{message}'")
print(f"\nShares per byte (3 parties):")
for char_idx, char in enumerate(message):
    shares_str = [f"{all_shares[char_idx][j]}" for j in range(n_parties)]
    print(f"  '{char}' ({ord(char)}): {' | '.join(shares_str)}")

# Reconstruct
reconstructed = ''.join(chr(xor_reconstruct([all_shares[i][j] for j in range(n_parties)])) for i in range(len(message)))
print(f"\nReconstructed: '{reconstructed}'")
print(f"\nEach party's shares look like random bytes, no information about the message.")

3. Operations on Additive Shares

Like Shamir, additive shares support local addition: each party adds their shares independently.

If $[a] = (a_1, \ldots, a_n)$ and $[b] = (b_1, \ldots, b_n)$, then $[a+b] = (a_1+b_1, \ldots, a_n+b_n)$.

# Addition on shared values
a, b = 42, 17
shares_a = additive_share(a, 3, F)
shares_b = additive_share(b, 3, F)

# Each party adds locally
shares_sum = [shares_a[i] + shares_b[i] for i in range(3)]

print(f"a = {a}, b = {b}")
print(f"Expected: a + b = {(a + b) % p}")
print(f"\nLocal addition (no communication):")
for i in range(3):
    print(f"  Party {i+1}: {shares_a[i]} + {shares_b[i]} = {shares_sum[i]}")
print(f"\nReconstructed sum: {additive_reconstruct(shares_sum)}")
print(f"Correct? {additive_reconstruct(shares_sum) == F(a + b)}")

# Scalar multiplication: also local
scalar = F(7)
shares_scaled = [scalar * s for s in shares_a]
print(f"Scalar multiply: {scalar} × {a} = {scalar * F(a)}")
print(f"Reconstructed: {additive_reconstruct(shares_scaled)}")
print(f"Correct? {additive_reconstruct(shares_scaled) == scalar * F(a)}")
print()

# Adding a public constant: only one party adds it
c = F(100)
shares_plus_c = list(shares_a)
shares_plus_c[0] = shares_plus_c[0] + c  # only party 1 adds c
print(f"Add public constant: {a} + {c} = {F(a) + c}")
print(f"Reconstructed: {additive_reconstruct(shares_plus_c)}")
print(f"Correct? {additive_reconstruct(shares_plus_c) == F(a) + c}")
print(f"\nOnly ONE party needs to add a public constant (not all of them).")

Checkpoint 2. Additive sharing supports free (no-communication) addition and scalar multiplication. Adding a public constant requires only one party to act. These are the same properties as Shamir, but simpler.

4. The Multiplication Problem

Multiplication is where things get hard. If parties hold $[a] = (a_1, a_2)$ and $[b] = (b_1, b_2)$, can they compute $[a \cdot b]$ locally?

$$(a_1 + a_2)(b_1 + b_2) = a_1 b_1 + a_1 b_2 + a_2 b_1 + a_2 b_2$$

Party 1 can compute $a_1 b_1$ but not $a_1 b_2$ (they don't know $b_2$). Multiplication requires communication between parties.

# Demonstrate the multiplication problem (2-party case)
a, b = F(5), F(7)
a1, a2 = F(randint(0, p-1)), None
a2 = a - a1
b1, b2 = F(randint(0, p-1)), None
b2 = b - b1

print(f"=== The Multiplication Problem ===")
print(f"a = {a}, b = {b}, a·b = {a*b}")
print(f"\nParty 1 knows: a_1 = {a1}, b_1 = {b1}")
print(f"Party 2 knows: a_2 = {a2}, b_2 = {b2}")
print(f"\na·b = (a_1+a_2)(b_1+b_2) = a_1·b_1 + a_1·b_2 + a_2·b_1 + a_2·b_2")
print(f"    = {a1*b1} + {a1*b2} + {a2*b1} + {a2*b2}")
print(f"    = {a1*b1 + a1*b2 + a2*b1 + a2*b2}")
print()
print(f"Party 1 can compute: a_1·b_1 = {a1*b1}")
print(f"Party 2 can compute: a_2·b_2 = {a2*b2}")
print(f"But CROSS terms (a_1·b_2, a_2·b_1) need data from the other party!")
print(f"\nNaive approach: share a_1 with Party 2 and b_2 with Party 1.")
print(f"But this REVEALS the secret! We need something cleverer → Beaver triples.")

5. Beaver Triples: Multiplication Without Revealing Inputs

A Beaver triple $(\alpha, \beta, \gamma)$ is a pre-computed triple of random values where $\gamma = \alpha \cdot \beta$, shared among all parties. Using a triple, parties can compute $[a \cdot b]$ from $[a]$ and $[b]$ with minimal communication:

1. Open $\epsilon = a - \alpha$ and $\delta = b - \beta$ (these are random, so they reveal nothing)

2. Each party computes: $[a \cdot b] = [\gamma] + \epsilon \cdot [\beta] + \delta \cdot [\alpha] + \epsilon \cdot \delta$

Why? $a \cdot b = (\epsilon + \alpha)(\delta + \beta) = \epsilon\delta + \epsilon\beta + \delta\alpha + \alpha\beta = \epsilon\delta + \epsilon\beta + \delta\alpha + \gamma$

def beaver_multiply(shares_a, shares_b, shares_alpha, shares_beta, shares_gamma, field):
    """Multiply two shared values using a Beaver triple.
    
    Returns shares of a*b.
    """
    n_parties = len(shares_a)
    
    # Step 1: Compute and open epsilon = a - alpha, delta = b - beta
    shares_eps = [shares_a[i] - shares_alpha[i] for i in range(n_parties)]
    shares_del = [shares_b[i] - shares_beta[i] for i in range(n_parties)]
    
    epsilon = sum(shares_eps)  # opened (all parties learn this)
    delta = sum(shares_del)    # opened (all parties learn this)
    
    # Step 2: Each party computes their share of a*b
    # [a*b] = [gamma] + epsilon * [beta] + delta * [alpha] + epsilon * delta
    shares_product = []
    for i in range(n_parties):
        share_i = shares_gamma[i] + epsilon * shares_beta[i] + delta * shares_alpha[i]
        if i == 0:  # only one party adds the public term
            share_i += epsilon * delta
        shares_product.append(share_i)
    
    return shares_product, epsilon, delta

# Generate a Beaver triple
alpha = F(randint(0, p-1))
beta = F(randint(0, p-1))
gamma = alpha * beta

n = 3
shares_alpha = additive_share(alpha, n, F)
shares_beta = additive_share(beta, n, F)
shares_gamma = additive_share(gamma, n, F)

print(f"Beaver triple: (α, β, γ) = ({alpha}, {beta}, {gamma})")
print(f"Check: α·β = {alpha}·{beta} = {alpha*beta} = γ ✓")
print(f"Triple is shared among {n} parties (no one knows the full triple).")

# Use the Beaver triple to multiply a = 5, b = 7
a, b = 5, 7
shares_a = additive_share(a, n, F)
shares_b = additive_share(b, n, F)

shares_prod, eps, dlt = beaver_multiply(
    shares_a, shares_b, shares_alpha, shares_beta, shares_gamma, F
)

result = additive_reconstruct(shares_prod)

print(f"a = {a}, b = {b}")
print(f"Expected: a·b = {F(a)*F(b)}")
print(f"\nOpened values (random, reveal nothing about a or b):")
print(f"  ε = a - α = {eps} (random because α is random)")
print(f"  δ = b - β = {dlt} (random because β is random)")
print(f"\nReconstructed product: {result}")
print(f"Correct? {result == F(a) * F(b)}")
print(f"\nOne Beaver triple consumed per multiplication.")

Misconception alert. "Opening $\epsilon$ and $\delta$ leaks the inputs." No! Since $\alpha$ and $\beta$ are uniformly random and unknown, $\epsilon = a - \alpha$ and $\delta = b - \beta$ are also uniformly random, they carry no information about $a$ or $b$.

6. Shamir vs Additive: Comparison

print("="*65)
print("Shamir vs Additive Secret Sharing")
print("="*65)
print()

comparison = [
    ("Threshold", "(t, n), flexible", "(n, n), all required"),
    ("Reconstruction", "Lagrange interpolation", "Simple summation"),
    ("Share generation", "Polynomial evaluation", "Random + adjustment"),
    ("Addition", "Local (free)", "Local (free)"),
    ("Scalar multiply", "Local (free)", "Local (free)"),
    ("Secret multiply", "Degree doubles → reshare", "Beaver triples"),
    ("Security", "Information-theoretic", "Information-theoretic"),
    ("Used in", "MPC (GMW, BGW)", "MPC (SPDZ, ABY)"),
]

for label, shamir, additive in comparison:
    print(f"  {label:.<22s} Shamir: {shamir}")
    print(f"  {'':22s} Additive: {additive}")
    print()

Crypto foreshadowing. The SPDZ protocol (Notebook 12e) uses additive secret sharing as its foundation. Beaver triples are generated in an offline preprocessing phase, then consumed during online computation. This separation makes the online phase extremely fast.

7. Exercises

Exercise 1 (Worked): Inner Product

Problem. Compute the inner product $\langle \mathbf{a}, \mathbf{b} \rangle = a_1 b_1 + a_2 b_2$ on additively shared vectors, using two Beaver triples.

Solution:

# Exercise 1: Worked solution
n_parties = 3
a_vec = [F(3), F(5)]
b_vec = [F(7), F(2)]
expected = sum(a_vec[i] * b_vec[i] for i in range(2))  # 3*7 + 5*2 = 31

# Share each element
shares_a = [additive_share(a_vec[i], n_parties, F) for i in range(2)]
shares_b = [additive_share(b_vec[i], n_parties, F) for i in range(2)]

# Two Beaver triples for two multiplications
products = []
for k in range(2):
    alpha_k = F(randint(0, p-1))
    beta_k = F(randint(0, p-1))
    gamma_k = alpha_k * beta_k
    sh_alpha = additive_share(alpha_k, n_parties, F)
    sh_beta = additive_share(beta_k, n_parties, F)
    sh_gamma = additive_share(gamma_k, n_parties, F)
    prod_shares, _, _ = beaver_multiply(shares_a[k], shares_b[k], sh_alpha, sh_beta, sh_gamma, F)
    products.append(prod_shares)

# Sum the products locally
inner_shares = [products[0][i] + products[1][i] for i in range(n_parties)]
result = additive_reconstruct(inner_shares)

print(f"a = {[str(x) for x in a_vec]}, b = {[str(x) for x in b_vec]}")
print(f"Inner product: {a_vec[0]}·{b_vec[0]} + {a_vec[1]}·{b_vec[1]} = {expected}")
print(f"Computed on shares: {result}")
print(f"Correct? {result == expected}")
print(f"Used 2 Beaver triples (one per multiplication).")

Exercise 2 (Guided): Comparison Protocol

Problem. Two parties each have a value. They want to know if their values are equal without revealing them. Use additive sharing: share both values, compute the difference, and check if it's zero.

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# TODO 1: Alice has value a = 42, Bob has value b = 42 (or try b = 43)
# alice_val = F(42)
# bob_val = F(42)

# TODO 2: Share each value among 2 parties
# shares_alice = additive_share(alice_val, 2, F)
# shares_bob = additive_share(bob_val, 2, F)

# TODO 3: Compute shares of the difference locally
# shares_diff = [shares_alice[i] - shares_bob[i] for i in range(2)]

# TODO 4: Open the difference (both parties reveal their diff shares)
# diff = additive_reconstruct(shares_diff)
# print(f"Difference: {diff}")
# print(f"Equal? {diff == F(0)}")
# Note: this reveals whether values are equal but not the values themselves
# (if diff ≠ 0, it also reveals the exact difference, a more careful
#  protocol would randomize: open r*(a-b) for random r, checking if zero)

Exercise 3 (Independent): Multi-Party Sum

Problem.

1. Five parties each have a private salary. Use additive sharing so they can compute the average salary without anyone learning individual values.

2. Implement this: each party creates shares of their value and distributes one share to each other party. Then all parties sum their received shares and broadcast the result.

3. Why doesn't this reveal individual salaries even though the average is public?

# Exercise 3: write your solution here

Summary

Concept	Key Fact
Additive sharing	$s = s_1 + s_2 + \ldots + s_n$; all $n$ shares needed
XOR sharing	Same idea for binary: $s = s_1 \oplus s_2 \oplus \ldots \oplus s_n$
Addition	Local: each party adds their shares (no communication)
Multiplication	Needs Beaver triples: open random masks, compute locally
Beaver triple	Pre-shared $(\alpha, \beta, \gamma)$ with $\gamma = \alpha\beta$; one per multiplication
vs Shamir	Simpler but no threshold flexibility (all-or-nothing)

Additive sharing trades threshold flexibility for simplicity. Combined with Beaver triples for multiplication, it forms the foundation of efficient MPC protocols like SPDZ.

---

Next: 12c: Yao's Garbled Circuits