A cryptographic key can become unavailable when a single custodian loses it, while distributing complete copies gives every custodian the ability to use it alone. A threshold scheme distributes evaluations of one hidden object so that a sufficiently large coalition can recover a secret and a smaller coalition learns no information from its observations. Adi Shamir's How to Share a Secret gives a polynomial construction with these properties and discusses participant changes, replacement of shares, and hierarchical allocation. The mathematical source is the two-page 1979 paper, especially its definition of a threshold scheme on p. 612 and its finite-field construction on p. 613.
The proposed development concerns a known mathematical result. Its purpose is to connect a concrete finite sampling experiment, an explicit reconstruction formula, and exact joint observation probabilities in Lean. The security statement must hold for every admissible parameter choice, every fixed secret, and every coalition covered by the threshold condition.
Fix a prime and integers with
Write . A secret is an element . The randomness is a vector
sampled uniformly from the full product space. The sharing polynomial is
Each coefficient may be zero. Consequently the appropriate degree condition is , including the zero polynomial. This convention follows the paper's uniform coefficient sampling, which places no restriction on a leading coefficient.
Participants have the public, distinct, nonzero identifiers in . Participant receives . In Lean, participants are indexed by Fin n, and index denotes the field element represented by . A coalition is a finite set of participants. Its observation is the entire function assigning a share value to each member of ; the coordinates of this function include all correlations among the observed shares.
The number of random choices is . For an observation , its probability is defined as an exact rational number:
The prime and positive-threshold assumptions ensure that the denominator represents a nonempty sample space.
The main theorem asserts both requirements of the concrete construction. For every coalition containing at least participants, the Lagrange expression evaluated at zero recovers the secret:
Here reconstruction is a specified finite sum of products and field divisions. It is a function supplied by the model, and its correctness is a conclusion to be proved.
For every coalition smaller than the threshold and every possible joint observation, the target is
This formula is independent of . Thus the observation channel has the same law for every fixed secret. In particular, a uniform prior on the secret remains uniform after an observation.
The supporting targets include validity of the constructed polynomial, correctness of reconstruction, and the exact compatible-randomness count
Companion targets formalize preservation of existing shares when participants are added, joint privacy across independently resampled sharing editions, and hierarchical access obtained by allocating several polynomial locations to a person. Their source is the properties listed in Section 2, p. 613. Share values and encoded secret blocks already have the same field-element representation in the model.
The finished main theorem will certify a concrete threshold protocol over every prime field and every configuration satisfying the displayed parameter conditions. The reconstruction branch covers all authorized coalitions, including coalitions larger than the threshold. The privacy branch specifies the distribution of their complete transcript for every unauthorized coalition and every secret.
Existing algebraic groundwork is available. Three Prove2Me results in the ShamirSecretSharing namespace are already Proved: uniqueness from sufficiently many evaluations, unique extension after prescribing the constant and the remaining threshold observations, and nonuniqueness below the reconstruction threshold. Their source is the existing Lean catalog. The proposal references those declarations with their existing identities and credit. The new targets add the explicit prime-field construction, finite coefficient sampling, exact observation probabilities, and the companion interfaces described above.
Joint privacy requires control of the number of random coefficient vectors producing each transcript. Polynomial compatibility by itself does not specify those probabilities. Smaller coalitions, empty observations, and positive thresholds as small as one must satisfy the same finite counting statement. Reconstruction also requires the public locations to remain distinct and nonzero after reduction modulo ; this is the reason for the parameter condition .
For several sharing editions, the sampling convention matters. Each edition uses the same secret constant and its own independent uniform coefficient vector. A combined transcript must retain a secret-independent law when every edition reveals fewer than locations. Hierarchical holdings require a union of distinct locations: assigning the same location to two people does not supply an additional polynomial evaluation.
The development uses Lean 4.30 and Mathlib's ZMod, polynomials, finite sets, finite function types, and rational arithmetic. The exact finite event-count representation makes uniform sampling part of the model. Recovery and privacy are proved about these formulas; neither is a hypothesis or a field in a structure that assumes the desired security guarantee.
All principal targets quantify over arbitrary admissible . Empty coalitions are included in the privacy clause. The boundary uses an empty randomness vector and constant sharing polynomials. The refresh experiment permits any finite set of editions, including the empty set, and uses the full product randomness space. A hierarchical coalition is interpreted through the union of the locations its members hold, even when holdings overlap. Participant extension retains the field, threshold, polynomial, and existing numerical identifiers.
The reusable outputs are a coefficient-vector construction, a Lagrange recovery interface, compatible-randomness counts, exact finite observation laws, and interfaces for independent editions and hierarchical holdings. The source paper's polynomial-evaluation complexity discussion cites external algorithms; the formal targets here are its threshold guarantees and its stated sharing properties.
Cryptography/ShamirSecretSharing.lean, in the paulklemstine/Lean catalog, commit 53c2925a02. Source. The proposal retains the three existing Prove2Me theorem references and their original provenance.Original mathematical credit belongs to Adi Shamir. Existing formalizations retain the attribution given above.
namespace Shamir1979
theorem threshold_scheme (p n k : Nat) [Fact (Nat.Prime p)]
(hk : 0 < k) (hkn : k ≤ n) (hnp : n < p) :
(∀ (secret : ZMod p) (coins : Coins p k) (Γ : Finset (Fin n)),
k ≤ Γ.card → recover Γ (observe Γ secret coins) = secret) ∧
(∀ (secret : ZMod p) (Γ : Finset (Fin n)) (values : Observation p Γ),
Γ.card < k → observationProbability (k := k) Γ secret values =
(1 : Rat) / (p : Rat) ^ Γ.card) := by sorry
end Shamir1979For every prime and every threshold configuration , the concrete polynomial scheme with participant identifiers satisfies both defining requirements of a threshold scheme. Any coalition of at least participants reconstructs the secret by the given Lagrange formula, for every choice of random coefficients. Any coalition of fewer than participants has exactly the same uniform joint observation distribution for every fixed secret when the coefficients are sampled independently and uniformly. Thus reconstruction and perfect privacy are conclusions about the actual construction, not assumptions about an abstract scheme. The empty observation and the positive-threshold boundary are included.
No open leaves. Every sub-goal is proved or awaiting decomposition.