Adi Shamir 2026-11-05
Adi Shamir introduced a polynomial-interpolation construction for threshold secret sharing in 1979. In Shamir's secret sharing, a secret is the constant term of a random polynomial of degree less than over a finite field; shares are its values at distinct nonzero field elements. Any shares recover the polynomial and hence the secret.[ref]
How to Share a Secret by Adi Shamir. pp.612–613
Fewer than shares leave every possible secret equally compatible when the other coefficients are uniformly random. This is an information-theoretic threshold guarantee, rather than a claim that recovering the secret merely takes a long time. The construction makes distributed authorization and resilience to missing shares compatible. It requires enough field elements for all distinct share positions.
Adi Shamir, portrait published by the Weizmann Institute
. Past exam of the mathematics course of the University of Cambridge 2010 ii Paper 2 12H Solution Created 2026-09-24 Updated 2026-10-14
The Vandermonde determinant isIndeed, the determinant is an alternating polynomial, hence divisible by every . Both sides have degree , and comparison of the coefficient of gives constant one. This is an identity over the integers, so reducing its coefficients modulo a prime number preserves it. For , two residues coincide and the determinant vanishes. For , choose all elements of once to obtain a nonzero determinant.
For the ordering , this determinant is . If is odd, put . Wilson theorem gives . Pairing the factors with indices and , and leaving unpaired, givesEvery distinct ordering changes the determinant by its permutation sign; repeated residues give zero. Thus the possible values are for odd , and for .
Use Shamir's secret sharing: choose independent uniform , and engrave the shares , where and the are distinct nonzero field elements. We may take ; otherwise use a sufficiently large finite field extension and an agreed integer encoding. Any shares determine by polynomial interpolation and hence . Given any shares and any proposed , their equations in the coefficients have a unique solution: the coefficient matrix has determinant times a nonzero Vandermonde determinant. Since the coefficients were uniform, the observed shares have the same distribution for every . Thus they give no information about the secret.
For the fake, reduce its integers to field elements and first check that its abscissa is distinct and nonzero. Random collisions or a zero abscissa are immediately detectable and have probability ; the following conclusions concern the overwhelmingly likely distinct-abscissa case.
With shares, there is always a unique degree-at-most- interpolating polynomial. If all shares are genuine it gives the correct secret. If one is fake, it normally gives the wrong secret, with probability conditional on a uniform fake ordinate, but the inconsistency is undetectable from those shares. The data do not certify which case has occurred.
With shares, genuine shares are consistent with one such polynomial. A fake is inconsistent with probability , so it is usually detected as an inconsistency. However, omitting each of the shares in turn gives possible polynomials. If the data are inconsistent, their constant terms are distinct: two candidate polynomials with the same constant term agree at zero and at their common abscissae, hence agree identically, which would make all the data consistent. The secret is narrowed to possibilities, but the fake is not identified.
With shares, at least are genuine. There is a unique degree-at-most- polynomial agreeing with at least shares: two candidates would agree on at least abscissae and hence coincide. Find it by deleting each share and checking consistency. The secret is recovered uniquely, and the fake is identified unless it happens to lie on the genuine polynomial, in which case it is harmless.
Past exam of the mathematics course of the University of Cambridge 2020 ii Paper 3 3I Solution Created 2026-09-24 Updated 2026-09-29
Use Shamir's secret sharing over the finite field . The Chair independently chooses from the uniform distribution on a finite set and forms the random polynomialChoose distinct nonzero , with equal to the number of discs to be issued, and inscribe on disc .
Any discs give distinct values of a polynomial of degree at most . Their Vandermonde determinant is nonzero, so polynomial interpolation recovers uniquely and hence recovers the secret as .
Conversely, fix any observed discs and any candidate secret . Interpolating through those points and gives exactly one polynomial of degree at most . Thus every candidate is compatible with the observed discs in exactly the same number of ways. Because the coefficients were chosen uniformly, the conditional distribution of the secret is unchanged after seeing any discs. This proves the Perfect secrecy of Shamir's threshold scheme.
Perfect secrecy of Shamir's threshold scheme Created 2026-09-29 Updated 2026-11-05
In Shamir's secret sharing, observing any shares leaves the secret's prior distribution unchanged. In particular, the posterior distribution is uniform if the prior distribution was uniform; uniformity of the secret is not required for perfect secrecy.
To prove this, fix distinct nonzero evaluation points and a candidate secret . The evaluations impose independent linear equations on the random coefficients. The evaluation matrix has rank : its first columns form a Vandermonde matrix multiplied by a nonsingular diagonal matrix of nonzero evaluation points. Every observed share tuple therefore has exactly compatible coefficient tuples. Since the coefficients were independently uniform, its conditional probability isindependent of . Thus the shares and the secret are independent random variables, which proves perfect secrecy.[ref]
How to Share a Secret by Adi Shamir. Pages 612–613: interpolation argument for fewer than the threshold number of shares
Shamir's secret sharing Created 2026-09-29 Updated 2026-11-05
Shamir's secret sharing distributes a secret in a finite field so that any of shares recover it, while fewer than shares reveal no information about it. Choose , distinct nonzero field elements , and independent uniformly distributed coefficients , independent of . Setand give participant the pair . Any shares determine by polynomial interpolation, hence determine . Fewer than shares have a distribution independent of ; this is Perfect secrecy of Shamir's threshold scheme.[ref]
How to Share a Secret by Adi Shamir. Pages 612–613: polynomial construction and threshold property
For example, over the finite field , a two-share threshold with secret and coefficient gives . The shares and recover and . Either share alone is compatible with every secret, and the uniform choice of makes its distribution independent of that secret.
