Lemma C.1 — an (𝓜, m, m′, t) secure sketch has m′ ≤ L(𝓜, t, m)
ProvedFuzzyExtractors.LowerBound.lemma_C_1Let be a finite metric space with integer-valued distance , and let be real numbers such that is a natural number with . If is an -secure sketch, then
where is the largest size of an -code all of whose points lie in .
The lemma is the coding lower bound on the entropy loss of secure sketches: no sketch correcting errors can leave more residual min-entropy than the logarithm of the size of a -error-correcting code fitting inside every set of points. It shows that the paper's Hamming and set-difference constructions are optimal for uniform inputs.
Formalization Note The paper leaves implicit that is defined only when is an integer at most ; we state the lemma for with and . All metric axioms of §2.1 are stated explicitly. The sketch is the worst-case secure sketch of Definition 3 (not the average-case one), with a randomized and an arbitrary sketch output type. Efficiency is not formalized.
import Mathlib import Definitions.Def_FuzzyExtractors_LowerBound_Basic
namespace FuzzyExtractors.LowerBound
/-- Lemma C.1 (Appendix C, p. 40): the existence of an (𝓜, m, m', t)-secure sketch implies
`m' ≤ L(𝓜, t, m)`, where `2^m = N` is a natural number with `N ≤ |𝓜|`. -/
theorem lemma_C_1 {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)
(m m' : ℝ) (t : ℕ)
(SS : M → PMF V) (Rec : M → V → PMF M) (hSS : FuzzyExtractors.Hamming.IsSecureSketch dis m m' t SS Rec)
(N : ℕ) (hN : N ≤ Fintype.card M) (hNm : (N : ℝ) = (2 : ℝ) ^ m) :
m' ≤ L dis t N hN := by sorry
end FuzzyExtractors.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.