Theorem 5.1, linear case — the syndrome sketch is deterministic, symbols long, and average-case secure with loss
ProvedFuzzyExtractors.Hamming.theorem_5_1_linearLet be a finite field with elements, , and let be a linear code of dimension in which distinct codewords are at Hamming distance at least . Let be a linear map with kernel . Let be the syndrome construction (Construction 3): , deterministically, and finds a vector of Hamming weight at most with and outputs . Then for every ,
whose output is the -symbol string .
This is the "Furthermore" sentence of Theorem 5.1: for linear codes the sketch can be made deterministic and short.
Formalization Note Determinism and the length are expressed by the construction itself: the sketch is a point mass with values in . The parity-check matrix is replaced by a linear map with kernel . The efficiency clause is dropped.
import Mathlib import Definitions.Def_FuzzyExtractors_Hamming_Basic
namespace FuzzyExtractors.Hamming
theorem theorem_5_1_linear {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') :
∀ m : ℝ, IsAvgSecureSketch hammingDist m
(m - ((n : ℝ) - k) * Real.logb 2 (Fintype.card F)) t
(syndromeSS syn) (syndromeRec syn t) := by sorry
end FuzzyExtractors.Hamming
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.