Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Section 2, property (3) — privacy across independent refreshes

Proved
Shamir1979.independent_refresh_privacy

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

cryptographyfinite-fieldssecret-sharing

For prime ppp and 1≤k≤n<p1\le k\le n<p1≤k≤n<p, take any finite collection of sharing editions. Every edition has the same secret constant and a freshly, independently, uniformly sampled vector of nonconstant coefficients. The observed coalition may differ between editions but must contain fewer than kkk participants in each. Every specified combined transcript then has probability p−∑e∣Γe∣p^{-\sum_e |\Gamma_e|}p−∑e​∣Γe​∣, independent of the secret. The finite collection may be empty. Independent resampling is part of the sample space; correlated refresh randomness is not covered.

Preamble
import Definitions.Def_Shamir1979_Model

open scoped BigOperators
universe u
Formal statement
namespace Shamir1979

theorem independent_refresh_privacy (p n k : Nat) [Fact (Nat.Prime p)]
    (hk : 0 < k) (hkn : k ≤ n) (hnp : n < p)
    {E : Type u} [Fintype E] (groups : E → Finset (Fin n))
    (hgroups : ∀ e, (groups e).card < k) (secret : ZMod p)
    (values : (e : E) → Observation p (groups e)) :
    epochProbability (k := k) groups secret values =
      (1 : Rat) / (p : Rat) ^ (∑ e : E, (groups e).card) := by sorry

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, useful property (3), under the stated fresh-independent-polynomial sampling convention
Read-back

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

For every prime natural number ppp, natural numbers n,kn,kn,k with 0<k≤n<p0<k\le n<p0<k≤n<p, every finite type EEE in any universe, every function assigning to each e∈Ee\in Ee∈E a finite subset Ge⊆{0,…,n−1}G_e\subseteq\{0,\ldots,n-1\}Ge​⊆{0,…,n−1} with ∣Ge∣<k|G_e|<k∣Ge​∣<k, every secret s∈Fp=Z/pZs\in\mathbb F_p=\mathbb Z/p\mathbb Zs∈Fp​=Z/pZ, and every family of prescribed functions ve:Ge→Fpv_e:G_e\to\mathbb F_pve​:Ge​→Fp​, let the randomness space be the full finite Cartesian product Ω=∏e∈E({0,…,k−2}→Fp)\Omega=\prod_{e\in E}(\{0,\ldots,k-2\}\to\mathbb F_p)Ω=∏e∈E​({0,…,k−2}→Fp​). Thus a sample specifies one coefficient function cec_ece​ for each eee, and uniform choice from Ω\OmegaΩ encodes mutually independent uniform coefficient functions, while using the same secret sss for every eee. For that sample define fe(X)=s+∑j=0k−2ce(j)Xj+1f_e(X)=s+\sum_{j=0}^{k-2}c_e(j)X^{j+1}fe​(X)=s+∑j=0k−2​ce​(j)Xj+1, and observe, for each eee and each i∈Gei\in G_ei∈Ge​, the value fe(i+1)f_e(i+1)fe​(i+1) in Fp\mathbb F_pFp​. The assertion is the exact rational identity ∣{c∈Ω: for every e∈E and i∈Ge, fe(i+1)=ve(i)}∣∣Ω∣=1p∑e∈E∣Ge∣\dfrac{|\{c\in\Omega:\text{ for every }e\in E\text{ and }i\in G_e,\ f_e(i+1)=v_e(i)\}|}{|\Omega|}=\dfrac{1}{p^{\sum_{e\in E}|G_e|}}∣Ω∣∣{c∈Ω: for every e∈E and i∈Ge​, fe​(i+1)=ve​(i)}∣​=p∑e∈E​∣Ge​∣1​, where ∣Ω∣=p∣E∣(k−1)|\Omega|=p^{|E|(k-1)}∣Ω∣=p∣E∣(k−1). No disjointness is required among the GeG_eGe​: they may coincide or overlap, and the same index occurring in several groups remains a separately prescribed observation of the separately chosen polynomial for each such eee; the exponent sums the group sizes and does not take the size of their union. Every group may be empty, and EEE itself may be empty; empty groups have a unique prescribed function and contribute zero to the exponent, and for empty EEE both the randomness space and the prescribed observation family are singletons and the asserted probability is 111. When k=1k=1k=1, every GeG_eGe​ is forced to be empty, every coefficient function has empty domain, and the asserted probability is again 111. The hypotheses exclude k=0k=0k=0 and n=0n=0n=0, and primality ensures that all probability denominators are nonzero.

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