Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Shamir’s finite-field sharing experiment and observation probabilities

Definition
Shamir1979_Model

by Victorized · Oct 29, 2026 · Mathlib c5ea003 (Lean v4.30.0)

cryptographyfinite-fieldssecret-sharing

This 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.

Definition code
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 Shamir1979
Source
Adi Shamir, How to Share a Secret, Communications of the ACM 22(11), 612–613 (1979), https://doi.org/10.1145/359168.359176, §2, p. 613: polynomial construction, interpolation, uniform sampling, and properties (2)–(4)
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (inherited session model)

Coins. For any natural numbers ppp and kkk, let r=k−1r=k-1r=k−1 with subtraction truncated at zero, so r=0r=0r=0 when k=0k=0k=0 or k=1k=1k=1. The type Coins⁡(p,k)\operatorname{Coins}(p,k)Coins(p,k) is the set of all functions {0,…,r−1}→Z/pZ\{0,\ldots,r-1\}\to\mathbb Z/p\mathbb Z{0,…,r−1}→Z/pZ, where the notation Z/pZ\mathbb Z/p\mathbb ZZ/pZ denotes ZMod⁡(p)\operatorname{ZMod}(p)ZMod(p), including ZMod⁡(0)=Z\operatorname{ZMod}(0)=\mathbb ZZMod(0)=Z and the one-element ring ZMod⁡(1)\operatorname{ZMod}(1)ZMod(1). No primality hypothesis is imposed. When r=0r=0r=0, this function type has exactly one member, the empty function, for every ppp; for positive ppp its cardinality is prp^rpr, while for p=0p=0p=0 and r>0r>0r>0 it is infinite.

Observation. For any natural numbers p,np,np,n and any finite subset Γ⊆{0,…,n−1}\Gamma\subseteq\{0,\ldots,n-1\}Γ⊆{0,…,n−1}, Observation⁡(p,Γ)\operatorname{Observation}(p,\Gamma)Observation(p,Γ) is the set of all functions from the selected indices i∈Γi\in\Gammai∈Γ to ZMod⁡(p)\operatorname{ZMod}(p)ZMod(p). Thus each argument is an index together with its membership in Γ\GammaΓ, and there is one coordinate for every member of Γ\GammaΓ. There is no primality assumption: the codomain is Z\mathbb ZZ when p=0p=0p=0 and a singleton when p=1p=1p=1. If Γ=∅\Gamma=\varnothingΓ=∅, including necessarily when n=0n=0n=0, there is exactly one observation, the empty function.

sharingPolynomial. For any natural numbers p,kp,kp,k, any s∈ZMod⁡(p)s\in\operatorname{ZMod}(p)s∈ZMod(p), and any function c:{0,…,r−1}→ZMod⁡(p)c:\{0,\ldots,r-1\}\to\operatorname{ZMod}(p)c:{0,…,r−1}→ZMod(p), where r=max⁡(k−1,0)r=\max(k-1,0)r=max(k−1,0), this definition returns the polynomial over ZMod⁡(p)\operatorname{ZMod}(p)ZMod(p) given by fs,c(X)=s+∑j=0r−1c(j)Xj+1f_{s,c}(X)=s+\sum_{j=0}^{r-1}c(j)X^{j+1}fs,c​(X)=s+∑j=0r−1​c(j)Xj+1. The sum is over all rrr indices, coefficients may be zero, and no primality or nonzero-leading-coefficient hypothesis is imposed. For k=0k=0k=0 or k=1k=1k=1 the sum is empty and the polynomial is the constant sss; for p=0p=0p=0 it is a polynomial over Z\mathbb ZZ, and for p=1p=1p=1 it is the zero polynomial in the one-element coefficient ring.

point. For any natural numbers p,np,np,n and any index i∈{0,…,n−1}i\in\{0,\ldots,n-1\}i∈{0,…,n−1}, the point assigned to iii is the image of the natural number i+1i+1i+1 in ZMod⁡(p)\operatorname{ZMod}(p)ZMod(p). For positive ppp this is the residue class of i+1i+1i+1 modulo ppp; for p=0p=0p=0 it is the integer i+1i+1i+1. There is no primality hypothesis and no bound relating nnn to ppp, so points may be zero and distinct indices may have equal points. In particular, for p=1p=1p=1 every point is zero; if n=0n=0n=0 there is no admissible index.

