Difficulty: Intermediate to Advanced | Prerequisites: Modular arithmetic, basic probability, polynomial algebra, familiarity with interactive proof concepts.
This material sits at the intersection of cryptography and complexity theory, near the end of a typical EECS 376 term. The core question: how can a group of people compute a joint result (like the sum of their salaries) without anyone revealing their private input? The tools here, secure multi-party computation (MPC) and secret sharing via polynomial interpolation, form the backbone of modern privacy-preserving protocols. You should already be comfortable with modular arithmetic over prime fields and with the idea that a degree-k polynomial is pinned by k + 1 points.
Secure multi-party computation lets several parties jointly compute a function of their private inputs without revealing any single input. Shamir's secret sharing hides a secret as the constant term of a random polynomial, distributing points to shareholders. Recovering the secret requires enough shareholders to reconstruct the unique polynomial via Lagrange interpolation.
Secure multi-party computation (MPC)
A protocol allowing n parties to jointly compute a function f(x₁, x₂, …, xₙ) over their private inputs, such that each party learns only the output and nothing else about the others' inputs.
In simple terms, this means a group can calculate something together (e.g. their total salary) without anyone having to show their cards.
Joint view (transcript)
The complete collection of messages a subset of participants can see during and after a protocol run.
Think of it as everything a coalition of players could write down on a whiteboard from their own perspective.
Simulatability (security test)
A protocol is secure for a coalition if those parties could generate their entire joint view from only their own inputs and the output, without needing the other parties' inputs.
In simple terms, if you can fake the transcript on your own, the protocol leaked nothing useful.
Shamir's secret sharing
A scheme that encodes a secret s as the constant term (f(0) = s) of a random polynomial of degree k − 1 over a prime field, then distributes points (xᵢ, f(xᵢ)) to shareholders. Any k points suffice to reconstruct s; fewer than k reveal nothing.
Think of it as hiding a number inside a curve that only enough friends, pooling their points together, can trace back to the origin.
Lagrange interpolation
A method for reconstructing the unique polynomial of degree < k that passes through k given points. Each basis polynomial Lⱼ(x) equals 1 at xⱼ and 0 at every other xᵢ.
In simple terms, it is the standard recipe for fitting exactly one smooth curve through a set of dots.
Polynomial uniqueness over a prime field
Over ℤₚ (integers mod a prime p), a nonzero polynomial of degree at most k − 1 can have at most k − 1 zeros. Therefore k points uniquely determine a polynomial of degree < k.
Think of it as: once you pin down enough dots on the curve, there is exactly one curve that hits them all.
Four parties (Graham, Mark, Clayton, Rashmika) each hold a private salary sᵢ. The goal: compute s_total = s₁ + s₂ + s₃ + s₄ without revealing any individual salary.
Graham + Clayton conspire: Clayton receives r + s₁ + s₂ from the protocol. Graham knows r + s₁. Subtracting yields s₂ (Mark's salary). Once they know s₁, s₂, s₃ and s_total, they recover s₄. The protocol is broken for this coalition.
Rashmika + Graham conspire: They learn only s₂ + s₃, the sum of Mark and Clayton's salaries. No individual salary is exposed, so the protocol remains secure for this pair.
Graham and Mark's joint view is (r, s₁, t, s₂, u) where t = s₁ + r and u = s_total + r.
Given only their own inputs (s₁, s₂) and the allowed output (s_total), they can pick a random r and reconstruct the entire transcript.
Because the transcript can be simulated without Clayton or Rashmika, the protocol leaks nothing beyond what the output itself reveals.
The formal test: any machine M that runs on the real transcript could equally well run on the simulated one.
All arithmetic is performed modulo a large prime. This ensures that the random value r uniformly masks the underlying values, so an adversary with partial information cannot infer the rest by, say, bounding the range of salaries.
The dealer holds a secret s and chooses a random polynomial f of degree k − 1 with f(0) = s, all arithmetic mod a prime p.
The dealer evaluates f at k − 1 distinct nonzero points x₁, …, x_{k−1} and hands share (xᵢ, f(xᵢ)) to shareholder i.
Any k shareholders can pool their points, reconstruct f by Lagrange interpolation, and compute f(0) = s.
Fewer than k shareholders hold fewer points than the polynomial's degree plus one, so every possible secret is equally consistent with what they see.
For any secret s and any (k − 1)-tuple of shares, the point (0, s) plus the k − 1 share-points give k points total.
A polynomial of degree < k is determined by k points: suppose two polynomials f₁ and f₂ agree on all k points. Then g(x) = f₁(x) − f₂(x) has degree ≤ k − 1 and k zeros.
Over ℤₚ, a nonzero polynomial of degree k − 1 has at most k − 1 zeros. Having k zeros forces g(x) = 0, so f₁ = f₂.
Consequence: given any set of k − 1 shares, for every possible secret value s there is exactly one polynomial passing through all the points. This is what makes the scheme information-theoretically secure for coalitions smaller than k.
Lagrange basis polynomial (general form)
L_j(x) = \prod_{\substack{m=1 \\ m \neq j}}^{k} \frac{x - x_m}{x_j - x_m}Each Lⱼ equals 1 at xⱼ and 0 at every other sample point.
Reconstructing the polynomial from k shares
f(x) = \sum_{j=1}^{k} y_j \, L_j(x)where (xⱼ, yⱼ) are the k known points. The secret is f(0).
Simulatability condition (informal)
A coalition C's view is secure if there exists a simulator Sim such that for all inputs:
Sim(inputs of C, output) produces a distribution indistinguishable from C's real transcript.
Secure multi-party computation underpins privacy-preserving auctions (bidders submit encrypted bids, and only the winner and price are revealed), secure voting protocols, and joint financial benchmarking where competing firms compare aggregate statistics without sharing raw data. Shamir's secret sharing is used in key management systems: a master encryption key is split among several officers so that no single person can decrypt sensitive data alone, but any quorum of them can.
Students often think that learning the sum of two salaries counts as a security breach. It does not: any protocol that outputs the total necessarily lets a pair infer the sum of the other pair's salaries. Security means learning nothing beyond what the output implies.
Students sometimes believe that any two colluding parties can break the salary protocol. Only certain coalitions are dangerous; others (like Rashmika + Graham in problem 12.1) learn nothing individual.
A common error is assuming that k − 1 shares of a secret leak partial information about the secret. They do not. For every possible secret value, there is a consistent polynomial, so k − 1 shares are information-theoretically useless.
Students occasionally confuse polynomial uniqueness with interpolation difficulty. The polynomial is unique with k points regardless of whether you use Lagrange, Gaussian elimination, or any other method. Uniqueness is a mathematical fact; interpolation is a computational procedure.
⚠️ Be ready to argue that a coalition's view is simulatable. The exam may give you a different protocol and ask whether a specific pair of parties can learn an individual input.
⚠️ Know the uniqueness proof cold: two polynomials agreeing on k points, difference polynomial has too many zeros, forced to be identically zero. This is a standard short-answer or proof question.
⚠️ Understand why arithmetic must be mod a prime. Over the integers, the range of values can leak information. The prime field makes every residue equally likely.
⚠️ Be prepared to state the threshold property of Shamir's scheme: exactly k shares needed, k − 1 are useless.
True or false: If two parties in a four-party salary protocol learn the sum of the other two salaries, the protocol is insecure. (False: the output itself reveals this.)
Fill in the blank: A polynomial of degree at most k − 1 over ℤₚ has at most ______ zeros. (k − 1)
True or false: With k − 1 shares in Shamir's scheme, an adversary can narrow down the secret to a smaller set of possible values. (False: every value of s is equally consistent.)
Fill in the blank: The Lagrange basis polynomial Lⱼ(xⱼ) = ______ and Lⱼ(xₘ) = ______ for m ≠ j. (1; 0)
True or false: Simulatability means the coalition can predict the other parties' inputs. (False: it means the coalition can generate its own view without the other parties, not that it learns their inputs.)
Q: In the salary-sum protocol, why does the collusion of Graham and Clayton break security while the collusion of Rashmika and Graham does not?
A: Graham knows r + s₁ and Clayton receives r + s₁ + s₂. Subtracting gives s₂ directly. From there, knowing s₁, s₂, s₃, and s_total, they recover s₄. By contrast, Rashmika and Graham together see only s₂ + s₃, which reveals no individual salary.
Q: Prove that a (k − 1)-tuple of shares uniquely determines the polynomial for any given secret s.
A: The k − 1 shares plus the point (0, s) give k points. Two polynomials of degree < k agreeing on all k points would have a difference polynomial of degree ≤ k − 1 with k zeros. Over ℤₚ, this forces the difference to be identically zero, so the polynomials are equal.
Q: Explain intuitively why k − 1 shares reveal no information about the secret in Shamir's scheme.
A: For any candidate secret value s', there exists exactly one polynomial of degree < k passing through all k − 1 share points and through (0, s'). Since every secret is equally consistent with the observed shares, the shares carry zero information about which secret was actually chosen.
Q: What role does the prime modulus play in ensuring security?
A: Working mod p ensures that intermediate values like r + s₁ are uniformly distributed over ℤₚ regardless of the actual value of s₁. Over the integers, the magnitude of the sum could leak information about the inputs.
Secure multi-party computation connects directly to zero-knowledge proofs (covered in the companion doc on problems 12.3 and 12.4): both ask how much information a protocol reveals beyond its intended output. Shamir's secret sharing also appears in threshold cryptography and distributed key generation, which extend the ideas here to real-world systems like multi-signature wallets. The polynomial uniqueness argument over prime fields recurs anywhere finite-field arithmetic is used, including error-correcting codes (Reed-Solomon codes are built on the same interpolation machinery).
Secure multi-party computation, MPC, secret sharing, Shamir's secret sharing, threshold scheme, polynomial interpolation, Lagrange interpolation, Lagrange basis polynomials, polynomial uniqueness, prime field, ℤₚ, modular arithmetic, simulatability, transcript simulation, joint view, collusion, coalition security, information-theoretic security, EECS 376, foundations of computer science, University of Michigan