§6.2, p. 21 — , so satisfies Step 3 of
ProvedFuzzyExtractors.ImprovedJS.intersection_boundcombinatoricsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomialssecure-sketch
Let be a field, natural numbers and with and . Then
- and have at least common points:
- the polynomial , where for and built from , satisfies the condition of Step 3 of in Construction 5: and for at least points .
This shows that the Reed–Solomon decoding step of the recovery procedure has a solution whenever the input set is within distance of the original.
Formalization Note. "At least " is doubled to in , which covers odd (distances in are even). The paper leaves implicit; it is a hypothesis here.
Preamble
import Mathlib import Definitions.Def_FuzzyExtractors_ImprovedJS_Basic open Polynomial
Formal statement
namespace FuzzyExtractors.ImprovedJS
/-- Construction 5 analysis (p. 21): if |w| = |w′| = s and |w △ w′| ≤ t, then w and w′ share at
least s − t/2 points (doubled: 2|w ∩ w′| ≥ 2s − t), and −q, where q = p′ − p_high, satisfies the
condition of Step 3 of Rec on input (w′, SS(w)). -/
theorem intersection_bound {𝔽 : Type} [Field 𝔽] [DecidableEq 𝔽] (s t : ℕ) (hts : t ≤ s)
(w w' : Finset 𝔽) (hw : w.card = s) (hw' : w'.card = s) (hd : (symmDiff w w').card ≤ t) :
2 * s - t ≤ 2 * (w ∩ w').card ∧
Step3Cond s t (sketchCoeffs s t w) w'
(-(charPoly w - pHigh s t (sketchCoeffs s t w))) := by sorry
end FuzzyExtractors.ImprovedJS
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, §6.2, analysis of Construction 5, p. 21, "Since the set w intersects w′ in at least s−t/2 points, the polynomial −q satisfies the conditions of Step 3 in Rec"; cf. §6, p. 18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.