Lemma 3.1 — a correct sketch with at most outputs is an average-case secure sketch with entropy loss
ProvedFuzzyExtractors.Hamming.lemma_3_1min-entropyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1secure-sketch
Let be randomized procedures on a space with distance that satisfy the correctness property of a secure sketch for some , and suppose the output range of has size at most : some finite set with contains every possible output of , for every . Then for every min-entropy threshold ,
So the entropy loss of a correct sketch is bounded by its length, uniformly in . This is how the syndrome construction is analysed.
Formalization Note is real and the sketch takes values in an arbitrary set. The paper's parenthetical case, a sketch that is a -bit string, is an instance of the size hypothesis. "Correctness for some " is the hypothesis that whenever and is a possible output of .
Preamble
import Mathlib import Definitions.Def_FuzzyExtractors_Hamming_Basic
Formal statement
namespace FuzzyExtractors.Hamming
theorem lemma_3_1 {M S : Type} (dis : M → M → ℕ) (t : ℕ)
(SS : M → PMF S) (Rec : M → S → PMF M) (hcorr : SketchCorrect dis t SS Rec) (lam : ℝ)
(hrange : ∃ T : Finset S, (T.card : ℝ) ≤ (2 : ℝ) ^ lam ∧ ∀ w, (SS w).support ⊆ (T : Set S)) :
∀ m : ℝ, IsAvgSecureSketch dis m (m - lam) t SS Rec := 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, Lemma 3.1, p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.