Proof of Lemma C.1 — the points producing a fixed sketch value form a code of error-correcting distance t
ProvedFuzzyExtractors.LowerBound.lemma_C_1_T_isCodecoding-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1secure-sketch
Let be a finite metric space with integer-valued distance , and let satisfy the correctness property of a secure sketch for errors: if and is a possible output of , then . Then for every and every sketch value , the set
is an -code: for every , at most one element of lies within distance of .
This is the step of the proof of Lemma C.1 that converts the correctness of the sketch into a packing of balls.
Formalization Note The metric axioms of §2.1 are explicit hypotheses. Symmetry is used because the ball condition measures while correctness is stated for ; zero distance and the triangle inequality carry the paper's standing metric assumption.
Preamble
import Mathlib import Definitions.Def_FuzzyExtractors_LowerBound_Basic
Formal statement
namespace FuzzyExtractors.LowerBound
/-- Appendix C, proof of Lemma C.1, pp. 40–41: for a sketch with the correctness property for
distance `t` in a finite metric space, the points of `S` that can produce a fixed sketch value
`v` form a code of error-correcting distance `t`. -/
theorem lemma_C_1_T_isCode {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)
(t : ℕ) (SS : M → PMF V) (Rec : M → V → PMF M)
(hcorr : FuzzyExtractors.Hamming.SketchCorrect dis t SS Rec) (S : Finset M) (v : V) :
FuzzyExtractors.Hamming.IsCode dis (producers SS S v) t := by sorry
end FuzzyExtractors.LowerBound
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, Appendix C, proof of Lemma C.1, pp. 40–41, "We claim that these 2^{m′} values of w form a code of error-correcting distance t"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.