Theorem 5.2 — every code gives an average-case fuzzy extractor with
ProvedFuzzyExtractors.Hamming.theorem_5_2Let be a finite additive group with elements, , and let with the Hamming distance. Let be a nonempty code with codewords in which distinct codewords are at Hamming distance at least , and write . Let be real, , and let be a natural number with
Then there exists an average-case -fuzzy extractor: procedures , producing an -bit string and a helper string from , and , such that whenever is within Hamming distance of , and
for every pair with .
This is the paper's fuzzy extractor for the Hamming metric: the key length loses only the redundancy of the code and the unavoidable .
Formalization Note The paper writes , a real number; since is an -bit string, we state the claim for every natural 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 implicit in ; we state it. covers non-linear codes. 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.
import Mathlib import Definitions.Def_FuzzyExtractors_Hamming_Basic
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.