Appendix E — in characteristic 2 the even syndromes are squares:
ProvedFuzzyExtractors.EditSketch.appendix_E_syn_sqbch-codesfinite-fieldsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1syndrome
Let be a finite field of characteristic and let be the support of a binary word. Write for its -th power-sum syndrome. Then for every
This is the case of the redundancy observed in Appendix E, : since the coefficients of a binary word satisfy and squaring is additive in characteristic , the even-indexed syndromes are determined by the odd-indexed ones. This is why PinSketch (Construction 6) publishes only .
Formalization Note. The paper states the identity for general and a general word ; only the binary case, with the word given by its support, is stated here. The field is any finite field of characteristic .
Preamble
import Mathlib import Definitions.Def_FuzzyExtractors_EditSketch_Basic
Formal statement
namespace FuzzyExtractors.EditSketch
theorem appendix_E_syn_sq {K : Type} [Field K] [Fintype K] [CharP K 2]
(w : Finset Kˣ) (i : ℕ) :
syn (2 * i) w = syn i w ^ 2 := by sorry
end FuzzyExtractors.EditSketch
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, Appendix E, p. 43 ("we have c(α^i)^q = Σ_{x≠0} c_x^q x^{iq} = c(α^{iq})")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.