§6.2, p. 21 — with , and , agree on
ProvedFuzzyExtractors.ImprovedJS.split_agreep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomialssecure-sketch
Let be a field, natural numbers and a set with . Let and let be built from the sketch of Construction 5, the coefficients of of degree down to . Then there is a polynomial with
This is the first step of the paper's correctness argument for Construction 5: the decoder knows , and on the points of its values are those of the low-degree polynomial .
Formalization Note. "" is q.degree < s - t, which forces when . 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): p′ = p_high + q with deg q ≤ s − t − 1, and p_high, −q agree
on every point of w. -/
theorem split_agree {𝔽 : Type} [Field 𝔽] [DecidableEq 𝔽] (s t : ℕ) (hts : t ≤ s)
(w : Finset 𝔽) (hw : w.card = s) :
∃ q : 𝔽[X], charPoly w = pHigh s t (sketchCoeffs s t w) + q ∧
q.degree < ((s - t : ℕ) : WithBot ℕ) ∧
∀ x ∈ w, (pHigh s t (sketchCoeffs s t w)).eval x = -(q.eval x) := by sorry
end FuzzyExtractors.ImprovedJS
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, §6.2, analysis of Construction 5, p. 21, "We can write p′ as p_high + q … agree at all points in w"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.