So Cramer’s rule is just Lagrange interpolation in disguise, and this note spells out the MPC/secret-sharing angle?
12 comments
> So Cramer’s rule is just Lagrange interpolation in disguise
Only in the narrow sense that both are closed forms for the same linear system, and the interpolation matrix usually has to be Vandermonde-like for the formulas to line up. Calling it “in disguise” makes it sound more general than it is, the determinant identity is the real content here.
> So Cramer’s rule is just Lagrange interpolation in disguise
Only after you pick a Vandermonde basis, not generally.
> Only after you pick a Vandermonde basis, not generally.
Yep, that part is the right constraint. But I think “basis” undersells it, the whole trick is the evaluation map, and once you’re there the interpolation formula is the coordinate expression, not some deep second theorem wearing a fake mustache (as nadiah said, the determinant identity is the invariant thing anyway).
The evaluation map bit is the one that feels like Shamir 1979, not some new theorem, since reconstruction is just the Lagrange coordinates after you’ve committed to those sample points. The only place it gets less tautological is when you try to move from the 1D Vandermonde case to anything messier, then the nice Cramer-looking determinant story stops being the whole picture.
> Only after you pick a Vandermonde basis, not generally.
And even then it only stays clean in 1D, the multivariate case is where the paper is glossing over the hard part, since there isnt a single canonical node set or basis that makes the inverse look like textbook Lagrange. Once you move off tensor-product grids, the “same formula” story stops being an identity and turns into a choice of representation, which is exactly where the MPC/security proofs start depending on the interpolation model.
> the determinant identity is the real content here
No, the basis change is. The determinant formula is just what falls out after you pick evaluation points and write the inverse in coordinates, which is why the Vandermonde case looks magical and the generic case does not.
Calling that “just a linear system” hides the tree-shaped part, the recursive structure is what makes the secret-sharing angle worth caring about.
> the basis change is
no, the determinant identity is the invariant statement, basis choice is bookkeeping.
> The determinant identity is invariant, but it is not the full story here
Sure, but the invariant only becomes usable after you pin down the evaluation map, because that is what turns the abstract matrix statement into Lagrange coefficients. Without that choice, “basis-free” is just hiding where the structure lives.
In the MPC case that matters, because the protocol cost is set by whether reconstruction stays as one recursive evaluation tree or collapses into a dense solve.
If the secret-sharing/MPC angle is the point, does this mean Shamir reconstruction is literally just the same Lagrange formula being used on shares instead of interpolation points, or is there a real extra step hiding there?
> is there a real extra step hiding there?
Yes: in Shamir, the shares are just evaluations of a random low-degree polynomial, and reconstruction is the Lagrange formula on those points, but the security comes from the random coefficients and the threshold choice, not from the interpolation itself. Calling it “the same formula” is fine, but it hides the real MPC step, which is the secret is encoded as a polynomial value and the other coefficients are fresh entropy.
> security comes from the random coefficients and threshold choice
no, the security proof is the extra step, not the polynomial costume.
> security proof is the extra step, not the polynomial costume.
Sure, but if your paper spends pages admiring the costume and never says what the model is, the proof is doing all the actual work. In Shamir, the interpolation identity is the easy algebra, the only nontrivial part is the entropy argument that says the shares leak nothing up to degree t - 1, which is one linear-algebra lemma, not a grand theorem.
And for MPC the gap gets bigger, because reconstruction is the boring piece, while robustness, consistency, and adversary thresholds are where the design lives. Calling that “just interpolation” is the sort of slogan that sounds deep until you try to implement it.