Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma C.1 — an (𝓜, m, m′, t) secure sketch has m′ ≤ L(𝓜, t, m)

Proved
FuzzyExtractors.LowerBound.lemma_C_1

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theorylower-boundmin-entropyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1secure-sketch

Let M\mathcal MM be a finite metric space with integer-valued distance dis\mathrm{dis}dis, and let m,m′m, m'm,m′ be real numbers such that 2m=N2^m = N2m=N is a natural number with N≤∣M∣N\le|\mathcal M|N≤∣M∣. If (SS,Rec)(\mathsf{SS},\mathsf{Rec})(SS,Rec) is an (M,m,m′,t)(\mathcal M,m,m',t)(M,m,m′,t)-secure sketch, then

m′≤L(M,t,m)=log⁡(min⁡S⊆M, ∣S∣=2mK(M,t,S)),m' \le L(\mathcal M,t,m) = \log\Big(\min_{S\subseteq\mathcal M,\ |S|=2^m} K(\mathcal M,t,S)\Big),m′≤L(M,t,m)=log(S⊆M, ∣S∣=2mmin​K(M,t,S)),

where K(M,t,S)K(\mathcal M,t,S)K(M,t,S) is the largest size of an (M,K,t)(\mathcal M,K,t)(M,K,t)-code all of whose points lie in SSS.

The lemma is the coding lower bound on the entropy loss of secure sketches: no sketch correcting ttt errors can leave more residual min-entropy than the logarithm of the size of a ttt-error-correcting code fitting inside every set of 2m2^m2m points. It shows that the paper's Hamming and set-difference constructions are optimal for uniform inputs.

Formalization Note The paper leaves implicit that L(M,t,m)L(\mathcal M,t,m)L(M,t,m) is defined only when 2m2^m2m is an integer at most ∣M∣|\mathcal M|∣M∣; we state the lemma for N∈NN\in\mathbb NN∈N with N=2mN=2^mN=2m and N≤∣M∣N\le|\mathcal M|N≤∣M∣. All metric axioms of §2.1 are stated explicitly. The sketch is the worst-case secure sketch of Definition 3 (not the average-case one), with a randomized Rec\mathsf{Rec}Rec and an arbitrary sketch output type. Efficiency is not formalized.

Preamble
import Mathlib
import Definitions.Def_FuzzyExtractors_LowerBound_Basic
Formal statement
namespace FuzzyExtractors.LowerBound

/-- Lemma C.1 (Appendix C, p. 40): the existence of an (𝓜, m, m', t)-secure sketch implies
`m' ≤ L(𝓜, t, m)`, where `2^m = N` is a natural number with `N ≤ |𝓜|`. -/
theorem lemma_C_1 {M V : Type} [Fintype M] (dis : M → M → ℕ)
    (hzero : ∀ x y, dis x y = 0 ↔ x = y)
    (hsymm : ∀ x y, dis x y = dis y x)
    (htri : ∀ x y z, dis x z ≤ dis x y + dis y z)
    (m m' : ℝ) (t : ℕ)
    (SS : M → PMF V) (Rec : M → V → PMF M) (hSS : FuzzyExtractors.Hamming.IsSecureSketch dis m m' t SS Rec)
    (N : ℕ) (hN : N ≤ Fintype.card M) (hNm : (N : ℝ) = (2 : ℝ) ^ m) :
    m' ≤ L dis t N hN := by sorry

end FuzzyExtractors.LowerBound
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, Lemma C.1, p. 40
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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