Section 2, property (4) — hierarchical allocation of polynomial shares
ProvedShamir1979.hierarchical_thresholdAllocate any finite sets of participant locations to people, allowing a person to hold several polynomial evaluations. A finite coalition can reconstruct whenever the union of the locations it holds contains at least distinct locations. If that union has fewer than locations, its joint share transcript has the same uniform distribution for every secret. Overlapping holdings are counted once, so giving the same evaluation to two people does not create an additional independent share. The paper's hierarchical example is obtained by allocating three, two, or one distinct locations to its three participant classes.
import Definitions.Def_Shamir1979_Model open scoped BigOperators universe u
namespace Shamir1979
theorem hierarchical_threshold (p n k : Nat) [Fact (Nat.Prime p)]
(hk : 0 < k) (hkn : k ≤ n) (hnp : n < p)
{A : Type u} (holdings : A → Finset (Fin n)) (coalition : Finset A) :
(k ≤ (heldLocations holdings coalition).card →
∀ (secret : ZMod p) (coins : Coins p k),
recover (heldLocations holdings coalition)
(observe (heldLocations holdings coalition) secret coins) = secret) ∧
((heldLocations holdings coalition).card < k →
∀ (secret : ZMod p) (values : Observation p (heldLocations holdings coalition)),
observationProbability (k := k) (heldLocations holdings coalition) secret values =
(1 : Rat) / (p : Rat) ^ (heldLocations holdings coalition).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 , natural numbers with , every type in any universe (with no finiteness or nonemptiness assumption), every assignment of a finite set to each , and every finite coalition , put . This is a union of sets of locations: repeated locations within different holdings are retained only once, so counts distinct locations, not owners or the sum of the holding sizes. The assertion is the conjunction of these two implications. If , then for every secret and every coefficient function , defining and , the recovery expression satisfies ; in the definition the product also includes with factor , equivalently omitted here. All locations use that same coefficient function and polynomial, including locations held by more than one coalition member, and makes distinct locations have distinct, nonzero , so the off-diagonal denominators in this expression are nonzero. If , then for every secret and every prescribed function , the exact rational identity holds; the left side is the probability of that observation under uniform choice from all coefficient functions. The two implications include equality in the recovery case only. An empty coalition, an empty type , or holdings whose union is empty gives : the recovery sum is then , its implication has false antecedent because , and the second implication asserts probability for the unique empty observation. When , the coefficient domain is empty, the polynomial is constant , and the recovery implication applies to every nonempty , while the probability implication applies only to empty . The hypotheses exclude and , and no independent coefficient choices by coalition members are included.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.