share. For any natural numbers p,n,kp,n,kp,n,k, any secret s∈ZMod⁡(p)s\in\operatorname{ZMod}(p)s∈ZMod(p), any function c:{0,…,r−1}→ZMod⁡(p)c:\{0,\ldots,r-1\}\to\operatorname{ZMod}(p)c:{0,…,r−1}→ZMod(p) with r=max⁡(k−1,0)r=\max(k-1,0)r=max(k−1,0), and any index i∈{0,…,n−1}i\in\{0,\ldots,n-1\}i∈{0,…,n−1}, this definition returns s+∑j=0r−1c(j)xij+1s+\sum_{j=0}^{r-1}c(j)x_i^{j+1}s+∑j=0r−1​c(j)xij+1​ in ZMod⁡(p)\operatorname{ZMod}(p)ZMod(p), where xix_ixi​ is the image of i+1i+1i+1 in that ring. It is polynomial evaluation with no primality, distinctness, or nonzero-point hypotheses, and with no restriction relating n,k,pn,k,pn,k,p. For k=0k=0k=0 or k=1k=1k=1 the returned share is sss at every index; for p=0p=0p=0 the calculation is in Z\mathbb ZZ, for p=1p=1p=1 every returned value is zero, and for n=0n=0n=0 there is no admissible index.

observe. For any natural numbers p,n,kp,n,kp,n,k, any finite subset Γ⊆{0,…,n−1}\Gamma\subseteq\{0,\ldots,n-1\}Γ⊆{0,…,n−1}, any s∈ZMod⁡(p)s\in\operatorname{ZMod}(p)s∈ZMod(p), and any function c:{0,…,r−1}→ZMod⁡(p)c:\{0,\ldots,r-1\}\to\operatorname{ZMod}(p)c:{0,…,r−1}→ZMod(p) with r=max⁡(k−1,0)r=\max(k-1,0)r=max(k−1,0), this definition returns the function on selected indices whose coordinate at i∈Γi\in\Gammai∈Γ is s+∑j=0r−1c(j)xij+1s+\sum_{j=0}^{r-1}c(j)x_i^{j+1}s+∑j=0r−1​c(j)xij+1​, where xix_ixi​ is the image of i+1i+1i+1 in ZMod⁡(p)\operatorname{ZMod}(p)ZMod(p). No primality or bounds on the parameters or on ∣Γ∣|\Gamma|∣Γ∣ are required. If Γ\GammaΓ is empty, including when n=0n=0n=0, the result is the unique empty observation; if k=0k=0k=0 or k=1k=1k=1, every existing coordinate is sss. For p=0p=0p=0 all coordinates are integers, and for p=1p=1p=1 all coordinates lie in the singleton ring.

recover. For any natural numbers p,np,np,n with the typeclass hypothesis that ppp is prime, any finite subset Γ⊆{0,…,n−1}\Gamma\subseteq\{0,\ldots,n-1\}Γ⊆{0,…,n−1}, and any function v:Γ→ZMod⁡(p)v:\Gamma\to\operatorname{ZMod}(p)v:Γ→ZMod(p), this definition returns the following element of the field ZMod⁡(p)\operatorname{ZMod}(p)ZMod(p): ∑i∈Γv(i)∏j∈Γai,j\sum_{i\in\Gamma}v(i)\prod_{j\in\Gamma}a_{i,j}∑i∈Γ​v(i)∏j∈Γ​ai,j​, where xix_ixi​ is the residue class of i+1i+1i+1 modulo ppp, ai,i=1a_{i,i}=1ai,i​=1, and ai,j=(−xj)/(xi−xj)a_{i,j}=(-x_j)/(x_i-x_j)ai,j​=(−xj​)/(xi​−xj​) whenever the selected indices jjj and iii 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 kkk, no bound relating nnn to ppp, 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 xi=xjx_i=x_jxi​=xj​ contributes factor zero. An empty selected set gives the empty sum 000; a singleton selected set gives its one supplied value. The primality hypothesis rules out p=0p=0p=0 and p=1p=1p=1, but permits n=0n=0n=0, when the selected set must be empty.

