Proof of Lemma C.1 — some sketch value v leaves H∞(W | SS(W) = v) ≥ m′
ProvedFuzzyExtractors.LowerBound.lemma_C_1_good_valuemin-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 with such that for every ,
that is, .
This is the first step of the proof of Lemma C.1: an average bound on the guessing probability yields one value of the sketch where the bound holds.
Formalization Note The conditional min-entropy is written in joint form, multiplied through by , so no division by a probability occurs; positivity of is part of the conclusion. Probabilities are in (ENNReal), and is embedded from the reals.
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 some sketch value `v` has positive probability and
`H∞(W | SS(W) = v) ≥ m'`, i.e. `Pr[W = w ∧ SS(W) = v] ≤ 2^(-m') · Pr[SS(W) = v]` for every `w`. -/
theorem lemma_C_1_good_value {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, 0 < ((PMF.uniformOfFinset S hS).bind SS) v ∧
∀ w : M, FuzzyExtractors.Hamming.withSketch SS (PMF.uniformOfFinset S hS) (w, v) ≤
ENNReal.ofReal ((2 : ℝ) ^ (-m')) * ((PMF.uniformOfFinset S hS).bind SS) v := by sorry
end FuzzyExtractors.LowerBound
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, Appendix C, proof of Lemma C.1, p. 40, "In particular, there must be some value v such that H∞(W | SS(W) = v) ≥ m′"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.