Shamir’s finite-field sharing experiment and observation probabilities
DefinitionShamir1979_ModelThis bundle defines a concrete finite experiment for Shamir's polynomial threshold construction. For a prime p and threshold k, randomness is a vector of k-1 elements of ZMod p; the sharing polynomial has the secret as constant coefficient. Participants use the public identifiers 1 through n. A coalition observes the function assigning its members their polynomial evaluations. Reconstruction is an explicit Lagrange sum evaluated at zero, with a product omitting the location being reconstructed. Event probabilities are exact rational counts over the entire finite coefficient-vector sample space. Auxiliary interfaces describe unions of polynomial locations held by a coalition and finite collections of independently sampled sharing editions. The epoch sample space is the full product of coefficient-vector spaces, which makes the independence convention explicit. No reconstruction, privacy, or interpolation theorem is assumed in these definitions. The functions are total; the proposed correctness and privacy targets impose 1 ≤ k ≤ n < p.
import Mathlib.Data.ZMod.Basic
import Mathlib.Algebra.Field.ZMod
import Mathlib.Algebra.Polynomial.Eval.Defs
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Rat.Defs
/-!
# Finite experiments for Shamir's threshold scheme
Adi Shamir, “How to Share a Secret,” Communications of the ACM 22(11),
612–613 (1979), §2. DOI: https://doi.org/10.1145/359168.359176.
The k-1 coefficients are independently uniform, including zero; polynomial
bounds are therefore degree < k. Participants use the public identifiers 1,...,n.
-/
noncomputable section
set_option autoImplicit false
open scoped BigOperators
namespace Shamir1979
universe u
abbrev Coins (p k : Nat) := Fin (k-1) → ZMod p
abbrev Observation (p : Nat) {n : Nat} (Γ : Finset (Fin n)) :=
{i : Fin n // i ∈ Γ} → ZMod p
def sharingPolynomial {p k : Nat} (secret : ZMod p) (coins : Coins p k) :
Polynomial (ZMod p) :=
Polynomial.C secret + ∑ j : Fin (k-1), Polynomial.monomial (j.val+1) (coins j)
def point {p n : Nat} (i : Fin n) : ZMod p := ((i.val+1 : Nat) : ZMod p)
def share {p n k : Nat} (secret : ZMod p) (coins : Coins p k) (i : Fin n) : ZMod p :=
(sharingPolynomial secret coins).eval (point i)
def observe {p n k : Nat} (Γ : Finset (Fin n)) (secret : ZMod p)
(coins : Coins p k) : Observation p Γ := fun i => share secret coins i.val
def recover {p n : Nat} [Fact (Nat.Prime p)] (Γ : Finset (Fin n))
(values : Observation p Γ) : ZMod p := by
classical
exact ∑ i : {i : Fin n // i ∈ Γ}, values i *
∏ j : {j : Fin n // j ∈ Γ},
if j=i then 1 else (-point (p := p) j.val) / (point (p := p) i.val - point (p := p) j.val)
def fiberCount {p n k : Nat} [Fact (Nat.Prime p)] (Γ : Finset (Fin n))
(secret : ZMod p) (values : Observation p Γ) : Nat := by
classical
exact (Finset.univ.filter fun coins : Coins p k => observe Γ secret coins = values).card
def observationProbability {p n k : Nat} [Fact (Nat.Prime p)] (Γ : Finset (Fin n))
(secret : ZMod p) (values : Observation p Γ) : Rat :=
(fiberCount (k := k) Γ secret values : Rat) / (Fintype.card (Coins p k) : Rat)
def heldLocations {A : Type u} {n : Nat} (holdings : A → Finset (Fin n))
(coalition : Finset A) : Finset (Fin n) := by
classical
exact coalition.biUnion holdings
def epochObservation {p n k : Nat} {E : Type u} (groups : E → Finset (Fin n))
(secret : ZMod p) (coins : E → Coins p k) : (e : E) → Observation p (groups e) :=
fun e => observe (groups e) secret (coins e)
def epochProbability {p n k : Nat} [Fact (Nat.Prime p)] {E : Type u} [Fintype E]
(groups : E → Finset (Fin n)) (secret : ZMod p)
(values : (e : E) → Observation p (groups e)) : Rat := by
classical
exact ((Finset.univ.filter fun coins : E → Coins p k =>
epochObservation groups secret coins = values).card : Rat) /
(Fintype.card (E → Coins p k) : Rat)
end Shamir1979Read-back
What the Lean code literally says, in plain math · OpenAI Codex (inherited session model)
Coins. For any natural numbers and , let with subtraction truncated at zero, so when or . The type is the set of all functions , where the notation denotes , including and the one-element ring . No primality hypothesis is imposed. When , this function type has exactly one member, the empty function, for every ; for positive its cardinality is , while for and it is infinite.
Observation. For any natural numbers and any finite subset , is the set of all functions from the selected indices to . Thus each argument is an index together with its membership in , and there is one coordinate for every member of . There is no primality assumption: the codomain is when and a singleton when . If , including necessarily when , there is exactly one observation, the empty function.
sharingPolynomial. For any natural numbers , any , and any function , where , this definition returns the polynomial over given by . The sum is over all indices, coefficients may be zero, and no primality or nonzero-leading-coefficient hypothesis is imposed. For or the sum is empty and the polynomial is the constant ; for it is a polynomial over , and for it is the zero polynomial in the one-element coefficient ring.
point. For any natural numbers and any index , the point assigned to is the image of the natural number in . For positive this is the residue class of modulo ; for it is the integer . There is no primality hypothesis and no bound relating to , so points may be zero and distinct indices may have equal points. In particular, for every point is zero; if there is no admissible index.
share. For any natural numbers , any secret , any function with , and any index , this definition returns in , where is the image of in that ring. It is polynomial evaluation with no primality, distinctness, or nonzero-point hypotheses, and with no restriction relating . For or the returned share is at every index; for the calculation is in , for every returned value is zero, and for there is no admissible index.
observe. For any natural numbers , any finite subset , any , and any function with , this definition returns the function on selected indices whose coordinate at is , where is the image of in . No primality or bounds on the parameters or on are required. If is empty, including when , the result is the unique empty observation; if or , every existing coordinate is . For all coordinates are integers, and for all coordinates lie in the singleton ring.
recover. For any natural numbers with the typeclass hypothesis that is prime, any finite subset , and any function , this definition returns the following element of the field : , where is the residue class of modulo , , and whenever the selected indices and are unequal. The test is equality of indices, not equality of their residue classes. There is no requirement that the values arise from a polynomial, no parameter , no bound relating to , and no requirement that the points be distinct or nonzero. Field division is total with inverse of zero equal to zero, so an unequal pair with contributes factor zero. An empty selected set gives the empty sum ; a singleton selected set gives its one supplied value. The primality hypothesis rules out and , but permits , when the selected set must be empty.
fiberCount. For any natural numbers with the typeclass hypothesis that is prime, any finite subset , any , and any function , this natural number is the cardinality of the set of all functions satisfying for every , where and is the residue class of modulo . The finite enumeration includes every one of the coefficient functions once. There is no bound on and no distinctness or nonzero requirement on the points, and the count may be zero. If is empty, including when , all coefficient functions satisfy the condition and the count is . If or , there is one coefficient function, so the count is exactly when every selected coordinate of is , and is otherwise.
observationProbability. For any natural numbers with the typeclass hypothesis that is prime, any finite subset , any , and any function , this definition returns the rational number , where and is the residue class of modulo . The numerator and denominator are natural-number cardinalities embedded in before division; the numerator counts matching functions among all coefficient functions. Primality makes , so the denominator is positive, although rational division itself is total. No restriction on , , or the points is assumed. An empty selected set gives probability ; for or the probability is if every selected coordinate is and otherwise.
heldLocations. For any type in the declared universe, any natural number , any function assigning a finite subset to each , and any finite subset , this definition returns the finite union . Thus an index occurs exactly when at least one member of has it in its assigned subset, and repeated occurrences are counted only once because the result is a set. The type need not be finite, no disjointness or coverage condition is imposed on the subsets, and no decidable-equality hypothesis is required from the caller because classical reasoning is used. If is empty or every selected subset is empty, the result is empty; when , every assigned subset and the resulting union are empty.
epochObservation. For any natural numbers , any type in the declared universe, any assignment of finite subsets to elements , any single , and any family of coefficient functions with , this definition returns a family of functions with for every and , where is the image of in . The same is used for all , while the coefficient family is an arbitrary supplied function; this declaration imposes no distribution or independence assumption, no primality hypothesis, and no finiteness hypothesis on . Empty groups yield empty coordinate functions, an empty yields the unique empty family, and forces all groups to be empty. If or , every existing coordinate is ; gives integer coordinates and gives singleton-ring coordinates.
epochProbability. For any natural numbers with the typeclass hypothesis that is prime, any type in the declared universe equipped with a finite enumeration, any assignment of finite subsets to , any , and any specified family , this definition returns a rational number whose numerator is the number of coefficient families , each , for which for every and every , and whose denominator is the number of all such coefficient families, namely ; here and is the residue class of modulo . Both counts are embedded in before division, every coefficient family is enumerated once, and the denominator is positive because is prime. There is no further restriction on group sizes, intersections, , or the evaluation points. If is empty, the numerator and denominator are both and the result is ; if every group is empty, including when , the result is also . If or , there is exactly one coefficient family, so the result is exactly when every specified coordinate equals , and is otherwise.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.