fiberCount. For any natural numbers p,n,kp,n,kp,n,k with the typeclass hypothesis that ppp is prime, any finite subset Γ⊆{0,…,n−1}\Gamma\subseteq\{0,\ldots,n-1\}Γ⊆{0,…,n−1}, any s∈ZMod⁡(p)s\in\operatorname{ZMod}(p)s∈ZMod(p), and any function v:Γ→ZMod⁡(p)v:\Gamma\to\operatorname{ZMod}(p)v:Γ→ZMod(p), this natural number is the cardinality of the set of all functions c:{0,…,r−1}→ZMod⁡(p)c:\{0,\ldots,r-1\}\to\operatorname{ZMod}(p)c:{0,…,r−1}→ZMod(p) satisfying s+∑j=0r−1c(j)xij+1=v(i)s+\sum_{j=0}^{r-1}c(j)x_i^{j+1}=v(i)s+∑j=0r−1​c(j)xij+1​=v(i) for every i∈Γi\in\Gammai∈Γ, where r=max⁡(k−1,0)r=\max(k-1,0)r=max(k−1,0) and xix_ixi​ is the residue class of i+1i+1i+1 modulo ppp. The finite enumeration includes every one of the prp^rpr coefficient functions once. There is no bound on ∣Γ∣|\Gamma|∣Γ∣ and no distinctness or nonzero requirement on the points, and the count may be zero. If Γ\GammaΓ is empty, including when n=0n=0n=0, all coefficient functions satisfy the condition and the count is prp^rpr. If k=0k=0k=0 or k=1k=1k=1, there is one coefficient function, so the count is 111 exactly when every selected coordinate of vvv is sss, and is 000 otherwise.

observationProbability. For any natural numbers p,n,kp,n,kp,n,k with the typeclass hypothesis that ppp is prime, any finite subset Γ⊆{0,…,n−1}\Gamma\subseteq\{0,\ldots,n-1\}Γ⊆{0,…,n−1}, any s∈ZMod⁡(p)s\in\operatorname{ZMod}(p)s∈ZMod(p), and any function v:Γ→ZMod⁡(p)v:\Gamma\to\operatorname{ZMod}(p)v:Γ→ZMod(p), this definition returns the rational number #{c:{0,…,r−1}→ZMod⁡(p)∣for every i∈Γ, s+∑j=0r−1c(j)xij+1=v(i)}/pr\#\{c:\{0,\ldots,r-1\}\to\operatorname{ZMod}(p)\mid \text{for every }i\in\Gamma,\ s+\sum_{j=0}^{r-1}c(j)x_i^{j+1}=v(i)\}/p^r#{c:{0,…,r−1}→ZMod(p)∣for every i∈Γ, s+∑j=0r−1​c(j)xij+1​=v(i)}/pr, where r=max⁡(k−1,0)r=\max(k-1,0)r=max(k−1,0) and xix_ixi​ is the residue class of i+1i+1i+1 modulo ppp. The numerator and denominator are natural-number cardinalities embedded in Q\mathbb QQ before division; the numerator counts matching functions among all prp^rpr coefficient functions. Primality makes p≥2p\ge2p≥2, so the denominator is positive, although rational division itself is total. No restriction on nnn, ∣Γ∣|\Gamma|∣Γ∣, or the points is assumed. An empty selected set gives probability 111; for k=0k=0k=0 or k=1k=1k=1 the probability is 111 if every selected coordinate is sss and 000 otherwise.

heldLocations. For any type AAA in the declared universe, any natural number nnn, any function HHH assigning a finite subset H(a)⊆{0,…,n−1}H(a)\subseteq\{0,\ldots,n-1\}H(a)⊆{0,…,n−1} to each a∈Aa\in Aa∈A, and any finite subset C⊆AC\subseteq AC⊆A, this definition returns the finite union ⋃a∈CH(a)\bigcup_{a\in C}H(a)⋃a∈C​H(a). Thus an index occurs exactly when at least one member of CCC has it in its assigned subset, and repeated occurrences are counted only once because the result is a set. The type AAA 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 CCC is empty or every selected subset is empty, the result is empty; when n=0n=0n=0, every assigned subset and the resulting union are empty.

