Proof of Lemma C.1 — at least 2^{m′} points of S can produce the sketch value v
ProvedFuzzyExtractors.LowerBound.lemma_C_1_large_Tmin-entropyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1secure-sketch
Let be a finite set, a randomized sketching procedure on , and nonempty. Let be uniform over and suppose . Then there is a sketch value such that the set
satisfies .
This is the counting step of the proof of Lemma C.1: the points of consistent with an observed sketch value are numerous.
Formalization Note is real and the comparison is made in the reals (no rounding of ).
Preamble
import Mathlib import Definitions.Def_FuzzyExtractors_LowerBound_Basic
Formal statement
namespace FuzzyExtractors.LowerBound
/-- Appendix C, proof of Lemma C.1, p. 40: if `W` is uniform over a nonempty `S ⊆ 𝓜` and
`H̃∞(W | SS(W)) ≥ m'`, then for some sketch value `v` at least `2^m'` points `w ∈ S` can produce
the sketch value `v`. -/
theorem lemma_C_1_large_T {M V : Type} [Fintype M] (SS : M → PMF V) (S : Finset M)
(hS : S.Nonempty) (m' : ℝ)
(h : m' ≤ FuzzyExtractors.Hamming.avgMinEntropy (FuzzyExtractors.Hamming.withSketch SS (PMF.uniformOfFinset S hS))) :
∃ v : V, (2 : ℝ) ^ m' ≤ ((producers SS S v).card : ℝ) := by sorry
end FuzzyExtractors.LowerBound
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, Appendix C, proof of Lemma C.1, p. 40, "there are at least 2^{m′} points w in S (call this set T) which could produce SS(W) = v"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.