Lemma C.1 (second sentence) — for uniform passwords, m′ ≤ log K(𝓜, t)
ProvedFuzzyExtractors.LowerBound.lemma_C_1_uniformcoding-theorylower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1secure-sketch
Let be a nonempty finite metric space with integer-valued distance . If is an -secure sketch with (the password is truly uniform), then
where is the largest size of an -code.
The residual entropy of a sketch for uniform inputs is bounded by the logarithm of the best code size, so sketches built from optimal codes have optimal entropy loss.
Formalization Note The metric axioms of §2.1 are stated explicitly; nonemptiness of is implicit in the paper (for empty no distribution exists and the claim fails). is K dis t Finset.univ.
Preamble
import Mathlib import Definitions.Def_FuzzyExtractors_LowerBound_Basic
Formal statement
namespace FuzzyExtractors.LowerBound
/-- Lemma C.1, second sentence (Appendix C, p. 40): when `m = log |𝓜|`, an (𝓜, m, m', t)-secure
sketch has `m' ≤ log K(𝓜, t)`. -/
theorem lemma_C_1_uniform {M V : Type} [Fintype M] [Nonempty 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)
(hm : m = Real.logb 2 (Fintype.card M)) :
m' ≤ Real.logb 2 (K dis t Finset.univ) := by sorry
end FuzzyExtractors.LowerBound
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, Lemma C.1 (second sentence), p. 40
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.