Section 2 — perfect privacy of the joint share distribution
ProvedShamir1979.perfect_privacyFor prime and , sample all nonconstant coefficients independently and uniformly from . For every fixed secret, every coalition of fewer than participants, and every joint assignment to their shares, the probability of observing is exactly . Probability is represented as the cardinality of the corresponding event divided by the cardinality of the finite sample space. This is joint privacy, rather than merely a claim about individual shares or the existence of alternative secrets.
import Definitions.Def_Shamir1979_Model open scoped BigOperators universe u
namespace Shamir1979
theorem perfect_privacy (p n k : Nat) [Fact (Nat.Prime p)]
(hk : 0 < k) (hkn : k ≤ n) (hnp : n < p)
(Γ : Finset (Fin n)) (hΓ : Γ.card < k)
(secret : ZMod p) (values : Observation p Γ) :
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 , natural numbers satisfying , , and , every subset with , every secret , and every prescribed tuple , the rational number obtained by dividing the number of coefficient tuples satisfying for all by the total number of coefficient tuples is exactly . All arithmetic inside the coordinate equations is in , with reduced modulo ; the division in this probability and in is rational division. Thus this is the probability of one specified complete joint observation when every coefficient tuple receives equal weight, for each separately quantified secret and prescribed tuple. Primality implies , so both probability denominators are nonzero, and the hypotheses exclude and . Empty is included: the only tuple on it is the empty function, the simultaneous event has no constraints and includes every coin tuple, and its probability is . The case forces this empty observation and has one empty coefficient tuple. The sum defining each share is then empty, giving the constant share . All other permitted sizes , arbitrary tuple values, and zero secrets and coefficients are included.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.