epochObservation. For any natural numbers p,n,kp,n,kp,n,k, any type EEE in the declared universe, any assignment of finite subsets G(e)⊆{0,…,n−1}G(e)\subseteq\{0,\ldots,n-1\}G(e)⊆{0,…,n−1} to elements e∈Ee\in Ee∈E, any single s∈ZMod⁡(p)s\in\operatorname{ZMod}(p)s∈ZMod(p), and any family of coefficient functions ce:{0,…,r−1}→ZMod⁡(p)c_e:\{0,\ldots,r-1\}\to\operatorname{ZMod}(p)ce​:{0,…,r−1}→ZMod(p) with r=max⁡(k−1,0)r=\max(k-1,0)r=max(k−1,0), this definition returns a family of functions ve:G(e)→ZMod⁡(p)v_e:G(e)\to\operatorname{ZMod}(p)ve​:G(e)→ZMod(p) with ve(i)=s+∑j=0r−1ce(j)xij+1v_e(i)=s+\sum_{j=0}^{r-1}c_e(j)x_i^{j+1}ve​(i)=s+∑j=0r−1​ce​(j)xij+1​ for every e∈Ee\in Ee∈E and i∈G(e)i\in G(e)i∈G(e), where xix_ixi​ is the image of i+1i+1i+1 in ZMod⁡(p)\operatorname{ZMod}(p)ZMod(p). The same sss is used for all eee, 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 EEE. Empty groups yield empty coordinate functions, an empty EEE yields the unique empty family, and n=0n=0n=0 forces all groups to be empty. If k=0k=0k=0 or k=1k=1k=1, every existing coordinate is sss; p=0p=0p=0 gives integer coordinates and p=1p=1p=1 gives singleton-ring coordinates.

epochProbability. For any natural numbers p,n,kp,n,kp,n,k with the typeclass hypothesis that ppp is prime, any type EEE in the declared universe equipped with a finite enumeration, any assignment of finite subsets G(e)⊆{0,…,n−1}G(e)\subseteq\{0,\ldots,n-1\}G(e)⊆{0,…,n−1} to e∈Ee\in Ee∈E, any s∈ZMod⁡(p)s\in\operatorname{ZMod}(p)s∈ZMod(p), and any specified family ve:G(e)→ZMod⁡(p)v_e:G(e)\to\operatorname{ZMod}(p)ve​:G(e)→ZMod(p), this definition returns a rational number whose numerator is the number of coefficient families (ce)e∈E(c_e)_{e\in E}(ce​)e∈E​, each ce:{0,…,r−1}→ZMod⁡(p)c_e:\{0,\ldots,r-1\}\to\operatorname{ZMod}(p)ce​:{0,…,r−1}→ZMod(p), for which s+∑j=0r−1ce(j)xij+1=ve(i)s+\sum_{j=0}^{r-1}c_e(j)x_i^{j+1}=v_e(i)s+∑j=0r−1​ce​(j)xij+1​=ve​(i) for every e∈Ee\in Ee∈E and every i∈G(e)i\in G(e)i∈G(e), and whose denominator is the number of all such coefficient families, namely (pr)∣E∣=pr∣E∣(p^r)^{|E|}=p^{r|E|}(pr)∣E∣=pr∣E∣; here r=max⁡(k−1,0)r=\max(k-1,0)r=max(k−1,0) and xix_ixi​ is the residue class of i+1i+1i+1 modulo ppp. Both counts are embedded in Q\mathbb QQ before division, every coefficient family is enumerated once, and the denominator is positive because ppp is prime. There is no further restriction on group sizes, intersections, nnn, or the evaluation points. If EEE is empty, the numerator and denominator are both 111 and the result is 111; if every group is empty, including when n=0n=0n=0, the result is also 111. If k=0k=0k=0 or k=1k=1k=1, there is exactly one coefficient family, so the result is 111 exactly when every specified coordinate equals sss, and is 000 otherwise.

Human review
  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Victorized · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me