Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.2 — every [n,k,2t+1]F[n,k,2t+1]_{\mathcal F}[n,k,2t+1]F​ code gives an average-case fuzzy extractor with ℓ=m+kf−nf−2log⁡(1/ε)+2\ell=m+kf-nf-2\log(1/\varepsilon)+2ℓ=m+kf−nf−2log(1/ε)+2

Proved
FuzzyExtractors.Hamming.theorem_5_2

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

coding-theoryfuzzy-extractorsinformation-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let F\mathcal FF be a finite additive group with F=∣F∣F=|\mathcal F|F=∣F∣ elements, f=log⁡Ff=\log Ff=logF, and let M=Fn\mathcal M=\mathcal F^nM=Fn with the Hamming distance. Let C⊆FnC\subseteq\mathcal F^nC⊆Fn be a nonempty code with KKK codewords in which distinct codewords are at Hamming distance at least 2t+12t+12t+1, and write kf=log⁡Kkf=\log Kkf=logK. Let mmm be real, ε>0\varepsilon>0ε>0, and let ℓ\ellℓ be a natural number with

ℓ  ≤  m+kf−nf−2log⁡(1/ε)+2.\ell\;\le\;m+kf-nf-2\log(1/\varepsilon)+2 .ℓ≤m+kf−nf−2log(1/ε)+2.

Then there exists an average-case (Fn,m,ℓ,t,ε)(\mathcal F^n,m,\ell,t,\varepsilon)(Fn,m,ℓ,t,ε)-fuzzy extractor: procedures Gen\mathsf{Gen}Gen, producing an ℓ\ellℓ-bit string RRR and a helper string PPP from www, and Rep\mathsf{Rep}Rep, such that Rep(w′,P)=R\mathsf{Rep}(w',P)=RRep(w′,P)=R whenever w′w'w′ is within Hamming distance ttt of www, and

SD((R,P,I),(Uℓ,P,I))≤ε\mathbf{SD}\big((R,P,I),(U_\ell,P,I)\big)\le\varepsilonSD((R,P,I),(Uℓ​,P,I))≤ε

for every pair (W,I)(W,I)(W,I) with H~∞(W∣I)≥m\tilde{\mathbf H}_\infty(W\mid I)\ge mH~∞​(W∣I)≥m.

This is the paper's fuzzy extractor for the Hamming metric: the key length loses only the redundancy (n−k)f(n-k)f(n−k)f of the code and the unavoidable 2log⁡(1/ε)2\log(1/\varepsilon)2log(1/ε).

Formalization Note The paper writes ℓ=m+kf−nf−2log⁡(1/ε)+2\ell = m+kf-nf-2\log(1/\varepsilon)+2ℓ=m+kf−nf−2log(1/ε)+2, a real number; since RRR is an ℓ\ellℓ-bit string, we state the claim for every natural ℓ\ellℓ up to that value, which is the printed claim when the value is a natural number (Lemma 4.3, used in the proof, is phrased the same way). The paper leaves ε>0\varepsilon>0ε>0 implicit in log⁡(1/ε)\log(1/\varepsilon)log(1/ε); we state it. kf=log⁡Kkf=\log Kkf=logK covers non-linear codes. F\mathcal FF may be any finite additive commutative group. The efficiency sentence is dropped. The universal hash family is not a hypothesis: its existence is part of the claim.

Preamble
import Mathlib
import Definitions.Def_FuzzyExtractors_Hamming_Basic
Formal statement
namespace FuzzyExtractors.Hamming

theorem theorem_5_2 {F : Type} [Fintype F] [DecidableEq F] [AddCommGroup F] {n : ℕ}
    (C : Finset (Fin n → F)) (hC : C.Nonempty) (t : ℕ) (hdist : MinDistGe C (2 * t + 1))
    (m ε : ℝ) (hε : 0 < ε) (ℓ : ℕ)
    (hℓ : (ℓ : ℝ) ≤ m + Real.logb 2 C.card - (n : ℝ) * Real.logb 2 (Fintype.card F)
      - 2 * Real.logb 2 (1 / ε) + 2) :
    ∃ (P : Type) (Gen : (Fin n → F) → PMF ((Fin ℓ → Bool) × P))
      (Rep : (Fin n → F) → P → PMF (Fin ℓ → Bool)),
      IsAvgFuzzyExtractor hammingDist m ℓ t ε Gen Rep := by sorry

end FuzzyExtractors.Hamming
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data, arXiv:cs/0602007v4, Theorem 5.2, p. 17
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