Construction 5, Step 2, p. 21 — the sketch entries are the first elementary symmetric polynomials of , up to sign
ProvedFuzzyExtractors.ImprovedJS.construction_5_step_2p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomialssymmetric-polynomials
Let be a field, natural numbers and with . For , the coefficient of degree of , which is the -th entry of the sketch of Construction 5, equals
This is the paper's remark that outputting the top coefficients of is equivalent to outputting the first elementary symmetric polynomials of the points of .
Formalization Note. The paper says "equivalent"; the precise relation includes the sign , which is stated here. The paper's display writes the second sum as ; we read it as the elementary symmetric polynomial , consistent with the general term . In Lean the entry indices are -based ( here is k + 1 for k : Fin t). The paper leaves implicit; it is a hypothesis here.
Preamble
import Mathlib import Definitions.Def_FuzzyExtractors_ImprovedJS_Basic
Formal statement
namespace FuzzyExtractors.ImprovedJS
/-- Construction 5, Step 2 (p. 21): the sketch entries are, up to sign, the first t elementary
symmetric polynomials of the points of w: the coefficient of degree s − (k + 1) of p′ is
(−1)^(k+1) e_{k+1}(w). -/
theorem construction_5_step_2 {𝔽 : Type} [Field 𝔽] [DecidableEq 𝔽] (s t : ℕ) (hts : t ≤ s)
(w : Finset 𝔽) (hw : w.card = s) (k : Fin t) :
sketchCoeffs s t w k = (-1) ^ ((k : ℕ) + 1) * w.val.esymm ((k : ℕ) + 1) := by sorry
end FuzzyExtractors.ImprovedJS
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, Construction 5, SS Step 2, p. 21
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.