Construction 6, step 4 — if then
ProvedFuzzyExtractors.EditSketch.construction_6_step_4bch-codesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1pinsketchsecure-sketch
Let be a finite field of characteristic , , and . Suppose , , and has the odd syndromes computed in step 2 of PinSketch's recovery:
Then
This is the correctness claim of step 4 of Construction 6: the set recovered by syndrome decoding is the symmetric difference, so .
Formalization Note. Indices are 0-based: entry is the paper's , for the paper's . Subtraction is in , where it coincides with addition.
Preamble
import Mathlib import Definitions.Def_FuzzyExtractors_EditSketch_Basic
Formal statement
namespace FuzzyExtractors.EditSketch
theorem construction_6_step_4 {K : Type} [Field K] [Fintype K] [DecidableEq K]
[CharP K 2] (t : ℕ) (w w' v : Finset Kˣ) (hdis : symmDiffDis w w' ≤ t) (hv : v.card ≤ t)
(hsyn : ∀ j : Fin t,
syn (2 * (j : ℕ) + 1) v = syn (2 * (j : ℕ) + 1) w' - syn (2 * (j : ℕ) + 1) w) :
v = symmDiff w w' := by sorry
end FuzzyExtractors.EditSketch
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors, arXiv:cs/0602007v4, Construction 6 (PinSketch), recovery step 4, p. 23
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.