Lemma 4.7 — a biometric embedding with recovery information transfers average-case secure sketches
ProvedFuzzyExtractors.EditSketch.lemma_4_7Let be spaces with integer distances . Let be a -biometric embedding with recovery information , and let be an average-case secure sketch. Define
and let compute to obtain and then invert to obtain . Then is an average-case secure sketch.
This lemma moves secure sketches across metric spaces: Theorem 7.5 applies it with shingling as and PinSketch as .
Formalization Note. The paper prints "computing to get "; acts on , so it is read as . Inverting chooses the with and , which is unique by Definition 7; if no such exists, is returned (this case does not arise under correctness). The paper's proof treats only the worst-case entropy hypothesis; the average-case statement, which is what the lemma asserts, is stated. is real, and "range size at most " is the existence of a finite set of at most elements containing every value of . No metric axioms or finiteness are assumed.
import Mathlib import Definitions.Def_FuzzyExtractors_EditSketch_Basic
namespace FuzzyExtractors.EditSketch
theorem lemma_4_7 {M₁ M₂ G S : Type} (dis₁ : M₁ → M₁ → ℕ) (dis₂ : M₂ → M₂ → ℕ)
(t₁ t₂ : ℕ) (lam m₁ m₂' : ℝ) (f : M₁ → M₂) (g : M₁ → G)
(SS : M₂ → PMF S) (Rec : M₂ → S → PMF M₂)
(hf : IsEmbeddingWithRecovery dis₁ dis₂ t₁ t₂ lam f g)
(hSS : FuzzyExtractors.Hamming.IsAvgSecureSketch dis₂ (m₁ - lam) m₂' t₂ SS Rec) :
FuzzyExtractors.Hamming.IsAvgSecureSketch dis₁ m₁ m₂' t₁ (embedSketch f g SS) (embedRec f g Rec) := by sorry
end FuzzyExtractors.EditSketch
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.