Shamir’s threshold scheme: reconstruction and perfect privacy
ProvedShamir1979.threshold_schemeFor 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.
import Definitions.Def_Shamir1979_Model open scoped BigOperators universe u
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 Shamir1979Read-back
What the Lean code literally says, in plain math · OpenAI Codex (inherited session model)
For every prime natural number and natural numbers satisfying , , and , write , , , and for and . The assertion is the conjunction of these two universal statements: for every secret , every coefficient tuple , and every subset , if , then recovery from the complete observation equals , meaning in ; and for every secret , every subset , and every prescribed complete tuple , if , then the rational ratio equals . The first product has a factor at its omitted diagonal index; makes all remaining denominators nonzero. The second ratio counts one simultaneous event for the entire observation tuple over all equally weighted coin tuples; primality gives , so its rational denominator is nonzero. Each clause is an implication, so for sets failing that clause's size condition it imposes no conclusion. Recovery uses every observed index even when . The hypotheses exclude and but allow empty , for which the first size condition is false and the second event is the full coin space with probability . They also allow and ; when , the coins and polynomial sum are empty, every share is , recovery applies to every nonempty , and the probability clause applies only to the empty set. Zero secrets, zero coefficient tuples, and arbitrary prescribed observation values are all within the quantifiers.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.