Pick a depth. Each prompt opens in your AI pre-loaded with the lesson. Click a row to preview the prompt.
Before any fancy protocol, MPC starts with one building block: a way to cut a secret into pieces such that a subset of pieces reveals nothing. Additive sharing over a prime field Z_p is the simplest version. To share x, pick n−1 uniform random field elements s_1, …, s_{n-1}, set s_n = x − Σs_i. Reconstruction is addition. Any n−1 shares look uniformly random — a strict information-theoretic guarantee, no computational assumption needed. Addition of two shared values is free (add local shares). Multiplication requires an interactive step (Beaver triples, covered in Module 5). Almost every protocol in this course either starts with additive shares or reduces to them.
A clean Python and Rust implementation. Use a prime-order field, not integer modulo, because weird moduli leak. The demo shows 3-out-of-3 sharing (all shares required — i.e., an (n,n) scheme); Module 2 upgrades to Shamir (t,n).
sub_shared and test that reconstruct(sub_shared(share(10), share(3))) == 7. Local subtraction is the same kind of free operation as addition.# Additive (n,n) secret sharing over GF(2^127 - 1) — a Mersenne prime.
import secrets
P = 2**127 - 1 # Mersenne; cheap to reduce, information-theoretically secure.
def share(x: int, n: int) -> list[int]:
assert 0 <= x < P, "secret must fit in the field"
rs = [secrets.randbelow(P) for _ in range(n - 1)]
last = (x - sum(rs)) % P
return rs + [last]
def reconstruct(shares: list[int]) -> int:
return sum(shares) % P
# Free addition: suppose Alice has shares_a and Bob has shares_b for secrets a, b.
# Each party locally adds their share_a[i] + share_b[i] — the result is a valid
# sharing of (a + b) mod P. No communication required.
def add_shared(shares_a: list[int], shares_b: list[int]) -> list[int]:
assert len(shares_a) == len(shares_b)
return [(a + b) % P for a, b in zip(shares_a, shares_b)]
# Self-test
a_shares = share(17, 3)
b_shares = share(25, 3)
c_shares = add_shared(a_shares, b_shares)
assert reconstruct(c_shares) == (17 + 25) % P
print("OK — local addition preserved the sharing invariant.")python3 main.py