§5, p. 17 — at most one word within distance of has a given syndrome
ProvedFuzzyExtractors.Hamming.syndrome_uniquecoding-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1secure-sketch
Let be a finite field and a linear code of dimension in which distinct codewords are at Hamming distance at least . Let be a linear map with kernel (a syndrome map, for a parity-check matrix ). If are both within Hamming distance of and have the same syndrome, then
This is the correctness argument of the syndrome construction (Construction 3): there can be only one value within distance of whose syndrome is .
Formalization Note The parity-check matrix is replaced by its defining property: any linear map onto coordinates whose kernel is . Minimum distance is read as "at least ".
Preamble
import Mathlib import Definitions.Def_FuzzyExtractors_Hamming_Basic
Formal statement
namespace FuzzyExtractors.Hamming
theorem syndrome_unique {F : Type} [Field F] [Fintype F] [DecidableEq F] {n k t : ℕ}
(C : Submodule F (Fin n → F)) (hk : Module.finrank F C = k)
(syn : (Fin n → F) →ₗ[F] (Fin (n - k) → F)) (hsyn : LinearMap.ker syn = C)
(hdist : ∀ c ∈ C, ∀ c' ∈ C, c ≠ c' → 2 * t + 1 ≤ hammingDist c c')
(w' v₁ v₂ : Fin n → F) (h₁ : hammingDist v₁ w' ≤ t) (h₂ : hammingDist v₂ w' ≤ t)
(hs : syn v₁ = syn v₂) : v₁ = v₂ := by sorry
end FuzzyExtractors.Hamming
Source
Dodis, Ostrovsky, Reyzin & Smith, Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data, arXiv:cs/0602007v4, §5, p. 17, "There can be only one value within distance t of w′ whose syndrome is s"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.